Top hot questions

算法
字数统计: 12.5k   |   阅读时长≈ 63 分钟

概述：本文根据CodeTop记录了热门的一些算法问题

反转链表

（需要完全掌握递归和非递归写法）

（1）迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
迭代方法
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur!=nullptr){
            ListNode* temp = cur->next;  //暂存后继节点
            cur->next=pre;
            pre=cur;
            cur=temp;
        }
        return pre;//注意返回的是pre而不是cur，cur在出循环后是nullptr
    }
};

（2）递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
//递归
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return recur(head, nullptr);           // 调用递归并返回
    }
private:
    ListNode* recur(ListNode* cur, ListNode* pre) {
        if (cur == nullptr) return pre;        // 终止条件
        ListNode* res = recur(cur->next, cur); // 递归后继节点
        cur->next = pre;                       // 修改节点引用指向
        return res;                            // 返回反转链表的头节点
    }
};

反转链表指定区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int left, int right) {
        // 设置 dummyNode 是这一类问题的一般做法
        ListNode *dummyNode = new ListNode(-1);
        dummyNode->next = head;
        ListNode *pre = dummyNode;
        for (int i = 0; i < left - 1; i++) {
            pre = pre->next;
        }
        ListNode *cur = pre->next;
        //核心逻辑，把cur右边的节点一个个插入到pre后面
        for (int i = 0; i < right - left; i++) {
            ListNode* temp = cur->next;
            cur->next = temp->next;
            temp->next = pre->next;
            pre->next = temp;
        }
        return dummyNode->next;
    }
};

k个一组反转链表

思想：

（1）设计一个反转[head,tail]区间的节点的函数，并返回反转后的头和尾

（2）注意保存头结点的前一节点，用于连接局部反转后的链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * 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* hair = new ListNode(0);
        hair->next = head;
        ListNode* pre = hair;

        while (head) {
            ListNode* tail = pre;
            // 查看剩余部分长度是否大于等于 k
            for (int i = 0; i < k; ++i) {
                tail = tail->next;
                if (!tail) {
                    return hair->next;
                }
            }
            ListNode* nex = tail->next;
            pair<ListNode*, ListNode*> result = reverseList(head, tail);
            head = result.first;
            tail = result.second;
            // 把子链表重新接回原链表
            pre->next = head;
            tail->next = nex;
            pre = tail;
            head = tail->next;
        }

        return hair->next;
    }
private:
    pair<ListNode*,ListNode*> reverseList(ListNode* head, ListNode* tail){
        //注意这里反转的写法，最后要把尾连接到下一个节点上去
        ListNode* prev = tail->next;
        ListNode* p = head;
        while (prev != tail) {
            ListNode* temp = p->next;
            p->next = prev;
            prev = p;
            p = temp;
        }
        return {tail, head};
    }
};

重排链表

（面试中遇到过）

时间O(n), 空间O(n)思想：将所有节点存储在vector<ListNode*>中，然后按要求重新连接

时间O(n), 空间O(1)思想：

（1）找到链表中间节点，并断开

（2）反转后半部分的链表

（3）合并两个链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
public:
    void reorderList(ListNode* head) {
        if(head == nullptr || head->next == nullptr) return;

        //找到中点并断开
        ListNode* slow = head, *fast = head;
        ListNode* dummyNode = new ListNode(-1, head);
        ListNode* pre = dummyNode;
        while(fast!=nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            pre = pre->next;
        }
        pre->next = nullptr;//断开
        ListNode* node2 = slow; //slow为新链表的头结点

        //反转后半部分链表
        ListNode* reversePre = nullptr;//表示反转后的下一个节点，也代表反转完成后的头节点
        while(node2!=nullptr){
            ListNode* temp = node2->next;
            node2->next = reversePre;
            reversePre = node2;
            node2 = temp;
        }

        //合并两个链表
        while(head != nullptr && reversePre != nullptr){
            ListNode* temp1 = head->next, *temp2 = reversePre->next;
            head->next = reversePre;
            //由于链表二长度一定大于等于链表一，因此发现链表一到末尾时可以直接全部连上链表二
            if(temp1 == nullptr) 
                break;
            reversePre->next = temp1;
            head = temp1;
            reversePre = temp2;
        }
    }
};

无重复最长子串

注意子串和子序列的区别！

思路：滑动窗口，哈希表记录上一个相同的字符出现的index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.empty()) return 0;
        //缓存记录上一个字符的位置
        unordered_map<char,int> mp;
        int left = 0, right = 0;
        int result = 1;
        while(right<s.size()){
            if(mp.find(s[right])==mp.end()){
                mp[s[right]] = right;
            }
            else{
                left = max(left,mp[s[right]]+1);
                mp[s[right]]=right;
            }
            result = max(result,right-left+1);
            ++right;
        }
        return result;
    }
};

LRU缓存

存储三个量：

  • 容量capacity
  • 一个pair<key,value>的双向链表cashe，存储键值对，其中最久未使用的放在尾部
  • 一个哈希表，存放每个key对应的链表节点的迭代器（指针）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class LRUCache {
public:
    LRUCache(int capacity) : cap(capacity){ }
    
    int get(int key) {
        auto it = hash.find(key);
        if(it == hash.end()) return -1;
        cache.splice(cache.begin(), cache, it->second);
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = hash.find(key);
        if(it != hash.end()){//已经在缓存中
            it->second->second = value;//改变值
            cache.splice(cache.begin(), cache, it->second);//改变位置 
            /*
            以上这一句也可以通过以下语句实现：(移除旧节点，在链表头增加新节点)
            pair<int,int> node =*it;
            cache.erase(it);
            cache.push_front(node);
            hash[key] = cache.begin();//不要忘了更新map
            */
            return;
        }
        else{//新添
            cache.push_front({key, value});//添加到头 最新使用
            hash[key] = cache.begin();

            if(hash.size() > cap){//新添可能超容
                hash.erase(cache.back().first);//在map中移除最久未使用的节点
                cache.pop_back();//在链表中移除节点
            }
        }
    }
private:
    int cap;
    list<pair<int, int>> cache;//链表的顺序就是缓存使用顺序
    unordered_map<int, list<pair<int, int>>::iterator> hash;//作key与节点的对应，用于快速找到节点
};
/**
 * 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);
 */

数组中的第K个最大元素

使用内置容器：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> pq;//默认大根堆，头元素最大，因此要改成小根堆
        for(int i=0;i!=nums.size();++i){
            if(pq.size()<k){
                pq.push(nums[i]);
            }
            else{
                pq.push(nums[i]);
                pq.pop();
            }
        }
        return pq.top();
    }
};

