Learn

有没有人一起从零开始刷力扣

并查集
动态规划
Array
Linklist
Stack
Queue
Tree
Graph
Greedy
Divide and conquer
Recursive（memorization backtracking）
Dfs bfs
Dp
字符串

1 数组

前缀和数组

238. 除自身以外数组的乘积

• 空间复杂度O(n)

时间复杂度O(n)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> pre(n, 1);
        for(int i = 1; i < n; i ++)//前缀,数组表示,计算pre[1]...pre[n-1]
            pre[i] = pre[i - 1] * nums[i - 1];//pre[i] = nums[0]*...nums[i-1]
        for(int i = n - 1, suf = 1; i >= 0; i --)//后缀, int suf表示
        {
            pre[i] *= suf;//pre[n-1]=nums[0]*...nums[n-2]
            suf *= nums[i];//pre[n-2] = nums[0]*...nums[n-3]*nums[n-1]
        }
        return pre;
    }
};

304. 二维区域和检索 - 矩阵不可变

class NumMatrix {
public:
    vector<vector<int>> s;
    NumMatrix(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();
        s.resize(m + 1, vector<int>(n + 1));
        for(int i = 1; i <= m; i ++)
        {
            for(int j = 1; j <= n; j ++)
            {
                s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        ++row1, ++row2, ++ col1, ++col2;
        int res = s[row2][col2] - s[row2][col1-1] - s[row1-1][col2] + s[row1-1][col1-1];
        return res;
    }
};

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

303. 区域和检索 - 数组不可变

时间复杂度O(n)
空间复杂度O(n)

class NumArray {
public:
    vector<int> a;
    NumArray(vector<int>& nums) {
        a.resize(nums.size() + 1, 0);//前缀和的index从1开始，因为当l = 0时，l-1越界
        for(int i = 1; i <= nums.size(); i ++)
        {
            a[i] = a[i - 1] + nums[i - 1];
            //a[1] = a[0] + nums[0]
            //a[2] = a[1] + nums[1]
        }
    }
    //nums[1]+...nums[n] = a[n]
    //nums[l]+...nums[r] = a[r] - a[l-1]
    int sumRange(int left, int right) {
        ++ left, ++ right;
        return a[right] - a[left - 1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

面试题 16.10. 生存人数

题解

class Solution {
public:
    int maxAliveYear(vector<int>& birth, vector<int>& death) {
        vector<int> live(2100, 0);
        int n = birth.size();
        for(int i = 0; i < n; i ++)
        {
            int b = birth[i], d = death[i];
            //差分
            live[b] ++;
            live[d + 1] --;
        }

        int p = 0, res = 0, sum = 0;
        for(int y = 1900; y < 2100; y ++)
        {
            sum += live[y]; //前缀和
            if(sum > p)
            {
                p = sum;
                res = y;
            }
        }

        return res;
    }
};

8 双指针法

头尾指针

15. 三数之和

题解

1. 如果数组为空，或数组长度小于3，return；
2. 排序； O(nlogn)
3. 遍历排序后的数组 O(n)

如果nums[i]>0，break；//由于已经排好序，所以后面不可能有三个数加和等于0
nums[i]不等于nums[i-1]，避免重复解；
//问题转换为从第i+1到n-1个数中，找到两数之和等于-nums[i]，且不能有重复解
//双指针 O(n)
left = i+1，right = n-1,当 L{
当nums[left]+nums[right] > -nums[i]时，执行循环：right —;
当nums[left]+nums[right] = -nums[i]，把当前三数加到答案数组中，并对左右指针去重；
left++;
}
时间复杂度O(n2)
空间复杂度：O(logn)。额外的排序的空间复杂度为O(logn)。然而修改了输入的数组nums，在实际情况下不一定允许，因此也可以看成使用了一个额外的数组存储了nums 的副本并进行排序，空间复杂度为 O(n)。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int n = nums.size();
        if(n < 3) return{};
        sort(nums.begin(), nums.end());

        for(int i = 0; i < n; i ++)
        {
            if(nums[i] > 0) break;
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while(left < right)
            {
                while(left < right && nums[left] + nums[right] > -nums[i]) 
                    right --;
                // cout<<"left="<<left<<"  right="<<right<<endl;
                if(left < right && nums[left] + nums[right] == -nums[i])
                {
                    ans.push_back(vector<int>{nums[i], nums[left], nums[right]});
                    //对左右指针去重,如果当前left和left+1所指的数相等，left++
                    while(left < right && nums[left] == nums[left + 1]) left ++;
                    while(left < right && nums[right] == nums[right - 1]) right --;
                }
                left ++;
            }
        }
        return ans;
    }
};

16. 最接近的三数之和

题解

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        sort(nums.begin(), nums.end());
        int ans = nums[0]+nums[1]+nums[2];//用前三个数的和初始化结果

        for(int i = 0; i < n - 2; i ++)
        {
            if(i > 0 && nums[i] == nums[i - 1]) continue;
            int left = i + 1, right = n - 1;
            while(left < right)
            {
                //target小于sum最小值nums[i]+nums[left]+nums[left+1]
                int min = nums[i] + nums[left] + nums[left + 1];
                if(target < min)
                {
                    if(min - target < abs(ans - target)) ans = min;
                    break;
                }

                //target大于sum最大值nums[i]+nums[right]+nums[right-1]
                int max = nums[i] + nums[right] + nums[right - 1];
                if(target > max)
                {
                    if(target - max < abs(ans - target)) ans = max;
                    break;
                }

                int sum = nums[i] + nums[left]+nums[right];
                if(abs(sum - target) < abs(ans - target)) ans = sum;

                if(sum > target) 
                {
                    right --;
                    while(left < right && nums[right] == nums[right + 1]) right --;
                }
                else if(sum < target)
                {
                    left ++;
                    while(left < right && nums[left] == nums[left - 1]) left ++;
                }
                else return sum;//若target和sum相等，直接返回sum
            }
        }

        return ans;
    }
};

同向双指针、滑动窗口

剑指 Offer 57 - II. 和为s的连续正数序列

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        int i = 1;//滑动窗口左边界
        int j = 1;//滑动窗口右边界
        //左闭右开 [i,j) sum = i + i+1 +...+ j-1
        int sum = 0;//滑动窗口中数字的和

        vector<vector<int>> res;

        //由于序列至少含两个数，则左边界i最大为target/2（向下取整）
        while(i <= target/2)
        {
            //sum<target,右边界右移
            if(sum < target) sum += j ++;
            //sum>target,左边界右移
            else if(sum > target) sum -= i ++;
            //sum=target,保存结果，左边界右移
            else if(sum == target) 
            {
                vector<int> arr;
                for(int a = i; a < j; a ++)
                    arr.push_back(a);
                res.push_back(arr);
                sum -= i ++;
            }
        }
        return res;
    }
};

