Leetcode 复习

Leetcode 复习 1. 两数之和 [链接]

• 一边遍历，一边把[nums[i], i]放入哈希中

vector twoSum(vector& nums, int target) {
    unordered_map ump;
    // 经典哈希套路，先查、查到就更新、最后记录当前数
    for(int i = 0; i < nums.size(); ++i){
        auto tar = ump.find(target-nums[i]);
        if(tar != ump.end()) return {tar->second, i};
        ump[nums[i]] = i;
    }
    return {-1, -1};
}

2. 两数相加 [链接]

• 逐个相加、记录进位，重点代码在于 while(l1 || l2 || flag)

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head = new ListNode(0), *cur = head;
    int flag = 0;
    while(l1 || l2 || flag){
        int num1 = 0, num2 = 0;
        if(l1){num1 = l1->val; l1 = l1->next; }
        if(l2){num2 = l2->val; l2 = l2->next; }
        int sum = num1 + num2 + flag;
        flag = sum / 10;
        cur->next = new ListNode(sum % 10);
        cur = cur->next;
    }
    cur = head->next;
    delete head; // 记得delete虚拟头节点
    return cur;
}

3. 二分查找 [链接]

• 背也得背下来

int search(vector& nums, int target) {
    // 左闭右闭 -- while(l<=r) -- r=mid-1 -- l=mid+1
    int l = 0, r = nums.size()-1;
    while(l <= r){
        int mid =  l + ((r-l)>>1);
        if(nums[mid] == target) return mid;
        else if(nums[mid] > target) r = mid-1;
        else l = mid + 1;
    }
    return -1;
}

4. 用两个栈实现队列 [链接]

• 尾进头出、头空尾补

class CQueue {
    public:
    CQueue() {}

    void appendTail(int value) { tail.push(value); }

    int deleteHead() {
        if(head.empty()){
            if(tail.empty()) return -1;
            while(!tail.empty()){
                head.push(tail.top());
                tail.pop();
            }
        }
        int ret = head.top();
        head.pop();
        return ret;
    }

    stack head;
    stack tail;
};

5. 寻找两个正序数组的中位数 [链接]

• 直接用归并

double findMedianSortedArrays(vector& nums1, vector& nums2) {
    vector res;
    int i = 0, j = 0;
    while(i < nums1.size() && j < nums2.size()){
        int temp = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
        res.push_back(temp);
    }
    while(i < nums1.size()) res.push_back(nums1[i++]);
    while(j < nums2.size()) res.push_back(nums2[j++]);
    int mid = res.size() / 2;
    if(res.size() % 2 == 0) return (res[mid] + res[mid-1])/2.0;
    else return res[mid];
}

6. 存在重复元素 [链接]

bool containsDuplicate(vector& nums) {
    unordered_map ump;
    for(auto it : nums){
        ++ump[it];
        if(ump[it] == 2) return true;
    }
    return false;
}

7. 整数反转 [链接]

• 基本的大思路是原数每次取最后一位，新数将这位放到最后
• 但要考虑超过int范围的情况
  • 所以原数字和新数字都用longlong
  • 最后判断是否溢出

int reverse(int x) {
    long long res = 0;
    long long n = x;
    while(n){
        res = res*10 + n%10;
        n /= 10;
    }
    return res < INT_MIN || res > INT_MAX ? 0 : res; 
}

8. 无重复字符的最长子串 [链接]

• 依然是基本的哈希套路，边遍历边添加
• 核心：记录当前字符最后出现的位置的下一个位置
  • 一旦这个位置比左边界大，那就必须更新左边界

int lengthOfLongestSubstring(string s) {
    if(s.size() <= 1) return s.size(); // 边界条件
    int dic[128]={}, len = 0; // 初始化
    dic[s[0]] = 1; // 初始条件
    for(int i = 0, j = 1; j < s.size(); ++j){
        i = max(i, dic[s[j]]); // 更新左边界
        len = max(len, j - i + 1); // 更新长度
        dic[s[j]] = j + 1; // 更新当前字母出现的最后位置
    }
    return len;
}

9. 最长公共前缀 [链接]

• 取第一个字符串，逐个取字母ch，找每个字符对应位置的字符是否都是该字母ch

string longestCommonPrefix(vector& strs) {
    string res = "";
    for(int i = 0; i < strs[0].size(); ++i){
        char ch = strs[0][i];
        for(int j = 1; j < strs.size(); ++j){
            if(i >= strs[j].size() || strs[j][i] != ch){
                return res;
            }
        }
        res += ch;
    }
    return res;
}

10. 最长回文子串 [链接]

• 动态规划，dp[i][j] 表示闭区间 [i , j] 是不是回文串
• 当s[i] == s[j] 时，如果ij相等或相邻、或[i+1, j-1]是回文串
  • 则[i, j]也一定是回文串
  • 此时更新起始位置和长度
• 最后用起始位置和长度作为substr的参数返回结果

string longestPalindrome(string s) {
    int len = s.size();
    vector> dp(len, vector(len));
    for(int i = 0; i < len; ++i) dp[i][i] = s[i];
    int bigLen = 0, start = 0;
    for(int i = len-1; i >= 0; --i){
        for(int j = i; j < len; ++j){
            if((s[j] == s[i]) && 
               (j - i <= 1 || dp[i+1][j-1])){
                dp[i][j] = true;
                if(j-i+1 >= bigLen){
                    bigLen = j-i+1;
                    start = i;
                }
            }
        }
    }
    return s.substr(start, bigLen);
}

