C++基础算法总结

https://leetcode.cn/problems/binary-search/

class Solution {
public:
    int search(vector& nums, int target) {
        if(nums.size() == 1) return nums[0] == target ? 0 : -1;
        int l = 0,r = nums.size() - 1,ans = -1;
        while(l <= r){
            int mid = l + (r - l) / 2;
            if(nums[mid] < target) l = mid + 1;
            if(nums[mid] == target){
                ans = mid;
                break;
            }
            if(nums[mid] > target) r = mid - 1;
        }
        return ans;
    }
};

https://leetcode.cn/problems/search-insert-position/

class Solution {
public:
    int searchInsert(vector& nums, int target) {
        int l = 0,r = nums.size() - 1,ans = -1;
        while(l <= r){
            int mid = l + ((r - l) >> 1);
            if(nums[mid] < target) l = mid + 1;
            if(nums[mid] == target){
                ans = mid;
                break;
            }
            if(nums[mid] > target) r = mid - 1;
        }
        return ans == -1 ? l : ans;
    }
};

https://leetcode.cn/problems/maximum-subarray/

class Solution {
public:
    int maxSubArray(vector& nums) {
        int n = nums.size(),res = 0;
        vector dp(n);
        res = dp[0] = nums[0];
        for(int i = 1;i < n;i++){
            dp[i] = max(dp[i-1] + nums[i], nums[i]); //与上一次最大和跟当前数值比较那个大
            res = max(res,dp[i]); //跟上一步比较那个总和最大
        }
        return res;
    }
};

https://leetcode.cn/problems/house-robber/

class Solution {
public:
    int rob(vector& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        if(n == 1) return nums[0];
        vector dp(n,0);
        dp[0] = nums[0];
        dp[1] = max(nums[0],nums[1]);
        for(int i = 2;i < n;i++) dp[i] = max(dp[i-2] + nums[i],dp[i-1]);
        return dp[n-1];
    }
};

https://leetcode.cn/problems/triangle/

class Solution {
public:
    int minimumTotal(vector>& triangle) {
        for(int i = triangle.size() - 2 ; i >= 0 ; i--){
            for(int j = 0;j < triangle[i].size();j++){
                triangle[i][j] += min(triangle[i+1][j], triangle[i+1][j+1]);
            }
        }
        return triangle[0][0];
    }
};

#include 
#include 
using namespace std;
const int N=200,n=19;
int dist[N];
int g[N][N];
void add(char x,char y,int c)
{
  int a=x-'A'+1;
  int b=y-'A'+1;
  g[a][b]=g[b][a]=c;
}
bool vis[N];
int dijkstra()
{
  memset(dist,0x3f,sizeof dist);
  dist[1]=0;
  for(int i=0;i 
双指针 
https://leetcode.cn/problems/move-zeroes/
 
class Solution {
public:
    void moveZeroes(vector& nums) {
        int l = 0,r = 0,n = nums.size();
        while(r < n){
            if(nums[r] != 0){
                int tmp = nums[r];
                nums[r] = nums[l];
                nums[l] = tmp;
                ++l;
            }
            ++r;
        }
    }
};
 
深度优先搜索 DFS 
图像渲染 
https://leetcode.cn/problems/flood-fill/
 
class Solution {
public:
    const int dx[4] = {1,0,0,-1};//下 右 左 上
    const int dy[4] = {0,1,-1,0};//下 右 左 上
    vector> floodFill(vector>& image, int sr, int sc, int newcolor) {
        int curcolor = image[sr][sc];//当前的颜色
        if(curcolor != newcolor) dfs(image,sr,sc,curcolor,newcolor);
        return image;
    }

    void dfs(vector>& image, int x, int y, int color, int newcolor){
        if(image[x][y] == color){
            if(image[x][y] == color){ //当前颜色
                image[x][y] = newcolor;
                for(int i = 0;i < 4;i++){
                    int mx = x + dx[i], my = y + dy[i];
                    if(mx >=0 && mx < image.size() && my >=0 && my < image[0].size()){
                        dfs(image,mx,my,color,newcolor);
                    }
                }
            }
        }
    }
};
 
岛屿的最大面积 
https://leetcode.cn/problems/max-area-of-island/
 
class Solution {
public:
    //  DFS
    const int dx[4] = {1,0,0,-1};//下 右 左 上
    const int dy[4] = {0,1,-1,0};//下 右 左 上
    int maxAreaOfIsland(vector>& grid) {
        int ans = 0,row = grid.size(),col = grid[0].size();
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                ans = max(ans,dfs(grid,i,j));
            }
        }
        return ans;
    }

    int dfs(vector> &grid,int i,int j){
        int cnt = 1;
        if(i >= 0 && i < grid.size() && j >= 0 && j < grid[0].size()){
            if(grid[i][j] == 0) return 0;
            grid[i][j] = 0;
            for(int idx = 0; idx < 4 ;idx++){
                cnt += dfs(grid,i + dx[idx], j + dy[idx]);
            }
        }else return 0;
        return cnt;
    }

};
 
