参考题单:
https://zhuanlan.zhihu.com/p/349940945

排序类

基础题

148 排序链表

原题链接:
https://leetcode.cn/problems/sort-list/

归并排序:

  1. 先快慢指针找到中点
  2. 切分
  3. 对子序列排序
  4. merge

1.归并排序 (TOP-DOWN 自顶向下)
把merge 拆分出去写 逻辑上更好理解一些

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
/**
 * 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* sortList(ListNode* head) {
        // 递归出口
        // 这里可能会有只有一个节点的情况 不需要排序故直接return head 而不是null
        if(!head || !head->next){
            return head;
        }

        // 这里快慢指针 这种写法是最稳的 不然会出错 
        ListNode * fast = head->next;
        ListNode * slow = head;        
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode * mid = slow->next;
        // 将链表断开 即 完成 切分  
        slow->next = nullptr;
        return merge(sortList(head),sortList(mid));
    }

    ListNode * merge(ListNode * l1,ListNode * l2){
        ListNode dummy(0);
        auto p =  &dummy;
        // 默认将l1 视为主链表
        while(l1 && l2){
            if(l1->val > l2->val){
                swap(l1,l2); 
            }
            p->next = l1;
            p = p->next;
            l1 = l1->next;
            
            // 加不加都行
            // p->next = nullptr;
        }

        if(l1){
            p->next = l1;
        }

        if(l2){
            p->next = l2;
        }

        return dummy.next;
    }
};

写法2
合在一起写 看着简洁一些 其实只是把merge的逻辑融合进去了 

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
/**
 * 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* sortList(ListNode* head) {
        if(!head || !head->next){
            return head;
        }

        ListNode * fast =  head->next;
        ListNode * slow = head;

        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode * mid = slow->next;
        slow->next = nullptr;

        ListNode * left = sortList(head);
        ListNode * right = sortList(mid);

        ListNode * dummy = new ListNode(0);
        auto p = dummy;

        while(left && right){
            if(left->val > right->val){
                swap(left,right);
            }

            p->next = left;
            p = p->next;
            left = left->next;
        }

        if(left){
            p->next = left;
        }

        if(right){
            p->next = right;
        }

        return dummy->next;
    }
};

  1. 归并排序(BOTTOM UP 自底向上)
    省去了递归的空间栈 优化了内存
    即实现了 constant space
    但代码和思维的难度都加大了

56 合并区间

原题链接:
https://leetcode.cn/problems/merge-intervals/submissions/
很经典的一道题了
虽然归类在排序 但还是在贪心里遇到的次数的多一些

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:
    vector<vector<int>> merge(vector<vector<int>>& intervals) {
        int n = intervals.size();
        sort(intervals.begin(),intervals.end(),[&](vector<int>&a,vector<int>&b){
            return a[0] < b[0];
        });

        vector<vector<int>> ans;
        for(int i=0 ; i < n ; i++){
            // 如果当前为空 或者 已处理完的区间最右边的端点 小于当前区间的左端点 则证明没有重叠直接加入即可 
            if(ans.empty() || ans.back()[1] <  intervals[i][0] ){
                ans.emplace_back(intervals[i]);
            }else{
                // 发生重叠时 右端点取最大的进行合并
                ans.back()[1] = max(ans.back()[1],intervals[i][1]);
            }
        }

        return ans;
    }
};

相似题: 插入区间57
原题链接:
https://leetcode.cn/problems/insert-interval/description/
几乎就是合并区间的思路一模一样 但是写法写出来 会有很巧妙的感觉

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>> insert(vector<vector<int>>& intervals, vector<int>& newInterval) {
        // 排新的区间也加进去一起排序
        intervals.emplace_back(newInterval);
        // sort排序 默认按照多元数组第一个值排序
        sort(intervals.begin(),intervals.end());

        // 然后合并后区间的思路走一遍
        vector<vector<int>>ans;

        for(int i = 0 ; i < intervals.size() ; i++){
            if(ans.empty() || ans.back()[1] < intervals[i][0]){
                ans.emplace_back(intervals[i]);
            }else{
                ans.back()[1] = max(ans.back()[1],intervals[i][1]);
            }
        }

        return ans; 

    }
};

当然以上是完全从合并区间 模仿而来的写法
实际上完全不需要遍历整个区间 即可以优化

优化:

27 移除元素

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 removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int i = 0, j = n - 1;
        while(i <= j  && i < n){
            if(nums[i] == val){
                swap(nums[i],nums[j]);
                // 防止换到前面的数 仍然是不符合条件的数  因此i-- 然后再判断一次 
                i--;
                j--;
            }
            i++;
        }

        // 返回是长度 所以  +1
        return j + 1; 
    }
};

进阶题

179 最大数

原题链接:
https://leetcode.cn/problems/largest-number/
这个题的解法基本没做过 就肯定出不来了
因为要求的是拼接后最大的数 那么对拼接后的效果进行比较
将ab转换为string后进行拼接 拼接后长度是一样的 所以直接比较字典序即可
然后最后要注意处理一下前导0的情况

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:
    string largestNumber(vector<int>& nums) {
        sort(nums.begin(),nums.end(),[&](int a,int b){
            string x = to_string(a);
            string y = to_string(b);
            return x + y > y + x;
        });

        string s = "";
        for(auto &ss : nums){
            s += to_string(ss);
        }

        int p = 0;
        // 最后一定还要剩余一个数 所以是s.size() - 1
        while(p < s.size() - 1 && s[p] == '0'){
            p++;
        }

        return s.substr(p);
    }
};

链表类

基础题

206 反转链表

原题链接:
https://leetcode.cn/problems/reverse-linked-list/description/

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode * pre = nullptr;
        ListNode * cur = head;
        while(cur){
            ListNode * ne = cur->next;
            cur->next = pre;
            pre = cur;   
            cur = ne ;
        }

        // 最后返回是pre 
        // 因为 pre指向的是 上一步 cur不为null 也就是cur到cur->next前的位置 
        return pre;
    }
};

876 链表的中间节点

原题链接:
https://leetcode.cn/problems/middle-of-the-linked-list/description/

快慢指针
唯一需要注意的是 这题中间节点要返回的是后面那个

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
/**
 * 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* middleNode(ListNode* head) {
        if(!head || !head->next){
            return head;
        }

        // 这种写法 即 快慢指针指向头节点的写法  有两个中间节点时返回后面那个

        ListNode * slow = head;
        ListNode * fast = head;

        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;

    }
};

扩展
返回中间两节点 返回前面那个写法

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
/**
 * 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* middleNode(ListNode* head) {
        if(!head || !head->next){
            return head;
        }

        //  这种写法 默认返回前面那个
        ListNode * slow = head;
        ListNode * fast = head->next;

        while(fast && fast->next){
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;

    }
};

summary：

  1. 中间节点返回后面那个： 快慢指针均指向首节点
  2. 中间节点返回前面那个: 快指针指向首节点 慢指针指向首节点

进阶题

160 相交链表

原题链接:
https://leetcode.cn/problems/intersection-of-two-linked-lists/

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

/*
    双指针 上下同时开始遍历 
    遍历完跳到另一条链表上遍历 如果相交那么二次遍历时会发生相交 反之不相交
*/ 

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode * p = headA;
        ListNode * q = headB;

        // 由于不相交 走完两条链表的总路程是一样的 最后一定停在nullptr的情况    
        while(p != q){
            /*
                这里第一次写成了 p->next == nullptr 这是不行的
                因为如果是p->next 那么如果两条不相交 那么p和q虽然走的路程一样 相对位置一样
                但最后都会指向链表的最后一个节点 即 始终满足 p!=q 陷入死循环
            */
            p = p == nullptr ? headB : p->next;
            q = q == nullptr ? headA : q->next;
        }

        return p;
    }
};

