動機

要複習怎麼用C++做leetcode

龜兔賽跑

一個快(2倍速)，一個慢(1倍速) 同樣都走k次 因為最後在loop遇到，所以兩者的距離只差在common的那一段 所以做最後只要再走一次就是起點

slow = common + x + (cycle*a)
fast = common*2 + x + 2*(cycle*a)
// 因為最後在loop遇到，所以x會是一樣 (我忘了實際的proof...)
fast = slow*2

fast-slow = common

142. Linked List Cycle II

class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if (head && head->next) {
            ListNode *a=head->next,*b=head->next->next;
            for(;a!=b && b && b->next;a=a->next, b=b->next->next) ;
            if (b && b->next && a == b) {
                a = head;
                for(;a!=b;a=a->next, b=b->next) ;
                return a;
            }
        }
        return 0;
    }
};

287. Find the Duplicate Number

這題的資料很特別，都是1~n，同時array長n+1 這代表array資料一定在array的index中，所以有重複就是cycle

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int a = nums[nums[0]], b = nums[nums[nums[0]]];
        for (;a!=b;a=nums[a], b=nums[nums[b]]) ;
        for (a = nums[0];a!=b;a=nums[a], b=nums[b]) ;
        return a;
    }
};

160. Intersection of Two Linked Lists

龜兔賽跑能找到起點是因為兩者只差一段common的距離

所以只要把兩個ptr走的距離湊成一樣的就可以找到起點

當走到底就從另一個開始走

a = a_diff + common
b = b_diff + common

走到底之後
a => a_diff + common + b_diff
b => b_diff + common + a_diff

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *a, ListNode *b) {
        if (!a || !b)
            return 0;
        ListNode *x = a, *y = b;
        while (x != y) {
            x = !x ? b : x->next;
            y = !y ? a : y->next;
        }
        return x;
    }
};

matrix翻翻樂

常常見到，不知道為什麼

48. Rotate Image

有兩個解法

一個是4個一起換

一個是對角線 (固定走橫的，想像成轉成直線) (i, j), (n-1-i, n-1-j) 另一個反對角線 (固定走直的，想像成轉成橫線) (n-1-j,i), (j,n-1-i) 之後把覆蓋順序寫下來 (i, j) <- (n-1-j, i) <- (n-1-i, n-1-j) <- (j, n-1-i)

class Solution {
public:
    void rotate(vector<vector<int>>& mx) {
        auto m = mx.size();
        auto inv = [m](int x) { return m-1-x; };
        // (i, j)  <-  (n-1-j, i)  <-  (n-1-i, n-1-j)  <-  (j, n-1-i)
        for (int i=0;i<(m>>1);i++)
            for (int j=0;j<(m-(m>>1));j++) {
                int tmp = mx[i][j];
                mx[i][j] = mx[inv(j)][i];
                mx[inv(j)][i] = mx[inv(i)][inv(j)];
                mx[inv(i)][inv(j)] = mx[j][inv(i)];
                mx[j][inv(i)] = tmp;
            }
    }
};

另一個是transpose(對角線互換)後把column都reverse

class Solution {
public:
    void rotate(vector<vector<int>>& mx) {
        for(int i=0;i<mx.size();i++) {
            for(int j=i+1;j<mx.size();j++) {
                swap(mx[i][j],mx[j][i]);
            }
            reverse(mx[i].begin(),mx[i].end());
        }
    }
};

54. Spiral Matrix

用index是最麻煩的，這裡可以拿第一排之後逆時針轉90度