广度优先搜索 BFS 
图像渲染 
https://leetcode.cn/problems/flood-fill/
 
class Solution {
public:
    const int dx[4] = {1,0,0,-1};//下 右 左 上
    const int dy[4] = {0,1,-1,0};//下 右 左 上
    vector> floodFill(vector>& image, int sr, int sc, int newcolor) {
        int curcolor = image[sr][sc];//当前的颜色
        if(curcolor == newcolor) return image;

        int row = image.size(), col = image[0].size();
        queue> q; //定义队列
        q.emplace(sr,sc);//添加元素
        image[sr][sc] = newcolor;//赋给新的值

        while(!q.empty()) //队列不为空
        {
            // int x = q.front().first;// 取出对首元素的x值
            // int y = q.front().second; // 取出对首元素的y值
            //下面这代码也ok
            auto [x, y] = q.front();

            q.pop(); //删除对首元素

            for(int i = 0;i < 4;i++){
                int mx = x + dx[i], my = y + dy[i];
                if(mx >= 0 && mx < row && my >= 0 && my < col && image[mx][my] == curcolor){
                    q.emplace(mx,my);
                    image[mx][my] = newcolor;
                } 
            }
        }
        return image;
    }
};
 
岛屿的最大面积 
https://leetcode.cn/problems/max-area-of-island/
 
class Solution {
public:
    //BFS
    const int dx[4] = {1,-1,0,0};
    const int dy[4] = {0,0,1,-1};
    int maxAreaOfIsland(vector>& grid) {
        int ans = 0,row = grid.size(),col = grid[0].size();
        for(int i = 0;i < row;i++){
            for(int j = 0;j < col;j++){
                ans = max(ans,bfs(grid,i,j));
            }
        }
        return ans;
    }

    int bfs(vector> &grid,int i,int j){
        queue> q;
        q.emplace(i,j);
        int cnt = 0;
        while(!q.empty()){
            auto [x,y] = q.front();
            q.pop();
            if(x >= 0 && x < grid.size() && y >= 0 && y < grid[0].size() && grid[x][y] == 1){
                ++cnt;
                grid[x][y] = 0;
                for(int idx = 0; idx < 4 ;idx++){
                    int mx = x + dx[idx], my = y + dy[idx];
                    q.emplace(mx,my);
                }
            }
        }
        return cnt;
    }

};
 
栈 
实现有效的括号 
https://leetcode.cn/problems/valid-parentheses/
 
class Solution {
public:
    bool isValid(string s) {
        stackstack;
        stack.push(s[0]);
        unordered_mapm;
        m.insert({{')','('},{'}','{'},{']','['}});
        for(int i = 1;i < s.size(); i++){
            if(stack.empty()){
                stack.push(s[i]);
                continue;
            }
            if(stack.top() == m[s[i]]) stack.pop();
            else stack.push(s[i]);
        }
        return stack.empty();
    }
};
 
树 
验证二叉搜索树 
https://leetcode.cn/problems/validate-binary-search-tree/
 
class Solution {
public:
    long pre = LONG_MIN;
    bool isValidBST(TreeNode* root) {
        if(!root) return true;
        if(!isValidBST(root->left)) return false;
        if(root->val <= pre) return false;
        pre = root->val;
        return isValidBST(root->right);
    }
};
 