11. 三数之和 [链接]

• 核心：排序、固定左结点，双指针
• 细节：去重

vector> threeSum(vector& nums) {
    vector> res;
    sort(nums.begin(), nums.end());
    int len = nums.size();
    for(int i = 0; i < len-2; ++i){
        if(i > 0 && nums[i] == nums[i-1]) continue; // 去重
        if(nums[i] > 0) break; 
        int j = i+1, k = len-1;
        while(j < k){
            if(j > i+1 && nums[j] == nums[j-1]){
                ++j; continue;
            } // 这里很重要
            int sum = nums[i] + nums[j] + nums[k];
            if(sum < 0) ++j;
            else if(sum > 0) --k;
            else {
                res.push_back({nums[i], nums[j], nums[k]});
                ++j; --k;
            }
        }
    }
    return res;
}

12. 爬楼梯 [链接]

int climbStairs(int n) {
    if(n == 1) return 1;
    int dp1 = 1, dp2 = 2, dp3 = 2;
    for(int i = 3; i <= n; ++i){
        dp3 = dp2 + dp1;
        dp1 = dp2;
        dp2 = dp3;
    }
    return dp3;
}

13. 罗马数字转整数 [链接]

• 一个字母 ch 如果比他右面的字母大或相等，则是加ch
• 否则是减ch

unordered_map ump = {
    {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50}, 
    {'C', 100}, {'D', 500}, {'M', 1000}
};
int romanToInt(string s) {
    int res = ump[s[s.size()-1]];
    for(int i = s.size()-2; i >= 0; --i){
        if(ump[s[i]] >= ump[s[i+1]]){
            res += ump[s[i]];
        } else res -= ump[s[i]];
    }
    return res;
}

14. 整数转罗马数字 [链接]

vector> ump = {
    {1, "I"}, {4, "IV"}, {5, "V"}, {9, "IX"},
    {10, "X"}, {40, "XL"}, {50, "L"}, {90, "XC"},
    {100, "C"}, {400, "CD"}, {500, "D"}, {900, "CM"},
    {1000, "M"}
};
string intToRoman(int num) {
    string res = "";
    for(int i = ump.size()-1; i >= 0; --i){
        while(num >= ump[i].first){
            res += ump[i].second;
            num -= ump[i].first;
        }
    }
    return res;
}

15. 括号生成 [链接]

• 这种思路是非递归的回溯
  1. 每个位置都可能是’(’ 或’)’
  2. 如果左括号个数已经达到n个，则剩下的都是右括号
  3. 任何一个状态，左括号个数必须>=右括号个数
     1. 如果左括号个数==右括号，则下一个一定得是左括号
     2. 如果左括号个数>右括号，那下一个有两种可能

vector generateParenthesis(int n) {
    vector res = {"("};
    vector left = {1};
    for(int i = 1; i < 2*n; ++i){
        int len = res.size();
        for(int j = 0; j < len; ++j){
            int total = res[j].size();
            if(total == 2*n) continue; // 长度已经达到了
            // 左括号够了，只能填右括号
            if(left[j] == n) res[j] += string(2*n-total, ')');
            else if(left[j] < n){
                if(total < 2*left[j]){ // 左括号比右括号多
                    res.push_back(res[j]+")");
                    left.push_back(left[j]);
                } // 左括号和右括号一样多
                res[j] += "(";
                left[j]++;
            }
        }
    }
    return res;
}

16. 合并两个有序链表 [链接]

• 核心：归并思想
• 细节：
  1. 边缘情况：两个链表都空、其中一个是空
  2. 虚拟头节点用来辅助，最后记得delete
  3. 中间不需要new，只需要直接连接即可

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    if(!list1 && !list2) return nullptr;
    if(!list1 || !list2) return list1 ? list1 : list2;
    ListNode *head = new ListNode(0), *cur = head;
    while(list1 && list2){
        if(list1->val < list2->val){
            cur->next = list1;
            list1 = list1->next;
        }else{
            cur->next = list2;
            list2 = list2->next;
        }
        cur = cur->next;
    }
    cur->next = list1 ? list1 : list2;
    cur = head->next;
    delete head;
    return cur;
}

17. 有效的括号[链接]

• 核心是栈，同类型的右括号可以消去栈顶的左括号

unordered_map brk = {
    {')', '('}, {']','['}, {'}', '{'}
}; // 创建一个右括号找同类左括号的哈希
bool isValid(string s) {
    stack left; // 只放入左括号的栈
    for(auto ch : s){
        if(ch == '(' || ch == '[' || ch == '{')
            left.push(ch);
        else{ // 右括号
            if(left.empty()) return false; // 栈空
            // 栈顶括号类型不匹配
            if(left.top() != brk[ch]) return false; 
            else left.pop(); // 匹配一个就消去
        }
    }
    return left.empty(); // 栈空说明左括号消完了
}

18. 判定字符是否唯一 [链接]

• 核心思路：哈希表字符统计，只要之前出现过就返回假
• 优化方法：用一个int的前26位来表示a～z