3. 无重复字符的最长子串

时间复杂度O（n）
空间复杂度O（∣Σ∣），∣Σ∣为128，因为ASCII 码包含128个字符

//双指针
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int n = s.size();
        const int N = 200;//ASCII 码包含128个字符
        int cnt[N] = {0};

        int res = 0;//最长子串的个数
        for(int i = 0, j = 0; i < n; i ++)
        {
            cnt[s[i]] ++;
            while (j < i && cnt[s[i]] > 1)
            {
                cnt[s[j]] --;
                j ++;
            }

            res = max(res, i - j + 1);
        }

        return res;
    }
};

中心扩散

5. 最长回文子串

• 此时1 <= s.length <= 1000

双指针 中心扩散 O(n^2)

class Solution {
public:
    string longestPalindrome(string s) {
        string res;
        for(int i =0; i < s.size(); i ++)
        {
            int l = i, r = i;
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
            if(r - l - 1 > res.size()) res = s.substr(l + 1, r - l - 1);

            l = i, r = i + 1;
            while(l >= 0 && r < s.size() && s[l] == s[r]) l --, r ++;
            if(r - l - 1 > res.size()) res = s.substr(l + 1, r - l - 1);
        }
        return res;
    }
};

• 此时1 <= s.length <= 10^6

  9 树

  树与递归

  226. 翻转二叉树/剑指 Offer 27. 二叉树的镜像

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == nullptr) return nullptr;
        swap(root->left, root->right);
        invertTree(root->left);
        invertTree(root->right);
        return root;
    }
  };
  

  101. 对称二叉树

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    bool isSymmetric(TreeNode* root) {
        if(!root) return true;
        return dfs(root->left, root->right);
    }
  
    bool dfs(TreeNode* l, TreeNode* r)
    {
        if(!l && !r) return true;
        if(!l || !r || l->val != r->val) return false;
        return dfs(l->left, r->right) && dfs(l->right, r->left);
    }
  };
  

  110. 平衡二叉树

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    bool flag = true;
    bool isBalanced(TreeNode* root) {
        dfs(root);
        return flag;
    }
  
    int dfs(TreeNode* root)//返回最大深度
    {
        if(!root) return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        if(abs(left - right) > 1) flag = false;
        return max(left, right) + 1; 
    }
  };
  

  129. 求根节点到叶节点数字之和

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    int sum = 0;
    int sumNumbers(TreeNode* root) {
        dfs(root, 0);
        return sum;
    }
  
    void dfs(TreeNode* root, int num)
    {
        num = num * 10 + root->val;
        if(!root->left && !root->right) sum += num;
        if(root->left) dfs(root->left, num);
        if(root->right) dfs(root->right, num);
    }
  };
  

  树的层序遍历

  199. 二叉树的右视图

  BFS，保存每层最右元素

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    vector<int> rightSideView(TreeNode* root) {
        if(!root) return {};
        vector<int> res;
        queue<TreeNode*> q;
        q.push(root);
  
        while(q.size() > 0)
        {
            int len = q.size();
            for(int i = 0; i < len; i ++)
            {
                TreeNode* t = q.front();
                q.pop();
                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
                if(i == len - 1) res.push_back(t->val);
            }
        }
        return res;
    }
  };
  

  树的中序遍历与二叉搜索树

  450. 删除二叉搜索树中的节点

  
  题解：三种情况
  （1）是叶节点
  （2）只有1个子节点
  （3）有2个子节点
  找到u的后继（一定没有左儿子），将后继的值覆盖到u上，然后删除后继节点

  /**
  * Definition for a binary tree node.
  * struct TreeNode {
  *     int val;
  *     TreeNode *left;
  *     TreeNode *right;
  *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
  *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
  *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
  * };
  */
  class Solution {
  public:
    TreeNode* deleteNode(TreeNode* root, int key) {
        del(root, key);
        return root;
    }
  
    void del(TreeNode* &root, int key)
    {
        if(!root) return;//root为空，返回
        if(key == root->val){
            if(!root->left && !root->right) root = NULL;//没有子节点
            else if(!root->left) root = root->right;//有右儿子
            else if(!root->right) root = root->left;//有左儿子
            else{//左右儿子都有
                auto p = root->right;
                while(p->left) p = p->left;//找root的后继p，p没有左儿子
                root->val = p->val;//root的值置为p的值
                del(root->right, p->val);//删去p，p没有左儿子，可能有右儿子或者叶节点
            }
        }
        else if(key < root->val) del(root->left, key);
        else del(root->right, key);
    }
  };
  

重构二叉树

105. 从前序与中序遍历序列构造二叉树

递归，前序序列的第一个为根节点，找到中序遍历中根节点的位置，左边是左子树中序，右边是右子树中序；
返回前序，根节点后依次为左子树前序和右子树前序。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> pos;

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pl, int pr, int il, int ir)
    {
        if(pl > pr) return nullptr;
        TreeNode* root = new TreeNode(preorder[pl]);
        int k = pos[preorder[pl]];
        root->left = build(preorder, inorder, pl+1, pl+k-il, il, k-1);
        root->right = build(preorder, inorder, pl+1+k-il, pr, k+1, ir);
        return root;
    } 

    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int len = inorder.size();
        for(int i = 0; i < len; i ++) pos[inorder[i]] = i;
        return build(preorder, inorder, 0, len-1, 0, len-1);
    }

};

10 图与搜索

DFS

695. 岛屿的最大面积

class Solution {
public:
    int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int max_area = 0;
        for(int i = 0; i < grid.size(); i ++)
        {
            for(int j = 0; j < grid[0].size(); j ++)
            {
                if(grid[i][j] == 1)
                {
                    max_area = max(max_area, dfs(grid, i, j));
                }
            }
        }
        return max_area;
    }

    int dfs(vector<vector<int>>& grid, int x, int y)
    {
        int area  = 1;
        grid[x][y] = 0;
        for(int k = 0; k < 4; k ++)
        {
            int nx = x + dx[k], ny = y + dy[k];
            if(nx >= 0 && nx < grid.size() && ny >= 0 && ny < grid[0].size() && grid[nx][ny] == 1)
            {
                area += dfs(grid, nx, ny);
            }
        }
        return area;
    }
};

200. 岛屿数量

flood fill算法

for(   i   )
    for(   j   )
        if(i,j)是未遍历的1
            则遍历(i,j)
            cnt ++;

