Leetcode

二分查找(278. 第一个错误的版本)

mid=left+(right-left)/2    //防止越界

数组翻转（189. 轮转数组）

class Solution {
public:
    void reverse(vector<int>& nums, int start, int end) {
        while (start < end) {
            swap(nums[start], nums[end]);
            start += 1;
            end -= 1;
        }
    }

    void rotate(vector<int>& nums, int k) {
        k %= nums.size();
        reverse(nums, 0, nums.size() - 1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.size() - 1);
    }
};

反转字符串里的单词（557. 反转字符串中的单词 III）

class Solution {
public:
    string reverseWords(string s) {
        int l=s.length();
        int i=0;
        while(i<l)
        {
            int start=i;
            while(i<l&&s[i]!=' ')
            {
                i++;
            }
            int left=start,right=i-1;
            while(left<right)
            {
                swap(s[left],s[right]);
                left++;
                right--;
            }
            while(i<l&&s[i]==' ')
            {
                i++;
            }
        }
        return s;
    }
};

快慢指针（876. 链表的中间结点）

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};

滑动窗口（3. 无重复字符的最长子串）

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        // 哈希集合，记录每个字符是否出现过
        unordered_set<char> occ;
        int n = s.size();
        // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
        int rk = -1, ans = 0;
        // 枚举左指针的位置，初始值隐性地表示为 -1
        for (int i = 0; i < n; ++i) {
            if (i != 0) {
                // 左指针向右移动一格，移除一个字符
                occ.erase(s[i - 1]);
            }
            while (rk + 1 < n && !occ.count(s[rk + 1])) {
                // 不断地移动右指针
                occ.insert(s[rk + 1]);
                ++rk;
            }
            // 第 i 到 rk 个字符是一个极长的无重复字符子串
            ans = max(ans, rk - i + 1);
        }
        return ans;
    }
};

字符串的排列（567. 字符串的排列）

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int L1=s1.size();
        int L2=s2.size();
        if(L1>L2)
        {
            return false;
        }
        vector<int>hash1(26);
        vector<int>hash2(26);
        for(int i=0;i<L1;i++)
        {
            hash1[s1[i]-'a']++;
            hash2[s2[i]-'a']++;
        }
        if(hash1==hash2)return true;

        for(int i=L1;i<L2;i++)
        {
            hash2[s2[i]-'a']++;
            hash2[s2[i-L1]-'a']--;
            if(hash1==hash2)return true;
        }
        return false;
    }
};

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        int n = s1.length(), m = s2.length();
        if (n > m) {
            return false;
        }
        vector<int> cnt(26);
        for (int i = 0; i < n; ++i) {
            --cnt[s1[i] - 'a'];
        }
        int left = 0;
        for (int right = 0; right < m; ++right) {
            int x = s2[right] - 'a';
            ++cnt[x];
            while (cnt[x] > 0) {
                --cnt[s2[left] - 'a'];
                ++left;
            }
            if (right - left + 1 == n) {
                return true;
            }
        }
        return false;
    }
};

图的BFS、DFS（733. 图像渲染）

注意emplace和push的区别

bfs（用到pair）

//BFS，利用队列我们从给定的起点开始，进行广度优先搜索。每次搜索到一个方格时，如果其与初始位置的方格颜色相同，就将该方格加入队列，并将该方格的颜色更新，以防止重复入队。注意：因为初始位置的颜色会被修改，所以我们需要保存初始位置的颜色，以便于之后的更新操作。
class Solution {
    const int dx[4]={1,-1,0,0};
    const int dy[4]={0,0,1,-1};
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        int CurrColor=image[sr][sc];
        if(image[sr][sc]==color)return image;
        int n=image.size();
        int m=image[0].size();
        queue<pair<int,int>>que;
        que.emplace(sr,sc);
        image[sr][sc]=color;
        while(!que.empty())
        {
            int x=que.front().first;
            int y=que.front().second;
            que.pop();
            for(int i=0;i<4;i++)
            {
                int mx=x+dx[i];
                int my=y+dy[i];
                if(mx>=0&&mx<n&&my>=0&&my<m&&image[mx][my]==CurrColor)
                {
                    que.emplace(mx,my);
                    image[mx][my]=color;
                }
            }
           
        }
         return image;
    }
};