141 环形链表

原题链接:
https://leetcode.cn/problems/linked-list-cycle/description/

法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

/**
 * 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) {
        int x = 1e6;
        ListNode * p = head;
        while(p){
            if(p->val == x){
                return true;
            }
            p->val = x;
            p = p->next;
        }

        return false;          
    }
};

法2: 快慢指针

快慢指针
fast每次走两步 slow每一次一步
这里有个问题 fast 会不会跳过slow 从不会与 slow相遇
这是不可能的 因为如果有环的话 那么fast slow都会进入环中
从相对速度的角度进行理解 即slow不动 fast每次走一步 那么fast slow必定相遇

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
/**
 * 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) {
        ListNode * fast = head;
        ListNode * slow = head;
        while(fast && fast->next){
            fast = fast->next->next;
            slow = slow->next;

            if(fast == slow){
                return true;
            }
        }

        return false;
    }
};

92 Reverse Linked List II

原题链接:
https://leetcode.cn/problems/reverse-linked-list-ii/

反转链表的进阶

原题链接:
https://leetcode.cn/problems/reverse-linked-list-ii/description/

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
    先找到需要翻转片段的第一个节点 记录p0 为要反转部分的前一个节点 pn为最后一个节点
    则 将中间部分反转后 再将 head->pn  p0->tail 即可
 */

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummy = new ListNode(0,head);
        ListNode p0 = dummy;

        // 找到要反转部分的第一个节点
        for(int i = 0 ; i < left - 1; i++){
            p0 = p0.next;
        }

        ListNode pre = null;
        ListNode cur = p0.next;

        for(int i = 0 ; i < right - left + 1 ; i++){
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        // cur操作完后 位于反转部分的后一个位置 
        // pre才在反转部分的最后一个位置
        
        // 顺序不能换 否则p0.next.next就找不到了

        // p0为反转部分第一个节点的前一个节点
        // p0.next反转部分的第一个节点 在反转后位于最后的位置
        // p0.next.next 将反转部分最后接在 cur 
        p0.next.next = cur;

        // p0 反转部分的前一个位置 将其与反转部分的最后一个位置直接相连
        p0.next = pre;
        
        return dummy.next;
    }
}

328 奇偶链表

原题链接:
https://leetcode.cn/problems/odd-even-linked-list/

要求O(1)空间 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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

/**
    遍历的同时 不断将偶数节点加入偶数的链表 同时删除链表的偶数节点
    最后将原链表尾部与 新链表直接拼接即可
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        ListNode oddDummy = new ListNode();
        ListNode oddTail = oddDummy;
        ListNode evenDummy = new ListNode();
        ListNode evenTail = evenDummy;

        boolean isOdd = false;

        while(head != null){
            // 奇数节点
            if(!isOdd){
                oddTail.next = head;
                oddTail = oddTail.next;
            }else{
                evenTail.next = head;
                evenTail = evenTail.next;
            }

            head = head.next;
            isOdd = !isOdd;
        }

        oddTail.next = evenDummy.next;
        evenTail.next = null;
            
        return oddDummy.next;
    }
}

堆、栈、队列、哈希表类

基础题 Queue

leetcode225 用队列实现栈

原题链接:
https://leetcode.cn/problems/implement-stack-using-queues/

双队列 q1 q2
q1直接视为栈的顺序 q2用于辅助q1在进行加入删除元素操作时 始终仍为栈的顺序

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
/**
    栈 先进后出
    队列 先进先出
    
    一个队列进行入栈 一个队列进行出栈

    java 队列 统一用 offer() 和 poll() 和 peek()
 */
class MyStack {
    Queue<Integer>q1;
    Queue<Integer>q2;

    public MyStack() {
        q1 = new LinkedList<Integer>();
        q2 = new LinkedList<Integer>();
    }
    