二叉搜索树中的搜索 
https://leetcode.cn/problems/search-in-a-binary-search-tree/
 
class Solution {
public:
    TreeNode* searchBST(TreeNode* root, int val) {
        if(!root || root -> val == val) return root;
        TreeNode *left = searchBST(root->left,val);
        TreeNode *right = searchBST(root->right,val);
        if(left != NULL) return left;
        if(right != NULL) return right;
        return NULL;
    }
};
 
二叉搜索树中的插入操作 
https://leetcode.cn/problems/insert-into-a-binary-search-tree/
 
class Solution {
public:
    TreeNode* insertIntoBST(TreeNode* root, int val) {
        if(!root) return new TreeNode(val); //没有子结点的时候，新建一个当前值的结点
        if(root->val < val) root->right = insertIntoBST(root->right,val);
        else root->left = insertIntoBST(root->left,val);
        return root;
    }
};
 
二叉树的层序遍历 
递归 
https://leetcode.cn/problems/binary-tree-level-order-traversal/
 
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector>ans;
        dfs(root,0,ans);
        return ans;
    }
    void dfs(TreeNode *root,int depth,vector> &ans){
        if(root == NULL) return ;
        if(depth >= ans.size()) ans.push_back(vector{});
        ans[depth].push_back(root->val);
        dfs(root->left,depth+1,ans);
        dfs(root->right,depth+1,ans);
    }
};
 
bfs 
https://leetcode.cn/problems/binary-tree-level-order-traversal/
 
class Solution {
public:
    vector> levelOrder(TreeNode* root) {
        vector>ans;
        if(root == NULL) return ans;
        queue q;
        q.push(root);
        while(!q.empty()){
            int cursize = q.size();
            ans.push_back(vector());
            for(int i = 0;i < cursize;i++){
                auto node = q.front();
                q.pop();
                ans.back().push_back(node->val);
                if(node -> left) q.push(node->left);
                if(node->right) q.push(node->right);
            } 
        }
        return ans;
    }
};
 
二叉树的最大深度 
递归 
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
 
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int left = maxDepth(root->left);
        int right = maxDepth(root->right);
        return max(left,right) + 1;
    }
};
 
bfs 
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
 
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        int depth = 0;
        queueq;
        q.push(root);
        while(!q.empty()){
            int cursize = q.size();
            ++depth;
            for(int i = 0;i < cursize;i++){
                auto node = q.front();
                q.pop();
                if(node -> left) q.push(node->left);
                if(node->right) q.push(node->right);
            }
        }
        return depth;
    }
};
 
dfs 
https://leetcode.cn/problems/maximum-depth-of-binary-tree/
 
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root) return 0;
        return dfs(root);
    }
    int dfs(TreeNode * root){
        if(!root) return 0;
        int left = dfs(root->left); //左根最大的深度
        int right = dfs(root->right);//右根最大的深度
        int depth  = 1 + max(left,right); //取左右根最大的深度 + 根节点一个
        return depth;
    }
};
 
对称二叉树 
https://leetcode.cn/problems/symmetric-tree/
 
//递归
class Solution {
public:
    bool isSymmetric(TreeNode *root) {
        if(!root) return true;
        return dfs(root->left,root->right);
    }
    bool dfs(TreeNode* n1,TreeNode* n2){
        if(!n1 && !n2) return true;
        if(!n1 || !n2 || n1->val != n2->val) return false;
        return dfs(n1->left,n2->right) && dfs(n1->right,n2->left);
    }
};
 
反转二叉树 
https://leetcode.cn/problems/invert-binary-tree/
 
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(!root) return root;
        TreeNode *r = root->right;
        root->right = invertTree(root->left);
        root->left =  invertTree(r);
        return root;
    }
};
 
两数之和 - BST 
https://leetcode.cn/problems/two-sum-iv-input-is-a-bst/
 
class Solution {
public:
    unordered_sethashset;
    bool preOrder(TreeNode *root,int k){
        if(!root) return false;
        if(hashset.count(k - root->val)) return true;
        hashset.insert(root->val);
        return preOrder(root->left,k) || preOrder(root->right,k);
    }
    bool findTarget(TreeNode* root, int k) {
        return preOrder(root,k);
    }
};
 