class Solution {
public:
    vector<vector<int>> back90(vector<vector<int>>& m) {
        vector<vector<int>> ret;
        for (int j=m[0].size()-1;j>=0;j--) {
            vector<int> row;
            for (int i=0;i<m.size();i++)
                row.push_back(m[i][j]);
            ret.push_back(row);
        }
        return ret;
    }
    vector<int> spiralOrder(vector<vector<int>>& m) {
        vector<int> ret;
        while (!m.empty()) {
            std::copy(m[0].begin(),m[0].end(), std::back_inserter(ret));
            m.erase(m.begin());
            m = back90(m);
        }
        return ret;
    }
};
  1. 做出單調函數，來猜數字
  2. 丟左邊，留右邊
  3. 終點(b)透過答案存不存在決定要不要-1

287. Find the Duplicate Number

因為數字是累積的，只會越來越多(單調) 所以可以設計一個函數把array轉成單調的array做bsearch

只要能湊出單調就能用bsearch

要找什麼? 找總量不對的第一個位置

b帶nums.size()-1，因為最後出來的最大數字就是這個值 需要捨棄的部分帶a = mid+1 要保留的部分帶b = mid return就是a

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        auto small_or_equal = [&](int cur) {
            int count = 0;
            for (auto &num: nums) {
                if (num <= cur)
                    count++;
            }
            return count;
        };
        int a = 0, b = nums.size()-1;
        while (a < b) {
            int mid = (a+b)/2;
            if (small_or_equal(mid) > mid)
                b = mid;
            else
                a = mid+1;
        }
        return a;
    }
};

33. Search in Rotated Sorted Array

第一段找最小 因為是rotate，所以最大一定在中間 總方向就是丟左邊

所以我們取中點看右邊

剩下就是用這個index做map之後做bsearch

注意到這裡的b是帶nums.size()，因為有可能不存在

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int a=0,b=nums.size()-1; // 這裡要-1
        while (a<b) {
            int mid = (a+b)/2;
            if (nums[mid]>nums[b])
                a = mid+1;
            else
                b = mid;
        }
        int base = a;
        for(a=0,b=nums.size();a<b;) { // 這裡不能-1
            int mid = (a+b)/2;
            int i = (mid+base) % nums.size();
            if (nums[i] == target)
                return i;
            else if (nums[i] < target)
                a = mid+1;
            else
                b = mid;
        }
        return -1;
    }
};

162. Find Peak Element

確定是上升就可以 丟左邊，留右邊

class Solution {
public:

    int findPeakElement(vector<int>& nums) {
        int a = 0, b = nums.size()-1;
        while (a < b) {
            int mid = (a+b)/2;
            if (nums[mid] < nums[mid+1])
                a = mid+1;
            else
                b = mid;
        }
        return a;
    }
};

34. Find First and Last Position of Element in Sorted Array

其實就是找lowerbound與upperbound-1

注意到

  1. lowerbound與upperbound只差在一個等號
  2. upperbound的b還是帶nums.size()，因為可能不存在
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        vector<int> ret;
        int a = 0, b = nums.size();
        while (a < b) {
            int mid = (a+b)/2;
            if (nums[mid] < target)
                a = mid+1;
            else
                b = mid;
        }
        if (a == nums.size() || nums[a] != target)
            return {-1, -1};
        ret.push_back(a);
        b = nums.size();
        while (a < b) {
            int mid = (a+b)/2;
            if (nums[mid] <= target)
                a = mid+1;
            else
                b = mid;
        }
        ret.push_back(a-1);
        return ret;
    }
};

154. Find Minimum in Rotated Sorted Array II

Find Peak Element重複的話?

重複就縮上界，因為不知道怎麼bsearch

class Solution {
public:
    int findMin(vector<int>& nums) {
        int a=0,b=nums.size()-1; // 這裡要-1
        while (a<b) {
            int mid = (a+b)/2;
            if (nums[mid]>nums[b])
                a = mid+1;
            else if (nums[mid] < nums[b])
                b = mid;
            else
                b--;
        }
        return nums[a];
    }
};

topo sort