    /**
        每次push时 由于队列时先进先出
        将q1队列内的元素 按顺序push到q2中 那么对于而言由于q2也是先进先出 那么相同元素在q2中的出队顺序就是q1中先进后出
        即实现了栈的效果
     */

     /**
        q1 : 1 2 3 4 5
        q2 : 5 4 3 2 1
        s :  5 4 3 2 1      
      */
    public void push(int x) {
        // 根据栈的定义最后一个入栈的元素 最先出栈
        // 暂存q2 的队头 在q2中最后出 推入q1后变为最先出
        q2.offer(x);

        while(!q1.isEmpty()){
            q2.offer(q1.poll());
        }
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    
    /**
        q1直接理解就是栈的顺序
        q2用于帮助q1实现栈
     */
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

leetcodeLCR041 数据流中的移动平均值

队列 按照题意模拟即可

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 MovingAverage {
public:
    queue<int>q;
    int s;
    double cur = 0;
    /** Initialize your data structure here. */
    MovingAverage(int size) {
        s = size;
    }
    
    double next(int val) {
        q.push(val);
        cur += val;
        if(q.size() > s){
            cur -= q.front();
            q.pop();
        }

        return cur / q.size();
    }
};

/**
 * Your MovingAverage object will be instantiated and called as such:
 * MovingAverage* obj = new MovingAverage(size);
 * double param_1 = obj->next(val);
 */

leetcode54 螺旋矩阵

原题链接:
https://leetcode.cn/problems/spiral-matrix/

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<int> spiralOrder(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<int> ans;
        // 程序里面 向下走为+1 向上走才是+1
        int dx[4] = {0,1,0,-1};
        int dy[4] = {1,0,-1,0};
        int d = 0;
        for(int x = 0, y = 0, k = 0; k < n * m ; k++ ){        
            ans.push_back(matrix[x][y]);
            matrix[x][y] = -1e9;
            int a = x + dx[d];
            int b = y + dy[d];
  
            if(a >= m || b >= n || a < 0 || b < 0 || matrix[a][b] == -1e9){
                d = (d + 1) % 4;
                a = x + dx[d];
                b = y + dy[d];
            }
            
            x = a;
            y = b;
            
        }

        return ans;
    }
};
};

基础题 Stack

leetcode155 最小栈

原题链接:
https://leetcode.cn/problems/min-stack/description/

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
/**
    辅助栈维护最小元素
    如果当前元素比 辅助栈栈顶元素小 则 入栈该元素 否则再次入栈辅助栈顶元素
    从而保证辅助栈的元素 始终与主栈同步
*/
class MinStack {
public: 
    stack<int>stk;
    stack<int>helper;

    MinStack() {
        // 否则第一次没法判断  
        helper.push(INT_MAX);
    }
    
    void push(int val) {
        stk.push(val);
        if(val < helper.top()){
            helper.push(val);
        }else{
            helper.push(helper.top());
        }
    }
    
    // 题目规定操作是在非空栈上执行 
    // 因此不需要判断元素是否为空直接pop即可
    void pop() {
        stk.pop();
        helper.pop();
    }
    
    int top() {
        return stk.top();
    }
    
    int getMin() {
        return helper.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(val);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

leetcode232 用栈实现队列

原题链接:
https://leetcode.cn/problems/implement-queue-using-stacks/

双栈思路

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
/*
    栈 后进先出
    队列 先进先出

    双栈一个栈专门用于入队 一个栈专门用于出队
*/
class MyQueue {
public:
    // 入队 
    stack<int>pushStk;
    // 出队 
    stack<int>popStk;

    MyQueue() {
        
    }
    
    void push(int x) {
        // 入栈 始终向 入队栈入
        pushStk.push(x);
    }
    
    int pop() {
        // 如果出队栈为空 无法出队
        // 将入队栈 所有元素推入出队栈
        if(popStk.empty()){
            while(pushStk.empty() == false){
                popStk.push(pushStk.top());
                pushStk.pop();
            }
        }

        int x = popStk.top();
        popStk.pop();
        return x;
    }
    
    int peek() {
        // 如果入队栈为空 
        // 将出队栈所有元素 压入入队栈
        if(popStk.empty()){
            while(pushStk.empty() == false){
                popStk.push(pushStk.top());
                pushStk.pop();
            }
        }
        // 栈顶出栈 那么对应也就是 队列出队的队头
        return popStk.top();
    }
    
    bool empty() {
        return pushStk.empty() && popStk.empty();
    }
};

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue* obj = new MyQueue();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->peek();
 * bool param_4 = obj->empty();
 */

150 逆波兰表达式求值

栈

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:
    int evalRPN(vector<string>& tokens) {
        stack<int>stk;
        for(auto & t : tokens){
            // 如果不是运算符 那么一定是数 则入栈
            if(t != "+" && t != "-" && t != "*" && t!= "/"){
                stk.push(stoi(t));
            }else{
                if(t == "+"){
                    int a = stk.top();
                    stk.pop();
                    int b = stk.top();
                    stk.pop();
                    stk.push(b + a);
                }

                if(t == "-"){
                    int a = stk.top();
                    stk.pop();
                    int b = stk.top();
                    stk.pop();
                    stk.push(b - a);
                }

                if(t == "*"){
                    int a = stk.top();
                    stk.pop();
                    int b = stk.top();
                    stk.pop();
                    stk.push(b * a);
                }

                if(t == "/"){
                    int a = stk.top();
                    stk.pop();
                    int b = stk.top();
                    stk.pop();
                    stk.push(b / a);
                }
            }
        }

        return stk.top();
    }
};

224 基本计算器

双栈思路

原题链接:
https://leetcode.cn/problems/basic-calculator/description/

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
/*
    逆波兰式的思想 (数字入栈 运计算符出栈) 但这里要额外考虑一个( ) 问题
    双栈 
    nums:存放所有的数字  ops: 存放所有的数字以外的操作
*/
class Solution {
public:
    // 将空格 全部跳过
    void replace(string &s){
        int pos = s.find(" ");
        while(pos != -1){
            s.replace(pos,1,"");
            pos = s.find(" ");
        }

    }
    