手写堆排序(大根堆)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
class MyPriorityQueue{
private:    
    vector<int> pq; // 首位填充一个数值，方便找根节点与子节点
public:
    MyPriorityQueue(){pq.push_back(0);}
    void push(int num) {
        pq.push_back(num);
        swim(pq.size() - 1);
    }
    int pop() {
        swap(pq[1], pq.back());
        int res = pq.back();
        pq.pop_back();
        sink(1);
        return res;
    }
    int top() {
        return pq[1];
    }
    bool isPrior(int i, int j) { // 自定义函数部分，此处实现的是大根堆
        return pq[i] < pq[j];
    }
    void swim(int i) { // 子节点与父节点比较
        while (i > 1 && isPrior(i, i / 2)) {
            swap(pq[i], pq[i / 2]);
            i /= 2;
        }
    }
    void sink(int i) { // 父节点与左右节点中最大的进行比较
        int n = pq.size();
        while (i * 2 < n) {
            int j = i * 2;
            if (j + 1 < n && isPrior(j + 1, j)) j++;
            if (isPrior(i , j)) break;
            swap(pq[i], pq[j]);
            i = j;
        }
    }
    int size(){
        return pq.size();
    }
};

两数之和

关键是哈希表中应该存 target-nums[i]作为key

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> mp;
        for(int i=0;i!=nums.size();++i){
            if(mp.find(nums[i]) != mp.end()){
                return {mp[nums[i]], i};
            }
            mp[target - nums[i]] = i;
        }
        return {};
    }
};

三数之和

思路：排序+双指针

特别注意去重的逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        if(nums.size()<3) return {};
        sort(nums.begin(),nums.end());
        vector<vector<int>> result;
        for(int i=0;i<nums.size()-2;++i){
            if(i>=1&&nums[i]==nums[i-1]) continue;
            int num1 = nums[i];
            int left = i+1;
            int right = nums.size()-1;
            while(right>left){
                //当找到一组之后，下一组的left和right一定是与之前完全不同的，因此相同的数字都跳过
                if(left>i+1&& nums[left] == nums[left-1]) {
                    ++left;
                    continue;
                }
                if(right<nums.size()-1&&nums[right]==nums[right+1]) {
                    --right;
                    continue;
                }
                if(nums[left]+nums[right] == -num1){
                    //找到目标三元组，push
                    result.push_back({num1,nums[left],nums[right]});
                    ++left;
                    --right;
                }
                else if(nums[left]+nums[right]<-num1)
                    ++left;
                else
                    --right;
            }
        }
        return result;
    }
};

手撕排序算法

快速排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        //打乱数组，提高速度
        random_shuffle(nums.begin(),nums.end());
        quick_sort(nums, 0, nums.size() - 1);
        return nums;
    }
private:
    void quick_sort(vector<int>& nums, int low, int high){
        if(low > high) return;
        int index = partition(nums, low, high);
        quick_sort(nums, low, index - 1);
        quick_sort(nums, index+1, high);
    }
    int partition(vector<int>& nums,int low, int high){
        int pivot = nums[low];
        while(low < high){
            while(low < high && nums[high] >= pivot) --high;
            nums[low] = nums[high];
            while(low <high && nums[low] <=pivot) ++low;
            nums[high] = nums[low];
        }
        //注意不要落下这句
        nums[low] = pivot;
        return low;//high或low都行，相等
    }
};

归并排序

Auxilary(辅助)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> aux(nums.size());
        merge_sort(nums, aux, 0, nums.size()-1);
        return nums;
    }
private:
    void merge_sort(vector<int>& nums, vector<int>& aux, int low, int high){
        if(high <= low) return;
        int mid = low + (high - low)/2;
        merge_sort(nums, aux, low, mid);
        merge_sort(nums, aux, mid+1, high);
        //优化，若nums[mid]<nums[mid+1]，则表示两边已经有序，不需合并，可以直接return
        if(nums[mid] < nums[mid+1]) return;
        merge(nums, aux, low, mid, high);
    }
    void merge(vector<int>& nums, vector<int>& aux, int low, int mid, int high){
        //这里可以用is_sorted判断数组是否是排序过的

        //copy
        for(int k = low; k <= high; ++k){
            aux[k] = nums[k];
        }
        //merge
        int i = low, j = mid +1;
        for(int k = low; k <= high; ++k){
            if(i > mid) nums[k] = aux[j++];
            else if(j > high) nums[k] = aux[i++];
            else if(aux[j] < aux[i]) nums[k] = aux[j++];
            else //aux[j] >= aux[i]
                nums[k] = aux[i++];
        }
    }
};

最大子数组之和

动态规划的思路，但是可以只用一个变量保存前一个结果即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        //子数组最少包含一个元素
        int result=nums[0];
        int pre = nums[0];
        for(int i = 1; i!=nums.size(); ++i){
            int cur = max(pre+nums[i], nums[i]);
            pre = cur;
            result = max(result, cur);
        }
        return result;
    }
};

合并两个有序列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
 * 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 *cur1 = list1, *cur2 = list2;
        ListNode* dummyNode = new ListNode();
        ListNode* prev = dummyNode;
        while(cur1 != nullptr && cur2 !=nullptr){
            if(cur1->val >= cur2->val){
                prev->next = cur2;
                cur2 = cur2->next;
            }
            else{
                prev->next = cur1;
                cur1 = cur1->next;
            }
            prev = prev->next;
        }
        if(cur1 != nullptr) prev->next = cur1;
        if(cur2 != nullptr) prev->next = cur2;
        return dummyNode->next;
    }
};

链表排序

解法一：自顶向下归并（递归），仍需要递归栈的O(n)空间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        return merge_sort(head);
    }
    ListNode* merge_sort(ListNode* head){
        if(head == nullptr) return nullptr;
        if(head->next == nullptr) return head;
        //找到中点并断开
        ListNode* pre = new ListNode(-1, head);
        ListNode* slow = head, *fast = head;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            pre = pre->next;
        }
        pre->next = nullptr;//断开

        //自顶向下递归
        ListNode* node1 = merge_sort(head);
        ListNode* node2 = merge_sort(slow);

        //merge
        return merge(node1, node2);
    }
    ListNode* merge(ListNode* head1, ListNode* head2){
        ListNode* dummyNode = new ListNode();
        ListNode* pre = dummyNode;
        while(head1!=nullptr || head2 != nullptr){
            if(head1 == nullptr){
                pre->next = head2;
                break;
            }
            if(head2 == nullptr){
                pre->next = head1;
                break;
            }
            if(head1->val > head2->val){
                pre->next = head2;
                head2 = head2->next;
                pre = pre->next;
            }else{
                pre->next = head1;
                head1 = head1->next;
                pre = pre->next;
            }
        }
        return dummyNode->next;
    }
};

解法二：自底向上归并（迭代）

二叉树层序遍历

主要用到queue队列来存储每一层的节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * 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) {
        if(root==nullptr) return {};
        queue<TreeNode*> q;
        q.push(root);
        vector<vector<int>> result;
        while(!q.empty()){
            int sz = q.size();
            vector<int> layer;
            for(int i=0;i!=sz;++i){
                if(q.front()->left != nullptr)
                    q.push(q.front()->left);
                if(q.front()->right != nullptr)
                    q.push(q.front()->right);
                layer.push_back(q.front()->val);
                q.pop();
            }
            result.push_back(layer);
        }
        return result;
    }
};

