算法題解題思路及代碼（不定時更新）

畢業(yè)半年, 平時工作總是關(guān)注業(yè)務(wù)、架構(gòu)，而卻越來越少關(guān)注性能, 也再也沒有做過任何涉及算法的工作了

希望有時間把這些拉下的東西拾起來，畢竟不論是使用什么語言，從事什么行業(yè)，只要是程序員，算法才是真正的基礎(chǔ)。

題目來自leetcode，代碼語言通常為C/C++，后期可能個別題目會用Golang

每道題都會闡述盡可能多的思路及不同思路的效率對比，以及每種思路的代碼實(shí)現(xiàn)

萬事開頭難，但堅持下去其實(shí)更難。

(2018.2.3)

題目1：給定和，獲取加數(shù)

描述： 給定一個整數(shù)數(shù)組，以及一個整數(shù)，已知這個整數(shù)是數(shù)組內(nèi)某兩個元素的和，現(xiàn)在需要找到，并返回這兩個元素的索引，例如：

    整數(shù)數(shù)組：{11, 7, 12, 2}

    整數(shù)       ：9

    返回結(jié)果：{1, 3}

（假定結(jié)果一定存在于給定數(shù)組，并且不需要考慮存在多組結(jié)果）

題目鏈接：https://leetcode.com/problems/two-sum/description/

解答：

解法1：

最傳統(tǒng)的方法就是挨個查找，判斷結(jié)果，具體步驟是：

每一趟都從下圖第一個元素(11)開始， 固定住第一個元素不變，計算當(dāng)前元素與其后每個元素的值之和，判斷是否等于目標(biāo)整數(shù)

這種方法，最壞的情況下，數(shù)組內(nèi)每一對元素都會被計算一次，因此時間復(fù)雜度為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：

上面的貪婪法可以將步驟分解為兩部分，外層循環(huán)和內(nèi)層循環(huán)，每當(dāng)外層循環(huán)執(zhí)行一步，內(nèi)層循環(huán)都需要逐個遍歷剩下的元素，執(zhí)行一趟時間復(fù)雜度為O(N)的過程，在整個過程中，外層循環(huán)是無法優(yōu)化的，而內(nèi)層的循環(huán)作為優(yōu)化，可以考慮用空間換取時間的思路：即事先對整個數(shù)組建立索引，使得每一趟的內(nèi)層循環(huán)不再是遍歷，而是精確查找，使得算法的時間復(fù)雜度由O(N*N)變?yōu)镺(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];     // 要查找的數(shù)據(jù)
        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（建立索引的過程可以分解到外層循環(huán)的每一步當(dāng)中）：

一開始無索引，每一步都在索引中查找目標(biāo)元素，如果沒有，則將當(dāng)前元素存入索引，并迭代至下一步

代碼：

// O(n), 速度最優(yōu), 但整體跟上一種方法在同一數(shù)量級內(nèi)
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];  // 要查找的數(shù)據(jù)
        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;
}

總結(jié)：

坑：

比較少

優(yōu)化：

比較1、2、3方法，

1方法時間復(fù)雜度為O(N*N)，最低效,

2、3方法整體時間復(fù)雜度都是O(N)，區(qū)別在于 2方法是在一開始就建立了完整的索引，而3方法則是在迭代的過程中逐步建立索引

在悲觀的情況下，2、3方法效率是相同的

在樂觀的情況下，3方法只需要向索引中存放一個元素，因此相對來說更高效

題目2：鏈表求和

描述： 給定兩個非空鏈表，每個鏈表代表一個整數(shù)，而鏈表的每個結(jié)點(diǎn)則代表每一位，此外規(guī)定鏈表為倒序排列，求兩鏈表所代表的正數(shù)之和對應(yīng)的鏈表。例如：

    整數(shù)鏈表：( 2->4->3 ) + ( 5->6->4 )         (相當(dāng)于 342 + 465 )

    返回結(jié)果：(7->0->8)                                  (相當(dāng)于 807 )

    鏈表結(jié)點(diǎn)：