    // 运算
    // 运算栈 以及 操作符栈
    // 直接改变数的值 要加引用
    void cal(stack<int>&nums,stack<char> &ops){
        if(nums.size() < 2 || ops.empty()){
            return;
        }
        char op = ops.top();
        ops.pop();
        int a = nums.top();
        nums.pop();
        int b = nums.top();
        nums.pop();
        int ans = 0;
        if(op == '+'){
            ans = b + a;
        }

        if(op == '-'){
            ans = b - a;
        }

        nums.push(ans);
    }

    int calculate(string s) {
        replace(s);
        // 存放所有数字
        stack<int>nums;
        nums.push(0);
        // 存放所有的操作 包括 +/- 
        stack<char> ops;

        int n = s.size();

        for(int i = 0 ; i < n ; i++){
            char c = s[i];
            // 加入操作符栈 等待与之匹配的 )
            if(c == '('){
                ops.push(c);
            }
            // 使用现有的nums和ops进行计算 直到遇到左边最近的一个左括号为止 计算结果放到nums中
            else if(c == ')'){
                while(!ops.empty()){
                    char op  = ops.top();
                    if(op != '('){
                        cal(nums,ops);
                    }else{
                        ops.pop();
                        break;
                    }
                }
            }else{
                // 非括号 二是操作符或者数字的情况
                // 数字
                if(isdigit(c)){
                    int cur = 0;
                    int j = i;
                    // 从j位开始的连续数字取出 加入到nums中
                    while(j < n && isdigit(s[j])){
                        cur = cur * 10 + (s[j++] - '0');
                    }   
                    nums.push(cur);
                    i = j - 1;
                }else{
                    // 操作符
                    // 防止() 内首个字符为运算符
                    if(i > 0 && (s[i - 1] ==  '(' || s[i - 1] == '+' || s[i - 1] == '-')){
                        // 这样就可以有规避 负数问题 直接将负数转换为减号运算 0 - xxx
                        nums.push(0);
                    }
                    
                    // 新操作符号入栈 先把栈内所有符号先算了
                    while(!ops.empty() && ops.top() != '(' ){
                        cal(nums,ops);
                    }
                    ops.push(c);
                }
            }
        }

        // 把()外的剩余数 全部算掉
        while(!ops.empty()){
            cal(nums,ops);
        }

        return nums.top();
    }
};

20 有效的括号

原题链接:
https://leetcode.cn/problems/valid-parentheses/

栈的基础应用

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
/*
    栈
    左边入栈  遇到右边出栈判断
*/
class Solution {
public:
    bool isValid(string s) {
        stack<char>stk;
        for(auto &c : s){
            if(c == '(' || c == '{' || c == '['){
                stk.push(c);
            }else{
                
                if(stk.size() < 1){
                    return false;
                }

                char x = stk.top();
                if( (x == '(' && c == ')') || (x == '[' && c == ']') || (x == '{' && c == '}')){
                    stk.pop();
                }else{
                    return false;
                }
            }
        } 

        // 如果栈中有多余元素则 证明未完成匹配
        return stk.empty();
    }
};

1472 设计浏览器历史记录

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

class BrowserHistory {
public:
    // 前进栈存储可以前进的页面
    // 在栈越前面 即越早入栈 越晚前进到
    stack<string>sfor;

    // 默认将后退栈顶视作当前浏览页 方便后续的讨
    stack<string>sback;

    BrowserHistory(string homepage) {
        sback.push(homepage);
    }
    
    void visit(string url) {
        sback.push(url);
        while(!sfor.empty()){
            sfor.pop();
        }
    }
    
    string back(int steps) {
        for(int i = 0 ; i < steps && sback.size() > 1 ; i++){
            // 后退意味有更多空间可以前进
            sfor.push(sback.top());
            sback.pop();

        }

        return sback.top();
    }
    
    string forward(int steps) {
        for(int i = 0; i < steps && sfor.size() > 0 ; i++){
            // 前进意味着有更多空间可以后退
            sback.push(sfor.top());
            sfor.pop();
        }

        // 这里返回的是 后退栈的顶部
        return sback.top();
    }
};

/**
 * Your BrowserHistory object will be instantiated and called as such:
 * BrowserHistory* obj = new BrowserHistory(homepage);
 * obj->visit(url);
 * string param_2 = obj->back(steps);
 * string param_3 = obj->forward(steps);
 */

1209 删除字符串中的所有相邻重复项

有很多种做法栈只是其中的一种

原题链接:
https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string-ii/

  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
/*
    栈实现 s
    栈遍历 然后统计相同字符数等于k个时执行删除操作
*/
class Solution {
public:
    string removeDuplicates(string s, int k) {
        int n = s.size();
        stack<int>stk;
        for(int i = 0 ; i < n ; i++){
            // 初始为空时 
            // 或者前后
            if(i == 0 || s[i] != s[i - 1]){
                stk.push(1);
            }else{
                stk.top()++;
                // 符合相同长度要求 则直接从字符串中移除这k个字符
                if(stk.top() == k){
                    // 准备删除这段字符所以直接出栈
                    stk.pop();
                    // erase 的做法 和 substr 是一样的 从首i 开始往后k个
                    s.erase(i - k + 1,k);        
                    // 相当于删除的部分 和原来直接拼接 然后再回头进行判断
                    i = i - k;                
                }
            }
        }

        return 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:
    string removeDuplicates(string s, int k) {
        // vector 代替栈在后面的实现过程中 会方便些
        vector<pair<int,char>>stk;
        int n = s.size();
        for(int i = 0 ; i < n; i++){
            if(stk.empty() || s[i] != stk.back().second){
                stk.push_back({1,s[i]});
            }else{
                stk.back().first++;
                if(stk.back().first == k){
                    // 直接删除即可 不需要回退 
                    // 因为出栈 之前字符组就会回到栈顶 相当于连接的情况
                    stk.pop_back();
                }
            }
        }

        string ans = "";

        for(auto ss : stk){
            ans += string(ss.first,ss.second);
        }

        return ans;
    }
};

Hashmap/ Hashset

146 LRU Cache

128 最长连续序列

原题链接:
https://leetcode.cn/problems/longest-consecutive-sequence/

hash只是其中的一种解法 这个题算是高频题 还有很多其他解法