二叉树的中序遍历

递归方法：(前序、中序、后序只需要调整push_back()的顺序就行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        dfs(root);
        return result;
    }
    void dfs(TreeNode* root){
        if(root == nullptr) return;
        dfs(root->left);
        result.push_back(root->val);
        dfs(root->right);
    }
private:
    vector<int> result;
};

迭代方法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//逻辑比较清晰直观的版本，思路很清楚！
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        auto p = root;

        // 左链入栈循环
        // 这个循环你会发现和后面的的循环代码有一部分重复，你可以进行合并。
        // 但是这样你就需要在后面循环条件多加一个判断 while (p || !st.empty())，代码也会变得稍微没那么直观
        while (p != nullptr) {
            stk.push(p);
            p = p->left;
        }
        
        while (!stk.empty()) {
            auto node = stk.top();
            stk.pop();
            res.emplace_back(node->val);
            p = node->right;
            // 一旦弹出一个节点，继续做“左链入栈”操作
            while (p) {
                stk.push(p);
                p = p->left;
            }
        }   
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//整合优化代码后的版本
class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> res;
        stack<TreeNode*> stk;
        TreeNode* cur=root;
        while(!stk.empty()||cur!=nullptr){
            // 指针来访问节点，访问到最底层
            if(cur!=nullptr){
                // 将访问的节点放进栈
                stk.push(cur);
                cur=cur->left;
            }
            else{
                //从栈里弹出的数据，就是要处理的数据（放进result数组里的数据）
                res.push_back(stk.top()->val);//中
                cur=stk.top()->right;
                stk.pop();
            }
        }
        return res;
    }
};

买卖股票的最佳时机

dp思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minPrice = prices[0];
        int result = 0;
        for(int i=0;i!=prices.size();++i){
            minPrice = min(minPrice, prices[i]);
            //在第i天卖出能获得的最大利润
            int profit = prices[i] - minPrice;
            result = max(result, profit);
        }
        return result;
    }
};

环形链表

常规思路：哈希表存储看是否被访问过

精妙思路：快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    bool hasCycle(ListNode *head) {
        ListNode* slow = head;
        ListNode* fast = head;
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
};

环形链表II

找到环形链表的入口

同样是快慢指针思想

注意慢指针跑一圈的过程中，快指针一定能追上：（极限思想） 假设他们都是从入环点开始跑的，那么当慢指针刚好跑完一圈时，快指针刚好跑完两圈，也是在一圈的末尾追上慢指针。而现实情况往往是在慢指针到入环处时快指针已经入环并走了了，所以实际情况一定会在第一圈之内相遇

fast = a+b+c+b

slow = a+b

因为fast = 2*slow 可得 a = c

因此只要在fast指针与slow指针相遇后，从链表头开始与slow指针同步继续前进，最终相遇点即为环形链表入口

image-20220817170158411 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode* slow = head, *fast = head;
        
        while(fast != nullptr && fast->next != nullptr){
            slow = slow->next;
            fast = fast->next->next;
            //确认有环，找到入环节点
            if(fast == slow){
                ListNode* temp = head;
                while(temp != slow){
                    temp = temp -> next;
                    slow = slow -> next;
                }
                return temp;
            }
        }
        return nullptr;
    }
};

搜索旋转数组

image-20220816021627932

二分查找，注意分析清楚所有情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (target < nums[mid]) {
                if (nums[left] <= nums[mid] && target < nums[left]) { // 情况（b）需要搜索右部的情况
                    left = mid + 1;
                } else {
                    right = mid - 1;
                }
            } else {
                if (nums[right] >= nums[mid] && target > nums[right]) { // 情况（c）需要搜索左部的情况
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }
        return -1;
    }
};

岛屿数量

基础：使用bfs或dfs解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Solution {
public:
    vector<int> dx = {1,-1,0,0},dy={0,0,1,-1};

    int numIslands(vector<vector<char>>& grid) {
        vector<vector<bool>> visited(grid.size(),vector<bool>(grid[0].size(),false));
        int result = 0;
        for(int i=0;i!=grid.size();++i){
            for(int j=0;j!=grid[0].size();++j){
                if(grid[i][j]=='0'){
                    continue;
                }
                if(visited[i][j] == true){
                    continue;
                }
                visited[i][j]=true;
                //进行bfs或dfs
                //bfs(grid, visited, i, j);
                dfs(grid,visited,i,j);
                ++result;
            }
        }
        return result;
    }
    void bfs(vector<vector<char>>& grid,vector<vector<bool>>& visited, int i, int j){
        queue<pair<int,int>> q;
        q.push({i,j});
        while(!q.empty()){
            auto [x,y] = q.front();
            q.pop();
            for(int k=0;k!=4;++k){
                int xx = x + dx[k], yy = y + dy[k];
                if(xx>=0 && xx<grid.size() 
                    && yy>=0 && yy<grid[0].size() 
                    && grid[xx][yy]=='1'&&visited[xx][yy]==false){
                    q.push({xx,yy});
                    visited[xx][yy] = true;
                }
            }
        }
    }

    void dfs(vector<vector<char>>& grid,vector<vector<bool>>& visited, int i, int j){
        visited[i][j] = true;
        for(int k=0;k!=4;++k){
            int xx = i + dx[k], yy = j + dy[k];
            if(xx>=0 && xx<grid.size() && yy>=0 && yy<grid[0].size()
            && grid[xx][yy]=='1'&&visited[xx][yy]==false){
                dfs(grid,visited,xx,yy);
            }
        }
        return;
    }
};