/**
 * 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：分別遍歷兩鏈表，按照倒序轉(zhuǎn)化的規(guī)則將兩個鏈表轉(zhuǎn)化成兩個整數(shù)   O(N) * 2   (借助棧)

    step2:  兩個整數(shù)相加    O(1)

    step3:  相加之和轉(zhuǎn)化為鏈表 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;
        }
        // 統(tǒng)計兩加數(shù)之和
        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;
    }

總的時間復(fù)雜度為：

3 * O(N) + O(1)  ~= O(N)

但是當(dāng)兩鏈表所表示的整數(shù)非常大，將會導(dǎo)致×××溢出，因此這種方法是有問題的

解法二：

同時遍歷兩個鏈表，遍歷的同時進(jìn)行相加，生成新的鏈表。思路就像筆算求解多位數(shù)之和的過程，比較簡單，主要需要考慮下面幾種情況即可：

    進(jìn)位問題；

    當(dāng)前位置兩數(shù)都有值的情況；

    當(dāng)前位置一個數(shù)有值一個數(shù)沒有值的情況；

代碼：

ListNode* addTwoNumbers_better(ListNode* l1, ListNode* l2) {
    ListNode* ret_head = NULL;
    ListNode* pcur     = NULL;
    ListNode* p1 = l1;
    ListNode* p2 = l2;
    int addi = 0;  // 進(jìn)位符
    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;
}

總結(jié)：

坑：

需要考慮到溢出問題，不然就踩坑了

優(yōu)化：

O(N), 優(yōu)化空間比較小

題目3：字符串獲取最長無重復(fù)子串的長度

描述： 給定某個字符串，計算其中所有子串中，最長的那個無重復(fù)字符的字串的長度。例如：

    給定字符串“abcabcbb”， 最長無重復(fù)子串是“abc”，長度為3

    給定字符串“bbbbb”， 最長無重復(fù)子串是“b”，長度為1

    給定字符串“pwwkew”， 最長無重復(fù)子串是“wke”，長度為3

題目鏈接：https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

解答：

方法一：（窮舉法）

思路就是列出給定的字符串的所有子串(兩層循環(huán)即可)，然后篩選出其中的所有無重復(fù)的字串，然后取出其中最長的一條

簡單粗暴，效率最低，時間復(fù)雜度O(N^2)

代碼略

方法二：（貪婪法）

遍歷一遍字符串，計算每個字符往后的最長無重復(fù)子串，統(tǒng)計出其中最大值。

具體分解成兩層循環(huán)，外層循環(huán)遍歷每個元素，

內(nèi)層循環(huán)從當(dāng)前元素開始往后遍歷，計數(shù)，直到遇到第一個重復(fù)字符為止，為了性能，需要維護(hù)一個map供內(nèi)層循環(huán)判斷重復(fù)字符使用，下面是代碼：

    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) {  // 有重復(fù)
                    if(cur > max) {
                        max = cur;
                    }
                    cur = 0;
                    s_map.clear();
                    break;// 結(jié)束循環(huán)
                }else {
                    cur += 1;
                    s_map[*s_itn] = 1;
                }
                // (坑2)此處的判斷是必須的
                if(cur > max) {
                    max = cur;
                }
            }
        }
        return max;
    }

進(jìn)一步優(yōu)化

相比窮舉法，這種方法的性能要高出不少，但是總的來說性能依然不夠理想，主要體現(xiàn)在：

1、本質(zhì)上還是內(nèi)外兩層循環(huán)

2、查找字符時用的集合是map，因此查找效率為O(logN)，而每個字符的范圍是已知的(0~255)，因此可以用一個數(shù)組作為查找集合，查找效率將可以提升為O(1)

解法3（滑動窗口）：

首先采用一個長度為256的順序表作為查找集合，這樣就可以將查找的時間復(fù)雜度降低為O(1)

同時維護(hù)兩個指針(或者說索引)，一前一后協(xié)同者往后遍歷，遍歷的過程中尋找兩索引的最大距離，就好像一個可以伸縮的窗口在不斷遍歷，這樣就可以將兩層遍歷減少為一層，時間復(fù)雜度由O(N*N) 降低為 O(N)

具體步驟如下圖：

p(head)為窗口的前指針，q(tail)為窗口的后指針，窗口移動的過程循環(huán)可以分解成兩步：

    step1：先向前移動p，不斷拉長窗口，直到遇到重復(fù)的字符；  （擴(kuò)大階段）

    step2：遇到重復(fù)的字符，這時候就需要向前移動q，逐步縮小窗口長度，直到將這個重復(fù)的元素剔除；  （縮小階段）

在移動的過程中記錄保存p、q的間距(最大值)

這種方法的整體時間復(fù)雜度為 2 * O(N) ≈ O(N)

這種方法的實(shí)現(xià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]) {  // 擴(kuò)大階段
            ++s_vec[head_val];
            ++head;
            max = (head - tail) > max ? (head - tail) : max;
        }else {  // 縮小階段
            s_vec[tail_val] = 0;
            ++tail;
        }

    }
    return max;
}

解法4（上一種解法的深度優(yōu)化）：

上一種方法的縮小階段其實(shí)是沒必要的，我們可以直接在查找集合中存入相應(yīng)的記錄，這樣每次縮小階段，就可以直接將tail指針跳到上一次出現(xiàn)的該字符的位置，時間就能由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;   // 跳轉(zhuǎn)到head_val字符出現(xiàn)的下一個位置 
            max = (head - tail + 1) > max ? (head - tail + 1) : max;
            s_vec[head_val] = head + 1;  // (永遠(yuǎn)記錄head_val字符出現(xiàn)的下一個位置)
        }
        return max;
    }

總結(jié)：

后面3種優(yōu)化方法本質(zhì)上其實(shí)都是貪婪法的思路，這個題目如果不仔細(xì)思考，很難一步到位得到最優(yōu)算法~

坑：

坑比較少

優(yōu)化：

優(yōu)化空間較大

題目4：獲取兩排序數(shù)組的中值

描述： 給定兩個排序好的數(shù)組（升序排序），計算兩個數(shù)組內(nèi)所有數(shù)的中值。例如：

    給定數(shù)組1 : [1, 3], 數(shù)組2 : [2] , 計算結(jié)果為：2

    給定數(shù)組1 : [1, 2], 數(shù)組2 : [3, 4] , 計算結(jié)果為：2.5

題目鏈接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

解答：

解法1：

最直接的做法就是對這兩個數(shù)組進(jìn)行排序，最直接的做法是創(chuàng)建一個臨時數(shù)組（或者堆），將兩個數(shù)組中的所有元素都存放進(jìn)去，然后對這個數(shù)組進(jìn)行排序，并找出中值，這種方法的時間復(fù)雜度為  

采用臨時數(shù)組方式：遍歷一遍O(N) + 排序O(log2N)  ，實(shí)現(xiàn)代碼略

采用堆的方式：       遍歷一遍 & 建堆O(N) + 查找O(log2N)

解法2（雙指針一趟(半趟)遍歷）：

已知兩個數(shù)組都是排序好的，那么其實(shí)可以根據(jù)這個特性進(jìn)行優(yōu)化，將時間復(fù)雜度降低為O(N)

思路是：維護(hù)兩個指針及一個計數(shù)器，按從小到大的順序遍歷兩數(shù)組，每一步遍歷計數(shù)器加1，直到計數(shù)器加到中值。 

非遞歸實(shí)現(xiàn)代碼如下： 

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;   // 奇數(shù)
        int val1    = 0;
        int val2    = 0;
        if(total % 2 == 0) {  // 總數(shù)為偶數(shù), 取中間兩位數(shù)的平均值
            pos1   = total / 2 - 1;
            pos2   = total / 2;
            is_odd = false;
        }else {
            pos1   = total / 2;
            is_odd = true;
        }
        int step = 0;  // 步數(shù)
        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){  // 找到奇數(shù)情況下的結(jié)果
               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提供了一種遞歸的方式，時間復(fù)雜度可以達(dá)到O(log2N)：

假如給定A、B兩個排序數(shù)組， 在A中尋找一處索引 i， 在B中尋找一處索引 j， 分別將A、B數(shù)組分割成左右兩部分 ；

合并A、B的左半部分；

合并A、B的右半部分；

假如左右兩部分長度相同(總數(shù)為偶數(shù)時滿足：i+j = (m-i) + (n-j)  總數(shù)為奇數(shù)時滿足 i + j = (m - i) + (n - j) + 1)， 并且左半部分最大的元素比右半部分最小的元素小時（A[i - 1] <= B[j] && B[j - 1] <= A[i]）

當(dāng)以上這兩個條件均滿足時 左半部分的最后一個元素和右半部分的第一個元素的平均值就是要求的結(jié)果。

將上面兩個條件轉(zhuǎn)化成：

條件1：j = (m+n+1)/2 - i  = halfLen - i (要保證j為正數(shù)， 因此又多了一個條件： n >= m)

條件2：A[i - 1] <= B[j] && B[j - 1] <= A[i]

因此可以用二分查找的方式, 查找那個合適的i值

這種方法實(shí)質(zhì)上是對元素的一次二分，因此時間復(fù)雜度為 O(log2N), 是這道題目已知的最優(yōu)解

偽代碼

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  // 奇數(shù)，直接返回中值
               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

總結(jié)：

不仔細(xì)推導(dǎo)很難得出最后一種方法...

坑：

坑比較少

優(yōu)化：

存在優(yōu)化空間

題目5：獲取最長回文字符串

描述： 給定兩個排序好的數(shù)組（升序排序），計算兩個數(shù)組內(nèi)所有數(shù)的中值。例如：

    輸入："babad"   輸出："bab"

    輸入："cbbd"     輸出："bb"

題目鏈接：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

解答：

解法1：

最簡單的思路，遍歷的同時找對稱點(diǎn)，一旦找到對稱點(diǎn)（考慮，分別處理好aa aba aaa這三種情況），維護(hù)兩個下標(biāo)分別向前、向后遍歷，找出所有對稱點(diǎn)及每個對稱點(diǎn)對應(yīng)的字符串，返回最長的那個，代碼如下：

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]) {  // 奇數(shù)的情況abcba  
            ileft  = i - 1;
            iright = i + 1;
        }else if(i >= 1 && s[i] == s[i - 1]) {  // 偶數(shù)的情況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;
}

思路比較簡單，但實(shí)現(xiàn)起來坑很多，時間復(fù)雜度O(N^2)

模板