  1. hash 集合

hash 记录所有元素
利用序列连续的性质 如果当前遍历的元素的前一个存在于hash中 则跳过 因为从该元素开始向后遍历的序列是不可能比前一个元素开始遍历序列的长度要长的 

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
/*
    O(n) 一次遍历 不排序 这个题的连续不包含相同
    hash
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int>hash;
        for(auto x : nums){
            hash.insert(x);
        }

        int ans = 0;

        for(int i = 0 ; i < nums.size() ; i++){
            int cur = nums[i];
            // 这个if判断 可以优化很多
            // 只有当前一个数不存在的时候才需要遍历
            // 前一个如果存在 那一定会在之前进行遍历
            if(!hash.count(cur - 1)){
                while(hash.count(cur)){
                    cur++;
                }
            }
            

            // while 循环 cur 已经是答案的下一位了 不需要再加1
            ans = max(ans,cur - nums[i]);
        }

        return ans;
    }
};

  1. hash集合优化 记录右边界
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
/*
    hash 记录右边界 每次遍历直接取出右边界进行判断省去了遍历过程
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int>hash;
        
        for(auto x : nums){
            // 初始化每个数的右边界为 其zishen
            hash[x] = x;
        }
        int ans = 0;
        for(auto x : nums){
            if(!hash.count(x - 1)){
                // 取出当前数的右端点
                int right = hash[x];
                // 右边界 在hash 中存在 那么跟新该数的右边界
                while(hash.count(right + 1) > 0){
                    right++;
                }

                // 更新该数的右节点 
                hash[x] = right;

                // 更新答案
                ans = max(ans,right - x + 1);
            }
        }

        return ans;
    }
};

  1. 动态规划

不使用count
其实下面这段语法是不够准确的

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

/*
    动态规划
    hash 记录数以及当前对应的区间长度 不断通过左右数的区间长度组合成当前数的区间 并更新hash
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int>hash;
        int ans = 0;

        for(auto x : nums){
            // 如果当前数没出过
            if(!hash[x]){
                // 左边区间的长度
                int left = hash[x - 1];
                // 右边区间的长度
                int right = hash[x + 1];
                // 当前区间长度
                int curlen = left + right + 1;
                ans = max(ans,curlen);
                // 表示以及遍历过了
                hash[x] = -1;
                // 更新左右区间的长度
                hash[x - left] = curlen;
                hash[x + right] = curlen;
            }
        }

        return ans;
    }
};

下面这段使用count会比较准确

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

/*
    动态规划
    hash 记录数以及当前对应的区间长度 不断通过左右数的区间长度组合成当前数的区间 并更新hash
*/
class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_map<int,int>hash;
        int ans = 0;

        for(auto x : nums){
            // 如果当前数没出过
            // 这个题 这里还是蛮坑的 如果用C++的话
            // hash[x - 1] hash[x + 1] 在C++如果找不到是默认直接插入
            // 这样如果直接用count判断就会出现问题
            if(!hash.count(x)){  
                int left = 0, right = 0;
                // 左边区间的长度 
                if(hash.find(x - 1) != hash.end()){
                    left = hash[x - 1];
                }
                
                // 右边区间的长度
                if(hash.find(x + 1) != hash.end()){
                    right = hash[x + 1];
                }

                // 当前区间长度
                int curlen = left + right + 1;
                ans = max(ans,curlen);
                // 表示以及遍历过了
                hash[x] = -1;
                // 更新左右区间的长度
                hash[x - left] = curlen;
                hash[x + right] = curlen;
            }
        }

        return ans;
    }
};

73 矩阵置零

原题链接:
https://leetcode.cn/problems/set-matrix-zeroes/description/

  1. 非常数空间
    O(m + n)
    标记数组
    hashMap 记录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
