(未整理完)十月每日一题打卡

每日打卡

10.1 [重新格式化电话号码 lc1694](1694. 重新格式化电话号码 - 力扣（LeetCode）)

模拟题：特殊情况就是在最后划分完全部三个之后，还剩四个需要变成aa-bb

class Solution {
public:
    string reformatNumber(string number) {
        string ans;
        queue q;
        for(char ch: number)
        {
            if(ch != ' ' && ch != '-')
                q.push(ch);
        }
        int cnt = 0;
        while(q.size())
        {
            if(cnt == 0 && q.size() == 4)
            {
                ans += q.front();
                q.pop();
                ans += q.front();
                q.pop();
                ans += '-';
                ans += q.front();
                q.pop();
                ans += q.front();
                q.pop();
            }
            if(!q.size())
                break;
            if(cnt == 3)
            {
                ans += '-';
                cnt = 0;
            }
            else
            {
                ans += q.front();
                q.pop();
                cnt++;
            }
        }
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

10.2 [在LR字符串中交换相邻字符 lc 777](777. 在LR字符串中交换相邻字符 - 力扣（LeetCode）)

题目的意思是L可以越过X向左移动，R可以越过X向右移动。

！也就是去掉X后start和end字符串的L和R位置相同！

class Solution {
public:
    bool canTransform(string start, string end) {
        int n = start.size();
        int i = 0, j = 0;
        while(1)
        {
            //越过所有的X
            while(i < n && start[i] == 'X')
                i++;
            while(j < n && end[j] == 'X')
                j++;
            //判断现在的i和j情况
            //如果两个都走到底了那可以
            if(i == n && j == n)
                return true;
            //有一个走到底了另一个没有或者二者对应的不相同那不行
            if(i == n || j == n || start[i] != end[j])
                return false;
            //两者的位置不同也不行L可以左移所以start的可以在end后面
            if(start[i] == 'L' && i < j)
                return false;
            //R可以右移所以start的可以在end前面
            if(start[i] =='R' && i > j)
                return false;
            i++;
            j++;
        }
        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

10.2 [每日温度 lc739](739. 每日温度 - 力扣（LeetCode）)

单调栈

明显的单调栈就是说维持这个栈单调递减，如果出现比栈顶大的元素，说明下一个更高温度已经出现，可以将其pop出来了。

可以在栈底设置一个哨兵0，这样便于处理边界

class Solution {
public:
    vector dailyTemperatures(vector& temp) {
        int n = temp.size();
        vector ans(n, 0);
        stack stk;
        stk.push(0);
        for(int i = 1; i < n; i++)
        {
            while(!stk.empty() && temp[stk.top()] < temp[i])
            {
                ans[stk.top()] = i - stk.top();
                stk.pop();
            }
            stk.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

10.3 [检查二进制字符串字段 lc1784](1784. 检查二进制字符串字段 - 力扣（LeetCode）)

题目含义很难理解，看了评论区之后：连续若干个"1"组成的字段是由一个或者多个连续‘1’组成的，如果这样的字段不超过1个，就返回true，多于1个就返回false。

1000 true 110001 false 统计即可

class Solution {
public:
    bool checkOnesSegment(string s) {
        int cnt = 0;
        int n = s.size();
        int len = 0;
        for(int i = 0; i < n; i++)
        {
            while(i < n && s[i] == '1')
            {
                len++;
                i++;
            }
            if(len >= 1)
                cnt++;
            if(i < n && s[i] == '0')
                len = 0;
            
        }
        return cnt <= 1;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

10.3 [柱状图中的最大矩形 lc 84](84. 柱状图中最大的矩形 - 力扣（LeetCode）)

我们之前做过一个类似的，盛最多水的容器，那个是构造的矩形是两个边界中最小即可，也即是双指针就行。这个不一样的是你需要使用整个容器内的最矮的作为高。所以我们想遍历每个柱子，以其作为高h，然后去寻找最宽的边，也即是向两边分别找高于h的柱子，找到第一个低于h的就停止。

这个也是单调栈，对于单调递增的栈来说：栈里的前一个元素就是左边第一个小于该元素的值，右边第一个小于我们可以在比较中得到。当发现小于栈顶元素时就可以得到右边第一个了，否则就加入栈中即可。

class Solution {
public:
    int largestRectangleArea(vector& heights) {
        int n = heights.size() + 2;
        //向两边加一个哨兵
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int ans = 0;
        stack s;
        for(int i = 0; i < n; i++)
        {
            while(!s.empty() && heights[i] < heights[s.top()])
            {
                int j = s.top();
                s.pop();
                ans = max(ans, heights[j] * (i - s.top() - 1));
            }
            s.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

10.3 [最大矩形 lc85](85. 最大矩形 - 力扣（LeetCode）)

就是上面lc84的二维版本

最形象的图就是这个

只用第一行高度是 1 0 1 0 0

12行高度是 2 0 2 1 1

13行高度是 3 1 3 2 2

这几行分别调用lc84即可取最大即可！

class Solution {
public:
    int maximalRectangle(vector>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        if(row == 0 || col == 0)
            return 0;
        int ans = 0;
        vector height(col, 0);
        for(int i = 0; i < row; i++)
        {
            for(int j = 0; j < col; j++)
            {
                if(matrix[i][j] == '1')
                    height[j] =  height[j] + 1;
                else
                    height[j] = 0;
            }
            for(int x: height)
                cout << x << " ";
            cout << endl;
            ans = max(ans, largestRectangleArea(height));
        }
        return ans;
    }

    int largestRectangleArea(vector heights) {
        int n = heights.size() + 2;
        heights.insert(heights.begin(), 0);
        heights.push_back(0);
        int ans = 0;
        stack s;
        for(int i = 0; i < n; i++)
        {
            while(!s.empty() && heights[i] < heights[s.top()])
            {
                int j = s.top();
                s.pop();
                ans = max(ans, heights[j] * (i - s.top() - 1));
            }
            s.push(i);
        }
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

10.4 [使括号有效的最少添加 lc 921](921. 使括号有效的最少添加 - 力扣（LeetCode）)

这个就是有效的括号，但是由于是任意位置插入左括号和右括号都行，只需要数量对应上即可。左括号+1，右括号先抵消再计数即可

class Solution {
public:
    int minAddToMakeValid(string s) {
        int l = 0, cnt = 0;
        for(char ch: s)
        {
            if(ch == '(')
                l++;
            else if(l > 0 && ch == ')')
                l--;
            else if(l == 0 && ch == ')')
                cnt++;
        }
        return cnt + l;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

10.4 [最短无序连续子数组 lc 581] (581. 最短无序连续子数组 - 力扣（LeetCode）)

这个看起来很简单，本来想着从两边向中间扩展出现无序就停止来着，但是其中的等号很麻烦。这个题一点都不简单。

两个边界l, r。l是最左边需要开始排序的数，应该从右边开始遍历。如果不需要排序的话，那么从右边开始应该每一个数nums[j]都小于等于右边遍历过的min。反之若nums[j] > min的话，就需要记录下来需要排序的值l。

同理，r是最右边需要开始排序的数，应该从左边开始遍历。如果不需要排序的话，那么从左边开始应该每一个数nums[i]都大于等于左边遍历过前i - 1个数的max。反之若nums[j] < max的话，就需要记录下来需要排序的值r。

class Solution {
public:
    int findUnsortedSubarray(vector& nums) {
        int n = nums.size();
        int ma = INT_MIN, mi = INT_MAX;
        int l = 0, r = 0;
        for(int i = 0; i < n; i++)
        {
            if(nums[i] < ma)
                r = i;
            else
                ma = max(ma, nums[i]);
        }
        for(int j = n - 1; j >= 0; j--)
        {
            if(nums[j] > mi)
                l = j;
            else
                mi = min(mi, nums[j]);
        } 
        if(l == r)
            return 0;
        else
            return r - l + 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

10.5 [子域名访问计数 lc 811](811. 子域名访问计数 - 力扣（LeetCode）)

简单模拟：使用hashmap的key存储域名，value存储个数，处理字符串计数即可。

class Solution {
public:
    vector subdomainVisits(vector& cpdomains) {
        unordered_map hashMap;
        vector ans;
        for(string s: cpdomains)
        {
            int i = 0;
            while(i < s.size() && s[i] != ' ')
                i++;
            int cnt = atoi(s.substr(0, i).c_str());
            string s1 = s.substr(++i);  //google.mail.com
            if(hashMap.find(s1) != hashMap.end())
                hashMap[s1] += cnt;
            else
                hashMap[s1] = cnt;
            while(i < s.size() && s[i] != '.')
                i++;
            string s2 = s.substr(++i); //mail.com
            if(hashMap.find(s2) != hashMap.end())
                hashMap[s2] += cnt;
            else
                hashMap[s2] = cnt;
            while(i < s.size() && s[i] != '.')
                i++;
            if(i < s.size() && s[i] == '.')
            {
                string s3 = s.substr(++i); //com
                if(hashMap.find(s3) != hashMap.end())
                    hashMap[s3] += cnt;
                else
                    hashMap[s3] = cnt;
            }
        }
        for(auto x: hashMap)
        {
            string s = to_string(x.second) + " " + x.first;
            ans.push_back(s);
        }
        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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

[10.5 盛最多水的容器 lc 11](11. 盛最多水的容器 - 力扣（LeetCode）)

这个就很简单啦，双指针遍历一下

class Solution {
public:
    int maxArea(vector& height) {
        int n = height.size();
        int i = 0, j = n - 1;
        int ans = 0;
        while(i < j)
        {
            int s = min(height[i], height[j]) * (j - i);
            ans = max(ans, s);
            if(height[i] < height[j])
                i++;
            else
                j--;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

[10.5 删掉链表的倒数第n个节点 lc 19](19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）)

也很简单啦，就是快慢指针先找到倒数第n个节点，然后删除即可。

注意一些边界条件，比如删除头节点、删除只有一个元素的链表等

/**
 * 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* removeNthFromEnd(ListNode* head, int n) {
        ListNode* p = head;
        if(head->next == nullptr)
            return nullptr;
        for(int i = 0; i < n; i++)
            p = p->next;
        ListNode* q = head;
        if(p == nullptr)
            return head->next;  //删掉头节点

        while(p->next != nullptr)
        {
            p = p->next;
            q = q->next;
        }
        ListNode* nx = q->next;
        q->next = nx->next; 
        return head;
    }
};
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

[10.6 三等分 lc 927](927. 三等分 - 力扣（LeetCode）)

三个指针判断三部分是否相等，二进制是否相等首先看1的个数，其次看第一个1后的排列是否相等。`

class Solution {
public:
    vector threeEqualParts(vector& arr) {
        vector ans = {-1, -1};
        int n = arr.size();
        int cnt = 0;
        //求出所有1的数量
        for(int i = 0; i < n; i++)
            cnt += arr[i];
        if(cnt == 0)
            return {0, n - 1};
        //三者平分 能分继续 不能分就不行
        if(cnt % 3) return ans;
        cnt = cnt / 3;
        int i = 0, j = 0, k = 0, s = 0;
        //根据1的数量将三个指针定位到各自第一个1的位置
        while(i < n && s < 1) { s += arr[i++];}
        s = 0;
        while(j < n && s < cnt + 1)  { s += arr[j++];}
        s = 0;
        while(k < n && s < 2 * cnt + 1)  { s += arr[k++];}

        //开始判断第一个1后面的是否完全相同
        while(k < n && arr[i] == arr[j] && arr[j] == arr[k])
        {
            i++; j++; k++;
        }
        if(k < n)
            return ans;
        else
            return {i - 1, 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
27
28
29
30
31
32
33
34

[10.6 下一个排列 lc 31](31. 下一个排列 - 力扣（LeetCode）)

这个题挺巧妙的，需要仔细分析排列。我们以2 6 3 5 4 1为例，可以从右边开始分析。就是如果是降序比如5 4 1这样的，就是已经是最大的了，不会再有下一个排列了。所以我们第一步需要从右边找第一个升序的，找到了 3 5。为了是下一个排列因此我们需要使这个排列尽可能地小，所以我们从后面5 4 1中选一个第一个比3大地和他交换，得到一个比3大一点的新开头，2 6 4 5 3 1。接下来需要将后面的变成最小的，因为是逆序，所以直接反转即可。

class Solution {
public:
    void nextPermutation(vector& nums) {
        int n = nums.size();
        int i = n - 1;
        //找到第一个升序的 3 5 
        while(i > 0 && nums[i] <= nums[i - 1]) i--;
        //如果不存在升序说明全部倒序，直接全部逆序即可
        if(i <= 0) {reverse(nums.begin(), nums.end()); return;}
        int j = i - 1; // j是3 等着待交换的那个
        //向右边倒序序列中找比nums[j]大一点的值 i - 1就是那个4
        while(i < n && nums[i] > nums[j]) i++;
        cout << nums[j] << " " << nums[i - 1] << endl;
        //swap(nums[j], nums[i - 1]); 将二者交换
        int t = nums[j];
        nums[j] = nums[i - 1];
        nums[i - 1] = t;
        //最后将后面的倒序逆转变小一点的排列
        reverse(nums.begin() + j + 1, nums.end());
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

[10.7 最大升序子序列和 lc1800](1800. 最大升序子数组和 - 力扣（LeetCode）)

class Solution {
public:
    int maxAscendingSum(vector& nums) {
        int ans = nums[0], s = nums[0];
        for(int i = 1; i < nums.size(); i++)
        {
            if(nums[i - 1] < nums[i])
                s += nums[i];
            else
                s = nums[i];
            ans = max(ans, s);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

[10.7 寻找重复数 lc 287](287. 寻找重复数 - 力扣（LeetCode）)

快慢指针，将1,3,4,2,2看成链表，判断链表是否有环以及找到链表的入口。

class Solution {
public:
    int findDuplicate(vector& nums) {
        //将数组看成链表,找到环的入口
        int slow = 0, fast = 0;
        while(1)
        {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if(slow == fast)
                break;
        }
        fast = 0;
        while(slow != fast)
        {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

[10.7 找到数组中消失的数字 lc 448](448. 找到所有数组中消失的数字 - 力扣（LeetCode）)

这个题也是将数组中的值和下标映射起来，比如[4,3,2,7,8,2,3,1]，nums[0] = 4，则将4对应的nums[4] = 8换成-8代表有4了，重复的已经成为负数的就不变，最后值为正的下标就是消失的数字。

class Solution {
public:
    vector findDisappearedNumbers(vector& nums) {
        vector ans;
        for(int i = 0; i < nums.size(); i++)
        {
            nums[abs(nums[i]) - 1] = - abs(nums[abs(nums[i]) - 1]);
        }
        for(int i = 0; i < nums.size(); i++)
        {
            if(nums[i] > 0)
                ans.push_back(i + 1);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

[10.8 优势洗牌 lc 870](870. 优势洗牌 - 力扣（LeetCode）)

贪心之田忌赛马：在nums1中找大于nums2[i]的最小值，如果没有则返回nums1中的最小值。直接找会导致超时，二分查找第一个。

class Solution {
public:
    vector advantageCount(vector& nums1, vector& nums2) {
        int n = nums1.size();
        vector ans(n, 0);
        bool st[n];
        int idx = 0;
        memset(st, false, sizeof st);
        sort(nums1.begin(), nums1.end());
        for(int i = 0; i < n; i++)
        {
            int l = 0, r = n;
            while(l < r)
            {
                int mid = l + r >> 1;
                if(nums1[mid] > nums2[i])
                    r = mid;
                else
                    l = mid + 1;
            }
            while(l < n && (st[l] || nums1[l] == nums2[i]))
                l++;
            if(l < n)
            {
                ans[i] = nums1[l];
                st[l] = true;
            }
            else
            {
                while(st[idx]) idx++;
                ans[i] = nums1[idx];
                st[idx++] = true;
            }
       }
        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
27
28
29
30
31
32
33
34
35
36
37

!10.8 三数之和 lc 15

[10.10 数组中第k个元素](215. 数组中的第K个最大元素 - 力扣（LeetCode）)

1. 快速排序

快速排序每次都可以使nums[r]== x，然后左侧都小于等于x，右侧都大于等于x。因此只要某次确定值的下标是k就可以返回第k个最大的元素了。

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        return quicksort(nums, k, 0, nums.size() - 1);
    }

    int quicksort(vector& nums, int k, int left, int right)
    {
        if(right < left)
            return INT_MAX;
        int x = nums[(left + right) >> 1];
        int l = left - 1, r = right + 1;
        while(l < r)
        {
            do l++; while(nums[l] > x);
            do r--; while(nums[r] < x);
            if(l < r)
            {
                int t = nums[l]; nums[l] = nums[r]; nums[r] = t;
            }
        }
        int p;
        if(nums[l] == x)
            p = l;
        if(nums[r] == x)
            p = r;
        if(p == k - 1)
            return nums[p];
        else if(p > k - 1)
            return quicksort(nums, k, left, r);
        else
            return quicksort(nums, k, r + 1, right);
        
    }
};
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

2. 建堆

维护一个k长度的小顶堆，堆顶元素就是第k大，当堆顶元素不再是第k大的时候，就调整堆。

最小堆 - 数组中的第K个最大元素 - 力扣（LeetCode）

class Solution {
public:
    int findKthLargest(vector& nums, int k) {
        int n = nums.size();

        make_heap(nums, k);
        for(int i = k; i < n; i++)
        {
            if(nums[i] < nums[0])
                continue;
            else
            {
                nums[0] = nums[i];
                shift_down(nums, k, 0);
            }
        }
        return nums[0];
    }

    void shift_down(vector& nums, int k, int i)
    {
        int j = 2 * i + 1;
        while(j < k)
        {
            if(j + 1 < k && nums[j] > nums[j + 1]) j++;
            if(nums[i] > nums[j])
            {
                swap(nums[i], nums[j]);
                i = j;
                j = 2 * i + 1;
            }
            else
                break;
        }
    }
    void make_heap(vector& nums, int k)
    {
        for(int i = k / 2; i >= 0; i--)
            shift_down(nums, k, 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

10.10 使序列递增的最小交换次数 lc 801

状态机dp:dp[i] [0]表示第i位不发生交换使得前i位递增的最小交换次数,1同理。

有两种情况可以交换：

• 两组都满足前后大于，这种就是要不i和i-1都不交换，要么都交换。
• 交叉满足前后大小关系，这种要不i- 1交换要不i交换。

class Solution {
public:
    int minSwap(vector& nums1, vector& nums2) {
        int n = nums1.size();
        int dp[n][2];
        memset(dp, 0x3f, sizeof dp);
        dp[0][0] = 0;
        dp[0][1] = 1;
        for(int i = 1; i < n; i++)
        {
            if(nums1[i] > nums1[i - 1] && nums2[i] > nums2[i - 1])
            {
                dp[i][0] = dp[i - 1][0];  //要么不交换
                dp[i][1] = dp[i - 1][1] + 1; //要么两个都交换
            }
            if(nums1[i] > nums2[i - 1] && nums2[i] > nums1[i - 1])
            {
                dp[i][0] = min(dp[i][0], dp[i - 1][1]);  //前一个发生交换
                dp[i][1] = min(dp[i][1], dp[i - 1][0] + 1); //后面这个发生交换
            }
        }
        return min(dp[n - 1][0], dp[n - 1][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

10.11 仅执行一次字符串交换能否使两个字符串相等 lc 1790

记录下两个不同的下标，超过两个不同返回false，最后看不同的两个下标交换后是否相同。

class Solution {
public:
    bool areAlmostEqual(string s1, string s2) {
        int n = s1.size();
        int cnt = 0;
        int a[2];
        for(int i = 0; i < n; i++)
        {
            if(s1[i] != s2[i])
            {
                if(cnt == 2)
                {
                    cnt++;
                    break;
                }
                a[cnt++] = i;
            }
        }
        if(cnt == 1 || cnt > 2)
            return false;
        if(cnt == 0)
            return true;
        if(s1[a[0]] == s2[a[1]] && s1[a[1]] == s2[a[0]])
            return true;
        return false;
    }
};
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

10.12 链表组件 lc 817

模拟即可

/**
 * 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:
// 被骗了,是求所有组件的个数而不是求组件的最大长度无语无语
    int numComponents(ListNode* head, vector& nums) {
        int n = nums.size(), ans = 0;
        unordered_set hashset;
        for(int x: nums)
            hashset.insert(x);
        ListNode* p = head;
        int cnt = 0;
        while(p != nullptr)
        {
            if(hashset.find(p->val) != hashset.end())
                cnt++;
            else
            {
                if(cnt)
                    ans++;
                cnt = 0;
                
            }
            p = p->next;
        }
        if(cnt)
            ans++;
        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
27
28
29
30
31
32
33
34
35
36
37
38

10.12 接雨水 lc 42

接雨水的关键就是单调栈

不同于柱状图的最大矩形（向两边找低于栈顶的递增），接雨水需要向两边找高于栈顶的，这样才能接住雨水，因此是递减栈。

以栈顶元素作为雨水高度t = height[stk.top()]，当右边高于栈顶时，就是找到了右边高于的，然后去找左边高于的，也即是下一个栈顶。还有要是有和栈顶相同的也要pop出去，而且高度要减去。下一个栈顶就是左边高于栈顶的了height[stk.top()]。比较这两边高的选小的作为高，减去t，乘上宽度即可。

class Solution {
public:
    int trap(vector& height) {
        int n = height.size();
        int ans = 0;
        stack stk;
        for(int i = 0; i < n; i++)
        {
            while(!stk.empty() && height[i] > height[stk.top()])
            {
                int t = stk.top();
                stk.pop();
                while(!stk.empty() && height[stk.top()] == height[t])
                    stk.pop();
                if(!stk.empty())
                    ans += ( min(height[stk.top()], height[i]) - height[t] ) * (i - stk.top() - 1);
            }
            stk.push(i);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

10.13 合并K个升序链表 lc 23

两两归并，最后变成两个合并。

/**
 * 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* l1, ListNode* l2)
    {
        ListNode* dummy = new ListNode(-1);
        ListNode* p = dummy;
        if(l1 == nullptr && l2 == nullptr)
            return nullptr;
        while(l1 != nullptr && l2 != nullptr)
        {
            if(l1->val < l2->val)
            {
                p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p->next = l2;
                l2 = l2->next;
            }
            p = p->next;
        }
        while(l1 != nullptr)
        {
            p->next = l1;
            l1 = l1->next;
            p = p->next;
        }
        while(l2 != nullptr)
        {
            p->next = l2;
            l2 = l2->next;
            p = p->next;
        }
        return dummy->next;
    }
    ListNode* binaryMerge(vector& lists, int low, int high)
    {
        if(low > high)
            return nullptr;
        if(low == high)
            return lists[low];
        if(high - low == 1)
            return mergeTwoLists(lists[low], lists[high]);
        int mid = (low + high) >> 1;
        return mergeTwoLists(binaryMerge(lists, low, mid), binaryMerge(lists, mid + 1, high));
    }
    ListNode* mergeKLists(vector& lists) {
        return binaryMerge(lists, 0, lists.size() - 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

10.13 找到字符串中所有字母异位词 lc 438

滑动窗口

class Solution {
public:
    vector findAnagrams(string s, string p) {
        vector ans;
        int sn = s.siz
1
2
3
4