进阶：使用并查集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
//并查集模板
class UF{ //注意class的最后需要";"
private:
    int count;            // 数目  
    vector<int> parent;   // 一维数组，父结点集合
    vector<int> rank;     // 秩（优化用），表示树的深度，如果两个秩相同的树合并，深度会加一
    vector<int> size;
public:
	// 并查集初始化：初始构造函数 主要初始化3个私有成员
    UF(int n):count(n),parent(n,-1),rank(n,0),size(n,1){
        iota(begin(parent), end(parent), 0);
    }
	// 查 (找结点所在树的根节点) 如1->2->3->5  find(1) 得到 5
    int find(int x){
        // （1）路径压缩 优化 （也可以用循环实现）
        // 所有子结点全部指向根节点 减少树的深度 但开销较大 不推荐
        // if(x!=parent[x]){
        //     parent[x] = find(parent[x]);
        // }
        // return parent[x];

        // （2）路径减半 优化 （使循环更快）
		// 使路径上每隔一个节点就指向其祖父节点(parent的parent)
		// 以 1->2->3->4->5 为例  若find(1) 路径查找优化为
		// 1->3->5 路径减半 减少树的深度 
        while(x!=parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
	// 并 (一个结点树并到另一个结点树上)
    void unite(int x1, int x2){
		// 使用秩优化 按秩合并 避免合成后变成单链表 O(n)复杂度
		// 找到 x1 和 x2两个树的根结点
        int f1 = find(x1);
        int f2 = find(x2);
		// 不相等才合并 相等就不需要合并了 证明在一棵树上
        if(f1!=f2){
		    // 秩f1>f2 f1长一些 把f2的树并在f1上 秩不增加 树总深度不变深
            if(rank[f1]>rank[f2]){
                parent[f2] = f1;  // 理解为 f2->f1
            }
            else{
		        // 秩f1<=f2 把f1的树并在f2上
                parent[f1] = f2;  // f1->f2
		        // 若 秩f1=f2 合并后秩会+1
		        // 例： f1:1->2  f2:3<-4   合： 1->2->3<-4 
                if(rank[f1]==rank[f2]){
                    rank[f2]++ ;
                }
            }
		    // 合并成一块 减去一个数量 很重要！
           --count;
        }
    }
    int get_count() const{
        return count;
    }
    int getSize(int x){
        return size[find(x)];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int numIslands(vector<vector<char>>& grid) {
        int row = grid.size(),col=grid[0].size();
        UF uf = UF(row*col);
        vector<int> dx = {1,-1,0,0}, dy = {0,0,1,-1};
        int num_0 = 0;
        for(int i=0;i!=row;++i){
            for(int j=0;j!=col;++j){
                if(grid[i][j]=='0') {
                    ++num_0;
                    continue;
                }

                for(int k=0;k!=4;++k){
                    int x = i+dx[k],y = j+dy[k];
                    if(x>=0 && x<row && y>=0 && y<col && grid[x][y]=='1'){
                        uf.unite(i*col+j, x*col+y);
                    }
                }
            }
        }
        return uf.get_count() - num_0;
    }
};

最长回文子串

中心扩散枚举（也算暴力解了，时间复杂度O(n^2)）

注意分类：当以一个char为中心和以两个char为中心时分开算， 然后可以发现以一个char为中心的情况其实可以和两个char为中心的情况合并，即 index1 = index2 = i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
class Solution {
public:
    string longestPalindrome(string s) {
        int start = 0, end = 0;
        for(int i=0; i!=s.size();++i){
            auto [left, right] = expand(s, i);
            if(right - left > end - start){
                end = right;
                start = left;
            }
            if(i>=1 && s[i-1]==s[i]){
                auto [left, right] = expand(s, i-1, i);
                if(right - left > end - start){
                    end = right;
                    start = left;
                }
            }
        }
        return s.substr(start, end - start + 1);
    }
    //以一个char为中心
    pair<int, int> expand(string s, int mid){
        int left = mid-1, right = mid + 1;
        pair<int,int> result{mid,mid};
        while(left>=0 && right<s.size()){
            if(s[left]==s[right]){
                result.first = left;
                result.second = right;
            }
            else{
                break;
            }
            --left;
            ++right;
        }
        return result;
    }
    //以两个char为中心
    pair<int, int> expand(string s, int index1, int index2){
        int left = index1-1, right = index2+1;
        pair<int,int> result{index1, index2};
        while(left>=0 && right<s.size()){
            if(s[left]==s[right]){
                result.first = left;
                result.second = right;
            }
            else{
                break;
            }
            --left;
            ++right;
        }
        return result;
    }
};

最近公共节点

偏暴力的解法：对于每个节点都要做dfs找是否目标p q节点位于左右节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        //关键:找到左子树和右子树分别包含节点p和q的第一个父节点
        if(root == nullptr) return nullptr;
        if(root == p || root == q) return root;
        bool findLeftP = find(root->left, p);
        bool findLeftQ = find(root->left, q);
        bool findRightP = !findLeftP; //不为根节点，则非左即右
        bool findRightQ = !findLeftQ;
        if(findLeftP && findLeftQ){
            //在左子树找
            return lowestCommonAncestor(root->left, p, q);
        }
        else if(findRightP && findRightQ){
            //在右子树找
            return lowestCommonAncestor(root->right, p, q);
        }
        //如果分别位于左右子树中，则root即为最近公共节点
        return root;
    }
    //find函数在以root为根节点的树中寻找是否有node节点
    bool find(TreeNode* root, TreeNode* node){
        if(root == nullptr) return false;
        if(root == node) return true;
        return find(root->left,node) || find(root->right,node);
    }
};

优化后的解法（不易理解）：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == nullptr || root == p || root == q) return root;
        TreeNode *left = lowestCommonAncestor(root->left, p, q);
        TreeNode *right = lowestCommonAncestor(root->right, p, q);
        if(left == nullptr && right == nullptr) return nullptr; // 1.
        if(left == nullptr) return right; // 3.
        if(right == nullptr) return left; // 4.
        return root; // 2. if(left != null and right != null)
    }
};

合并两个有序数组

空间复杂度O(1)的解法：双指针，从后往前

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        if(nums2.empty()) return;
        //双指针，从后向前，把大的放在最后
        int index1 = m-1, index2 = n-1;
        int count = m+n-1;
        while(index1>=0 || index2>=0){
            if(index1<0) 
                nums1[count--] = nums2[index2--];
            else if(index2<0) 
                nums1[count--] = nums1[index1--];
            else if(nums1[index1]>nums2[index2]) 
                nums1[count--] = nums1[index1--];
            else
                nums1[count--] = nums2[index2--];
        }
    }
};

合并区间

思路：排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        //按第一个数从小到大排序，相等时按第二个数从大到小排序
        sort(intervals.begin(),intervals.end(),[](vector<int>& stage1, vector<int>& stage2)->bool{
            if(stage1[0] != stage2[0]) return stage1[0]<stage2[0];
            
            return stage1[1]>stage2[1];
        });
        vector<vector<int>> result;
        vector<int> stage = intervals[0];
        for(int i=1;i!=intervals.size();++i){
            if(stage[1]>=intervals[i][0]){
                stage[1] = max(stage[1],intervals[i][1]);
            }
            else{
                result.push_back(stage);
                stage = intervals[i];
            }
        }
        result.push_back(stage);
        return result;
    }
};

全排列

递归版本：思想是回溯，要注意回退状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<bool> visited(nums.size(),false);
        vector<int> path;
        dfs(nums, visited, path);
        return result;
    }
    void dfs(vector<int>& nums, vector<bool>& visited, vector<int>& path){
        if(path.size() == nums.size()){
            result.push_back(path);
            return;
        }
        //回溯的思想，注意回退状态
        for(int i=0;i!=nums.size();++i){
            if(visited[i] == false){
                visited[i] = true;
                path.push_back(nums[i]);
                dfs(nums, visited, path);
                path.pop_back();
                visited[i] = false;
            }
        }
    }
private:
    vector<vector<int>> result;
};