class Solution {
    public void setZeroes(int[][] matrix) {
        int n = matrix.length;
        int m = matrix[0].length;
        // 行
        int [] row = new int[n];
        // 列
        int [] col = new int[m];
        
        for (int i = 0 ; i  <  n ; i++){
            for (int j = 0 ; j < m ; j++){ 
                if(matrix[i][j] == 0){
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }

        for (int i = 0 ; i  <  n ; i++){
            for (int j = 0 ; j < m ; j++){
                if(row[i] == 1 || col[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        }
        
    }
}

  1. 常数空间
    非常麻烦

380 O(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
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
class RandomizedSet {
    /**
     *  hash 记录所有元素的位置与下标 用作O(1) 删除与插入
     *  数组存储数 用于random查找
     */
    // 数组的最大大小 因为最多只会进行 2 * 10^5 操作
    public final int N = 200010;
    // val,idx
    HashMap<Integer,Integer> hash;
    Random random  = new Random();
    public int [] q;
    // idx记录当前数组的范围
    int idx;
    // 初始化
    public RandomizedSet() {
        hash = new HashMap<>();
        idx = -1;
        q = new int[N];
    }

    // 插入元素
    public boolean insert(int val) {
        if(hash.containsKey(val)){
            return false;
        }

        idx++;

        q[idx] = val;
        hash.put(val,idx);

        return true;
    }


    // 移除
    // 不能仅仅是移除元素 而是在移除元素后 将当前数组最后位置的元素 补充在被删除数的位置
    public boolean remove(int val) {
        if(!hash.containsKey(val)){
            return false;
        }
        
        // 获取要删除元素的位置
        int loc = hash.getOrDefault(val,0);
        hash.remove(val);
        

        // 这里的这一步判断是必须的 
        // 因为如果删除数 刚好就是idx位置的那个 如果不跳过的话相当于i将该数重新插入回了hash 就会导致出错
        if(loc != idx){
            hash.put(q[idx],loc);
        }
        
        // 将要删除的数 替换为数组末尾的数
        q[loc] = q[idx];
        idx--;

        return true;
    }


    // 随机返回
    public int getRandom() {
        return q[random.nextInt(idx + 1)];
    }
}

/**
 * Your RandomizedSet object will be instantiated and called as such:
 * RandomizedSet obj = new RandomizedSet();
 * boolean param_1 = obj.insert(val);
 * boolean param_2 = obj.remove(val);
 * int param_3 = obj.getRandom();
 */

49 字母异位词分组

原题链接:
https://leetcode.cn/problems/group-anagrams/

  1. 排序
    将排序后的单词作为键值 使用哈希进行存储 不断更新答案
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 List<List<String>> groupAnagrams(String[] strs) {
        HashMap<String, List<String>> hash = new HashMap<>();
        for(var  ss : strs){
            char[] array = ss.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = hash.getOrDefault(new String(array), new ArrayList<String>());
            // 更新 字母异位词的集合
            list.add(ss);
            // 更新答案
            hash.put(key, list);
        }

        return new ArrayList<List<String>>(hash.values()) ;
    }
}

  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
34
35
36
37

class Solution {
    /**
     *  计数
     *  根据题意 异位词中每个字母出现的次数一定相同 使用数组进行记录 每个单词出现字母的次数作为键值
     *  由于数组存的是地址 还是要把数组进行编码转换成相应的字符串 作为键值进行存储
     */

    public List<List<String>> groupAnagrams(String[] strs) {
        // 键值---以字符串形式表现的不同的字符出现的个数  以及 每个键值对应的由异位词组合的字符串集合
        HashMap<String, List<String>> hash = new HashMap<>();

        for(var ss : strs){
            // 记录每个位字符出现的次数
            int [] count = new int[26];
            for(var c  : ss.toCharArray()){
                count[c - 'a']++;
            }

            // 进行编码 生成key
            String key = "";
            for(int i = 0 ; i < 26 ; i++){
                key += (char) ('a' + i) ;
                key += count[i];
            }

            List<String> list = hash.getOrDefault(key,new ArrayList<String>());
            list.add(ss);

            hash.put(key,list);
        }

        return new ArrayList<List<String>>(hash.values());
    }

}

350 两个数组的交集Ⅱ

原题链接:
https://leetcode.cn/problems/intersection-of-two-arrays-ii/description/

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[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> hash = new HashMap<>();
        for(var x : nums1){
            int count = hash.getOrDefault(x,0);
            count++;
            hash.put(x,count);
        }
        
        int [] ans = new int[Math.min(nums1.length,nums2.length)]; 
        int k = 0;
        for(var x : nums2){
            int count = hash.getOrDefault(x,0);
            if(count > 0){
                count--;
                ans[k++] = x;
                
                hash.put(x,count);
            }
        }
        
        return Arrays.copyOfRange(ans,0,k);
    }
}

299 猜数字游戏

根据题意 哈希 + 模拟

  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
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 getHint(String secret, String guess) {
        char [] sarr = secret.toCharArray();
        char [] garr = guess.toCharArray();


        // char -> id出现次数
        HashMap<Character, Integer> c2i = new HashMap<>();

        int n = sarr.length;
        for(int i = 0  ; i < n; i++){
            Integer tmp = c2i.getOrDefault(sarr[i],0);
            tmp++;
            c2i.put(sarr[i],tmp);
        }

        int a = 0;
        int b = 0;

        // 第一次匹配数和位置 都猜对
        // 否则会导致 数猜对答案 对 数和位置都猜对的答案造成干扰
        for(int i = 0 ; i < n ; i++){
            char ch = sarr[i];
            if(ch == garr[i]){
                a++;
                int tmp = c2i.getOrDefault(ch,0);
                tmp--;
                c2i.put(ch,tmp);
            }
        }

        // 第二次再找数猜对的
        for (int i = 0 ; i  < n ; i++){
            char ch = garr[i];
            if(sarr[i] == ch){
                continue;
            }
            
            if(!c2i.containsKey(ch)){
                continue;
            }
            
            int tmp = c2i.getOrDefault(ch,0);
            if(tmp > 0){
                b++;
                tmp--;
                c2i.put(ch,tmp);
            }
            
        }

        return a + "A" + b + "B" ;
    }
}

  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

class Solution {
    public String getHint(String secret, String guess) {
        char [] s1 = secret.toCharArray();
        char [] s2 = guess.toCharArray();

        int n = s1.length;  

        // 哈希 记录两个串中不同数出现的次数
        int [] cnt1 = new int [10];
        int [] cnt2 = new int [10]; 

        int a = 0;
        int b = 0;

        for(int i = 0 ; i < n ; i++){
            if(s1[i] == s2[i]){
                a++;
            }else{
                cnt1[s1[i] - '0']++;
                cnt2[s2[i] - '0']++;
            }
        }

        for(int i = 0 ; i < 10 ; i++){
            b += Math.min(cnt1[i],cnt2[i]);
        }

        return a + "A" + b + "B"; 
    }
}

Heap

973. 最接近原点的 K 个点

原题链接:
https://leetcode.cn/problems/k-closest-points-to-origin/description/

堆的基本应用 主要还是语法题 练习java的语法 heap可以直接用lambda传入比较器还是比较方便的

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 Node {
    int a;
    int b;
    int v;

    Node(int a, int b){
        this.a = a;
        this.b = b;
        this.v = a * a + b * b;
    }
}

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<Node>heap = new PriorityQueue<>(((o1, o2) -> o1.v - o2.v ));
        int n = points.length;
        for(int i = 0; i < n ; i++){
            int a = points[i][0];
            int b = points[i][1];
            heap.add(new Node(a,b));
        }
        
        int [][] ans = new int[k][2];
        
        for(int i = 0 ; i < k ; i++){
            var node = heap.poll();
            ans[i][0] = node.a;
            ans[i][1] = node.b;
        }
        
        return ans;
    }
}

347 前k个高频元素

原题链接:
https://leetcode.cn/problems/top-k-frequent-elements/

基本是对 堆语法的考察

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 int[] topKFrequent(int[] nums, int k) {
        // 值 --- 出现的次数
        var hash = new HashMap<Integer,Integer>();
        for(var x : nums){
            int v = hash.getOrDefault(x,0);
            v++;
            hash.put(x,v);
        }

        // 存符合条件的k个数 存键值 通过hash进行排序 (非常巧妙这种做法)
        PriorityQueue<Integer>heap = new PriorityQueue<>(((o1, o2) -> hash.get(o1) - hash.get(o2)));

        for(var e : hash.entrySet()){
            if(heap.size() >= k){
                int key = heap.peek();
                if(hash.get(key) < e.getValue()){
                    heap.remove();
                    heap.add(e.getKey());
                }
            }else {
                heap.add(e.getKey());
            }
        }
        
        int [] ans = new int[k];
        int idx = 0;

        while (!heap.isEmpty()){
            ans[idx++] = heap.poll(); 
        }
        
        return ans;
    }
}

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:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int>hash;
        unordered_set<int>hs;
        vector<int>ans;

        for(auto x : nums){
            hash[x]++;
            if(hs.contains(x)){
                continue;
            }
            hs.insert(x);
            ans.push_back(x);
        }

        sort(ans.begin(),ans.end(),[&](int a,int b)->bool{
            return hash[a] > hash[b];
        });

        return vector<int>(ans.begin(),ans.begin() + k) ;
    }
};


