畢業半年, 平時工作總是關注業務、架構，而卻越來越少關注性能, 也再也沒有做過任何涉及算法的工作了
希望有時間把這些拉下的東西拾起來，畢竟不論是使用什么語言，從事什么行業，只要是程序員，算法才是真正的基礎。
題目來自leetcode，代碼語言通常為C/C++，后期可能個別題目會用Golang
每道題都會闡述盡可能多的思路及不同思路的效率對比，以及每種思路的代碼實現
萬事開頭難，但堅持下去其實更難。
(2018.2.3)
題目1：給定和，獲取加數
描述： 給定一個整數數組，以及一個整數，已知這個整數是數組內某兩個元素的和，現在需要找到，并返回這兩個元素的索引，例如：
整數數組：{11, 7, 12, 2}
整數 ：9
返回結果：{1, 3}
（假定結果一定存在于給定數組，并且不需要考慮存在多組結果）
題目鏈接：https://leetcode.com/problems/two-sum/description/
解答：
解法1：
最傳統的方法就是挨個查找，判斷結果，具體步驟是：
每一趟都從下圖第一個元素(11)開始， 固定住第一個元素不變，計算當前元素與其后每個元素的值之和，判斷是否等于目標整數
這種方法，最壞的情況下，數組內每一對元素都會被計算一次，因此時間復雜度為O(N * N)
代碼：
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ret;
int sz = nums.size();
for(size_t i = 0; i < sz - 1; ++i) {
for(size_t j = i + 1; j < sz; ++j) {
if(nums[i] + nums[j] == target) {
ret.push_back(i);
ret.push_back(j);
return ret;
}
}
}
return ret;
}解法2：
上面的貪婪法可以將步驟分解為兩部分，外層循環和內層循環，每當外層循環執行一步，內層循環都需要逐個遍歷剩下的元素，執行一趟時間復雜度為O(N)的過程，在整個過程中，外層循環是無法優化的，而內層的循環作為優化，可以考慮用空間換取時間的思路：即事先對整個數組建立索引，使得每一趟的內層循環不再是遍歷，而是精確查找，使得算法的時間復雜度由O(N*N)變為O(N*1)
具體步驟是：
代碼：
// O(n)
vector<int> twoSum_better1(vector<int>& nums, int target) {
int sz = nums.size();
map<int, int> dic_map;
// 先建立索引
for(size_t i = 0; i < sz; ++i) {
dic_map[nums[i]] = i;
}
vector<int> ret;
// 開始查找
for(size_t i = 0; i < sz; ++i) {
int pos_val = target - nums[i]; // 要查找的數據
int pos_key = dic_map[pos_val];
if(pos_key != i && (nums[i] + nums[pos_key]) == target ) { // 找到
ret.push_back(i);
ret.push_back(pos_key);
break;
}
}
return ret;
}解法3（建立索引的過程可以分解到外層循環的每一步當中）：
一開始無索引，每一步都在索引中查找目標元素，如果沒有，則將當前元素存入索引，并迭代至下一步
代碼：
// O(n), 速度最優, 但整體跟上一種方法在同一數量級內
vector<int> twoSum_better2(vector<int>& nums, int target) {
int sz = nums.size();
map<int, int> dic_map;
vector<int> ret;
// 開始查找
for(size_t i = 0; i < sz; ++i) {
int pos_val = target - nums[i]; // 要查找的數據
int pos_key = dic_map[pos_val];
if(pos_key != i && (nums[i] + nums[pos_key]) == target) {
ret.push_back(i);
ret.push_back(pos_key);
break;
}else {
dic_map[nums[i]] = i; // 添加索引
}
}
return ret;
}總結：
坑：
比較少
優化：
比較1、2、3方法，
1方法時間復雜度為O(N*N)，最低效,
2、3方法整體時間復雜度都是O(N)，區別在于 2方法是在一開始就建立了完整的索引，而3方法則是在迭代的過程中逐步建立索引
在悲觀的情況下，2、3方法效率是相同的
在樂觀的情況下，3方法只需要向索引中存放一個元素，因此相對來說更高效
題目2：鏈表求和
描述： 給定兩個非空鏈表，每個鏈表代表一個整數，而鏈表的每個結點則代表每一位，此外規定鏈表為倒序排列，求兩鏈表所代表的正數之和對應的鏈表。例如：
整數鏈表：( 2->4->3 ) + ( 5->6->4 ) (相當于 342 + 465 )
返回結果：(7->0->8) (相當于 807 )
鏈表結點：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/題目鏈接：https://leetcode.com/problems/add-two-numbers/description/
解答：
解法一：（不完全正確的方法）
step1：分別遍歷兩鏈表，按照倒序轉化的規則將兩個鏈表轉化成兩個整數 O(N) * 2 (借助棧)
step2: 兩個整數相加 O(1)
step3: 相加之和轉化為鏈表 O(N)
代碼：
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
stack<int> s1;
stack<int> s2;
// l1、l2元素入棧
ListNode* p1 = l1;
ListNode* p2 = l2;
while(p1 != NULL) {
s1.push(p1->val);
p1 = p1->next;
}
while(p2 != NULL) {
s2.push(p2->val);
p2 = p2->next;
}
// 統計兩加數之和
long count1 = 0;
long count2 = 0;
while(!s1.empty()) {
count1 = s1.top() + 10 * count1;
s1.pop();
}
while(!s2.empty()) {
count2 = s2.top() + 10 * count2;
s2.pop();
}
long sum = count1 + count2;
// 生成新鏈表
long res = sum;
ListNode* ret_node = NULL;
ListNode* pos = NULL;
if(res == 0) {
ListNode* ret_node = new ListNode(0);
return ret_node;
}
while(res != 0) {
int unit = res % 10;
res = res / 10;
if(ret_node == NULL) {
ret_node = new ListNode(unit);
pos = ret_node;
}else {
ListNode* next_node = new ListNode(unit);
pos->next = next_node;
pos = next_node;
}
}
return ret_node;
}總的時間復雜度為：
3 * O(N) + O(1) ~= O(N)
但是當兩鏈表所表示的整數非常大，將會導致×××溢出，因此這種方法是有問題的
解法二：
同時遍歷兩個鏈表，遍歷的同時進行相加，生成新的鏈表。思路就像筆算求解多位數之和的過程，比較簡單，主要需要考慮下面幾種情況即可：
進位問題；
當前位置兩數都有值的情況；
當前位置一個數有值一個數沒有值的情況；
代碼：
ListNode* addTwoNumbers_better(ListNode* l1, ListNode* l2) {
ListNode* ret_head = NULL;
ListNode* pcur = NULL;
ListNode* p1 = l1;
ListNode* p2 = l2;
int addi = 0; // 進位符
while(p1 != NULL || p2 != NULL) {
int cur = addi;
if(p1 != NULL) {
cur += p1->val;
p1 = p1->next;
}
if(p2 != NULL) {
cur += p2->val;
p2 = p2->next;
}
if(cur > 9) {
addi = 1;
cur %= 10;
}else {
addi = 0;
}
ListNode* newNode = new ListNode(cur);
if(ret_head == NULL) {
ret_head = newNode;
pcur = newNode;
}else {
pcur->next = newNode;
pcur = pcur->next;
}
}
if(addi == 1) {
ListNode* newNode = new ListNode(1);
if(ret_head == NULL) {
ret_head = newNode;
pcur = newNode;
}else {
pcur->next = newNode;
pcur = pcur->next;
}
}
return ret_head;
}總結：
坑：
需要考慮到溢出問題，不然就踩坑了
優化：
O(N), 優化空間比較小
題目3：字符串獲取最長無重復子串的長度
描述： 給定某個字符串，計算其中所有子串中，最長的那個無重復字符的字串的長度。例如：
給定字符串“abcabcbb”， 最長無重復子串是“abc”，長度為3
給定字符串“bbbbb”， 最長無重復子串是“b”，長度為1
給定字符串“pwwkew”， 最長無重復子串是“wke”，長度為3
題目鏈接：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
解答：
方法一：（窮舉法）
思路就是列出給定的字符串的所有子串(兩層循環即可)，然后篩選出其中的所有無重復的字串，然后取出其中最長的一條
簡單粗暴，效率最低，時間復雜度O(N^2)
代碼略
方法二：（貪婪法）
遍歷一遍字符串，計算每個字符往后的最長無重復子串，統計出其中最大值。
具體分解成兩層循環，外層循環遍歷每個元素，
內層循環從當前元素開始往后遍歷，計數，直到遇到第一個重復字符為止，為了性能，需要維護一個map供內層循環判斷重復字符使用，下面是代碼：
int lengthOfLongestSubstring(string s) {
// 貪婪法
map<char, int> s_map;
int max = 0;
int cur = 0;
for(string::iterator s_it = s.begin(); s_it != s.end(); ++s_it) {
for(string::iterator s_itn = s_it; s_itn != s.end(); ++s_itn) {
if(s_map[*s_itn] != 0) { // 有重復
if(cur > max) {
max = cur;
}
cur = 0;
s_map.clear();
break;// 結束循環
}else {
cur += 1;
s_map[*s_itn] = 1;
}
// (坑2)此處的判斷是必須的
if(cur > max) {
max = cur;
}
}
}
return max;
}進一步優化
相比窮舉法，這種方法的性能要高出不少，但是總的來說性能依然不夠理想，主要體現在：
1、本質上還是內外兩層循環
2、查找字符時用的集合是map，因此查找效率為O(logN)，而每個字符的范圍是已知的(0~255)，因此可以用一個數組作為查找集合，查找效率將可以提升為O(1)
解法3（滑動窗口）：
首先采用一個長度為256的順序表作為查找集合，這樣就可以將查找的時間復雜度降低為O(1)
同時維護兩個指針(或者說索引)，一前一后協同者往后遍歷，遍歷的過程中尋找兩索引的最大距離，就好像一個可以伸縮的窗口在不斷遍歷，這樣就可以將兩層遍歷減少為一層，時間復雜度由O(N*N) 降低為 O(N)
具體步驟如下圖：
p(head)為窗口的前指針，q(tail)為窗口的后指針，窗口移動的過程循環可以分解成兩步：
step1：先向前移動p，不斷拉長窗口，直到遇到重復的字符； （擴大階段）
step2：遇到重復的字符，這時候就需要向前移動q，逐步縮小窗口長度，直到將這個重復的元素剔除； （縮小階段）
在移動的過程中記錄保存p、q的間距(最大值)
這種方法的整體時間復雜度為 2 * O(N) ≈ O(N)
這種方法的實現代碼如下：
int lengthOfLongestSubstring_better(string s) {
vector<int> s_vec(256, 0);
int max = 0;
int head = 0;
int tail = 0;
int length = s.length();
while(head < length && tail < length) {
char head_val = s[head];
char tail_val = s[tail];
if(0 == s_vec[head_val]) { // 擴大階段
++s_vec[head_val];
++head;
max = (head - tail) > max ? (head - tail) : max;
}else { // 縮小階段
s_vec[tail_val] = 0;
++tail;
}
}
return max;
}解法4（上一種解法的深度優化）：
上一種方法的縮小階段其實是沒必要的，我們可以直接在查找集合中存入相應的記錄，這樣每次縮小階段，就可以直接將tail指針跳到上一次出現的該字符的位置，時間就能由O(N)縮減為O(1)了
代碼如下：
int lengthOfLongestSubstring(string s) {
vector<int> s_vec(256, 0);
int length = s.length();
int max = 0;
for(size_t head = 0, tail = 0; head < length; ++head) {
char head_val = s[head];
tail = s_vec[head_val] > tail ? s_vec[head_val] : tail; // 跳轉到head_val字符出現的下一個位置
max = (head - tail + 1) > max ? (head - tail + 1) : max;
s_vec[head_val] = head + 1; // (永遠記錄head_val字符出現的下一個位置)
}
return max;
}總結：
后面3種優化方法本質上其實都是貪婪法的思路，這個題目如果不仔細思考，很難一步到位得到最優算法~
坑：
坑比較少
優化：
優化空間較大
題目4：獲取兩排序數組的中值
描述： 給定兩個排序好的數組（升序排序），計算兩個數組內所有數的中值。例如：
給定數組1 : [1, 3], 數組2 : [2] , 計算結果為：2
給定數組1 : [1, 2], 數組2 : [3, 4] , 計算結果為：2.5
題目鏈接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/
解答：
解法1：
最直接的做法就是對這兩個數組進行排序，最直接的做法是創建一個臨時數組（或者堆），將兩個數組中的所有元素都存放進去，然后對這個數組進行排序，并找出中值，這種方法的時間復雜度為
采用臨時數組方式：遍歷一遍O(N) + 排序O(log2N) ，實現代碼略
采用堆的方式： 遍歷一遍 & 建堆O(N) + 查找O(log2N)
解法2（雙指針一趟(半趟)遍歷）：
已知兩個數組都是排序好的，那么其實可以根據這個特性進行優化，將時間復雜度降低為O(N)
思路是：維護兩個指針及一個計數器，按從小到大的順序遍歷兩數組，每一步遍歷計數器加1，直到計數器加到中值。
非遞歸實現代碼如下：
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 中間位置的確定 (奇or偶 & 各自的位置)
int length2 = nums1.size();
int length3 = nums2.size();
int total = length2 + length3;
int pos1 = 0;
int pos2 = 0;
bool is_odd = true; // 奇數
int val1 = 0;
int val2 = 0;
if(total % 2 == 0) { // 總數為偶數, 取中間兩位數的平均值
pos1 = total / 2 - 1;
pos2 = total / 2;
is_odd = false;
}else {
pos1 = total / 2;
is_odd = true;
}
int step = 0; // 步數
vector<int>::iterator p1 = nums1.begin();
vector<int>::iterator p2 = nums2.begin();
vector<int>::iterator cur = nums1.begin();
while(p1 != nums1.end() || p2 != nums2.end()) {
if(p1 != nums1.end() && (p2 == nums2.end() || *p1 < *p2)) {
cur = p1++;
}else {
cur = p2++;
}
if(is_odd && step == pos1){ // 找到奇數情況下的結果
return *cur;
}
if(!is_odd && step == pos1) {
val1 = *cur;
}else if(!is_odd && step == pos2) {
val2 = *cur;
return ((double)val1 + val2) / 2;
}
++step;
}
return 0;
}解法3：
leetcode提供了一種遞歸的方式，時間復雜度可以達到O(log2N)：
假如給定A、B兩個排序數組， 在A中尋找一處索引 i， 在B中尋找一處索引 j， 分別將A、B數組分割成左右兩部分 ；
合并A、B的左半部分；
合并A、B的右半部分；
假如左右兩部分長度相同(總數為偶數時滿足：i+j = (m-i) + (n-j) 總數為奇數時滿足 i + j = (m - i) + (n - j) + 1)， 并且左半部分最大的元素比右半部分最小的元素小時（A[i - 1] <= B[j] && B[j - 1] <= A[i]）
當以上這兩個條件均滿足時 左半部分的最后一個元素和右半部分的第一個元素的平均值就是要求的結果。
將上面兩個條件轉化成：
條件1：j = (m+n+1)/2 - i = halfLen - i (要保證j為正數， 因此又多了一個條件： n >= m)
條件2：A[i - 1] <= B[j] && B[j - 1] <= A[i]
因此可以用二分查找的方式, 查找那個合適的i值
這種方法實質上是對元素的一次二分，因此時間復雜度為 O(log2N), 是這道題目已知的最優解
偽代碼
m = A.length n = B.length // 確保左邊的值更小 if m > n then swap(A, B) swap(m, n) end // 二分查找合適的i iMin = 0 IMax = m halfLen = (m + n + 1) / 2 while(iMin <= iMax) then i = (iMin + iMax) / 2 j = halfLen - i if i < iMax && B[j - 1] > A[i] then // 說明i太小了 iMin = iMin + 1 else if i > iMin && A[i - 1] > B[j] then // 說明i太大了 iMax = iMax - 1 else // 找到合適的i maxLeft = 0 if i == 0 then maxLeft = B[j - 1] else if j == 0 then maxLeft = A[i - 1] else maxLeft = max(A[i - 1], B[j - 1]) end if (m + n) % 2 == 1 then // 奇數，直接返回中值 return maxLeft end maxRight = 0 if i == m then maxRight = B[j] else if j == m then maxRight = A[j] else maxRigth = max(A[j], B[j]) end return (maxLeft + maxRight ) / 2.0 end end
總結：
不仔細推導很難得出最后一種方法...
坑：
坑比較少
優化：
存在優化空間
題目5：獲取最長回文字符串
描述： 給定兩個排序好的數組（升序排序），計算兩個數組內所有數的中值。例如：
輸入："babad" 輸出："bab"
輸入："cbbd" 輸出："bb"
題目鏈接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/
解答：
解法1：
最簡單的思路，遍歷的同時找對稱點，一旦找到對稱點（考慮，分別處理好aa aba aaa這三種情況），維護兩個下標分別向前、向后遍歷，找出所有對稱點及每個對稱點對應的字符串，返回最長的那個，代碼如下：
string getDstStr(string s, size_t& ileft, size_t& iright, size_t sz, size_t pos, int& maxlen) {
string ret = "";
if(ileft >= 0 && iright < sz) {
while(ileft >= 0 && iright < sz ) { // 坑
if(s[ileft] == s[iright]) {
--ileft;
++iright;
}else {
break;
}
}
++ileft;
--iright;
}
int len = (iright == pos) ? 0 : 1;
string tmp = "";
if(len + 1 + iright - ileft > maxlen) {
for(size_t i = ileft; i <= iright; ++i) {
tmp += s[i];
}
ret = tmp;
maxlen = ret.size();
return ret;
}
return ret;
}
string longestPalindrome(string s) {
// 坑
if(s.size() == 1) {
return s;
}
size_t sz = s.size();
string ret = "";
int maxlen = 0;
for(size_t i = 0; i < sz; ++i) {
bool is_special = false; // 'bbb'這種情況
size_t ileft = 0;
size_t iright = 0;
if(i >= 1 && i < sz && s[i - 1] == s[i + 1]) { // 奇數的情況abcba
ileft = i - 1;
iright = i + 1;
}else if(i >= 1 && s[i] == s[i - 1]) { // 偶數的情況abba
ileft = i - 1;
iright = i;
}
if(i >= 1 && s[i] == s[i - 1] && s[i] == s[i + 1] ) { // 考慮'bbb'這種情況
is_special = true;
}
// 滿足條件, 計算長度
if(iright > 0) {
if(is_special) {
ileft = i - 1;
iright = i + 1;
string tmp1 = getDstStr(s, ileft, iright, sz, i, maxlen);
ileft = i - 1;
iright = i;
string tmp2 = getDstStr(s, ileft, iright, sz, i, maxlen);
if(tmp1.size() > tmp2.size()) {
if(!tmp1.empty()) {
ret = tmp1;
}
}else {
if(!tmp2.empty()) {
ret = tmp2;
}
}
}else {
string tmp = getDstStr(s, ileft, iright, sz, i, maxlen);
if(!tmp.empty()) {
ret = tmp;
}
}
}
}
// 坑
if(ret.empty()) {
return s.substr(0, 1);
}
return ret;
}思路比較簡單，但實現起來坑很多，時間復雜度O(N^2)
模板
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