bool isUnique(string astr) {
    int hash = 0;
    for(auto ch : astr){
        int bit = 1 << (ch-'a');
        if(hash & bit) return false;
        hash |= bit;
    }
    return true;
}

19. 二叉树的层序遍历 [链接]

vector> levelOrder(TreeNode* root) {
    if(!root) return {}; // 边缘条件
    queue que; // 队列
    que.push(root); // 初始化
    int num = 1; // 记录每层个数
    vector>res;
    vector layer;
    while(!que.empty()){
        if(num == 0) { // 说明一层空了
            num = que.size(); // 此时队列里的个数为下一层的个数
            res.push_back(layer); // 保存这一层
            layer.clear();
        }
        root = que.front(); que.pop(); --num; // 核心代码
        layer.push_back(root->val);
        if(root->left) que.push(root->left);
        if(root->right) que.push(root->right);
    }
    if(!layer.empty()) res.push_back(layer); // 别忘了这个
    return res;

20. 买卖股票的最佳时机 [链接]

• 在每个位置的时候，都有一个这个位置之前最小的值
• 当前最大收益，一定是max(前一个位置的最大收益，当前-最小)

int maxProfit(vector& prices) {
    int low = prices[0];
    int profit = 0;
    for(int i = 1; i < prices.size(); ++i){
        low = min(prices[i], low);
        profit = max(profit, prices[i] - low);
    }
    return profit;
}

21. 最长连续序列 [链接]

• 核心
  1. unordered_set去重
  2. 遍历set，如果某个数it的前驱it-1不在set里，说明这个数是序列的开头
  3. 从这个数开始找，it+1、… ，直达找不为止
  4. 结尾位置和开头位置做差即为这段连续子序列长度

int longestConsecutive(vector& nums) {
    unordered_set ump(nums.begin(), nums.end());
    int maxLen = 0;
    for(auto it : ump){ // 不要遍历数组，遍历哈希
        if(!ump.count(it-1)){
            int digit = it;
            while(ump.count(++digit))
            maxLen = max(maxLen, digit-it);
        }
    }
    return maxLen;
}

22. 最接近的三数之和 [链接]

• 同三数之和

int threeSumClosest(vector& nums, int target) {
    sort(nums.begin(), nums.end());
    int res = nums[0] + nums[1] + nums[2], len = nums.size();
    for(int i = 0; i < len - 2; ++i){
        if(i > 0 && nums[i] == nums[i-1]) continue;
        int j = i + 1, k = len - 1;
        while(j < k){
            if(j > i + 1 && nums[j] == nums[j-1]){
                ++j; continue;
            }
            int sum = nums[i] + nums[j] + nums[k];
            if(sum == target) return target;
            res = abs(sum-target) < abs(res-target) 
                  ? sum : res;
            if(sum > target) --k;
            else ++j;
        }
    }
    return res;
}

23. 盛最多水的容器 [链接]

• 面积 = 较低的那个✖️坐标差
• 两个指针从两端出发，更新较低的那个
• 因为两指针在靠近的过程中，坐标差是减少的
  • 如果更新较高的那个，只有变得更小的可能

int capacity(vector& height, int i, int j){
    return min(height[i], height[j]) * abs(j-i);
}
int maxArea(vector& height) {
    int i = 0, j = height.size()-1;
    int res = capacity(height, i, j);
    while(i < j){
        if(height[i] <= height[j]) ++i;
        else --j;
        res = max(res , capacity(height, i, j));
    }
    return res;
}

24. 合并两个有序数组 [链接]

• 本质还是归并排序的merge部分
• 但先要把nums1的前m个数字移到后面，这样会多遍历一次nums1
• 所以反向操作：将两个数组里较大的放到nums1的最后面

void merge(vector& nums1, int m, 
           vector& nums2, int n) {
    int i = m-1, j = n-1, k = m+n-1;
    while(i >= 0 && j >= 0){
        nums1[k--] = nums1[i] > nums2[j] 
            	? nums1[i--] : nums2[j--];
    }
    while(j >= 0) nums1[k--] = nums2[j--];
}

25. 字符串相乘 [链接]

• 长度为m和长度为n的两个数相乘，结果一定是 m+n 或 m+n-1 位的
• 建立一个长度为m+n的数组D
  • m的第i个数字和n的第j个数字相乘，加在D的第i+j+1位上
  • 从最后一位开始，十进制化，进位加到前一位
• 确认有多少位，创立全’0’的string
• 对应位放入string

string multiply(string num1, string num2) {
    if(num1 == "0" || num2 == "0") return "0"; // 边界条件
    int m = num1.size(), n = num2.size(); // 两个数位数
    vector digits(m+n); // 最长m+n，最短m+n-1
    for(int i = m-1; i >= 0; --i){ // 对应位乘法
        int cur1 = num1[i]-'0';
        for(int j = n-1; j >= 0; --j){
            int cur2 = num2[j]-'0';
            digits[i+j+1] += cur1*cur2; // 记得是 +=
        }
    }
    for(int i = n+m-1; i > 0; --i){ // 每一位变成1～9并进位
        digits[i-1] += digits[i] / 10; // 记得是 +=
        digits[i] %= 10;
    }
    int sz = digits[0] == 0 ? m+n-1 : m+n; // 确定位数
    string res(sz, '0'); // 结果字符串
    for(int i = 1; i <= sz; ++i){ // 对应位赋值
        res[sz-i] += digits[m+n-i];
    }
    return res;
}

26. 回文数 [链接]

• 思路同 7. 整数反转
  1. 负数一定不是回文数
  2. 将一个数反转后和之前相等则说明是回文数

bool isPalindrome(int x) {
    if(x < 0) return false;
    long long rev = 0;
    for(int i = x; i > 0; i /= 10){
        rev = rev*10 + i%10;
    }
    return rev == x;
}

27. 排序数组 [链接]

• 快速排序

vector sortArray(vector& nums) {
    sortArray(nums, 0, nums.size()-1);
    return nums;
}
void sortArray(vector &nums, int L, int R){
    if(L >= R) return;
    vector lr = pivot(nums, L, R);
    sortArray(nums, L, 	lr[0]); 
    sortArray(nums, lr[1], R);
}
vector pivot(vector &nums, int L, int R){
    int pvt = nums[rand()%(R-L+1)+L]; // 随机轴点
    int less = L-1, more = R+1; // 起始位置很重要
    while(L < more){
        if(nums[L] < pvt) 	 swap(nums[L++], nums[++less]);
        else if(nums[L] > pvt) swap(nums[L], nums[--more]);
        else ++L;
    }
    return {less, more}; // 返回的两个边界很重要
}

• 归并排序

vector sortArray(vector& nums) {
    split(nums, 0, nums.size()-1);
    return nums;
}
void split(vector &nums, int L, int R){
    if(L >= R) return;
    int mid = (L + R) >> 1;
    split(nums, L, mid);
    split(nums, mid+1, R);
    merge(nums, L, mid+1, R);
}
void merge(vector &nums, int L, int R, int end){
    vector res;
    int i = L, j = R;
    while(i < R && j <= end){
        int temp = nums[i] < nums[j] ? nums[i++] : nums[j++];
        res.push_back(temp);
    }
    while(i < R) res.push_back(nums[i++]);
    while(j <= end) res.push_back(nums[j++]);
    for(int i = 0; i < res.size(); ++i){
        nums[i+L] = res[i];
    }
}

• 堆排序

vector sortArray(vector& nums) {
    int len = nums.size();
    // 找到最后一个非叶子结点，逐个堆化
    for(int i = len/2-1; i >= 0; --i){
        heapify(nums, i, len);
    }
    swap(nums[0], nums[--len]);
    while(len > 1){
        heapify(nums, 0, len);
        swap(nums[0], nums[--len]);
    }
    return nums;
}
// 下标为idx的位置为头节点，进行堆化
void heapify(vector &nums, int idx, int len){
    int left = 2*idx+1; // 左孩子
    int temp = nums[idx]; // 记录头节点的值
    while(left < len){
        // 记录头、左、右三个里最大的下标
        int large = left+1 < len && nums[left+1] > nums[left]
            		? left+1 : left;
        large = nums[large] > temp ? large : idx;
        if(large == idx) break; // 如果idx就是最大的，就结束
        nums[idx] = nums[large]; // 否则头为较大的那个
        idx = large; // 继续将large这个结点进行堆化
        left = 2*idx+1;
    }
    nums[idx] = temp;
}

28. 合并区间 [链接]

• 贪心
  • 先按区间左端点从小到大排序
  • 相邻的两个重叠，则更新右边界
  • 不重叠则下一个为一个独立的新区间

vector> merge(vector>& intervals) {
    sort(intervals.begin(), intervals.end());
    // 先放进去第一个
    vector> res = {intervals.front()};
    // 从第二个开始
    for(int i = 1; i < intervals.size(); ++i){
        // 不重叠，当前区间为新的独立区间，插入结果数组
        if(res.back()[1] < intervals[i][0]){
            res.push_back(intervals[i]);
        }else{ // 重叠更新右边界
            res.back()[1] = 
                max(intervals[i][1], res.back()[1]);
        }
    }
    return res;
}

29. 只出现一次的数字 [链接]

• 利用异或
• a^a = 0，b^0 = b

int singleNumber(vector& nums) {
    int res = 0;
    for(auto it : nums){
        res ^= it;
    }
    return res;
}

30. 跳跃游戏II [链接]

• 贪心：在第i个位置时，遍历其可达区间，跳到能跳的最远的地方

int jump(vector& nums) {
    if(nums.size() <= 1) return 0;
    int i = 0;
    int step = 0;
    while(1){
        if(i + nums[i] >= nums.size()-1) return step+1;
        int k = i+1;
        for(int j = i+2; j <= i+nums[i]; ++j){
            k = j+nums[j] > k+nums[k] ? j : k;
        }
        i = k;
        ++step;
    }
    return -1;
}

31. 第一个错误的版本 [链接]

• 二分，每次mid如果是bad，那就记录mid

int firstBadVersion(int n) {
    int l = 1, r = n, res = 0;
    while(l <= r){
        int mid = l + ((r-l)>>1);
        bool Bad = isBadVersion(mid);
        if(Bad){
            res = mid;
            r = mid - 1;
        }
        else l = mid + 1;
    }
    return res;
}

32. 编辑距离 [链接]

• dp[i][j]表示 word1[0:i-1] 和 word2[0:j-1] 变成一样最少需要多少操作
• 如果第i个和第j个相等，那一定有 dp[i][j] = dp[i-1][j-1]
• 如果不相等，得考虑三种修改方法
  • 修改后即第i个第j个相等 dp[i-1][j-1] + 1
  • word1添加等价于word2删除；word1删除等价于word2添加
  • 即dp[i-1][j] + 1 和 dp[i][j-1]
  • 这三者取最小即可
• 初始化：dp[i][0] = i; dp[0][j] = j

int minDistance(string word1, string word2) {
    int len1 = word1.size(), len2 = word2.size();
    vector> dp(len1+1, vector(len2+1));
    for(int i = 0; i <= len1; ++i) dp[i][0] = i;
    for(int j = 0; j <= len2; ++j) dp[0][j] = j;
    for(int i = 1; i <= len1; ++i){
        for(int j = 1; j <= len2; ++j){
            if(word1[i-1] == word2[j-1])
                dp[i][j] = dp[i-1][j-1];
            else
                dp[i][j] = 1 + min(
                	{dp[i-1][j], dp[i][j-1], dp[i-1][j-1]});
        }
    }
    return dp[len1][len2];
}

33. 最大子数组和 [链接]

• 三种思路：前缀和、贪心、动态规划
• 优先级队列：
  • 不停求和，不断获得前i个里前缀和最小的
  • 不断更新，最大子数组和 = 当前前缀和 - 最小前缀和

int maxSubArray(vector& nums) {
    int sum = nums[0]; // 初始化细节
    int minSum = 0;
    int res = nums[0];
    for(int i = 1; i < nums.size(); ++i){
        minSum = min(sum, minSum); // 记录最小前缀和
        sum += nums[i]; // 不断计算前缀和
        res = max(res, sum-minSum); // 更新最大和值
    }
    return res;
}

• 贪心，求和，一旦发现和小于0，就从下一个数开始重新求和

int maxSubArray(vector& nums) {
    int cur = 0, res = INT_MIN;
    for(auto it : nums){
        cur += it;
        res = max(res, cur); // 注意更新的时机
        if(cur < 0) cur = 0;
    }
    return res;
}

• 动态规划：以第i个位置结尾的子数组的最大和，其最大值只能是
  • num[i] + 以第i-1个位置结尾的子数组的最大和
  • num[i]

int maxSubArray(vector& nums) {
    int dp = nums[0], res = nums[0];
    for(int i = 1; i < nums.size(); ++i){
        dp = max(dp+nums[i], nums[i]);
        res = max(res, dp);
    }
    return res;
}

34. 删除有序数组中的重复项 [链接]

• 双指针原地删除

int removeDuplicates(vector& nums) {
    int i = 0;
    for(int j = 0; j < nums.size(); ++j){
        if(nums[j] != nums[i]){
            nums[++i] = nums[j];
        }
    }
    return i+1;
}

35. N 皇后 [链接]

• 第一：状态压缩，用一个数组表示第i列第放在第几行
  • 比如board[i] = m表示第i列，第m行有一个棋子
• 第二：有效性检查，放第i个棋子时，只需检查是不是和前i-1个冲突就行
• 第三：深度优先遍历，只要一个位置有效，就以其为基础进行下一个位置

vector> res;
vector board;
vector> solveNQueens(int n) {
    board.resize(n);
    check(0);
    vector> solv;
    for(auto bd : res){
        vector temp;
        for(auto col : bd){
            string s(n, '.');
            s[col] = 'Q';
            temp.push_back(s);
        }
        solv.push_back(temp);
    }
    return solv;
}
void check(int i){
    if(i == board.size()){
        res.push_back(board);
        return;
    }
    for(int k = 0; k < board.size(); ++k){
        board[i] = k;
        if(isValid(i)) check(i+1);
    }
}
bool isValid(int i){
    for(int m = 0; m < i; ++m){
        if(board[m] == board[i] || 
           	abs(board[m]-board[i]) == i-m)
            return false;
    }
    return true;
}

36. 数组中的第K个最大元素 [链接]

• 小根堆

int findKthLargest(vector& nums, int k) {
    priority_queue, greater> que;
    for(auto it : nums){
        if(que.size() < k) que.push(it);
        else if(it > que.top()){
            que.push(it);
            que.pop();
        } 
    }
    return que.top();
}

• 快排

int findKthLargest(vector& nums, int k) {
    srand(time(NULL));
    return split(nums, 0, nums.size()-1, nums.size()-k);
}
int split(vector &nums, int L, int R, int m){
    if(L == R) return nums[L]; // 左右撞上了说明就是这个值
    vector mid = pivot(nums, L, R); // partition
    // 在相等区域
    if(m > mid[0] && m < mid[1]) return nums[mid[0]+1];
    // 在左边的区域
    else if(m <= mid[0]) return split(nums, L, mid[0], m);
    // 在右边区域
    else return split(nums, mid[1], R, m);
}
// partition部分和快排一模一样
vector pivot(vector &nums, int L, int R){
    int pvt = nums[rand()%(R-L+1) + L];
    int less = L-1, more = R+1;
    while(L < more){
        if(nums[L] < pvt) swap(nums[L++], nums[++less]);
        else if(nums[L] > pvt) swap(nums[L], nums[--more]);
        else ++L;
    }
    return {less, more};
}

37. 反转链表 [链接]

• 核心代码就四行

ListNode* reverseList(ListNode* head) {
    ListNode *cur1 = nullptr, *cur2 = nullptr;
    while(head){
        cur1 = head;
        head = head->next;
        cur1->next = cur2;
        cur2 = cur1;
    }
    return cur2;
}

38. 字符串的排列 [链接]

vector res;
void dfs(string s, int i){
    if(i == s.size()-1){
        res.push_back(s);
        return;
    }
    unordered_set ust; // 第j个元素在第i位出现过
    for(int j = i; j < s.size(); ++j){
        if(ust.count(s[j])) continue;
        ust.insert(s[j]);
        swap(s[i], s[j]);
        dfs(s, i+1);
        swap(s[i], s[j]);
    }
}
vector permutation(string s) {
    dfs(s, 0);
    return res;
}

39. 全排列 [链接]

• 同上题，但没有重复元素

vector> res;
void dfs(vector& nums, int i){
    if(i == nums.size() - 1){
        res.push_back(nums);
        return;
    }
    for(int j = i; j < nums.size(); ++j){
        swap(nums[i], nums[j]);
        dfs(nums, i+1);
        swap(nums[i], nums[j]);
    }
}
vector> permute(vector& nums) {
    dfs(nums, 0);
    return res;
}

40. 数组中重复的数字 [链接]

• 常规做法就是哈希

int findRepeatNumber(vector& nums) {
    vector lable(nums.size());
    for(auto num : nums){
        lable[num]++;
        if(lable[num] == 2) return num;
    }
    return -1;
}

• 交换法，不需要额外空间

int findRepeatNumber(vector& nums) {
    for(int i = 0; i < nums.size();){
        if(nums[i] != i){
            int j = nums[i];
            if(nums[j] == j)
                return nums[i];
            swap(nums[i], nums[nums[i]]);
        }else ++i;
    }
    return -1;
}

41. 旋转数组的最小数字 [链接]

• 二分查找

int minArray(vector& numbers) {
    int l = 0, r = numbers.size()-1;
    while(l < r){
        int mid = l + ((r-l)>>1);
        if(numbers[mid] > numbers[r]) l = mid+1;
        else if(numbers[mid] < numbers[r]) 
            r = mid;
        else r--;
    }
    return numbers[l];
}

42. 搜素旋转排序数组 [链接]

int search(vector& nums, int target) {
    if(nums[0] == target) return 0; // 起点
    int l = 0, r = nums.size();
    while(l < r){
        int mid = (r+l)>>1;
        if(nums[mid] == target) return mid;
        if(nums[mid] > nums[0]){ // 左半边
            if(target < nums[mid] && target > nums[0]) 
                r = mid;
            else l = mid + 1;
        }else{ // 右半边
            if(target > nums[mid] && target < nums[0]) 
                l = mid + 1;
            else r = mid;
        }
    }
    return -1;
}

43. 重复的DNA序列 [链接]

vector findRepeatedDnaSequences(string s) {
    int len = s.size();
    if(len < 10) return {};
    string win = s.substr(len-10);
    unordered_set ust ={win};
    unordered_set res;
    for(int i = len-11; i >= 0; --i){
        win.pop_back();
        win = s[i] + win;
        if(ust.count(win)) res.insert(win);
        ust.insert(win);
    }
    return vector(res.begin(), res.end());
}

44. 反转字符串中的单词 III [链接]

• 简简单单双指针

string reverseWords(string s) {
    s += ' ';
    int i = 0, j = 0;
    while(i < s.size() && j < s.size()){
        while(i < s.size() && s[i] == ' ')++i;
        j = i+1;
        while(j < s.size() && s[j] != ' ')++j;
        int p = i, q = j-1;
        while(p < q){
            swap(s[p], s[q]);
            ++p; --q;
        }
        i = j + 1;
    }
    s.pop_back();
    return s;
}

45. 正则表达式匹配[链接]

• 动态规划

bool isMatch(string s, string p) {
    int m = s.size(), n = p.size();
    // 第i-1和第j-1匹配
    auto match = [&](int i, int j){
        if(i == 0) return false; // 不存在的下标
        if(p[j-1] == '.') return true; // 通配符都可以
        return s[i-1] == p[j-1];
    };
    vector> dp(m+1, vector(n+1, false));
    dp[0][0] = true; // 初始条件
    for(int i = 0; i <= m; ++i){
        for(int j = 1; j <= n; ++j){
            if(p[j-1] == '*'){ // 匹配多个
                dp[i][j] |= dp[i][j-2]; // 最起码和前一相同
                if(match(i, j-1)){ // 匹配i-1和j-2
                    dp[i][j] |= dp[i-1][j];
                }
            }else{
                if(match(i, j)){
                    dp[i][j] |= dp[i-1][j-1];
                }
            }
        }
    }
    return dp[m][n];
}

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-HSwGGIAd-1650779288009)(assets/截屏2022-04-23 20.14.48.png)]