23 合并k个升序链表

原题链接:
https://leetcode.cn/problems/merge-k-sorted-lists/

堆(是其中的一种解法)

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

class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        // 最小堆 根据当前节点进行排序
        PriorityQueue<ListNode>heap = new PriorityQueue<>((o1,o2) ->{
            return o1.val - o2.val;
        });

        for(var node : lists){
            if(node != null){
                heap.offer(node);
            }   
        }

        ListNode dummy = new ListNode(0);

        ListNode cur = dummy;

        while (!heap.isEmpty()){
            var node = heap.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next != null){
                heap.offer(cur.next);
            }
        }

        return dummy.next;

    }
}

264 丑数Ⅱ

原题链接:
https://leetcode.cn/problems/ugly-number-ii/

优先队列(不止这一种做法) 丑数也是leetcode里面的一个经典题型了 

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
/**
 打表
 对于任意一个丑数 x，其与任意的质因数 (2、3、5)相乘，结果 (2x、3x、5x) 仍为丑数
 */
class Solution {
    public static final int N = 1690;
    public static int [] ans = new int[N];
    public static long [] nums = new long[]{2,3,5};

    static {
        // 最小堆
        // 这个点非常的坑 
        // Long 这里排序 不能用 o1 - o2 因为会存在溢出问题 一定要统一使用 o1.compareTo(o2)
        PriorityQueue<Long>pq = new PriorityQueue<>((o1, o2) -> o1.compareTo(o2));
        // 存储出现过的元素 防止再次入堆
        HashSet<Long> hash = new HashSet<>();
        pq.offer(1L);
        hash.add(1L);

        for(int i = 0 ; i < N ; i++){
            var x = pq.poll();
            ans[i] = x.intValue();
            for(var num : nums){
                long t = num * x;
                if(!hash.contains(t)){
                    pq.offer(t);
                    hash.add(t);
                }
            }
        }
    }

    public int nthUglyNumber(int n) {
        return ans[n - 1];
    }
}

88 合并两个有序数组

原题链接:
https://leetcode.cn/problems/merge-sorted-array/

这个题堆可以做 但不是一种的好的解法
双指针才是最优解 这里只展示堆的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        PriorityQueue<Integer>pq = new PriorityQueue<>((o1,o2)->o1 - o2);
        
        for(int i = 0 ; i < m ; i++){
            pq.add(nums1[i]);
        }

        for(int i = 0 ; i < n ; i++){
            pq.add(nums2[i]);
        }
        
        for(int i = 0 ; i < m + n ; i++){
            nums1[i] = pq.poll();
        }

    }
}

692 前k个高频单词

原题链接:
https://leetcode.cn/problems/top-k-frequent-words/description/

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 List<String> topKFrequent(String[] words, int k) {
        HashMap<String,Integer> hash = new HashMap<>();

        for(var s : words){
            var c = hash.getOrDefault(s,0);
            c++;
            hash.put(s,c);
        }

        // 大根堆
        PriorityQueue<String>pq = new PriorityQueue<>((o1,o2)-> {
            if(hash.get(o2) == hash.get(o1)){
                // 字典序 直接用compareTo 比较
                return o1.compareTo(o2);
            }
            return hash.get(o2) - hash.get(o1);
        });

        for(var s : hash.keySet()){
            pq.add(s);
        }

        List<String> ans = new ArrayList<>();
        
        for(int i = 0 ; i  < k ; i++){
            ans.add(pq.poll());
        }
        
        return ans;
    }  
}

378 有序矩阵中第k小的元素

个人认为是堆中一道很好的题

原题链接:
https://leetcode.cn/problems/kth-smallest-element-in-a-sorted-matrix/

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

/**
    根据题意最小的元素一定在左上角
    先将第一列的元素以及位置加入堆中 
    每次都比较第一列以及第一行右边的一个元素 这样就可以保证堆中始终存放着全局的最小元素
    第一行如果选完了就往下选一行 直到出堆k个数 就可以得到答案
 */