迭代版本（面试遇到过，没写出来。思路完全不同，要通过实现“下一个排列”，来记录所有可能值）

下一个排列：从后往前搜索数组，找到第一个逆序对。如<3,4,7,6,5>中4是第一个出现逆序的。将4置换为<7,6,5>中比4大且最小的那个数（即5），数组变为<3,5,7,6,4>。再将<7,6,4>部分升序排列（实际上反转就是排序）即可，变为<3,5,4,6,7>即为下一个排列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<int> tempNums = nums;
        do{
            result.push_back(tempNums);
            nextState(tempNums);
        } while(tempNums != nums);
        return result;
    }
    void nextState(vector<int>& nums){
        for(int i=nums.size()-1;i>=0;--i){
            if(i > 0 && nums[i] <= nums[i-1]) continue;
            else if(i == 0){
                reverse(nums.begin(),nums.end());
            }
            else{
                //i为从右往左第一个峰值
                for(int j = nums.size()-1; j >= i; --j){
                    if(nums[j]>nums[i-1]){
                        int temp = nums[i-1];
                        nums[i-1] = nums[j];
                        nums[j] = temp;
                        break;
                    }
                }
                reverse(nums.begin()+i,nums.end());
                //注意这个break不要漏下
                break;
            }
        }
    }
private:
    vector<vector<int>> result;
};

合并k个升序链表

思路1：顺序两两合并链表

思路2：分治两两合并链表（多一层递归）

思路3：使用优先队列（注意要使用小根堆并手写比较结构cmp重载括号）（默认为大根堆，less<T>)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * 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) {}
 * };
 */
struct cmp{
    bool operator() (ListNode* node1, ListNode* node2){
        return node1->val > node2->val;
    }
};
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size()==0) return nullptr;
        if(lists.size()==1) return lists[0];
        //思路1：两两合并，直到只有一个链表 132ms
        // ListNode* result = lists[0];
        // for(int i=1;i!=lists.size();++i){
        //     result = mergeTwoList(result, lists[i]);
        // }

        //思路2：分治合并 24ms
        //ListNode* result = merge(lists,0,lists.size()-1);

        //思路3：优先队列存储节点（需要自定义comp）
        ListNode* result = new ListNode();
        ListNode* cur = result;
        priority_queue<ListNode*, vector<ListNode*>, cmp> pq;
        for(ListNode* node:lists){
            if(node!=nullptr){
                pq.push(node);
            }
        }
        while(!pq.empty()){
            auto node = pq.top();
            pq.pop();
            cur->next = node;
            cur = cur->next;
            if(node->next!=nullptr){
                pq.push(node->next);
            }
        }
        return result->next;
    }

    ListNode* merge(vector<ListNode*>& lists, int left, int right){
        if(right < left) return nullptr;
        if(right -left <=1) return mergeTwoList(lists[left],lists[right]);
        int mid = left + ((right - left) >> 1);
        ListNode* leftList = merge(lists, left, mid - 1);
        ListNode* rightList = merge(lists,mid, right);
        return mergeTwoList(leftList, rightList);
    }

    ListNode* mergeTwoList(ListNode* first, ListNode* second){
        if(first == second) return first;
        ListNode* cur1 = first, *cur2 = second;
        ListNode* dummyNode = new ListNode();
        ListNode* pre = dummyNode;
        while(cur1!=nullptr && cur2!=nullptr){
            if(cur1->val <= cur2->val){
                pre->next = cur1;
                cur1 = cur1->next;
            }else{
                pre->next = cur2;
                cur2 = cur2->next;
            }
            pre = pre->next;
        }
        if(cur1 != nullptr) pre->next = cur1;
        if(cur2 != nullptr) pre->next = cur2;
        return dummyNode->next;
    }
};

打印螺旋矩阵

关键思路：定义四个边界，从外向内一层层遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        //定义上下左右四个边界
        int left = 0, right = matrix[0].size()-1, up = 0, down = matrix.size()-1;
        vector<int> result;
        while(right>=left && down>=up){
            //注意：如果出现任何一个if不满足，则说明已经全部遍历完，直接break
            //不要忘记break这一步，否则会出现重复包含的情况，如3*3时中心元素被遍历了两次
            if(right >= left){
                //上左到上右
                for(int i = left; i <= right; ++i){
                    result.push_back(matrix[up][i]);
                }
                ++up;
            } else break;
            if(down >= up){
                //上右到下右
                for(int i = up; i <= down; ++i){
                    result.push_back(matrix[i][right]);
                }
                --right;
            } else break;
            if(right >= left){
                //下右到下左
                for(int i = right; i >= left; --i){
                    result.push_back(matrix[down][i]);
                }
                --down;
            } else break;
            if(down >= up){
                //下左到上左
                for(int i = down; i >= up; --i){
                    result.push_back(matrix[i][left]);
                }
                ++left;
            } else break;
        }
        return result;
    }
};

字符串相加

注意在处理完后记得判断flag是否有进位，要加在result最后

再将result反转

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    string addStrings(string num1, string num2) {
        int flag = 0;
        int right1 = num1.size()-1, right2 = num2.size()-1;
        string result;
        while(right1>=0 || right2>=0){
            int sum = flag;
            if(right1>=0){
                sum+=num1[right1] - '0';
                --right1;
            }
            if(right2>=0){
                sum+=num2[right2] - '0';
                --right2;
            }
            char c = sum+'0';
            if(sum>=10){
                c -= 10;
                flag=1;
            } else {
                flag = 0;
            }
            result+=c;
        }
        if(flag==1) result+='1'; 
        reverse(result.begin(),result.end());
        return result;
    }
};

链表相加

同样注意不要忘记最后的进位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* cur1 = l1, *cur2 = l2;
        ListNode* result = new ListNode(-1);
        ListNode* cur = result;
        int flag=0;
        int *p = &flag;
        while(cur1!=nullptr || cur2 != nullptr){
            cur->next = addSingle(cur1,cur2,p);
            if(cur1!=nullptr) cur1 = cur1->next;
            if(cur2!=nullptr) cur2 = cur2->next;
            cur = cur->next;
        }
        if(flag==1){
            ListNode* last = new ListNode(1);
            cur->next = last;
        }
        return result->next;
    }
    ListNode* addSingle(ListNode* l1, ListNode* l2, int* p){
        int sum = *p;
        if(l1 != nullptr) sum += l1->val;
        if(l2 != nullptr) sum += l2->val;
        if(sum >= 10){
            sum -= 10;
            *p = 1;
        }else{
            *p = 0;
        }
        ListNode* node = new ListNode(sum);
        return node;
    }
};

最长递增子序列

常规思路：

dp数组存储以当前 nums[i] 为结尾的递增子序列的最大长度，内层for循环找比nums[i]小的nums[j]对应的dp[j]，更新dp[j]的最大值+1到dp[i]中