dfs

//dfs
//二维数组的创建 vector<vector<int>>flag(image.size(),vector<int>(image[0].size(),0));需要好好理解
class Solution {
public:
    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
        vector<vector<int>>flag(image.size(),vector<int>(image[0].size(),0));
        int CurrColor=image[sr][sc];
        dfs(image,sr,sc,color,CurrColor,flag);
        return image;
    }
public:
    void dfs(vector<vector<int>>& image, int sr, int sc, int color,int CurrColor,vector<vector<int>>& flag)
    {
        if(!(sr>=0&&sr<image.size()&&sc>=0&&sc<image[0].size()))return;
        if(image[sr][sc]!=CurrColor)return;
        if(flag[sr][sc]==-1)return;
        image[sr][sc]=color;
        flag[sr][sc]=-1;
        dfs(image,sr+1,sc,color,CurrColor,flag);
        dfs(image,sr-1,sc,color,CurrColor,flag);
        dfs(image,sr,sc+1,color,CurrColor,flag);
        dfs(image,sr,sc-1,color,CurrColor,flag);
    }
};

树的搜索（617. 合并二叉树）

/**
 * 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* mergeTrees(TreeNode* root1, TreeNode* root2) {
        if(root1==nullptr)return root2;
        if(root2==nullptr)return root1;
        root1->val+=root2->val;
        root1->left=mergeTrees(root1->left,root2->left);
        root1->right=mergeTrees(root1->right,root2->right);
        return root1;
    }
};

树、递归、搜索（116. 填充每个节点的下一个右侧节点指针）

有时间再试试层次遍历 熟练运用stl

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* connect(Node* root) {
        if(root==nullptr)return nullptr;
        if(root->left)
        {
            root->left->next=root->right;
            if(root->next)
            {
                root->right->next=root->next->left;
            }
        }
        connect(root->left);
        connect(root->right);
        return root;
    }
};

链表的合并、递归、迭代（21. 合并两个有序链表）

递归

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1==nullptr)return list2;
        else if(list2==nullptr)return list1;
        else if(list1->val<list2->val)
        {
            list1->next=mergeTwoLists(list1->next,list2);
            return list1;
        }
        else{
            list2->next=mergeTwoLists(list1,list2->next);
            return list2;
        }
    }
};

迭代

/**
 * 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* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode*prehead=new ListNode(-1);
        ListNode*vis=prehead;
        while(list1!=nullptr&&list2!=nullptr)
        {
            if(list1->val<list2->val)
            {
                vis->next=list1;
                list1=list1->next;
            }
            else
            {
                vis->next=list2;
                list2=list2->next;
            }
            vis=vis->next;
        }
        vis->next=list1==nullptr?list2:list1;
        return prehead->next;
    }
};

考虑问题周全（14. 最长公共前缀）

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if(strs[0]=="")return "";//
        int m=strs.size();
        if(m==1)return strs[0];//
        string ans;
        for(int i=0;;i++)
        {   
            if(strs[0][i]=='\0')break;//
            int temp=0;
            for(int j=1;j<m;j++)
            {
                if(strs[j][i]!=strs[0][i])
                {
                    temp=-1;
                }
            }
            if(temp==-1)break;
            if(temp==0)
            {
                ans+=strs[0][i];
            }
        }
        return ans;
    }
};

BFS、写代码注意时间复杂度（542. 01 矩阵）

//updateMatrix函数里for就m*n了  再加上bfs肯定会超时，有意识分析一下。
class Solution {
public:
    void bfs(vector<vector<int>>& mat,int i,int j)
    {
        int ans=0;
        int m=mat.size();
        int n=mat[0].size();
        int dx[4]={1,-1,0,0};
        int dy[4]={0,0,1,-1};
        queue<pair<int,int>>que;
        que.emplace(i,j);
        while(!que.empty()){
        ans++;
        int l=que.size();
        for(int k=0;k<l;k++)
        {
            int x=que.front().first;int y=que.front().second;
            que.pop();
            for(int z=0;z<4;z++)
            {
                int X=x+dx[z];int Y=y+dy[z];
                if(X>=0&&X<m&&Y>=0&&Y<n)
                {
                    que.emplace(X,Y);
                    if(mat[X][Y]==0)
                    {
                        mat[i][j]=ans;
                        return;
                    }
                }
            }
        }
        }
    }
public:
    vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {
        int m=mat.size();
        int n=mat[0].size();
        for(int i=0;i<m;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(mat[i][j]!=0)
                {
                    bfs(mat,i,j);
                }
            }
        }
        return mat;
    }
};

哈希表unorder_set count、insert（141. 环形链表）

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*>hash;
        while(head!=NULL)
        {
            if(hash.count(head))
            {
                return true;
            }
            hash.insert(head);
            head=head->next;
        }
        return false;
    }
};

//快慢指针，龟兔赛跑
class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

链表题通常可以递归、迭代（203. 移除链表元素）

递归

/**
 * 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* removeElements(ListNode* head, int val) {
        if(head==nullptr)
        {
            return head;
        }
        head->next=removeElements(head->next,val);
        return head->val==val?head->next:head;
    }
};

迭代

class Solution {
    public ListNode removeElements(ListNode head, int val) {
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }
}

链表的递归迭代（206. 反转链表）

迭代

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

递归

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (!head || !head->next) {
            return head;
        }
        ListNode* newHead = reverseList(head->next);
        head->next->next = head;
        head->next = nullptr;
        return newHead;
    }
};

二叉树前序遍历，分两个函数写（144. 二叉树的前序遍历）

/**
 * 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:
    void Preorder(TreeNode*root,vector<int>&res)
    {
        if(root==nullptr)return;
        else
        {
            res.push_back(root->val);
            Preorder(root->left,res);
            Preorder(root->right,res);
        }
    }
    vector<int> preorderTraversal(TreeNode* root) {
        vector<int>res;
        Preorder(root,res);
        return res;
    }
};

位运算(&、|、^、~、>>、<<)

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&(n&(n-1))==0;
    }
};

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n>0&&(n&(-n))==n;
    }
};

二维vector的创建

/**
 * 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*>que;
        que.push(root);
        vector<vector<int>>ans;
        if(root==nullptr)
        {
            return ans;
        }
        while(!que.empty())
        {
            ans.push_back(vector<int>());//关键一步
            int l=que.size();
            for(int j=0;j<l;j++)
            {
                TreeNode*cur=que.front();
                if(cur->left!=nullptr)que.push(cur->left);
                if(cur->right!=nullptr)que.push(cur->right);
                ans.back().push_back(cur->val);
                que.pop();
            }
        }
        return ans;
    }
};

树的高度

最低

/**
 * 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 minDepth(TreeNode* root) {
        if(root==nullptr)return 0;
        if(root->left==nullptr&&root->right==nullptr)return 1;
        int min_Depth=0x3f3f3f3f;
        if(root->left!=nullptr)
        {
            min_Depth=min(minDepth(root->left),min_Depth);
        }
        if(root->right!=nullptr)
        {
            min_Depth=min(minDepth(root->right),min_Depth);
        }
        return min_Depth+1;

    }
};

最高

/**
 * 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 maxDepth(TreeNode* root) {
        if(root==nullptr)return 0;
        int max1=maxDepth(root->left);
        int max2=maxDepth(root->right);
        return max(max1,max2)+1;
    }
};

tolower，isalnum，string ans_rev(ans.rbegin(), ans.rend());

对称二叉树（递归）

class Solution {
public:
    bool check(TreeNode *p, TreeNode *q) {
        if (!p && !q) return true;
        if (!p || !q) return false;
        return p->val == q->val && check(p->left, q->right) && check(p->right, q->left);
    }

    bool isSymmetric(TreeNode* root) {
        return check(root, root);
    }
};