46. 电话号码的组合 [链接]

• 一眼dfs

vector vst = {
    "", "", "abc", "def", "ghi", 
    "jkl", "mno", "pqrs", "tuv", "wxyz"
};
vector res;
string temp; 
void dfs(string digits, int i){
    if(i == digits.size()) {
        res.push_back(temp);
        return;
    }
    for(auto ch : vst[digits[i]-'0']){
        temp += ch;
        dfs(digits, i+1);
        temp.pop_back();
    }
}
vector letterCombinations(string digits) {
    if(digits.size() == 0) return {};
    dfs(digits, 0);
    return res;
}

47. 删除链表的倒数第N个结点 [链接]

• 双指针

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode *cur1 = head, *cur2 = head;
    for(int i = 0; i < n; ++i){
        cur1 = cur1->next;
    }
    if(!cur1) return head->next; 
    while(cur1->next){
        cur1 = cur1->next;
        cur2 = cur2->next;
    }
    ListNode *tmp = cur2->next;
    cur2->next = tmp->next;
    delete tmp;
    return head;
}

48. 合并K个省序链表

• 归并的思路

ListNode* mergeKLists(vector& lists) {
    return split(lists, 0, lists.size()-1);
}
// 两两合并
ListNode* split(vector &lists, int L, int R){
    if(L == R) return lists[L];
    if(L > R) return nullptr;
    int mid = L + ((R - L) >> 1);
    return merge(split(lists, L, mid), 
                 split(lists, mid+1, R));
}
// 两个链表合并
ListNode* merge(ListNode* l1, ListNode* l2){
    if(!l1 && !l2) return nullptr;
    if(!l1 || !l2) return l1 ? l1 : l2;
    ListNode* nhead = new ListNode(0), *l3 = nhead;
    while(l1 && l2){
        if(l1->val <= l2->val){
            l3->next = l1;
            l1 = l1->next;
        }else{
            l3->next = l2;
            l2 = l2->next;
        }
        l3 = l3->next;
    }
    l3->next = l1 ? l1 : l2;
    l3 = nhead->next;
    delete nhead;
    return l3;
}

