LeetCode - 202 解題紀錄
題目: LeetCode - 202. Happy Number
題目說明將題目給的數字拆開並求出拆開的數字的平方和,若結果為 1 則為 Happy Number。
解題思路使用 Floyd Cycle Detection Algorithm 即可,詳細介紹可參考:Wiki
參考解法123456789101112131415161718192021222324class Solution {public: int next(int n) { int next = 0; while( n > 0) { next += (n % 10) * ( n % 10); n /= 10; } return next; } bool isHappy(int n) { int tortoise = n; int hare = n; do ...
LeetCode - 136 解題紀錄
題目: LeetCode - 136. Single Number
題目說明從一個陣列中找出不重複的數字。( 只會有一個數字不重複 )
解題思路使用 XOR 位元運算,將 ans 先設為 nums[0],再用一個迴圈從 1 開始,對 ans 做 XOR 位元運算,最後的結果即是答案。XOR 的介紹可以參考本篇文章:XOR 位元運算介紹。
為什麼要使用 XOR 呢?因為 XOR 有一個特性是 A ^ A = 0,意思是當兩個相同的數字做 XOR 運算後會變成 0,而另一個特性是 A ^ 0 = A,意思是當任意一個數字對 0 做 XOR 運算後還是自己,恰巧很符合本題的題目,一個陣列內只有一個數字是單獨存在的,其他數字都會有兩個。那你可能會想說:可是陣列的順序不一定是 [A, A, B, B, C, C, D] 呀。這時就要提到 XOR 的第三個特性,A ^ B = B ^ A,就是說 XOR 其實是有交換律的,所以順序其實並不重要。這個題目其實也是 XOR 的經典題目,所有概念都有使用到。
參考解法123456789class Solution {public: i ...
XOR 位元運算介紹
簡介XOR 的中文是互斥或的意思,它是一種位元運算子,會單獨對每個位元進行運算,在程式語言中寫作 a ^ b。詳細介紹可參考:Wiki
真值表XOR 簡單來說就是兩者相同為 0,不同為 1。
A
B
輸出
0
0
0
0
1
1
1
0
1
1
1
0
特性XOR 會有以下幾種特性:
A ^ 0 = A若 A 為 0,0 ^ 0 = 0,若 A 為 1,1 ^ 0 = 1。
A ^ A = 0若 A 為 0,0 ^ 0 = 0,若 A 為 1,1 ^ 1 = 0。
A ^ B = B ^ A若 A 為 0,B 為 0,0 ^ 0 = 0 ^ 0 = 0。若 A 為 0,B 為 1,0 ^ 1 = 1 ^ 0 = 1。若 A 為 1,B 為 0,1 ^ 0 = 0 ^ 1 = 1。
上面這些都是以位元為單位來運算的,但其實對於十進位的數字也是通用的,有興趣的可以自己把十進位的數字轉為二進位來做就會明白了。
實際應用LeetCode - 136 就是一個經典的 XOR 題目,詳細解法可參考本篇文章:LeeCode - 136 解題紀錄。
C++ 檔案下載
用處當我們完成一支程式發布出去時,我們可能會希望後續還能夠控制這支程式。例如使程式失效、更新等等…,這時我們就可以透過下載檔案並讀取檔案內容,再根據讀取到的內容做出對應的操作。
實現方法需要引入以下的頭文件:
1234#include <tchar.h>#include <urlmon.h>#pragma comment(lib, "urlmon.lib")#pragma comment(lib, "ws2_32.lib")
只需使用一行 code 即可:
1HRESULT hr = URLDownloadToFile(NULL, _T("檔案下載路徑"), _T("檔案儲存路徑"), 0, NULL);
簡單實作1234567891011121314151617181920212223#include <iostream>#include <fstream>#include <tchar.h>#include <urlmon.h> ...
UVa - 10082 解題紀錄
題目: UVa - 10082 - WERTYU
題目說明每筆測資為一個對於鍵盤而言向右偏移一個字的字串,需要輸出原本未偏移的字串。
解題思路利用 String 讀取測資,使用 unordered_map<char, char> 建表,並根據字串內容輸出即可。建表資料參考:#21510: 建立map表須注意空白也必須加入表中,雖然自己測試時沒加入也會輸出空白,但是繳交執行時不會。
參考解法123456789101112131415161718192021222324252627282930313233343536#include <iostream>#include <string>#include <unordered_map>using namespace std;void build(unordered_map< char, char>& table); // 建表int main(){ string data; unordered_map< char, char> dict ...
C++ String 介紹
簡介String 是 STL 內含的一個容器,專門用來放字符,有許多方便的字串操作。可以想像成它是一個強化版的 Vector,其實他們的構造也非常像,核心都是使用動態陣列存放資料。它除了擁有和 Vector 相似的特性外,還加載了許多 Operator。因為之前介紹過 Vector 了,所以本篇會著重在介紹其他的功能,Vector 能使用的函式 String 大部分都能使用,想了解的可以參考本篇文章:C++ Vector 介紹。
使用方式include使用前需要先 #include <string>
變數宣告
string name 建立一個空的 String。
string name(str) 建立一個內容與 str 相同的 String。
成員函式
str1 = str2:將 str2 的內容放進 str1。
str1 += str2:將 str2 接在 str1 後。
str1 == str2:若 str1 的內容和 str2 相等則回傳 True,反之則回傳 False。
str1.find(str2):在 str1 內尋找 str2 並回傳第一個字符位置 ...
UVa - 10935 解題紀錄
題目: UVa - 10935 - Throwing cards away I
題目說明每筆測資為一個數字 n,會有一個 1 ~ n 的紙牌堆,題目要求丟掉最上面的牌,然後把目前最上面的那張牌放到牌堆的最下面。
解題思路利用 queue 先進先出的特性,先輸出 front() 然後 pop() 掉,再把 front() push() 進去,最後再 pop() 即可。
參考解法1234567891011121314151617181920212223242526272829303132333435#include <iostream>#include <queue>using namespace std;int main(){ int n; queue< int > cards; while ((cin >> n) && n != 0) { for (int i = 1; i <= n; ++i) cards.push(i); ...
UVa - 10035 解題紀錄
題目: UVa - 10035 - Primary Arithmetic
題目說明每筆測資會有兩個數字,計算這兩個數字相加時做進位的次數。
解題思路使用兩個 String 讀取測資,利用一個 int 做 Carry,重複將 Carry 加上兩數最後一位數字的和,若大於等於 10 表示有做進位,最後再將 Carry 除以 10,並將兩者都 pop_back() 刪除最後一位,直到其中一者做完為止。
參考解法12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include <iostream>using namespace std;int main(){ string num1, num2; while (cin >> num1 >> num2) { if (num1 == "0" && num2 == "0") ...
UVa - 12503 解題紀錄
題目: UVa - 12503 - Robot Instructions
題目說明第一個數字代表有幾筆測資,每筆測資會有一個數字,代表會有幾條字串,根據字串內容移動機器人的座標。
解題思路使用 String 讀取測資,只需要判斷第一個字是哪個字並做出對應的動作即可,使用 Vector 來儲存做過的指令。
參考解法123456789101112131415161718192021222324252627282930313233343536373839404142434445#include <iostream>#include <string>#include <vector>using namespace std;int main(){ int T, p, temp, moveNum; string move; vector< int > moveTemp; cin >> T; while (T--) { p = 0; cin >&g ...
UVa - 11192 解題紀錄
題目: UVa - 11192 - Group Reverse
題目說明每筆測資會有一個數字及一個字串,數字代表分割的組數,字串的長度會是該數的倍數,題目要求按照組數輸出其字串反轉的內容。
解題思路使用 String 讀取測資,將一組大小的字串反轉後放到另一個 String 並輸出,之後再將反轉過的資料 erase() 掉即可。
參考解法12345678910111213141516171819202122232425262728293031#include <iostream>#include <algorithm>using namespace std;int main(){ int groupNum, groupSize; string data, output; while (cin >> groupNum) { if (!groupNum) break; cin >> data; groupSize = data.si ...