时间复杂度O(n^2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> dp(nums.size(),1);
        for(int i=0;i!=nums.size();++i){
            for(int j=0;j!=i;++j){
                if(nums[j]<nums[i]){
                    dp[i] = max(dp[i],dp[j]+1);
                }
            }
        }
        int result = *max_element(dp.begin(),dp.end());
        return result;
    }
};

精妙思路：二分+贪心

考虑一个简单的贪心，如果我们要使上升子序列尽可能的长，则我们需要让序列上升得尽可能慢，因此我们希望每次在上升子序列最后加上的那个数尽可能的小。

基于上面的贪心思路，我们维护一个数组 d[i]，表示长度为 ii 的最长上升子序列的末尾元素的最小值，用 len 记录目前最长上升子序列的长度，起始时 len 为 1，d[1]=nums[0]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        vector<int> result;
        result.push_back(nums[0]);
        for(int i=1;i!=nums.size();++i){
            //if(nums[i] == result.back()) continue;
            if(nums[i] > result.back()){
                result.push_back(nums[i]);
                continue;
            }
            //手写二分，也可用C++标准库的lower_bound()代替(找到范围内大于等于target的最小值， upper_bound()不包含等于)
            //int index = lower_bound(result.begin(),result.end(),nums[i]) - result.begin();
            int index = binarySearch(result, nums[i]);
            result[index] = nums[i];
        }
        return result.size();
    }
    int binarySearch(vector<int>& nums, int target){
        //二分找到大于等于target的最小值
        int left = 0, right = nums.size()-1;
        while(right > left){
            int mid = left + (right-left)/2;
            if(nums[mid] >= target) right = mid;
            else left = mid+1;
        }
        //出循环时left==right
        return right;
    }
};

注意二分查找的常见写法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left = 0, right = nums.size()-1;
        //第一种写法
        // while(right >= left){
        //     int mid = left + (right - left) /2;
        //     if(nums[mid] > target) right = mid - 1;
        //     else if(nums[mid] < target) left = mid + 1;
        //     else return mid;
        // }

        //第二种写法
        right = nums.size();
        while(right> left){
            int mid = left + (right - left)/2;
            if(nums[mid] > target) right = mid;
            else if(nums[mid] < target) left = mid + 1;
            else return mid;
        }
        return -1;
    }
};

最长排序连续上升子段

（深信服面试题）给一个长度为n的数组，求出最大排序连续上升子段的长度

注意题意是指该子段元素在经过排序后是严格递增的，并且两两之间相差1

如 3 1 2 4 6 最长子段长度为4 （3 1 2 4可以排序组成 1 2 3 4 是连续上升的）

思路：双指针 i，j 区间满足 j - i == maxNum - minNum即满足要求

接雨水

常规思路：

对于每一个柱子接的水，那么它能接的水 = min(左右两边最高柱子）- 当前柱子高度

因此可以通过两次动态规划（从左到右，从右到左）分别记录每根柱子左右两边最高的柱子

也可以用单调栈做（还没仔细研究这种方法）

我这里用了一种比较取巧的分析图形的方法 result = S1 + S2 - Stotal - Sshadow，注意用long long存储面积结果否则会溢出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int trap(vector<int>& height) {
        int h = 0;
        long long shadow = 0;
        long long S1 = 0, S2 = 0;
        for(int i=0;i!=height.size();++i){
            shadow += height[i];
            h = max(h,height[i]);
            S1 += h;
        }
        int tempMax = 0;
        for(int i=height.size()-1; i>=0;--i){
            tempMax = max(tempMax, height[i]);
            S2 += tempMax;
        }
        return S1 + S2 - h*height.size() - shadow;
    }
};

二叉树中最大路径和

关键：

  1. 理清递归思路： dfs返回的是以当前节点为头的最大路径和，在函数体中间会对题意要求的最大路径和进行更新
  2. 注意最大路径放在外面进行更新
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxPath = INT_MIN;
    int maxPathSum(TreeNode* root) {
        dfs(root);
        return maxPath;
    }
    int dfs(TreeNode* root){
        //返回以该节点为头时最大的路径
        if(root == nullptr) return 0;
        int left = max(dfs(root->left),0);
        int right = max(dfs(root->right),0);
        //更新包含该节点（不止为头，也可以在中间）时的最大路径
        maxPath = max(maxPath, left+right+root->val);
        return max(left,right)+root->val;
    }
};

栈实现队列

思路：构建两个栈，一个用于存放输入，一个用于存放输出，当pop时如果输出栈为空，则将输入栈元素一次性push到输出栈中

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class MyQueue {
public:
    MyQueue() {

    }
    
    void push(int x) {
        inStack.push(x);
    }
    
    int pop() {
        if(outStack.empty()){
            while(!inStack.empty()){
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        int result = outStack.top();
        outStack.pop();
        return result;
    }
    
    int peek() {
        if(outStack.empty()){
            while(!inStack.empty()){
                outStack.push(inStack.top());
                inStack.pop();
            }
        }
        return outStack.top();
    }
    
    bool empty() {
        return (inStack.size()+outStack.size() == 0);
    }
private:
    stack<int> inStack, outStack;
};

编辑距离

给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数 。

你可以对一个单词进行如下三种操作：

  • 插入一个字符
  • 删除一个字符
  • 替换一个字符

思路：动态规划

  • 有word1和word2，我们定义dp[i][j]的含义为：word1的前i个字符和word2的前j个字符的编辑距离。意思就是word1的前i个字符，变成word2的前j个字符，最少需要这么多步。

    • 例如word1 = "horse", word2 = "ros"，那么dp[3][2]=X就表示”hor”和“ro”的编辑距离，即把”hor”变成“ro”最少需要X步。
    • 如果下标为零则表示空串，比如：dp[0][2]就表示空串””和“ro”的编辑距离

  • 定理一：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。比如空串“”和“ro”的编辑距离是2（做两次“插入”操作）。再比如”hor”和空串“”的编辑距离是3（做三次“删除”操作）。

  • 定理二：当i>0,j>0时（即两个串都不空时）dp[i][j] = min(dp[i-1][j] + 1,dp[i][j-1] + 1, dp[i-1][j-1] + int(word1[i] != word2[j]))。

    • 举个例子，word1 = "abcde", word2 = "fgh",我们现在算这俩字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：

      • 知道”abcd”变成”fgh”多少步（假设X步），那么从”abcde”到”fgh”就是”abcde”->”abcd”->”fgh”。（一次删除，加X步，总共X+1步）
      • 知道”abcde”变成“fg”多少步（假设Y步），那么从”abcde”到”fgh”就是”abcde”->”fg”->”fgh”。（先Y步，再一次添加，加X步，总共Y+1步）
      • 知道”abcd”变成“fg”多少步（假设Z步），那么从”abcde”到”fgh”就是”abcde”->”fge”->”fgh”。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）

    • 以上三种方式算出来选最少的，就是答案。所以定理二可以表现为：

    • ```C++
      dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))
      dp[i-1][j]：情况一
      dp[i][j-1]+1：情况二
      dp[i-1][j-1]+int(word1[i]!=word2[j])：情况三

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26

      有了定理二的递推公式，你就建立一个二维数组，考虑好空串的情况，就能写出来

      ```C++
      class Solution {
      public:
          int minDistance(string word1, string word2) {
              int len1 = word1.size(), len2 = word2.size();
              if(len1 == 0) return len2;
              if(len2 == 0) return len1;
              //dp[i][j]表示word1的前i个字符和word2的前j个字符的编辑距离
              vector<vector<int>> dp(len1+1, vector<int>(len2+1,INT_MAX));
              for(int i=0;i<=len1;++i){
                  dp[i][0] = i;
              }
              for(int j=0;j<=len2;++j){
                  dp[0][j] = j;
              }
              for(int i=1;i<=len1;++i){
                  for(int j=1;j<=len2;++j){
                      dp[i][j] = min(dp[i-1][j]+1,min(dp[i][j-1]+1,dp[i-1][j-1]+(word1[i-1]!=word2[j-1] ? 1:0)));
                  }
              }
              return dp[len1][len2];
          }
      };

x的平方根

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l) / 2;
            if ((long long)mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
};

删除链表中所有重复元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        ListNode* cur = head;
        ListNode* dummyNode = new ListNode(-1,head);
        ListNode* pre = dummyNode;
        while(cur!=nullptr && cur->next != nullptr){
            if(cur->val == cur->next->val){
                int val = cur->val;
                while(cur!=nullptr && cur->val == val){
                    cur = cur->next;
                }
                pre->next =cur;
            }
            else{
                cur = cur->next;
                pre = pre->next;
            }
        }
        return dummyNode->next;
    }
};