• 改进版本 – 非递归

ListNode* mergeKLists(vector& lists) {
    if(lists.empty()) return nullptr;
    for(int step = 1; step < lists.size(); step *= 2){
        for(int i = 0; i < lists.size(); i += 2*step){
            if(i + step < lists.size())
                lists[i] = merge(lists[i], lists[i+step]);
        }
    }
    return lists[0];
}
ListNode* merge(ListNode* l1, ListNode* l2){
    if(!l1 && !l2) return nullptr;
    if(!l1 || !l2) return l1 ? l1 : l2;
    ListNode* nhead = new ListNode(0), *l3 = nhead;
    while(l1 && l2){
        if(l1->val <= l2->val){
            l3->next = l1;
            l1 = l1->next;
        }else{
            l3->next = l2;
            l2 = l2->next;
        }
        l3 = l3->next;
    }
    l3->next = l1 ? l1 : l2;
    l3 = nhead->next;
    delete nhead;
    return l3;
}

49. 下一个排列[链接]

• 两点需求：下一个数比当前数大，增加的幅度尽可能小
  • 大数和小数交换
  • 从右往前找
• 从右往左第一个升序对 [a[i], a[i+1]] – a[i] < a[i+1]
  • a[i]就是小数
  • 找 i 右面比比他大的最小的数，就是大数
  • 这俩交换，第i位就变大了
  • 之后还需要将i后面的数字升序，才能保证最小

