[数据结构与算法]C++基础算法总结

二分法

二分查找

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

class Solution {
public:
    int search(vector<int>& 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<int>& 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<int>& nums) {
        int n = nums.size(),res = 0;
        vector<int> 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<int>& nums) {
        if(nums.empty()) return 0;
        int n = nums.size();
        if(n == 1) return nums[0];
        vector<int> 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<vector<int>>& 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];
    }
};

Dijkstra算法

#include <iostream>
#include <cstring>
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<n;i++)
  {
    int t=-1;
    for(int j=1;j<=n;j++)
    {
      if(!vis[j]&&(t==-1||dist[j]<dist[t]))
        t=j;
    }
    vis[t]=1;

    for(int j=1;j<=n;j++)
    {
      dist[j]=min(dist[j],dist[t]+g[t][j]);
    }
  }
  return dist[n];
}
int main()
{
    memset(g,0x3f,sizeof g);
    add('A','B',2);
    add('A','C',1);
    add('A','D',1);
    add('A','D',1);
    add('B','J',2);
    add('B','G',1);
    add('C','D',3);
    add('C','F',3);
    add('C','G',3);
    add('D','E',1);
    add('D','G',2);
    add('D','H',1);
    add('D','I',2);
    add('E','H',1);
    add('E','I',3);
    add('F','G',1);
    add('F','J',1);
    add('G','F',1);
    add('G','I',3);
    add('G','K',2);
    add('H','I',1);
    add('H','L',2);
    add('I','M',3);
    add('J','S',2);
    add('K','N',1);
    add('K','L',3);
    add('K','P',2);
    add('L','M',1);
    add('L','R',1);
    add('M','N',2);
    add('M','Q',1);
    add('M','S',1);
    add('N','P',1);
    add('O','P',1);
    add('O','Q',1);
    add('O','R',3);
    add('R','S',1);
    cout<<dijkstra();
  return 0;
}

双指针

https://leetcode.cn/problems/move-zeroes/

class Solution {
public:
    void moveZeroes(vector<int>& 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<vector<int>> floodFill(vector<vector<int>>& 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<vector<int>>& 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<vector<int>>& 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<vector<int>> &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<vector<int>> floodFill(vector<vector<int>>& 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<pair<int,int>> 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<vector<int>>& 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<vector<int>> &grid,int i,int j){
        queue<pair<int,int>> 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) {
        stack<char>stack;
        stack.push(s[0]);
        unordered_map<char,char>m;
        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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        dfs(root,0,ans);
        return ans;
    }
    void dfs(TreeNode *root,int depth,vector<vector<int>> &ans){
        if(root == NULL) return ;
        if(depth >= ans.size()) ans.push_back(vector<int>{});
        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<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>>ans;
        if(root == NULL) return ans;
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty()){
            int cursize = q.size();
            ans.push_back(vector<int>());
            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;
        queue<TreeNode *>q;
        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_set<int>hashset;
    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:
    vector<int>tmp;
    vector<vector<int>>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<vector<int>> combine(int n, int k) {
        helper(n,k,1);
        return ans;
    }
};

全排列

https://leetcode.cn/problems/permutations/

class Solution {
public:

    vector<vector<int>>ans;
    vector<int>path;

    void helper(vector<int>& nums,vector<bool> &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<vector<int>> permute(vector<int>& nums) {
        vector<bool> 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;
    }
};