class Solution {

public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0,-1, 0, 1};
    vector<vector<char>> g;//全局变量g = grid
    int numIslands(vector<vector<char>>& grid) {
        g = grid;
        int cnt = 0;
        for(int i = 0; i < grid.size(); i ++)
        {
            for(int j = 0; j < grid[0].size(); j ++)
            {
                if(g[i][j] == '1')
                {
                    dfs(i, j);//将1组成的连通块置为0
                    cnt ++;
                }
            }
        }
        return cnt;
    }

    void dfs(int x, int y)
    {
        g[x][y] = 0;//dfs遍历后,g[x][y]由1置为0

        for(int i = 0; i < 4; i ++)
        {
            int nx = x + dx[i], ny = y + dy[i];
            if(nx >= 0 && nx < g.size() && ny >= 0 && ny < g[0].size() && g[nx][ny] == '1')
            {
                dfs(nx, ny);
            }
        }
    }
};

694. 不同岛屿的数量

题目描述：
给定一个非空 01 二维数组表示的网格，一个岛屿由四连通（上、下、左、右四个方向）的 1 组成，你可以认为网格的四周被海水包围。
请你计算这个网格中共有多少个形状不同的岛屿。两个岛屿被认为是相同的，当且仅当一个岛屿可以通过平移变换（不可以旋转、翻转）和另一个岛屿重合。
提示：二维数组每维的大小都不会超过 50 。

示例 1：
11000
11000
00011
00011
给定上图，返回结果 1 。

示例 2：
11011
10000
00001
11011
给定上图，返回结果 3 。

注意：
11
1
和
 1
11
是不同的岛屿，因为我们不考虑旋转、翻转操作。

题解

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void dfs(vector<vector<int>>& g, int x, int y, int i, int j, vector<pair<int, int>>& path)
{//连通块左上角为[x][y],当前点[i][j]
    g[i][j] = 0;
    path.push_back({i - x, j - y});
    for(int k = 0; k < 4; k ++)
    {
        int ni = i + dx[k], nj = j + dy[k];
        if(ni >= 0 && ni < g.size() && nj >= 0 && nj < g[ni].size() && g[ni][nj] == 1)
            dfs(g, x, y, ni, nj, path);
    }
}

int numDistinctIslands(vector<vector<int>>& grid) {
    vector<vector<pair<int, int>>> paths;

    for(int i = 0; i < grid.size(); i ++)
    {
        for(int j = 0; j < grid[i].size(); j ++)
        {
            if(grid[i][j] == 1)
            {
                vector<pair<int, int>> path;
                dfs(grid, i, j, i, j, path);
                paths.push_back(path);
            }
        }
    }

    sort(paths.begin(), paths.end());
    int cnt = unique(paths.begin(), paths.end()) - paths.begin();
    return cnt;
}