二叉搜索树的最近公共祖先 
https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-search-tree/
 
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == NULL) return NULL;
        if (root->val > p->val && root->val > q->val)
            return lowestCommonAncestor(root->left, p, q); // p 和 q 都在左子树上
        if (root->val < p->val && root->val < q->val)
            return lowestCommonAncestor(root->right, p, q); // p 和 q 都在右子树上
        return root;
    }
};
 
回溯 
组合 
https://leetcode.cn/problems/combinations/
 
class Solution {
public:
    vectortmp;
    vector>ans; 
    void helper(int n,int k,int startIdx){
        if(tmp.size() == k){
            ans.push_back(tmp);//刚好找到一组
            return ;
        }
        for(int i = startIdx;i <= n;i++){
            tmp.push_back(i);
            helper(n,k,i+1); //递归
            tmp.pop_back();//删除最后一个元素
        }
    }
    vector> combine(int n, int k) {
        helper(n,k,1);
        return ans;
    }
};
 
全排列 
https://leetcode.cn/problems/permutations/
 
class Solution {
public:

    vector>ans;
    vectorpath;

    void helper(vector& nums,vector &used){
        if(path.size() == nums.size()){
            ans.push_back(path);
            return;
        }
        for(int i = 0;i < nums.size();i++){
            if(used[i] == true) continue;
            used[i] = true;//当前行使用
            path.push_back(nums[i]);
            helper(nums,used);
            path.pop_back();
            used[i] = false;
        }
    }

    vector> permute(vector& nums) {
        vector used(nums.size(), false); //是否被使用数组
        helper(nums,used);
        return ans;
    }
};
 
链表 
反转链表 
https://leetcode.cn/problems/reverse-linked-list/
 
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *p;
        for(p = NULL; head; swap(head,p)) swap(p,head->next);
        return p;
    }
};
 
合并两个有序链表 
https://leetcode.cn/problems/merge-two-sorted-lists/
 
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == NULL) return list2;
        if(list2 == NULL) return list1;
        if(list1->val <= list2->val){
            list1->next = mergeTwoLists(list1->next,list2);
            return list1;
        }else {
            list2->next = mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};
 
删除链表的倒数第 N 个结点 
https://leetcode.cn/problems/remove-nth-node-from-end-of-list/
 
class Solution {
public:
    int cur = 0;
    ListNode* removeNthFromEnd(ListNode* head, int n) {
       if(!head) return NULL;
       head->next = removeNthFromEnd(head->next,n);
       cur++; //cur++是在函数回溯的时候， 是从后往前++，所以n=cur的时候就是倒数第n个节点
       if(n == cur) return head->next;
       return head;
    }
};
 
删除排序链表中的重复元素 
https://leetcode.cn/problems/remove-duplicates-from-sorted-list/
 
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head == NULL || head -> next == NULL) return head;
        head -> next = deleteDuplicates(head -> next);
        if(head -> val == head -> next -> val) head = head -> next; //找到该元素，头结点的next赋值给头结点
        return head;
    }
};
 
环形链表 
https://leetcode.cn/problems/linked-list-cycle/
 
class Solution {
public:
    bool hasCycle(ListNode *head) {
        //快指针比慢指针快走2步，当快指针和慢指针相等，及说明存在环
        ListNode* l = head;
        ListNode* r = head;
        while(r != NULL && r -> next != NULL) {
            l = l -> next;
            r = r -> next -> next;
            if(l == r) return true;
        }
        return false;
    }
};
 
位运算 
2的幂次方 
https://leetcode.cn/problems/power-of-two/
 
class Solution {
public:
    bool isPowerOfTwo(int n) {
        // (n & (n - 1)) 可以判断n > 0 下，n为偶数
        return n > 0 && (n & (n - 1)) == 0;
    }
};
 
二进制位1的个数 
https://leetcode.cn/problems/number-of-1-bits/
 
class Solution {
public:
    int hammingWeight(uint32_t n) {
        // return bitset<32>(n).count(); //法一
        int ans=0;
        while(n){
            ans += n % 2; //由于个位上只有0或1，对n取模计数即可。
            n >>= 1; // n向右移位1位
        }
        return ans;
    }
};