括号生成

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

思路：回溯

关键是要理清一个逻辑：当左括号数量大于右括号时，才可加右括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
    vector<string> generateParenthesis(int n) {
        //左括号的数量大于右括号，才能加右括号
        dfs(n,0,0);
        return result;
    }

private:
    void dfs(int n, int leftNum, int rightNum){
        if(rightNum==n && leftNum==n) {
            result.push_back(path);
            return;
        }
        if(leftNum<n){
            path.push_back('(');
            dfs(n, leftNum+1, rightNum);
            path.pop_back();
        }
        if(leftNum<=n && rightNum<n && rightNum<leftNum){
            path.push_back(')');
            dfs(n, leftNum, rightNum+1);
            path.pop_back();
        }
    }
    string path;
    vector<string> result;
};

缺失的第一个正数

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        //遍历一次数组把大于等于1的和小于数组大小的值放到原数组对应位置
        //然后再遍历一次数组查当前下标是否和值对应
        //如果不对应那这个下标就是答案，否则遍历完都没出现那么答案就是数组长度加1。
        for(int i=0;i!=nums.size();++i){
            while(nums[i]>=1 && nums[i]<=nums.size() && nums[i] != i+1){
                if(nums[i] == nums[nums[i]-1]) break;
                swap(nums[i],nums[nums[i]-1]);
            }
        }
        for(int i=0;i!=nums.size();++i){
            if(nums[i]!=i+1)
            return i+1;
        }
        return nums.size()+1;
    }
};

最长公共子序列

给定两个字符串 text1 和 text2，返回这两个字符串的最长 公共子序列 的长度。如果不存在 公共子序列 ，返回 0 。

思路：

二维动态规划，创建(m+1)*(n+1)大小的dp数组，dp[i][j]表示 string1的前i个字符 和string2的前j个字符的最长公共子序列长度

  • 考虑动态规划的边界情况：

    空字符串和任何字符串的最长公共子序列的长度都是 0，因此边界为0

  • 递推关系（状态转移方程）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int longestCommonSubsequence(string text1, string text2) {
        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));
        for(int i = 1; i != text1.size()+1;++i){
            for(int j = 1; j != text2.size()+1;++j){
                dp[i][j] = max(dp[i-1][j],dp[i][j-1]);
                if(text1[i-1] == text2[j-1]){
                    dp[i][j] = max(dp[i][j], dp[i-1][j-1]+1);
                }
            }
        }
        return dp[text1.size()][text2.size()];
    }
};

复原IP地址

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。

方法1：三重循环（暴力解）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    vector<string> restoreIpAddresses(string s) {
        if(s.size()>12||s.size()<4) return {};
        vector<string> result;
        //i,j,k表示在s[i]/s[j]/s[k]"前"进行分割
        for(int i=1;i!=s.size()-2;++i){
            if(!isValid(s.substr(0,i))) continue;
            for(int j=i+1;j!=s.size()-1;++j){
                if(!isValid(s.substr(i,j-i))) continue;
                for(int k = j+1;k!=s.size();++k){
                    if(!isValid(s.substr(j,k-j))) continue;
                    if(!isValid(s.substr(k,s.size()-k))) continue;
                    string res = s.substr(0,i) + '.' + s.substr(i,j-i) + '.' + s.substr(j,k-j) + '.' + s.substr(k,s.size()-k); 
                    result.push_back(res);
                }
            }
        }
        return result;
    }
private:
    bool isValid(string s){
        if(s.empty()) return false; 
        if(s[0]=='0' && s.size()!=1) return false;
        if(s.size()>=4) return false;
        if(stoi(s)>255) return false;
        return true;
    }
};

方法2：递归回溯

滑动窗口的最大值

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值

方法一：优先队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        priority_queue<pair<int,int>,vector<pair<int,int>>,less<pair<int,int>>> pq;
        vector<int> result;
        for(int i=0;i!=k;++i){
            pq.push({nums[i],i});
        }
        result.push_back(pq.top().first);
        for(int i=k;i!=nums.size();++i){
            pq.push({nums[i],i});
            while(!pq.empty() && pq.top().second<=i-k){
                pq.pop();
            }
            result.push_back(pq.top().first);
        }
        return result;
    }
};

方法二：利用双向数组构造单调队列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //按顺序维护一个单调非递增的数组，并且保证头元素在(i-k,i]内
        deque<pair<int,int>> dq;
        vector<int> result;
        for(int i=0;i!=k;++i){
            while(!dq.empty() && dq.back().first<nums[i]){
                dq.pop_back();
            }
            dq.push_back({nums[i],i});
        }
        result.push_back(dq.front().first);
        for(int i=k;i!=nums.size();++i){
            if(dq.front().second<=i-k) dq.pop_front();
            while(!dq.empty() && dq.back().first<nums[i]){
                dq.pop_back();
            }
            dq.push_back({nums[i],i});
            result.push_back(dq.front().first);
        }
        return result;
    }
};

进一步优化可以不在deque中使用pair，而是只储存索引。

从前序和中序遍历序列构造二叉树

思路：

（1）明白前序遍历的第一个节点永远是根节点

（2）用哈希表记录中序遍历中每个节点值对应的索引位置