int main()
{
    vector<vector<int>> grid = {{1,1,0,0,0}, {1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
    cout << numDistinctIslands(grid);
}

//优化，用set存path，利用set有序不重复的特点
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;

int dx[4] = {0, 1, 0, -1}, dy[4] = {1, 0, -1, 0};

void dfs(vector<vector<int>>& g, int x, int y, int i, int j, vector<pair<int, int>>& path)
{//连通块左上角为[x][y],当前点[i][j]
    g[i][j] = 0;
    path.push_back({i - x, j - y});
    for(int k = 0; k < 4; k ++)
    {
        int ni = i + dx[k], nj = j + dy[k];
        if(ni >= 0 && ni < g.size() && nj >= 0 && nj < g[ni].size() && g[ni][nj] == 1)
            dfs(g, x, y, ni, nj, path);
    }
}

int numDistinctIslands(vector<vector<int>>& grid) {
    set<vector<pair<int, int>>> s;

    for(int i = 0; i < grid.size(); i ++)
    {
        for(int j = 0; j < grid[i].size(); j ++)
        {
            if(grid[i][j] == 1)
            {
                vector<pair<int, int>> path;
                dfs(grid, i, j, i, j, path);
                s.insert(path);
            }
        }
    }

    return s.size();
}


int main()
{
    vector<vector<int>> grid = {{1,1,0,0,0}, {1,1,0,0,0},{0,0,0,1,1},{0,0,0,1,1}};
    cout << numDistinctIslands(grid);
}

11 二分查找

6096. 咒语和药水的成功对数

class Solution {

public:
    vector<int> successfulPairs(vector<int>& spells, vector<int>& potions, long long success) {
        int n = spells.size(), m = potions.size();
        vector<int> pairs(n, 0);
        //排序
        sort(potions.begin(), potions.end());

        for(int i = 0; i < n; i ++) {
            long long a = ((success - 1) / spells[i]) + 1; //向上取整

            //二分
            // //lower_bound
            // auto it = lower_bound(potions.begin(), potions.end(), a);
            // pairs[i] = potions.end() - it;

            //手写二分找到potions中第一个大于等于a的数
            int l = 0, r = m - 1;

            while(l < r) {
                int mid = l + r >> 1;
                if(potions[mid] >= a) r = mid;
                else l = mid + 1;
            }

            //特例：
            //1）如果potions的最后一个数都不满足大于等于a
            //即找不到potions中第一个大于等于a的数
            //2）potions中第一个大于等于a的数是最后一个数
            //两种情况l都是m-1，用条件语句区分
            if (potions[l] >= a) pairs[i] = m - l;            
        }

        return pairs;
    }
};

二分查找与旋转数组

33. 搜索旋转排序数组

1. 根据nums[0]二分,找到边界1

2. 找到在哪一段，再次二分找到target

   class Solution {
   public:
    int search(vector<int>& nums, int target) {
        if(nums.empty()) return -1;
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = (l + r + 1) >> 1;
            if(nums[mid] >= nums[0]) l = mid;
            else r = mid - 1;
        }
        //此时l = r = 边界1
        cout << l << endl;
        cout << r << endl;
        if(target >= nums[0]) l = 0;
        else l = l + 1, r = nums.size() - 1;
        cout << l << endl;
        cout << r << endl;
   
        while(l < r)
        {
            int mid = (l + r) >> 1;
            if(nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
   
        if(nums[r] == target) return r;
        else return -1;
        //如果是nums = [1],target = 0情况，
        //边界一l = r = 0
        //target <= nums[0],边界为l = l+1 = 1越界，r = nums.size()-1=0
        //l>r不进入第二次二分，由于l越界，比较nums[r]和target
    }
   };
   

   13 动态规划

   数组中的动态规划

   53. 最大子数组和

   题解

• 状态表示：一维f[i]
  • 集合：最后一位为i的最大子数组和
  • 属性：最大子数组和

• 状态计算f[i] | f[i - 1]+nums[i] | nums[i] | | —- | —- |

• 时间复杂度 O(n) ；空间复杂度O（1）

  class Solution {
  public:
    int maxSubArray(vector<int>& nums) {
        int res = INT_MIN;
        for(int i = 0, last = 0; i < nums.size(); i ++)
        {
            last = max(last, 0) + nums[i];
            //写成max(nums[i], nums[i] + last)，当max(INT_MIN, 负数)时会溢出
            res = max(res, last);
        }
        return res;
    }
  };
  

  树形dp

  124. 二叉树中的最大路径和

  ```cpp class Solution { public: int maxPathSum(TreeNode* root) {

    ret = INT_MIN;
    dfs(root);
    return ret;
  

  }

private: int ret; int dfs(TreeNode* root) { if (root == nullptr) { return 0; } int left = max(0, dfs(root->left)); int right = max(0, dfs(root->right)); ret = max(ret, left + right + root->val); return root->val + max(left, right); } };

<a name="M5DWR"></a>
## 待整理
<a name="KUaqr"></a>
#### [1143. 最长公共子序列](https://leetcode-cn.com/problems/longest-common-subsequence/)
状态表示:f[i][j]<br />集合：s1前i个字符串，s2前j个字符串的公共子序列<br />属性：max<br />状态计算：f[i][j]

| s1[i] | s2[j] | <br /> |
| --- | --- | --- |
| 0 | 0 | <br /> |
| 1 | 0 | <br /> |
| 0 | 1 | <br /> |
| 1 | 1 | <br /> |

<a name="cDJPH"></a>
#### [63. 不同路径 II](https://leetcode-cn.com/problems/unique-paths-ii/)
时间复杂度O(mn)，空间复杂度O(mn)
```cpp
class Solution {
public:
    int uniquePathsWithObstacles(vector<vector<int>>& o) {
        int n = o.size();//n行
        if(!n) return 0;//0行时，网格为空，返回0条路径
        int m = o[0].size();//m列
        vector<vector<int>> f(n, vector<int>(m));//f[i][j]存储到[i][j]的路径数

        for(int i = 0; i < n; i ++)
            for(int j = 0; j < m; j ++)
                if(!o[i][j])//[i][j]没有障碍物
                {
                    //设f[0][0] = 1
                    if(!i && !j) f[i][j] = 1;
                    else 
                    {
                        //行数大于0，可从[i-1][j]到[i][j]
                        if(i) f[i][j] += f[i - 1][j];
                        //列数大于0，可从[i][j-1]到[i][j]
                        if(j) f[i][j] += f[i][j - 1];
                    }
                }

        return f[n - 1] [m - 1];
    }
};

1262. 可被三整除的最大和

题解

• 状态表示：f[i][j]
  • 集合：nums[0,…,i]中模3余j（j = 0，1，2）的sum
  • 属性：sum MAX
• 状态计算f[i][j]

f[i][0]

f[i][1]

f[i][2]

• 时间复杂度 = 状态数量（O(n))*每个状态转移时间（O(1)） = O(n)

  class Solution {
  public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> f(n+1, vector<int>(3, 0));
        f[0][1] = INT_MIN, f[0][2] = INT_MIN;
        for(int i = 1; i <= n; i ++) 
        {
            if(nums[i - 1] % 3 == 0)
            {
                f[i][0] = max(f[i - 1][0], f[i - 1][0] + nums[i - 1]);
                f[i][1] = max(f[i - 1][1], f[i - 1][1] + nums[i - 1]);
                f[i][2] = max(f[i - 1][2], f[i - 1][2] + nums[i - 1]);                
            }
            if(nums[i - 1] % 3 == 1)
            {
                f[i][0] = max(f[i - 1][0], f[i - 1][2] + nums[i - 1]);
                f[i][1] = max(f[i - 1][1], f[i - 1][0] + nums[i - 1]);
                f[i][2] = max(f[i - 1][2], f[i - 1][1] + nums[i - 1]);                
            }  
            if(nums[i - 1] % 3 == 2)
            {
                f[i][0] = max(f[i - 1][0], f[i - 1][1] + nums[i - 1]);
                f[i][1] = max(f[i - 1][1], f[i - 1][2] + nums[i - 1]);
                f[i][2] = max(f[i - 1][2], f[i - 1][0] + nums[i - 1]);                
            }         
        }
        return f[n][0];
    }
  };
  

• 状态表示：f[j]

  • 集合：nums[0,…,i]中模3余j（j = 0，1，2）的sum
  • 属性：sum MAX
• 状态计算f[j]

  class Solution {
  public:
    int maxSumDivThree(vector<int>& nums) {
        int n = nums.size();
        int f[3] = {0};
        for(int i = 0; i < n; i ++) 
        {
            int a = f[0] + nums[i];
            int b = f[1] + nums[i];
            int c = f[2] + nums[i];
            f[a % 3] = max(f[a % 3], a);
            f[b % 3] = max(f[b % 3], b);
            f[c % 3] = max(f[c % 3], c);
        }
        return f[0];
    }
  };
  

14 数据结构

1188. 设计有限阻塞队列

实现一个拥有如下方法的线程安全有限阻塞队列：
BoundedBlockingQueue(int capacity) 构造方法初始化队列，其中capacity代表队列长度上限。
void enqueue(int element)在队首增加一个element. 如果队列满，调用线程被阻塞直到队列非满。
int dequeue()返回队尾元素并从队列中将其删除. 如果队列为空，调用线程被阻塞直到队列非空。
int size()返回当前队列元素个数。
你的实现将会被多线程同时访问进行测试。每一个线程要么是一个只调用enqueue方法的生产者线程，要么是一个只调用dequeue方法的消费者线程。size方法将会在每一个测试用例之后进行调用。

请不要使用内置的有限阻塞队列实现，否则面试将不会通过。

输入:
1
1
["BoundedBlockingQueue","enqueue","dequeue","dequeue","enqueue","enqueue","enqueue","enqueue","dequeue"]
[[2],[1],[],[],[0],[2],[3],[4],[]]

输出:
[1,0,2,2]

解释:
生产者线程数目 = 1
消费者线程数目 = 1

BoundedBlockingQueue queue = new BoundedBlockingQueue(2);   // 使用capacity = 2初始化队列。

queue.enqueue(1);   // 生产者线程将 1 插入队列。
queue.dequeue();    // 消费者线程调用 dequeue 并返回 1 。
queue.dequeue();    // 由于队列为空，消费者线程被阻塞。
queue.enqueue(0);   // 生产者线程将 0 插入队列。消费者线程被解除阻塞同时将 0 弹出队列并返回。
queue.enqueue(2);   // 生产者线程将 2 插入队列。
queue.enqueue(3);   // 生产者线程将 3 插入队列。
queue.enqueue(4);   // 生产者线程由于队列长度已达到上限 2 而被阻塞。
queue.dequeue();    // 消费者线程将 2 从队列弹出并返回。生产者线程解除阻塞同时将4插入队列。
queue.size();       // 队列中还有 2 个元素。size()方法在每组测试用例最后调用。

输入:
3
4
["BoundedBlockingQueue","enqueue","enqueue","enqueue","dequeue","dequeue","dequeue","enqueue"]
[[3],[1],[0],[2],[],[],[],[3]]

输出:
[1,0,2,1]

解释:
生产者线程数目 = 3
消费者线程数目 = 4

BoundedBlockingQueue queue = new BoundedBlockingQueue(3);   // 使用capacity = 3初始化队列。

queue.enqueue(1);   // 生产者线程 P1 将 1 插入队列。
queue.enqueue(0);   // 生产者线程 P2 将 0 插入队列。
queue.enqueue(2);   // 生产者线程 P3 将2插入队列。
queue.dequeue();    // 消费者线程 C1 调用 dequeue。
queue.dequeue();    // 消费者线程 C2 调用 dequeue。
queue.dequeue();    // 消费者线程 C3 调用 dequeue。
queue.enqueue(3);   // 其中一个生产者线程将3插入队列。
queue.size();       // 队列中还有 1 个元素。

由于生产者/消费者线程的数目可能大于 1 ，我们并不知道线程如何被操作系统调度，即使输入看上去隐含了顺序。因此任意一种输出[1,0,2]或[1,2,0]或[0,1,2]或[0,2,1]或[2,0,1]或[2,1,0]都可被接受。

1 <= Number of Prdoucers <= 8
1 <= Number of Consumers <= 8
1 <= size <= 30
0 <= element <= 20
enqueue的调用次数 大于等于  dequeue 的调用次数。
enque, deque 和 size 最多被调用 40 次

//synchronized
class BoundedBlockingQueue {

    private int capacity;
    private Queue<Integer> queue;
    private Object lock = new Object();

    public BoundedBlockingQueue(int capacity) {
        this.capacity = capacity;
        queue = new LinkedList<>();
    }

    public void enqueue(int element) throws InterruptedException {
        synchronized (lock) {
            while (queue.size() > capacity) {
                lock.wait();
            }
            queue.add(element);
            lock.notify();
        }
    }

    public int dequeue() throws InterruptedException {
        int result;
        synchronized (lock) {
        while (queue.size() == 0) {
            lock.wait();
        }
        result = queue.poll();
        lock.notify();
        }
        return result;
    }

    public int size() {
        synchronized (lock) {
            return queue.size();
        }
    }
}

//ReentrantLock
class BoundedBlockingQueue {
    private ReentrantLock lock = new ReentrantLock();
    private Condition full = lock.newCondition();
    private Condition empty = lock.newCondition();
    private int[] queue;

    private int tail = 0;
    private int head = 0;
    private int size = 0;

    public BoundedBlockingQueue(int capacity) {
        queue = new int[capacity];
    }

    public void enqueue(int element) throws InterruptedException {
        lock.lock();
        try{

            while(size == queue.length){
                full.await();
            }

            queue[tail ++] = element;
            tail %= queue.length;
            size ++;
            empty.signal();

        }finally{
            lock.unlock();
        }
    }

    public int dequeue() throws InterruptedException {
        lock.lock();
        try{

            while(size == 0){
                empty.await();
            }

            int res = queue[head ++];
            head %= queue.length;
            size --;
            full.signal();
            return res;

        }finally{
            lock.unlock();
        }
    }

    public int size() {
        lock.lock();
        try{
            return this.size;
        }finally{
            lock.unlock();
        }
    }
}

待整理

82 23 200 694

二叉树

297. 二叉树的序列化与反序列化

1. 层序遍历 ```cpp

   include

   include

   include

   include

   include

   using namespace std;

struct TreeNode { int val; TreeNode left; TreeNode right; TreeNode() : val(0), left(nullptr), right(nullptr) {} TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} TreeNode(int x, TreeNode left, TreeNode right) : val(x), left(left), right(right) {} };

//层序数组构建二叉树 // https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/solution/zha-zha-fa-xian-de-wen-ti-xi-wang-geng-duo-ren-kan/

TreeNode deserialize(string data) { if(data.size() == 0) return NULL; int len = data.size(); int i = 0; vector<TreeNode> vec;//存储节点到数组中 while(i < len) { string str = “”; //将当前逗号之间的字符串存入str while(i < len && data[i] != ‘,’) { str.push_back(data[i]); i ++; }

    if(str == "null")
    {
        TreeNode* temp = NULL;
        vec.push_back(temp);
    }
    else//str为数字字符串
    {
        int temp = stoi(str);
        TreeNode* cur = new TreeNode(temp);
        vec.push_back(cur);
    }
    i ++;
}

//层序i从0开始，父节点i,左子节点2i+1，右子节点2i+2
int j = 1;
for(int i = 0; j < vec.size(); i ++)
{
    if(vec[i] == NULL) continue;
    if(j < vec.size()) vec[i] ->left = vec[j++];
    if(j < vec.size()) vec[i] ->right = vec[j++];
}
return vec[0];

}

//序列化二叉树 bfs 队列 string serialize(TreeNode root) { string res = “”;//存结果字符串 //构造队列，并插入非空根节点 queue<TreeNode > q; if (root) q.push(root); else return “”; //队列非空时循环 while (q.size()) { //队列长度 int len = q.size(); while (len—) { auto cur = q.front(); q.pop(); if (cur) res.append(to_string(cur->val)); else res.append(“null”); res.push_back(‘,’); if (cur) { q.push(cur->left); q.push(cur->right); } } }

res.pop_back();//删去末尾逗号
while(!isdigit(res.back())) res.pop_back();//删去末尾的null，isdigit()判断是不是数字
return res;

}

int main() { //输入string转为树 string data; getline(cin, data); TreeNode *t = deserialize(data); //层序遍历树转换为string string s = serialize(t); cout << s; }

<a name="rMYVf"></a>
#### [102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)
BFS
```cpp
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        queue<TreeNode*> q;
        vector<vector<int>> res;
        if(root != nullptr) q.push(root);

        while(!q.empty())
        {
            vector<int> vec;
            int size = q.size();
            for(int i = 0; i < size; ++ i)
            {
                TreeNode* node = q.front();
                q.pop();
                if(node->left) q.push(node->left);
                if(node->right) q.push(node->right);
                vec.push_back(node->val);
            }

            res.push_back(vec);
        }

        return res;
    }
};