void nextPermutation(vector& nums) {
    int i = nums.size()-2;
    while(i >= 0 && nums[i] >= nums[i+1]) --i;
    if(i >= 0){
        int j = nums.size()-1;
        while(j > i && nums[i] >= nums[j]) --j;
        swap(nums[i], nums[j]);
    }
    reverse(nums.begin()+i+1, nums.end());
}

50. 最长有效括号[链接]

• 用栈
  • 遇到左括号直接将下标入栈
  • 遇到右括号先弹栈
    • 弹完如果空了，就记录当前右括号下标，作为起始点
    • 没空就可以计算长度：i - stack.top()

int longestValidParentheses(string s) {
    stack stk;
    stk.push(-1);
    int maxLen = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '(') stk.push(i);
        else{
            stk.pop();
            if(stk.empty()) stk.push(i);
            else maxLen = max(maxLen, i - stk.top());
        }
    }
    return maxLen;
}

• 正反两次遍历

int longestValidParentheses(string s) {
    int left = 0, right = 0, maxLen = 0;
    for(int i = 0; i < s.size(); ++i){
        if(s[i] == '(') ++left;
        else ++right;
        if(left == right) maxLen = max(maxLen, left+right);
        else if(left < right) left = right = 0;
    }
    left = 0; right = 0;
    for(int i = s.size()-1; i >= 0; --i){
        if(s[i] == '(') ++left;
        else ++right;
        if(left == right) maxLen = max(maxLen, left+right);
        else if(left > right) left = right = 0;
    }
    return maxLen;
}