我真的忘了

  1. 建圖
  2. 做topo sort
  • dfs
    • dfs紀錄node狀態
    • 沒走過、走過、正在走
    • 遇到正在走要報錯
    • 最後要記得reverse結果
  • bfs
    • 要算in_degree(有多少點指到)
    • 把degree 0塞到queue
    • 處理完把別人的ingree去掉

除非要求，不然用bfs比較好，因為cycle只要看bfs結束時in_degree的表還有沒有東西就好 dfs要另外處理cycle還要管理中間走過的點，如果是python就算了，用c++真的很痛苦，同時還要reverse結果…

mono stack

  • 根據關注點不同有不同的看法
    • 排序，留下最後的字典序 (stk是重點)
      • 1 3 7 2
      • 1 2
        • 可以看成2把3,7吃了，只留下該範圍最小的，這也是字典序的由來
      • 內容物:
        • 節點
        • 區塊
    • 夾出區間，中間是最大或是最小 (被pop的資料是重點)
      • while stk and stk[-1] <= n
        • 7 3 2 ..left.. 1 ..right.. 2
          • right的所有數字都會小於1
          • left的所有數字都會等於1
          • 1是這個區間(去頭尾)最大的，含頭尾的區間中的最小的
      • while stk and stk[-1] >= n
        • 1 2 3 ..left.. 7 ..right.. 2
          • right的所有數字都會大於7
          • left的所有數字都會等於7
          • 7是這個區間最小的，含頭尾的區間中的最大的
      • 這樣就可以用stk[-2]與n，做出一個閉區間
      • 記得處理沒有stk的case
  • <=與>=怎麼用?
    • 看資料是遞增(>=)還是遞減(<=)
    • 箭頭指向最低的地方
  • 在需要保持原本的順序、字典序、前面的資料會被後面的蓋掉時就可以老慮用用看

84. Largest Rectangle in Histogram

class Solution {
public:
    int largestRectangleArea(vector<int>& hs) {
        vector<int> stk;
        int ret = 0;
        hs.push_back(0); // 留一個最低的把stack都壓出來
        for (int i=0;i<hs.size();i++) {
            while (!stk.empty() && hs[stk.back()] >= hs[i]) { // not <=
                if (stk.size() > 1)
                    ret = max(ret, hs[stk.back()]*(i-stk[stk.size()-2]-1)); // not +1
                else
                    ret = max(ret, hs[stk.back()]*i);
                stk.pop_back();
            }
            stk.push_back(i);
        }
        return ret;
    }
};

sliding windows

用閉區間做

列舉起點

b = 0
win = []
for a in range(len(fs)):
    while b < len(fs) and when_win_is_legal():
        update_ret()
        expand_win()
    shrink_win()
return ret

列舉終點

a = 0
win = []
for b in range(len(fs)):
    update_win()
    while a <= b and when_win_is_illegal():
        shrink_win()
    update_ret()
return ret

atMost

def atmost(bound):
    ret = i = 0
    for j,n in enumerate(nums):
        update_win()
        while i <= j and when_win_is_illegal():
            shrink_win()
        ret += j-i+1
    return ret

prefix sum

  • 算區間和
  • 和
    • 從a~b的總和
    • 如果有負數，可以代表偏離原點多遠
  • 一般來說，通常第一個會是0代表沒有加任何東西的狀態
  • 所以index從1開始，代表從arr[0]~arr[i-1]

static (index -> sum)

  • list(accumulate(nums, initial=0))
  • LC209
    • 因為arr只有正數
      • 可以用sliding window，去收縮大小
      • 可以用prefix sum，在prefix sum做binary search
        • 我們會先列舉起點到終點
        • 所以prefix sum也是從起點去往後找終點
        • TODO: LC209與LC525為什麼一個是從後面一個從前面

in fly (sum -> count or [index])

  • LC560
    • 基本款
  • LC525
    • 與LC209不同這裡是每加一個都會產生變化
    • 所以可以用in fly一邊建prefix sum，再找有沒有符合的
    • 注意同一個sum我們只要最前面的