DFS

排序

912. 排序数组

• 快速排序

时间复杂度O(nlogn)
空间复杂度O(h)，其中 h 为递归调用的层数，最坏情况下需 O(n)的空间，最优情况下每次都平衡，此时整个递归树高度logn，空间复杂度为 O(logn)。

class Solution {
void quick_sort(vector<int>& nums, int l, int r)
{
    if(l >= r) return;
    int i = l - 1, j = r + 1, x = nums[(l + r) >> 1];
    while(i < j)
    {
        do i ++; while(nums[i] < x);
        do j --; while(nums[j] > x);
        if(i < j) swap(nums[i] ,nums[j]);
    }
    quick_sort(nums, l, j);
    quick_sort(nums, j + 1, r);
}

public:
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

• 归并排序

时间复杂度：O(nlogn)
空间复杂度：递归栈logn，tmp数组最大为n，所需的空间复杂度即为O(n+logn)=O(n)。

class Solution {
vector<int> tmp;
void merge_sort(vector<int>& nums, int l, int r)
    {
        if(l >= r) return;
        int mid = (l + r) >> 1;
        merge_sort(nums, l, mid);
        merge_sort(nums, mid + 1, r);

        int i = l, j = mid + 1, k = 0;

        while(i <= mid && j <= r)
        {
            if(nums[i] <= nums[j]) tmp[k ++] = nums[i ++];
            else tmp[k ++] = nums[j ++];
        }

        while(i <= mid) tmp[k ++] = nums[i ++];
        while(j <= r) tmp[k ++] = nums[j ++];

        for(int i = l, k = 0; i <= r; i ++, k ++) nums[i] = tmp[k];
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size(), 0);//需要明确数组大小，才能利用索引找到数组中对应的数，使用nums[i]
        merge_sort(nums, 0, nums.size() - 1);
        return nums;
    }
};