class Node{
    int x;
    int y;
    int v;
    Node(int x,int y,int v){
        this.x = x;
        this.y = y;
        this.v = v;
    }
}

class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        PriorityQueue<Node>pq = new PriorityQueue<>((o1,o2)->o1.v - o2.v);
        int n = matrix.length;
        int m = matrix[0].length;
        // 加入 第1列
        for(int i = 0; i < n ; i++){
            pq.offer(new Node(i,0,matrix[i][0]));
        }

        // pq.poll();

        for(int i = 0 ; i < k - 1 ; i++){
            var node = pq.poll();
            // System.out.println(i);
            int x = node.x , y = node.y , v = node.v;
            if(y + 1 < m){
                pq.offer(new Node(x,y + 1,matrix[x][y + 1]));
            }
            // 下面这一行其实是没必要的 
            // 行中取满后 由于我们已经把第一列加入到堆中了 不需要生动去调整行
            // 直接从堆中自动取出下一行的元素即可
            // else{
            //     y = 1;
            //     x++;
            //     pq.add(new Node(x,y,matrix[x][y + 1]));
            // }
        }
        
        return pq.poll().v;
    }
}

295 数据流的中位数

原题链接:
https://leetcode.cn/problems/find-median-from-data-stream/description/

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

/**
    双堆
    一个大根堆l 维护数据流左半  一个小根堆r 维护数据流右半
    计算中间值时 取出 l的堆顶 和 r的堆顶即可

    l 存储奇数值 
 */
class MedianFinder {
    // 大根堆
    private static PriorityQueue<Integer>l;
    // 小根堆
    private static PriorityQueue<Integer>r;
    

    public MedianFinder() {
        l = new PriorityQueue<Integer>((o1,o2)->o2 - o1);
        r = new PriorityQueue<Integer>((o1,o2)->o1 - o2);
    }
    
    public void addNum(int num) {
        int s1 = l.size();
        int s2 = r.size();

        // 偶数的情况 
        if(s1 == s2){
            // r 右半集合为空 或者 num 比 r的最小值小 则证明当前应存储与左半集合
            if(r.isEmpty() ||  num <= r.peek()){
                l.offer(num);
            }else{
                // 根据定义 左半维持的奇数的情况
                l.offer(r.poll());
                r.offer(num);
            }
        }else{
            // 根据定义 s1 != s2 只可能是 s1 > s2 且 s1为奇数

            // l的最大值 如果比 num小 那么直接放入右半边接口
            if(l.peek() <= num){
                r.offer(num);
            }else{
                // 与上述调整相同 防止出现l与r差两个元素情况 调整完后s1 == s2
                r.offer(l.poll());
                l.offer(num);
            }
        }
    }
    
    public double findMedian() {
        int s1 = l.size();
        int s2 = r.size();

        // 两者大小相等那么 直接根据定义返回均值即可
        if(s1 == s2){
            return (l.peek() + r.peek()) / 2.0;
        }else{
            // 奇数的情况直接返回中间数
            return l.peek();
        }

    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

767 重构字符串

原题链接:
https://leetcode.cn/problems/reorganize-string/description/

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
class Solution {
    public String reorganizeString(String s) {
        int [] count = new int[26];
        var ss = s.toCharArray();
        int n =  ss.length;
        
        if(n < 2){
            return s;
        }
        
        for(var c:ss){
            count[c - 'a']++;
            if(count[c - 'a'] > (n + 1) >> 1){
                return "";
            }
        }
        
        

        // 大根堆 根据字符的出现次数排序
        PriorityQueue<Character>pq = new PriorityQueue<>(((o1, o2) -> count[o2.charValue() - 'a'] - count[o1.charValue() - 'a']));

        for(var c = 'a' ; c <= 'z' ; c++){
            // 只将 出现次数大于0 入队 提高效率
            if(count[c - 'a'] > 0){
                pq.add(c);   
            }
        }
        
        StringBuffer sb = new StringBuffer();

        while(pq.size() > 1){
            var letter1 = pq.poll();
            var letter2 = pq.poll();
            sb.append(letter1);
            sb.append(letter2);
            count[letter1 - 'a']--;
            count[letter2 - 'a']--;
            if(count[letter1 - 'a'] > 0){
                pq.add(letter1);
            }

            if(count[letter2 - 'a'] > 0){
                pq.add(letter2);
            }
        }

        if(pq.size() > 0){
            sb.append(pq.poll());
        }

        return sb.toString();

    }
}

二分

34 在排序数组中查找元素的第一个和最后一个位置

原题链接:
https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/

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
/**
查找元素x的第一个位置和最后一个位置 即
1.>=x 的第一个位置
2.>=(x + 1) 的第一个位置前面的的一个位置

 */
class Solution {
    public int[] searchRange(int[] nums, int target) {
        int a = lower_bound(nums,target);
        if(a >= nums.length || nums[a] != target){
            return new int [] {-1,-1};
        }

        int b = lower_bound(nums,target + 1) - 1;
        // a 存在那么b一定存在 因为大不了 a == b
        return new int [] {a,b};
    }

    // >= 
    // 闭区间写法 [l,r]
    public int lower_bound(int [] arr, int x){
        int l = 0 , r = arr.length - 1;
        while(l <= r){
            int mid = l + r >>1;
            if(arr[mid] >= x){
                // l x mid r
                // [l , mid - 1]
                r = mid - 1;
            }else{
                // l mid x r
                // [mid + 1 , r]
                l = mid + 1;
            }
        }

        return l;
    }
}

双指针

常见双指针算法分为三类，同向（即两个指针都相同一个方向移动），背向（两个指针从相同或者相邻的位置出发，背向移动直到其中一根指针到达边界为止），相向（两个指针从两边出发一起向中间移动直到两个指针

背向双指针