（3）结合（1）（2）可知根节点在中序遍历中的位置，从而可以知道左子树和右子树的大小

（4）递归地进行左右子树的构建，函数返回根节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    unordered_map<int,int> mp;      //{value, index in inorder array}
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n = preorder.size();    //两个数组长度相等
        for(int i=0;i!=inorder.size();++i){
            mp[inorder[i]] = i;
        }
        TreeNode* root = rebuild(preorder,inorder,0,n-1,0,n-1);
        return root;
    }

private:
    //函数入参表示要构建 前序遍历数组中[pl,pr]范围 对应的中序遍历数组 [il,ir]范围的树
    TreeNode* rebuild(vector<int>& pv,vector<int>& iv,int pl,int pr, int il, int ir){
        //注意不要落下递归的终止条件
        if(pr<pl) return nullptr;
        //前序遍历的第一个节点即为根节点
        TreeNode* root = new TreeNode(pv[pl]);
        //在中序遍历中找到对应根节点，即可知道左子树的大小,也即可以得到右子树的范围
        int leftsize = mp[pv[pl]] - il;
        root->left = rebuild(pv,iv,pl+1,pl+leftsize,il,il+leftsize-1);
        root->right = rebuild(pv,iv,pl+leftsize+1,pr,il+leftsize+1,ir);
        return root;
    }
};

从中序遍历和后序遍历序列构造二叉树

思路近似，都是要计算出左右子树的大小，然后进行递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    unordered_map<int,int> mp;      //{value, index in inorder array}
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        int n = inorder.size();    //两个数组长度相等
        for(int i=0;i!=inorder.size();++i){
            mp[inorder[i]] = i;
        }
        TreeNode* root = rebuild(inorder,postorder,0,n-1,0,n-1);
        return root;
    }
private:
    TreeNode* rebuild(vector<int>& iv,vector<int>& pv,int il,int ir, int pl, int pr){
        //注意不要落下递归的终止条件
        if(ir<il) return nullptr;
        //后序遍历的最后一个节点即为根节点
        TreeNode* root = new TreeNode(pv[pr]);
        //在中序遍历中找到对应根节点，即可知道左子树和右子树的大小
        int leftsize = mp[pv[pr]] - il;
        root->left = rebuild(iv,pv,il,il+leftsize-1,pl,pl+leftsize-1);
        root->right = rebuild(iv,pv,il+leftsize+1,ir,pl+leftsize,pr-1);
        return root;
    }
};

判断是否为平衡二叉树

一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
 //自顶向下,复杂度高，对于每一个节点都要搜索一遍对应的左右子树
// class Solution {
// public:
//     int count=0;
//     bool isBalanced(TreeNode* root) 
//     {
//         if(root==nullptr)  return true;
//         int depth=abs(height(root->left)-height(root->right));
//         return (depth<=1) && (isBalanced(root->left)) && (isBalanced(root->right));
//     }
//     int height(TreeNode* root)
//     {
//         if(root==nullptr)  return 0;
//         return max(height(root->left), height(root->right))+1;
//     }
// };


//自底向上
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        return height(root) != -1;
    }
    int height(TreeNode* node){
        if (node == nullptr) return 0;
        int left = height(node->left);
        if(left == -1) return -1;
        int right = height(node->right);
        if(right == -1) return -1;
        return abs(left-right)>1 ? -1 : max(left,right)+1;
    }
};

零钱兑换

思路：动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        sort(coins.begin(),coins.end());
        vector<int> dp(amount+1,INT_MAX);//记录组成金额i所需要的最少硬币数量
        dp[0]=0;
        for(int i=0;i!=dp.size();++i){
            for(int j=0;j!=coins.size();++j){
                if(i - coins[j] < 0) break;
                if(i - coins[j] >=0 && dp[i-coins[j]] != INT_MAX){
                    dp[i] = min(dp[i], dp[i-coins[j]]+1); 
                }
            }
        }
        return dp[amount] == INT_MAX ? -1 : dp[amount];  
    }
};

最小栈

思路：用两个栈存储，一个栈正常push数，一个栈push单调递减的子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class MinStack {
public:
    MinStack() {

    }
    
    void push(int val) {
        stkNums.push(val);
        if(stkMin.empty() || val <= stkMin.top()){
            stkMin.push(val);
        }
    }
    
    void pop() {
        if(stkNums.top()==stkMin.top()) stkMin.pop();
        stkNums.pop();
    }
    
    int top() {
        return stkNums.top();
    }
    
    int getMin() {
        return stkMin.top();
    }
private:
    stack<int> stkMin;
    stack<int> stkNums;
};

对称二叉树

递归思路：

写一个check函数，传入左子节点和右子节点，进行一系列判断

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        return check(root->left,root->right);
    }
    bool check(TreeNode* leftNode, TreeNode* rightNode){
        if(leftNode == nullptr && rightNode == nullptr) 
            return true;
        if(leftNode == nullptr || rightNode == nullptr) 
            return false;
        if(leftNode->val != rightNode->val) 
            return false;
        if(check(leftNode->left,rightNode->right) && check(leftNode->right,rightNode->left)) 
            return true;

        return false;
    }
};

更改为迭代实现：

使用一个队列保存，并两两一组将左右子树的镜像节点push进去

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        if(root==nullptr) return true;
        queue<TreeNode*> q;
        q.push(root->left);
        q.push(root->right);
        while(!q.empty()){
            TreeNode* node1 = q.front(); q.pop();
            TreeNode* node2 = q.front(); q.pop();
            if(!node1 && !node2) continue;
            if(!node1 || !node2) return false;
            if(node1->val != node2->val) return false;
            q.push(node1->left);
            q.push(node2->right);
            q.push(node1->right);
            q.push(node2->left); 
        }
        return true;
    }
};

最长有效括号

给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    int longestValidParentheses(string s) {
        //建立一个与s等长的数组初始化为0
        //用栈模拟，将所有无法匹配的扩号置为1
        //题目就转换为数组中连续的0的最大个数

        //优化后思路
        //用栈模拟，栈中存放下标
        //在匹配"()"时可将当前下标与全部匹配完后栈顶元素下标相减得到这段的匹配长度
        //取一个最大的匹配长度

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

求数组中的多数元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        //摩尔投票法：设众数为1，其他数为-1，则所有数加起来应该大于0
        //核心：维护一个候选val和该val对应的count
        //初始count =0，candidate随意
        //遇到与candidate相同的数时 ++count，否则--count
        //当count == 0 时，更换候选candidate
        //这样最后留下的一定是众数，因为众数可以把所有其他candidate的count全部减掉还有剩余
        int candidate = nums[0];
        int count = 0;
        for(int i=0;i!=nums.size();++i){
            if(nums[i] == candidate){
                ++count;
            }
            else{
                --count;
                if(count == 0){
                    candidate = nums[i];
                    count =1;
                }
            }
        }
        return candidate;
    }
};
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2022 ZHU
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信