• 堆排序

时间复杂度：O(nlogn)。
初始化建堆的时间复杂度为 O(n);
建完堆以后需要进行 n-1次调整，一次调整（即 down） 的时间复杂度为O(logn)，堆的大小也在不断减小，具体时间复杂度应为(log(n!))=O(nlogn)。
因此，总时间复杂度为O(n+nlogn)=O(nlogn)。
空间复杂度：O(1)。只需要常数的空间存放若干变量。

class Solution {
//建堆，大根堆
void buildMaxHeap(vector<int>& nums, int heapSize)
{
    for(int i = heapSize/2 - 1; i >= 0; i --)
        down(nums, heapSize, i);
}

void down(vector<int>& nums, int heapSize, int u)
{
    int t = u;//存子父节点中更大的节点的索引

    if(2*u+2 < heapSize && nums[2*u+2] > nums[t]) t = 2*u+2;
    if(2*u+1 < heapSize && nums[2*u+1] > nums[t]) t = 2*u+1;


    if(t != u)
    {
        swap(nums[t], nums[u]);
        down(nums, heapSize, t);
    }
}

void heap_sort(vector<int> &nums, int heapSize)
{
    buildMaxHeap(nums, heapSize);
    int cnt = heapSize;
    //反转得到从小到大顺序
    //1.将当前大根堆堆顶与堆的最后一个数交换
    //2.堆的大小减1，对现在的堆顶堆化
    for(int i = heapSize - 1; i > 0; i --)
    {
        swap(nums[0], nums[i]);
        cnt --;
        down(nums, cnt, 0);
    }
}

public:
    vector<int> sortArray(vector<int>& nums) {
        heap_sort(nums, nums.size());
        return nums;
    }
};

215. 数组中的第K个最大元素

• 快速排序 题解
  • 思路

随机选择nums中的一个数x，以x为边界, 数组整理为[left, j] < x, [i, right] > x，j表示当前x为第j小的数;
划分区间递归：如果K < j，在区间[left, j里递归；如果K > j，在区间[i, right]里递归，返回K==j时的nums[K]

• 时间空间复杂度

//快速排序
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int len = nums.size();
        int target = len - k;//第k个最大=第len-k个最小
        return partition(nums, 0, len - 1, target);

    }

    //随机选择nums中的一个数x;
    //以x为边界, 数组整理为[left, j] < x, [j + 1, right] > x
    //返回j表示当前x为第j小的数;
    int partition(vector<int>& nums, int left, int right, int tar)
    {
        // cout << "left=" <<left << " right="<<right<<endl;
        int i = left - 1, j = right + 1;
        //从最中间的点开始，不从[left,right]两头开始，避免快速排序的最坏情况(顺序或逆序)
        int x = nums[(left + right) >> 1];
        // cout << "x = " << x << endl;
        while(i <= j)
        {
            do i ++; while(i <= j && nums[i] < x);
            do j --; while(i <= j && nums[j] > x);
            if(i <= j) swap(nums[i], nums[j]); 
            // cout << "i=" << i << "  j="<<j<<endl;
            // for(int num : nums) cout << num << " ";
            // cout <<endl;
        }

        //一次整理之后，[left，j], x,[i, right]
        if(tar <= j) return partition(nums, left, j, tar);
        if(tar >= i) return partition(nums, i, right, tar);
        //如果tar最后刚好在j和i之间
        return nums[tar];
    }
};

• 样例：

输入：[5,2,4,1,3,6,0] 4 输出：3
tar = 3
left=0 right=6
x = 1
i=0 j=6
0 2 4 1 3 6 5
i=1 j=3
0 1 4 2 3 6 5
i=2 j=1
0 1 4 2 3 6 5
left=2 right=6
x = 3
i=2 j=4
0 1 3 2 4 6 5
i=4 j=3
0 1 3 2 4 6 5 判断tar和j的关系需要用 ≤和≥，需要等号进入下一层递归
left=2 right=3
x = 3
i=2 j=3
0 1 2 3 4 6 5
i=3 j=2
0 1 2 3 4 6 5
left=3 right=3
x = 3
i=3 j=3 while(i <= j)需要等号，再增加一轮循环
0 1 2 3 4 6 5
i=4 j=2 tar最后刚好在j和i之间
0 1 2 3 4 6 5

• 手写堆排序 题解 题解1

  • 思路

  维护有K个元素的小根堆：
  （1）如果当前堆不满，直接添加；
  （2）堆满的时候，如果新读到的数小于等于堆顶，肯定不是我们要找的元素，只有新遍历到的数大于堆顶的时候，才将堆顶拿出，然后放入新读到的数，进而让堆自己去调整内部结构。

  • 时间复杂度：O(NlogK)，遍历数据 O(N)，堆内元素调整O(logK)；

空间复杂度：O(K)。

//使用STL中的优先队列
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int, vector<int>, greater<int>> minheap;
        for(int i = 0; i < nums.size(); i ++)
        {
            if(minheap.size() < k) minheap.push(nums[i]);
            else if(minheap.top() < nums[i])
            {
                minheap.pop();
                minheap.push(nums[i]);
            }
        }

        return minheap.top();
    }
};

//手写堆
class Solution {
public:
    //建堆，从最后一个非叶子节点开始down，其下标为节点数n/2 - 1
    void bulidMinHeap(vector<int>& nums, int heapSize)
    {
        for(int i = heapSize / 2 - 1; i >= 0; i --) 
            down(nums, heapSize, i);
    }

    //down递归
    void down(vector<int>& nums, int heapSize, int u)
        {
            int t = u;
            //堆顶从0开始，若父节点为u，左右子节点为u * 2 + 1，u * 2 + 2
            if(u * 2 + 1 < heapSize && nums[u * 2 + 1] < nums[t]) t = u * 2 + 1;
            if(u * 2 + 2 < heapSize && nums[u * 2 + 2] < nums[t]) t = u * 2 + 2;
            if(u != t)
            {
                swap(nums[u] ,nums[t]);
                down(nums, heapSize, t);
            }
        }