51. 组合总和 [链接]

• dfs

vector> res;
void dfs(vector &candidates, int i, int sum, int target, vector temp){
    if(sum == target){
        res.push_back(temp);
        return;
    }
    if(i == candidates.size() || sum > target) return;
    for(int j=0; sum+j*candidates[i] <= target; ++j){
        if(j) temp.push_back(candidates[i]);
        dfs(candidates, i+1, 
            sum + j*candidates[i], target, temp);
    }
}
vector> combinationSum(vector& candidates, int target) {
    dfs(candidates, 0, 0, target, {});
    return res;
}

52. 子集 [链接]

• dfs

vector> res;
vector cur;
void dfs(vector &nums, int i, vector &cur){
    if(i == nums.size()){
        res.push_back(cur);
        return;
    }
    dfs(nums, i+1, cur);
    cur.push_back(nums[i]);
    dfs(nums, i+1, cur);
    cur.pop_back();
}
vector> subsets(vector& nums) {
    dfs(nums, 0, cur);
    return res;
}

53. 接雨水 [链接]

• 单调栈

int trap(vector& height) {
    stack stk;
    int rain = 0;
    for(int i = 0; i < height.size(); ++i){
        while(!stk.empty() 
              && height[i] > height[stk.top()]){
            int mid = stk.top(); stk.pop();
            if(stk.empty()) break;
            int left = stk.top();
            int curWidth = i - left - 1;
            int curHeight = min(height[i], height[left]) 
                			- height[mid];
            rain += curHeight * curWidth;
        }
        stk.push(i);
    }
    return rain;
}