    int findKthLargest(vector<int>& nums, int k) {
        //将nums的前k个数建堆，小根堆，大小为k
        bulidMinHeap(nums, k);
        //遍历nums中余下的数
        for(int i = k; i < nums.size(); i ++)
        {
            //如果比最小值（堆顶）大
            if(nums[0] < nums[i]) 
            {
                //删除最小值（堆顶）并把nums[i]插入堆顶
                nums[0] = nums[i];
                down(nums, k, 0);
            }
        }
        return nums[0];//遍历结束，返回堆顶，即为第K大的数
    }

};

21. 合并两个有序链表

归并

• 迭代法题解

时间复杂度：O(n + m)，其中 n和 m分别为两个链表的长度。因为每次循环迭代中，l1 和 l2 只有一个元素会被放进合并链表中， 因此 while 循环的次数不会超过两个链表的长度之和。所有其他操作的时间复杂度都是常数级别的，因此总的时间复杂度为 O(n+m)。
空间复杂度：O(1)。我们只需要常数的空间存放若干变量。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummyhead = new ListNode();
        ListNode* pre = dummyhead;

        while(list1 != nullptr && list2 != nullptr)
        {
            if(list1->val <= list2->val)
            {
                pre->next = list1;
                list1 = list1->next;
            }
            else
            {
                pre->next = list2;
                list2 = list2->next;                
            }
            pre = pre->next;
        }
        if(list1 != nullptr) pre->next = list1;
        if(list2 != nullptr) pre->next = list2;
        return dummyhead->next;
    }
};

• 递归法题解

时间复杂度：O(n + m)，递归函数每次去掉一个元素，直到两个链表都为空O(n + m)；递归函数只有赋值next指针操作O(1)
空间复杂度：O(n+m),递归栈

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr) return list2;
        if(list2 == nullptr) return list1;

        if(list1->val <= list2->val) 
        {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        }

        list2->next = mergeTwoLists(list1, list2->next);
        return list2;
    }
};

链表

234. 回文链表

题解
1.链表值复制到指针中后用双指针
时间复杂度O（n）
空间复杂度O（n）

bool solution(ListNode* head)
{
    vector<int> val;
    while(head)
    {
        val.push_back(head->val);
        head = head->next;
    }

    for(int i = 0, j = val.size() - 1; i < j; ++i, --j)
    {
        if(val[i] != val[j]) return false;
    }
    return true;
}

2.反转链表

1. 找到前半部分链表的尾节点。
2. 反转后半部分链表。
3. 判断是否回文。
4. 恢复链表。
5. 返回结果。

时间复杂度O（n）
空间复杂度O（1）

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

3.双向链表（还没看）

#include <iostream>
using namespace std;
struct ListNode
{
    int val;
    ListNode* prev;
    ListNode* next;
    ListNode() : val(0), prev(nullptr), next(nullptr) {};
    ListNode(int num) : val(num), prev(nullptr), next(nullptr) {};
    ListNode(int num, ListNode* p1, ListNode* p2) : val(num), prev(p1), next(p2) {};
};

ListNode* head, * tail;

void add2tail(ListNode* node)
{
    node->prev = tail->prev;
    node->next = tail;
    node->prev->next = node;
    tail->prev = node;
}

int main()
{
    head = new ListNode(), tail = new ListNode();
    head->next = tail;
    tail->prev = head;
    int num;
    cout << "Please input number or press Ctrl + D: " << endl;
    while (cin >> num)
    {
        ListNode* ptr = new ListNode(num);
        add2tail(ptr);
        cout << "Please input number or press Ctrl + D: " << endl;
    }
    cout << "The result is: ";
    ListNode* ptr1 = head, * ptr2 = tail;
    bool flag = true;
    while (ptr1 != ptr2 && ptr2->next != ptr1)
    {
        if (ptr1->val == ptr2->val)
        {
            ptr1 = ptr1->next;
            ptr2 = ptr2->prev;
        }
        else
        {
            flag = false;
            break;
        }
    }
    if (flag)    cout << "True" << endl;
    else
    {
        cout << "False" << endl;
    }
    return 0;

}

83. 删除排序链表中的重复元素

• 一次遍历

  class Solution {
  public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head) return head;
  
        ListNode* cur = head;
        while(cur->next)
        {
            if(cur->val == cur->next->val)
                cur->next = cur->next->next;
            else cur = cur->next;
        }
  
        return head;
    }
  };
  

• 双指针

  class Solution {
  public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(!head || !head->next) return head;
  
        ListNode*  fast = head;
        ListNode* slow = head;
        while(fast)
        {
            //fast指针找到第一个与slow指针不同的元素
            if(fast->val != slow->val)
            {
                slow->next = fast;
                slow = fast;
            }
            else fast = fast->next;
        }
        //若最后几个元素是重复的，slow指向null
        slow->next = nullptr;
        return head;
    }
  };
  

  206. 反转链表

  题解

• 迭代

遍历当前节点pNode，预先保存链表顺序中的后一个节点pNext，让pNode指向链表顺序中的前一个节点pPrev，再让pNext指向pNode

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* reversehead = nullptr;
        ListNode* pPrev = nullptr;

        ListNode* pNode = head;
        while(pNode != nullptr)//遍历单链表
        {
            ListNode *pNext = pNode->next;
            if(pNext == nullptr) reversehead = pNode;//反转链表的头节点

            //第一次循环，链表的第一个节点为反转链表的最后一个节点，链表的尾节点为nullptr，故pPrev初始化为nullptr
            pNode->next = pPrev;

            //pPrev,pNode按照链表顺序向后移一位
            pPrev = pNode;
            pNode = pNext;
        }

        return reversehead;
    }
};

• 递归

  class Solution {
  public:
    ListNode* reverseList(ListNode* head) {
        //1.head == nullptr,链表为空的情况
        //2.head->next == nullptr,递归的终止条件,返回链表的尾节点
        if(head == nullptr || head->next == nullptr)
            return head;
  
        ListNode* reversehead = reverseList(head->next);
        //当前递归层head->next节点之后的节点已反转，只需使head->next->next指向head
        head->next->next = head;
        head->next = nullptr;
  
        return reversehead;
    }
  };
  

  92. 反转链表 II

  题解

  /**
  * Definition for singly-linked list.
  * struct ListNode {
  *     int val;
  *     ListNode *next;
  *     ListNode() : val(0), next(nullptr) {}
  *     ListNode(int x) : val(x), next(nullptr) {}
  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  * };
  */
  class Solution {
  public:
    ListNode* reverseBetween(ListNode* head, int left, int right) {
        //在head前头插一个虚拟头节点dummyhead
        //为了避开head是否会反转的分类问题，最后返回dummyhead->next
        ListNode* dummyhead = new ListNode();
        dummyhead->next = head;
  
        //初始化指针g和p
        ListNode* g = dummyhead;
        ListNode* p = dummyhead->next;
        //将g移动到第一个要反转的节点left的前面，将p移动到left的位置上
        for(int i = 0; i < left - 1; i ++)
        {
            g = g->next;
            p = p->next;
        }
        //头插法反转,将p之后的right - left个节点依次插到g之后
        for(int i = 0; i < right - left; i ++)
        {
            ListNode* moved = p->next;
            p->next = p->next->next;
            moved->next = g->next;
            g->next = moved;
        }
        return dummyhead->next;
    }
  };
  

  25. K 个一组翻转链表