54. 旋转图像 [链接]

void rotate(vector>& matrix) {
    int n = matrix.size();
    for(int i = 0; i < n/2; ++i){
        int L = i, R = n-i-1;
        for(int j = 0; j < R-L; ++j){
            int temp = matrix[L][L+j];
            matrix[L][L+j] = matrix[R-j][L];
            matrix[R-j][L] = matrix[R][R-j];
            matrix[R][R-j] = matrix[L+j][R];
            matrix[L+j][R] = temp;
        }
    }
}

55. 字母异位词分组 [链接]

• 哈希

long long mod = 1e9 + 7;
int prime[26] = {
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 
    73, 79, 83, 89, 97, 101
};
int getKey(string s){
    long long key = 1;
    for(auto ch : s){
        key = (key*prime[ch-'a']) % mod;
    }
    return key;
}
vector> groupAnagrams(vector& strs) {
    unordered_map> ump;
    for(auto s : strs){
        int key = getKey(s);
        if(ump.count(key)) ump[key].push_back(s);
        else ump[key] = {s};
    }
    vector> res;
    for(auto ss : ump){
        res.push_back(ss.second);
    }
    return res;
}

56. 不同路径 [链接]

• 动态规划

int uniquePaths(int m, int n) {
    vector dp(n, 1);
    for(int i = 1; i < m; ++i){
        for(int j = 1; j < n; ++j){
            dp[j] += dp[j-1];
        }
    }
    return dp.back();
}

57. 从前序与中序遍历序列构造二叉树 [链接]

• 用栈

TreeNode* buildTree(vector& preorder, vector& inorder) {
    stack stk;
    TreeNode* root = new TreeNode(preorder[0]);
    stk.push(root);
    for(int i = 1, j = 0; i < preorder.size(); ++i){
        TreeNode* node = stk.top();
        if(node->val != inorder[j]){
            node->left = new TreeNode(preorder[i]);
            stk.push(node->left);
        }else{
            while(!stk.empty() 
                  && stk.top()->val == inorder[j]){
                node = stk.top();
                stk.pop();
                ++j;
            }
            node->right = new TreeNode(preorder[i]);
            stk.push(node->right);
        }
    }
    return root;
}

58. 从中序与后序遍历序列构造二叉树 [链接]

TreeNode* buildTree(vector& inorder, vector& postorder) {
    int len = postorder.size();
    if(len == 0) return nullptr;
    stack stk;
    TreeNode* root = new TreeNode(postorder[len-1]);
    stk.push(root);
    for(int i = len-2, j = len-1; i >= 0; --i){
        auto node = stk.top();
        if(node->val != inorder[j]){
            node->right = new TreeNode(postorder[i]);
            stk.push(node->right);
        }else{
            while(!stk.empty() 
                  && stk.top()->val == inorder[j]){
                node = stk.top();
                stk.pop();
                --j;
            }
            node->left = new TreeNode(postorder[i]);
            stk.push(node->left);
        }
    }
    return root;
}

59. LRU

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->pre = head;
    }
    
    int get(int key) {
        if(!cache.count(key)) return -1;
        Node *node = cache[key];
        moveToHead(node);
        return node->value;
    }
    
    void put(int key, int value) {
        if(!cache.count(key)){
            Node *node = new Node(key, value);
            addToHead(node);
            cache[key] = node;
            if(cache.size() > cap){
                node = removeTail();
                cache.erase(node->key);
                delete node;
            }
        }else{
            Node *node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }
private:
    struct Node{
        int key, value;
        Node *pre, *next;
        Node(int k=0, int v=0)
            :key(k), value(v), pre(nullptr), next(nullptr){}
    };
    Node *head, *tail;
    unordered_map cache;
    int cap;
    void remove(Node *node){
        node->pre->next = node->next;
        node->next->pre = node->pre;
    }
    void addToHead(Node *node){
        node->pre = head;
        node->next = head->next;
        head->next->pre = node;
        head->next = node;
    }
    void moveToHead(Node *node){
        remove(node);
        addToHead(node);
    }
    Node* removeTail(){
        Node *node = tail->pre;
        remove(node);
        return node;
    }
};