• 尾插法 题解

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* dummyhead = new ListNode();
        dummyhead->next = head;

        ListNode* pre = dummyhead;
        ListNode* end = dummyhead;

        if(head == nullptr || head->next == nullptr) return head;

        while(end != nullptr)
        {
            for(int i = 0; i < k && end != nullptr; i ++) 
                end = end->next;

            if(end == nullptr) break;

            ListNode* start = pre->next;
            ListNode* next = end->next;
            end->next = nullptr;
            pre->next = reverseList(start);
            start->next = next;
            pre = start;
            end = start;
        }

        return dummyhead->next;
    }

    //反转链表
    //遍历当前节点pNode，预先保存链表顺序中的后一个节点pNext，让pNode指向链表顺序中的前一个节点pPrev，再让pNext指向pNode
    //返回反转后的链表头节点pPre
    ListNode* reverseList(ListNode* head)
    {
        ListNode* pNode = head;
        ListNode* pPre = nullptr;
        while(pNode != nullptr)
        {
            ListNode* pNext = pNode->next;
            pNode->next = pPre;
            pPre = pNode;
            pNode = pNext;

        }
        return pPre;
    }
};

• 递归 题解

  class Solution {
  public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* cur = head;
        int count = 0;
        while(cur && count < k)
        {
            count ++;
            cur = cur->next;
        }
  
        if(count == k)
        {
            cur = reverseKGroup(cur, k);//递归返回后一层已反转链表的头节点
            while(count)
            {
                count --;
                ListNode* tmp = head->next;
                head->next = cur;
                cur = head;
                head = tmp;
            }
            head = cur;//当前递归层中反转后，头节点应为原head节点移动count-1次，即为cur
        }
        return head;
    }
  };
  

• 栈 题解

  class Solution {
  public:
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* preHead = new ListNode(-1); // fake head
        preHead->next = head;
        int cnt = 0; // cnt counts to k
        stack<ListNode *> stemp;
        ListNode* p = head; // p is the pointer iterating through the whole linked list
        ListNode* preLog = preHead; //preLog deals with the linkage with the last part
        ListNode* preLogNext = preHead->next; //preLogNext deals with the linkage with the next part
        while(p != NULL){ //loop through the linked list, only once, so the time complexity is O(n)
            stemp.push(p);
            cnt++;
            if(cnt == k){   //using the maximum space of stack of size k
                ListNode* first = stemp.top();
                preLogNext = first->next; //record the linkage to the next part
                stemp.pop();
                ListNode* now = first;
                while(!stemp.empty()){
                    ListNode* top1 = stemp.top();
                    now->next = top1;
                    now = now->next;
                    stemp.pop();
                }
                preLog->next = first; //link to the last part
                preLog = now; // reset the preLog to the last node in the k nodes group
                preLog->next = preLogNext; //link to the next part
                cnt =0;
                p = now; // it's important to set p to the right position of reversed k nodes group
            }
            p = p->next;
        }
  
        return preHead->next; //taking advantage of the fake head
    }
  };
  

• 拓展：不足k个也要反转

尾插法：

//27行改为            
if(end == nullptr)
{
    pre->next = reverseList(pre->next);
    break;
}

递归：

//12行改为
if(count && count <= k)

哈希表

146. LRU 缓存机制

题解

/*
    哈希表快速查找的特性
    双向链表快速添加删除节点的特性
*/
//手写双链表
struct DLinkedNode{
    int key, value;
    DLinkedNode* prev;
    DLinkedNode* next;
    DLinkedNode(): key(0), value(0), prev(nullptr), next(nullptr){}
    DLinkedNode(int _key, int _value): key(_key), value(_value), prev(nullptr), next(nullptr){}
};

class LRUCache {
private:
    unordered_map<int, DLinkedNode*> cache;//哈希链表
    int size, cap;
    DLinkedNode* head;
    DLinkedNode* tail;

public:
    LRUCache(int capacity):cap(capacity), size(0) {
        //使用伪头部和伪尾部节点
        head = new DLinkedNode();
        tail = new DLinkedNode();
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        //如果key不存在，返回-1
        if(!cache.count(key)) return -1;
        //如果key存在
        DLinkedNode* node = cache[key];//通过key在哈希表中定位，得到对应的双链表节点
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        //如果key不存在
        //1.将<key, node>添加到哈希表中
        //2.在虚拟头节点前插入新节点node
        //3.cache的size加1
        //4.判断size是否超过最大容量cap
        if(!cache.count(key))
        {
            DLinkedNode* node = new DLinkedNode(key, value);
            cache[key] = node;
            addToHead(node);
            ++ size;
            //如果超出容量
            //1.删除双向链表的尾节点(虚拟尾节点之前)
            //2.删除哈希表中对应的项
            //3.delete被删除的点，防止内存泄漏
            //4.cache的size减1
            if(size > cap){
                DLinkedNode* removed = removeTail();
                cache.erase(removed->key);
                delete removed;
                size --;
            }
        }
        //如果key存在
        //1.通过哈希表定位到双链表节点
        //2.修改value
        //3.将该节点移到头部
        else
        {
            DLinkedNode* node = cache[key];
            node->value = value;
            moveToHead(node);
        }
    }

    void moveToHead(DLinkedNode* node)//双向链表：将该节点移动到虚拟头节点后面
    {
        removeNode(node);
        addToHead(node);//在头节点插入node
    }

    void removeNode(DLinkedNode* node)//双向链表：删除node
    {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    void addToHead(DLinkedNode* node)//双向链表：在虚拟头节点后面插入node
    {
        node->prev = head;
        node->next = head->next;
        head->next->prev = node;
        head->next = node;
    }

    DLinkedNode* removeTail()//双向链表：删除的尾节点(虚拟尾节点之前)，并返回被删除的节点
    {
        DLinkedNode* node = tail->prev;
        removeNode(node);
        return node;
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */

1. 两数之和

题解
哈希表O（1）查找
hashtable(nums[x]) = x

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for(int i = 0; i < nums.size(); ++i){
            auto it = hashtable.find(target - nums[i]);
            if(it != hashtable.end()){
                return {it -> second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};