This is defy_odd's blog

人在有闲的时候，才最像一个人 —— 梁实秋

leetcode(持续更新ing)

发表于 更新于 分类于
本文字数： 35k 阅读时长 ≈ 31 分钟

Leetcode 704. 二分查找 24.12.13

梦开始的地方

题面

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

示例 2:

1
2
3
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：

  1. 你可以假设 nums 中的所有元素是不重复的。
  2. n 将在 [1, 10000]之间。
  3. nums 的每个元素都将在 [-9999, 9999]之间。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include<algorithm>
class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        while (left<=right){
            int middle=(left+right)/2;
            if (nums[middle]<target){
                left=middle+1;
            }
            else if (nums[middle]>target){
                right=middle-1;
            }
            else return middle;
        }
        return -1;
    }
};

Leetcode 27. 移除元素 24.12.15

题面

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

  • 更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
  • 返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

1
2
3
4
5
6
7
8
9
10
11
12
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
                            // 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会 通过。

示例 1：

1
2
3
4
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

示例 2：

1
2
3
4
5
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。

提示：

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

题解： 双指针

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow=0;
        for (int fast=0;fast<nums.size();fast++){
            if (nums[fast]!=val){
                nums[slow++]=nums[fast];
            }
        }
        return slow;
    }
};

Leetcode 977. 有序数组的平方 24.12.15

题面

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1：

1
2
3
4
输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

1
2
输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 已按 非递减顺序 排序

进阶：

  • 请你设计时间复杂度为 O(n) 的算法解决本问题

题解：双指针，注意初始化vector长度

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:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res(nums.size());
        int t=nums.size()-1;
        int i,j;
        for (i=0, j=nums.size()-1;i<=j;){
            if ( abs(nums[i]) > abs(nums[j]) ) {
                res[t]=nums[i]*nums[i];
                //res.insert(res.begin(),nums[i]*nums[i]);
                i++;t--;
            }
            else {
                res[t]=nums[j]*nums[j];
                //res.insert(res.begin(),nums[j]*nums[j]);
                j--;t--;
            }
        }
        return res;
    }

};

Leetcode 209. 长度最小的子数组 24.12.17

题面

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的

子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

示例 1：

1
2
3
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

1
2
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

1
2
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

提示：

  • 1 <= target <= 109
  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 104

进阶：

  • 如果你已经实现 O(n) 时间复杂度的解法, 请尝试设计一个 O(n log(n)) 时间复杂度的解法。

题解：滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int i=0;//起始
        int sum=0;
        int res=99999999;
        int len=0;
        //j为终止下标
        for (int j=0;j<nums.size();j++){
            sum+=nums[j];
            while(sum>=target){
                len=j-i+1;
                res=min(res,len);
                sum-=nums[i];
                i++;
            }
        }
        if (sum<target&&res==99999999) return 0;
        return res;
    }
};

Leetcode 59. 螺旋矩阵 II 24.12.17

给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。

示例 1：

img

1
2
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

示例 2：

1
2
输入：n = 1
输出：[[1]]

提示：

  • 1 <= n <= 20

题解：模拟，注意创建二维数组方式

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>> generateMatrix(int n) {
        //采用左闭右开
        vector<vector<int>> matrix(n,vector<int>(n));
        int startx=0;int starty=0;//起始位置
        int offset=1;//右开
        int t=n/2;//转几圈
        int i,j;
        int count=1;
        while(t){
            //从左到右
            for (j=starty;j<n-offset;j++){
                matrix[startx][j]=count++;
            }
            //从上到下
            for (i=startx;i<n-offset;i++){
                matrix[i][j]=count++;
            }
            //从右到左
            for (;j>starty;j--){
                matrix[i][j]=count++;
            }
            //从下到上
            for (;i>startx;i--){
                matrix[i][j]=count++;
            }
            startx++;starty++;offset++;
            t--;
        }
        if (n%2==1){
            matrix[n/2][n/2]=count++;
        }
        return matrix;
    }
};

Leetcode 203. 移除链表元素

题面

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。

示例 1：

img

1
2
输入：head = [1,2,6,3,4,5,6], val = 6
输出：[1,2,3,4,5]

示例 2：

1
2
输入：head = [], val = 1
输出：[]

示例 3：

1
2
输入：head = [7,7,7,7], val = 7
输出：[]

提示：

  • 列表中的节点数目在范围 [0, 104] 内
  • 1 <= Node.val <= 50
  • 0 <= val <= 50

题解：虚拟头节点

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
//方法一：虚拟头节点，这种方法比较正常
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        ListNode* dhead= new ListNode;
        dhead->next=head;
        ListNode* cur=dhead;
        while(cur->next!=NULL){
            if (cur->next->val==val){
                cur->next=cur->next->next;
            }
            else {
                cur=cur->next;
            }
        }
        return dhead->next;
    }
};

//方法二：不创建虚拟头节点，直接使用第一个元素作为head，需要多处理一下删除头节点的情况，相对复杂
class Solution {
public:
    ListNode* removeElements(ListNode* head, int val) {
        while (head!=NULL&&head->val==val){
            head=head->next;
        }
        ListNode* cur=head;
        if (cur==NULL) return head;
        while(cur->next!=NULL&&cur!=NULL){
            if (cur->next->val==val){
                cur->next=cur->next->next;
            }
            else {
                cur=cur->next;
            }
        }
        return head;
    }
};

Leetcode 707. 设计链表 1.12

题面

你可以选择使用单链表或者双链表，设计并实现自己的链表。

单链表中的节点应该具备两个属性：val 和 next 。val 是当前节点的值，next 是指向下一个节点的指针/引用。

如果是双向链表，则还需要属性 prev 以指示链表中的上一个节点。假设链表中的所有节点下标从 0 开始。

实现 MyLinkedList 类：

  • MyLinkedList() 初始化 MyLinkedList 对象。
  • int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效，则返回 -1 。
  • void addAtHead(int val) 将一个值为 val 的节点插入到链表中第一个元素之前。在插入完成后，新节点会成为链表的第一个节点。
  • void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  • void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度，那么该节点会被追加到链表的末尾。如果 index 比长度更大，该节点将 不会插入 到链表中。
  • void deleteAtIndex(int index) 如果下标有效，则删除链表中下标为 index 的节点。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
输入
["MyLinkedList", "addAtHead", "addAtTail", "addAtIndex", "get", "deleteAtIndex", "get"]
[[], [1], [3], [1, 2], [1], [1], [1]]
输出
[null, null, null, null, 2, null, 3]

解释
MyLinkedList myLinkedList = new MyLinkedList();
myLinkedList.addAtHead(1);
myLinkedList.addAtTail(3);
myLinkedList.addAtIndex(1, 2);    // 链表变为 1->2->3
myLinkedList.get(1);              // 返回 2
myLinkedList.deleteAtIndex(1);    // 现在，链表变为 1->3
myLinkedList.get(1);              // 返回 3

提示：

  • 0 <= index, val <= 1000
  • 请不要使用内置的 LinkedList 库。
  • 调用 get、addAtHead、addAtTail、addAtIndex 和 deleteAtIndex 的次数不超过 2000 。

题解：挺红的，这给一个样例改一次bug，改了有半小时还不止，关注addAtTail，addAtIndex，deleteAtIndex函数，它们都从head开始遍历，不从head->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
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
// 题目当中的ListNode的结构是这样的
// struct ListNode{
//     int val;
//     ListNode *next;
// };
class MyLinkedList {
//public:
private:
    int size;
    ListNode *head;
public:
    MyLinkedList() {
        size=0;
        head = new ListNode;
        head->val=0;
        head->next=NULL;
    }
    // 第一个元素的下标是0，从虚拟头节点的下一个开始向后遍历
    int get(int index) {
        if (index<0||index>size-1) return -1;
        ListNode *cur = head->next;
        while (index--){
            cur=cur->next;
        }
        return cur->val;
    }
    
    void addAtHead(int val) {
        ListNode *t=new ListNode;
        t->val=val;
        t->next=head->next;
        head->next=t;    
        size++;
    }
    
    void addAtTail(int val) {
        ListNode *t = new ListNode;
        ListNode *cur = head;
        while (cur->next!=NULL){
            cur= cur->next;
        }
        cur->next=t;
        t->next=NULL;
        t->val=val;
        size++;
    }
    
    void addAtIndex(int index, int val) {
        if (index>size) return ;
        ListNode *t = new ListNode;
        ListNode *cur = head;
        //index-=1;
        while (index>0){
            cur=cur->next;
            index--;
        }
        t->next=cur->next;
        cur->next=t;
        t->val=val;
        size++;
    }
    
    void deleteAtIndex(int index) {
        if (index<0||index>size-1) return ;
        ListNode *cur=head;
        //index-=1;
        while (index>0){
            cur=cur->next;
            index--;
        }
        cur->next=cur->next->next;
        size--;
    }
};

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList* obj = new MyLinkedList();
 * int param_1 = obj->get(index);
 * obj->addAtHead(val);
 * obj->addAtTail(val);
 * obj->addAtIndex(index,val);
 * obj->deleteAtIndex(index);
 */

Leetcode 206. 反转链表 1.13

题面

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

img

1
2
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

img

1
2
输入：head = [1,2]
输出：[2,1]

示例 3：

1
2
输入：head = []
输出：[]

提示：

  • 链表中节点的数目范围是 [0, 5000]
  • -5000 <= Node.val <= 5000

进阶：链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？

题解 双指针解法 就是一个cur一个pre，让cur往前指。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode *cur=head;
        ListNode *pre=NULL;
        while (cur){
            ListNode *t=cur->next;
            cur->next= pre;
            pre=cur;
            cur=t;
        }
        return pre;
    }
};

解法二：递归，其实就是简略版本的双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
ListNode* reverse(ListNode *pre,ListNode *cur){
    if (cur==NULL) return pre;
    ListNode *t= cur->next;
    cur->next=pre;
    return reverse(cur,t);
}

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        return reverse(NULL,head);
    }
};

leetcode 24. 两两交换链表中的节点 1.14

题面

给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。

示例 1：

img

1
2
输入：head = [1,2,3,4]
输出：[2,1,4,3]

示例 2：

1
2
输入：head = []
输出：[]

示例 3：

1
2
输入：head = [1]
输出：[1]

提示：

  • 链表中节点的数目在范围 [0, 100] 内
  • 0 <= Node.val <= 100

题解：交换的是节点，需要有一个虚拟头节点，让cur指针去操作后面的两个节点，循环条件是要cur->next!=NULL&&cur->next->next!=NULL。两者要一起，最后return的是dummyhead->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
/**
 * 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* swapPairs(ListNode* head) {
        ListNode *dummyhead = new ListNode;
        dummyhead->next = head;
        ListNode *cur = dummyhead;
        while (cur->next!=NULL&&cur->next->next!=NULL){
            ListNode *t = cur->next;
            ListNode *t1 = cur->next->next->next;
            cur->next = cur->next->next;
            cur->next->next = t;
            t->next = t1;
            cur = cur->next->next;
        }
        return dummyhead->next;
    }
};

leetcode 19. 删除链表的倒数第 N 个结点 1.18

题面

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

img

1
2
输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

1
2
输入：head = [1], n = 1
输出：[]

示例 3：

1
2
输入：head = [1,2], n = 1
输出：[1]

提示：

  • 链表中结点的数目为 sz
  • 1 <= sz <= 30
  • 0 <= Node.val <= 100
  • 1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

题解：经典双指针（fast,slow）+dummyhead,先移动fast指针，到相距n+1的位置，之后再同时移动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
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* removeNthFromEnd(ListNode* head, int n) {
        ListNode *dummyhead = new ListNode;
        dummyhead->next=head;
        ListNode *fast = dummyhead;
        ListNode *slow = dummyhead;
        //注意fast要再往前移一位，先移动fast指针，之后再移动slow指针
        //这样刚好slow指针可以移动到需要被删除的节点的前一个
        n++; 
        while (n--&&fast!=NULL){
            fast = fast->next;
        }
        while (fast!=NULL){
            fast = fast->next;
            slow = slow->next;
        }
        //删除节点
        slow->next = slow->next->next;
        return dummyhead->next;
    }
};

leetcode142. 环形链表 II 1.19

题面

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

示例 1：

img

1
2
3
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

img

1
2
3
输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

img

1
2
3
输入：head = [1], pos = -1
输出：返回 null
解释：链表中没有环。

提示：

  • 链表中节点的数目范围在范围 [0, 104] 内
  • -105 <= Node.val <= 105
  • pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

思路：karl is all you need.

双指针，一个走的快一个走的慢，快的一次走两格，慢的一次走一格。如果有环的话，一定会在环内相遇。确定进入环的节点，需要使用一个公式推导。

假设快指针走两格，慢指针走一格。

在A点相遇时，快指针已经走过了的路程

慢指针走过了的路程。至于为什么不需要加上，主要是因为，只要慢指针进入之后，快指针一定只需要一圈之内就能追上，因为速度是慢指针的两倍。

相遇是判断是否有环的重要判断条件。

然后就开始了快乐的公式推导过程：

因为我们假设的是快指针是慢指针速度的两倍，所以

因为我们想要得到的是 ,所以

接下来一步很关键，很厉害

这说明，在的时候，。如果的时候，只不过是快指针在环里面多走了圈。和最后相遇是没有差别的。

其实，的意义在于，我从起点向进入环的点走和从相遇点到进入点的距离是一样的。这个是重要的寻找进入点的条件。就在相遇之后，利用这个条件，让两个点都向进入点走。两个相遇的时候就是进入点.

代码

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *fast = head;
        ListNode *slow = head;
        while (fast!=NULL && fast->next!=NULL){
            fast = fast->next->next;
            slow = slow->next;
            if (fast == slow){
                ListNode *index1 = fast;
                ListNode *index2 = head;
                while (index1!=index2){
                    index1 = index1->next;
                    index2 = index2->next;
                }
                return index1;
            }
        }
        return NULL;
    }
};

leetcode242. 有效的字母异位词 1.20

题面

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的 字母异位词。

示例 1:

1
2
输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

1
2
输入: s = "rat", t = "car"
输出: false

提示:

  • 1 <= s.length, t.length <= 5 * 104
  • s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

题解：之前上课的时候遇到过这样的题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool isAnagram(string s, string t) {
        int arr [26] = {0};
        for (int i = 0;i<s.size();i++){
            arr[s[i]-'a']++;
        }
        for (int i = 0; i<t.size();i++){
            arr[t[i]-'a']--;
        }
        for (int i = 0;i<26;i++){
            if (arr[i]!=0){
            return false;
            }
        }
        return true;
    }
};

leetcode349. 两个数组的交集 1.20

题面

给定两个数组 nums1 和 nums2 ，返回 它们的 交集

输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。

示例 1：

1
2
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

1
2
3
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

  • 1 <= nums1.length, nums2.length <= 1000
  • 0 <= nums1[i], nums2[i] <= 1000

题解：使用unordered_set进行操作，并且注意将vector转化成set时候的代码。使用.find函数时，没找到会返回.end()。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res;
        unordered_set<int> num_set(nums1.begin(),nums1.end());
        for (int i=0;i<nums2.size();i++){
            if (num_set.find(nums2[i])!=num_set.end()){
                res.insert(nums2[i]);
            }
        }
        return vector<int>(res.begin(),res.end());
    }
};

参考

代码随想录

【C++】unordered_set中find()用法及代码示例_c++ unorderset的find-CSDN博客

leetcode 1. 两数之和 1.21

这是很多人梦开始的地方（不是很能理解这道题是容易题）

题面

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例 1：

1
2
3
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

1
2
输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

1
2
输入：nums = [3,3], target = 6
输出：[0,1]

提示：

  • 2 <= nums.length <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

题解：重点是使用unordered_map去存取那些已经遍历过的数。因为只要两数之和，遍历过的数可以放在map里面，而且巧妙的是，由于只需要两个数，另一个数可以直接由target-nums[i]得到。

1、双重循环深似海，皆为纸上谈兵之事

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

2、一招map走天下，全是Carl下人间

梦开始的地方，Leetcode：1.两数之和，学透哈希表，map使用有技巧！_哔哩哔哩_bilibili

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        vector<int> res;
        for (int i=0;i<nums.size();i++){
            int s = target - nums[i];
            auto it = map.find(s);
            if (it!=map.end()){
                res.push_back(it->second);
                res.push_back(i);
                return res;
            }
            map.insert(pair<int,int>(nums[i],i));
        }
        return res;
    }
};

3、你知道的，代码和你有一个能跑就行。只不过这次是代码能跑（leetcode借鉴版）

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

参考

C++之STL整理（3）之map 用法（创建、赋值、方法）整理_c++ map初始化-CSDN博客

C++中 Map的了解与基本用法（代码演示+自我总结+map中一对多的用法）_c++map函数的用法-CSDN博客

leetcode 454. 四数相加 II 1.22

题面 属于第一眼看会懵逼系列

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

  • 0 <= i, j, k, l < n
  • nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

1
2
3
4
5
6
输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

1
2
输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

  • n == nums1.length
  • n == nums2.length
  • n == nums3.length
  • n == nums4.length
  • 1 <= n <= 200
  • -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

题解：思路类似于242题，把前两个当作是一个整体，把a+b的出现的次数放进一个map中，然后遍历c和d，计算-(c+d)，查找这个值是否在map中出现过

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:
    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
        unordered_map<int,int> map;
        // for (int i=0;i<nums1.size() ;i++){
        //     for (int j=0;j<nums2.size();j++){
        //         map[nums1[i]+nums2[j]]++;//在map中存放前两个数组的a+b以及出现的次数，用于后续计数
        //     }
        // }
        for (int a:nums1){//遍历vector可以这么干
            for (int b: nums2){
                map[a+b]++;
            }
        }
        int count=0;
        // for (int i=0;i<nums3.size();i++){
        //     for (int j=0;j<nums4.size();j++){
        //         int t = -(nums3[i]+nums4[j]);
        //         if (map.find(t)!=map.end()){
        //             count+=map[t];
        //         }
        //     }
        // }
        for (int c:nums3){
            for (int d:nums4){
                int t = -(c+d);
                if (map.find(t)!=map.end()){
                    count+=map[t];
                }
            }
        }
        return count;
    }
};

leetcode 15. 三数之和 1.25

该不会还是不会（即使看了三遍的Carl……)

果然是梦破碎的地方 第一次看了三遍视频还没看明白的题目

题面

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

1
2
3
4
5
6
7
8
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

1
2
3
输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

1
2
3
输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

  • 3 <= nums.length <= 3000
  • -105 <= nums[i] <= 105

题解：双指针+乱七八糟的去重

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:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res; //保存结果
        sort(nums.begin(),nums.end());
        for (int i=0;i<nums.size();i++){
            //a b c 三个数，i就是a，left是b，right是c
            
            //每一次遍历，会把包含a的所有集合都扫描一遍了
            //换句话说，nums[i]是这个组合中最小的数，如果这个最小的数大于0了，三数相加就根本不可能是0了
            if (nums[i]>0) return res;

            //对a去重,这里判断的是跟前一个元素，而不是后一个。
            //因为如果跟后一个进行判断的话，left在a的后一个，如果刚好一样的话，等于是说元组之间不能重复，不符合题意
            if (i>0&&nums[i]==nums[i-1]) continue;

            int left = i+1;
            int right = nums.size()-1;
            //因为已经排好序了，left比i大一点，right是最大的
            while (right>left){
                if (nums[i]+nums[left]+nums[right]>0) right--;
                else if (nums[i]+nums[left]+nums[right]<0) left++;
                else {
                    res.push_back(vector<int>{nums[i],nums[left],nums[right]});
                
                    //b,c去重
                    while (right>left&&nums[right]==nums[right-1]) right--;
                    while (right>left&&nums[left]==nums[left+1]) left++;
					
                    //这里是得到一个组合之后再进行两个指针的收缩，开始的时候搞成了每一次循环都做一次操作
                    left++;
                    right--;
                    }

            }
        }
        return res;
    }
};

参考

c++:vector sort()排序-CSDN博客

代码随想录

leetcode18. 四数之和 1.26

这题逆天完了

题面

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

  • 0 <= a, b, c, d < n
  • a、b、c 和 d 互不相同
  • nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

1
2
输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

1
2
输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

  • 1 <= nums.length <= 200
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109

题解：最快的一版答案，重点在剪枝去重(我XXX)，竟然还卡我数组长度和long靠。第一个剪枝用return，但是第二个只能是break，直接return的话就结束了，后续的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:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        //思路类似于三数之和,在外面再套一个for循环代表第四个数
        vector<vector<int>> res;
        sort(nums.begin(),nums.end());
        int len = nums.size();//不用这一步也行，一样的
        if (len<4) return res;//这个一定要，被一个[0]干傻了
        for(int i=0;i<len-3;i++){
            //可以理解为这是第一个指针
            //先做一步剪枝,这里要注意，nums[i]和target都要是正数
            
            //这里的两个剪枝的话，效果一般，可加可不加
            //if(nums[i]>target&&nums[i]>0&&target>=0) return res;
            //if (nums[i]>target/4) return res;
             //对i去重
            if (i>0&&nums[i]==nums[i-1]) continue;

            //接下来开始快乐的三数之和的部分咯
            for (int j=i+1;j<len-2;j++){
                //j是三数之和中的i，也就是第二个数
                
                //剪枝，这个Carl的二级剪枝没啥效果
                //if (nums[j]+nums[i]>target&&target>=0&&nums[i]+nums[j]>0) break;
                
                //这个剪枝是看leetcode里面题解看到的，感觉很合理，而且确实剪枝了一部分
                if (nums[j]+nums[i]>target/2) break;
                //去重
                if (j>i+1&&nums[j]==nums[j-1]) continue;

                int left = j+1;
                int right = len-1;

                while (left<right){
                    if ((long)nums[i]+nums[j]+nums[left]+nums[right]>target) right--;
                    else if ((long)nums[i]+nums[j]+nums[left]+nums[right]<target) left++;
                    else {
                        //放入结果
                        res.push_back(vector<int>{nums[i],nums[j],nums[left],nums[right]});
                        //对left和right去重
                        while (right>left&&nums[left]==nums[left+1]) left++;
                        while (right>left&&nums[right]==nums[right-1]) right--;

                        //移动left和right
                        left++;
                        right--;
                    }

                }

            }
        }
        return res;
    }
};

参考

Char 34: runtime error: addition of unsigned offset to 0x603000000070 overflowed to 0x60300000006c-CSDN博客

leetcode 344. 反转字符串 1.27

似乎是最简单的一集

题面

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

1
2
输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

1
2
输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

  • 1 <= s.length <= 105
  • s[i] 都是 ASCII 码表中的可打印字符\

题解：来，四种

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 reverseString(vector<char>& s) {
        
        //第一：没想到swap
        // for (int i=0;i<s.size()/2;i++){
        //     // char t = s[i];
        //     // s[i] = s[s.size()-i-1];
        //     // s[s.size()-i-1] = t;
        
        //第二：题解是个好东西，swap：你好
        //     swap(s[i],s[s.size()-i-1]);
        // }
        
        //第三：评论区是个好东西,reverse：你好
        reverse(s.begin(),s.end());
    }
};


//第四：看了Carl的视频之后，感觉双指针更清晰一点（虽然原理上差不多）
class Solution {
public:
    void reverseString(vector<char>& s) {
        for (int i=0,j=s.size()-1;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }
};

leetcode 541. 反转字符串 II 1.27

问就是不会……

题面

给定一个字符串 s 和一个整数 k，从字符串开头算起，每计数至 2k 个字符，就反转这 2k 字符中的前 k 个字符。

  • 如果剩余字符少于 k 个，则将剩余字符全部反转。
  • 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

1
2
输入：s = "abcdefg", k = 2
输出："bacdfeg"

示例 2：

1
2
输入：s = "abcd", k = 2
输出："bacd"

提示：

  • 1 <= s.length <= 104
  • s 仅由小写英文组成
  • 1 <= k <= 104

题解：两种方法，第一种直接用reverse函数，第二种，自己实现reverse函数

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:
    string reverseStr(string s, int k) {
        //i+=2k是直接跳到2K处，可以减少运算
        for(int i=0;i<s.size();i+=2*k){
            
            //这个是为了反转前k个字符的判断条件，针对每一个i，不论是否满足2k，只要满足有k个就反转。
            //小于等于s.size()是针对于最后一部分的判断。注意这里有等号
            if (i+k<=s.size()){
                //reverse函数可以这样用，从第i位开始s.begin()+i。
                //而且reverse函数实现的时候是左闭右开的，第二个参数直接加上就行了
                reverse(s.begin()+i,s.begin()+i+k);
            }
            else reverse(s.begin()+i,s.end());
        }
        return s;

    }
    
};
//方法二，手写reverse函数，注意这里要用&引用，这样才能保证操作的是同一个string。亲测，没加上没用。并且使用双指针，比只有一个变量方便多了。
void reverse(string &s,int start,int end){
    for (int i=start,j=end;i<j;i++,j--){
        swap(s[i],s[j]);
    }
}
class Solution {
public:
    string reverseStr(string s, int k) {
        for(int i=0;i<s.size();i+=2*k){
            if (i+k<=s.size()){
                //由于是自己定义的，这里的end就需要-1.
                reverse(s,i,i+k-1);
            }
            else reverse(s,i,s.size()-1);
        }
        return s;
    }
};

参考

代码随想录

leetcode151 151. 反转字符串中的单词 25.3.7

孩子我回来啦 一整个2月份在焦虑和自我内耗中度过……

题面

给你一个字符串 s ，请你反转字符串中 单词 的顺序。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。

注意：输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

1
2
输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

1
2
3
输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

1
2
3
输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个。

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

题解：问就是看Carl的书，现在觉得书比视频来的舒服。用双指针删除多余空格，注意点都在注释里了

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
class Solution {
public:
    //反转单个单词
    void reverse(string &s,int start,int end){
        for (int i=start,j=end;i<j;i++,j--){
            swap(s[i],s[j]);
        }
    }

    //删除多余空格
    void removespace(string &s){
        int fastindex=0,slowindex=0;
        //去除开头的空格
        while (s[fastindex]==' '&&fastindex<s.size()) fastindex++;
        //去除中间的空格，但是保证单词中间还有一个空格
        for (;fastindex<s.size();fastindex++){
            if (fastindex-1>0 //这个是保证下面两个条件的一个前提
            &&s[fastindex] == s[fastindex-1] 
            &&s[fastindex]==' ' 
            //需要我忽略的是中间有两个空格的时候。换句话说就是当遇到中间有两个空格的时候
            //不移动slowindex指针，让后面的字符来覆盖前面的空格
            ) continue;
            else s[slowindex++] = s[fastindex];
            //这个操作会把最后末尾的空格也加进来,如果末尾还有空格的话
            //会刚好再多读入一个空格，如果没有的话就不会
        }
        //去除末尾空格,如果有空格的话，
        // while (s[slowindex]==' ' &&slowindex>0) slowindex--;
        // s.resize(slowindex);
        if (s[slowindex-1]==' ') //这里是判断字符串的最后一位是不是空格
            s.resize(slowindex-1);
        else s.resize(slowindex);
    }

    string reverseWords(string s) {
        removespace(s);
        reverse(s,0,s.size()-1);
        int begin=0,end=0;
        bool entry = false; //这个是判断是否进入字符串，反转每个单词
        for (int i=0;i<s.size();i++){
            if ((!entry)||(s[i-1]==' '&&s[i]!=' ')){
                begin = i;
                entry = true;
            }
            else if (entry && s[i]==' '&& s[i-1]!=' '){ //这里如果用i+1来判断的话有可能溢出
                end = i-1;
                entry = false;
                reverse(s,begin,end);
            }
            else if (entry && (i==s.size()-1) && s[i]!=' '){ //这是判断最后一个单词，后面没有空格了
                end = i;
                entry = false;
                reverse(s,begin,end);
            }
        }
        return s;
    }
};

leetcode 455 455. 分发饼干 25.3.8

想学贪心和dp了

题面

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是满足尽可能多的孩子，并输出这个最大数值。

示例 1:

1
2
3
4
5
6
输入: g = [1,2,3], s = [1,1]
输出: 1
解释: 
你有三个孩子和两块小饼干，3 个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是 1，你只能让胃口值是 1 的孩子满足。
所以你应该输出 1。

示例 2:

1
2
3
4
5
6
输入: g = [1,2], s = [1,2,3]
输出: 2
解释: 
你有两个孩子和三块小饼干，2 个孩子的胃口值分别是 1,2。
你拥有的饼干数量和尺寸都足以让所有孩子满足。
所以你应该输出 2。

提示：

  • 1 <= g.length <= 3 * 104
  • 0 <= s.length <= 3 * 104
  • 1 <= g[i], s[j] <= 231 - 1

题解：先排个序，从小到大看饼干能满足哪些小孩

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int index = 0;
        for (int i=0;i<s.size();i++){
            if (index<g.size() && g[index]<=s[i]){
                index++;
            }
        }
        return index;
    }
};

leetcode 376 376. 摆动序列 25.3.10

昨天有点摆了

题面

如果连续数字之间的差严格地在正数和负数之间交替，则数字序列称为 摆动序列 。第一个差（如果存在的话）可能是正数或负数。仅有一个元素或者含两个不等元素的序列也视作摆动序列。

  • 例如， [1, 7, 4, 9, 2, 5] 是一个 摆动序列 ，因为差值 (6, -3, 5, -7, 3) 是正负交替出现的。
  • 相反，[1, 4, 7, 2, 5] 和 [1, 7, 4, 5, 5] 不是摆动序列，第一个序列是因为它的前两个差值都是正数，第二个序列是因为它的最后一个差值为零。

子序列 可以通过从原始序列中删除一些（也可以不删除）元素来获得，剩下的元素保持其原始顺序。

给你一个整数数组 nums ，返回 nums 中作为 摆动序列 的 最长子序列的长度 。

示例 1：

1
2
3
输入：nums = [1,7,4,9,2,5]
输出：6
解释：整个序列均为摆动序列，各元素之间的差值为 (6, -3, 5, -7, 3) 。

示例 2：

1
2
3
4
输入：nums = [1,17,5,10,13,15,10,5,16,8]
输出：7
解释：这个序列包含几个长度为 7 摆动序列。
其中一个是 [1, 17, 10, 13, 10, 16, 8] ，各元素之间的差值为 (16, -7, 3, -3, 6, -8) 。

示例 3：

1
2
输入：nums = [1,2,3,4,5,6,7,8,9]
输出：2

提示：

  • 1 <= nums.length <= 1000
  • 0 <= nums[i] <= 1000

进阶：你能否用 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 wiggleMaxLength(vector<int>& nums) {
        if (nums.size()<=1) return nums.size();
        int cur = 0; //当前的差值
        int pre = 0; //之前的插值
        int res = 1; //假设最后有一个峰值，默认为1
        for (int i=0;i<nums.size()-1;i++){
            cur = nums[i+1] - nums[i];
            //这里的判断条件，pre可以等于0是为了满足有不单调但中间有平坡的情况
            if ((cur>0&&pre<=0)||(pre>=0&&cur<0)){
                res++;
                pre = cur;
                //pre放在这里赋值时为了解决单调有平坡的情况，pre不需要每次都跟着cur改变，只需要记录有变化的时候
            }
        }
        return res;
    }
};

leetcode 53 53. 最大子数组和 25.3.14

emmm刚搞完一个分享会，ppt做的好累

题面

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • 1 <= nums.length <= 105
  • -104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

题解：需要关注的是，贪心贪在哪里。它需要找的是局部最优解，通过局部最优找到全局最优。这题主要是关注的是nums[i+1]。不是在遇到负数就下一个。只要count还是>0就还对下一个数有增大作用。是在count<0才要跳过。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int res = -99999;
        int count = 0;//记录每个区间的最大值
        for (int i=0;i<nums.size();i++){
            count += nums[i];
            if (count>res) res = count;
            if (count<0) count=0;
            //不是遇到负数就直接跳过，而是整体为负数才跳过。
            //只要我这一部分的和还是正数，对于后面的数就是一个增大的作用，关心的主体是nums[i+1]
            //整体为负数会拖累后面累加的数，不会让总体的和更大，不如重新开始
            //而且每次都及时更新到res里面了，不用担心会丢下最大值
        }
        return res;
    }
};

leetcode 122 122. 买卖股票的最佳时机 II 25.3.15

昨晚太晚睡了，今天一整天都没精神

题面

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

1
2
3
4
5
输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3。
最大总利润为 4 + 3 = 7 。

示例 2：

1
2
3
4
输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4。
最大总利润为 4 。

示例 3：

1
2
3
输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0。

提示：

  • 1 <= prices.length <= 3 * 104
  • 0 <= prices[i] <= 104

题解：贪心。每次都关注局部最大值，然后最后合在一起得到全局最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int res = 0;
        // 这里实际构建了一个新的数组，就是每天的利润
        // 我需要找到的是每天的利润都为正数的天数全加起来就可以了
        // 因为比如第一天买入，第三天卖出
        // prices[3]-prices[0] = prices[3]-prices[2]+prices[2]-prices[1]+prices[1]-prices[0]
        // 要保证利润最大，就是只需要每两个之间的差值为正数就是赚
        for (int i=1;i<prices.size();i++){
            res += max((prices[i]-prices[i-1]),0);
        }
        return res;
    }
};

leetcode 55 55. 跳跃游戏 25.3.17

昨天周日，六刷thu

题面

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

示例 1：

1
2
3
输入：nums = [2,3,1,1,4]
输出：true
解释：可以先跳 1 步，从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2：

1
2
3
输入：nums = [3,2,1,0,4]
输出：false
解释：无论怎样，总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 ， 所以永远不可能到达最后一个下标。

提示：

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 105

题解

我自己的版本。看到题面就觉得只要能到达最远的地方就行，取max最重要。结果一交发现了一堆问题，那三个if是对着错误样例改出来的（捂脸）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canJump(vector<int>& nums) {
        if (nums.size()==1) return true;
        if (nums[0]==0) return false;
        int res = 0;
        for (int i=0;i<nums.size()-1;i++){
            res = max(res,nums[i]+i);
            if (nums[i]==0 && res == i) return false;
            if (res >= nums.size()-1) return true;
        }
        return false;
    }
};

代码随想录版本，更加简洁，直接用了cover，然后还直接让i<=cover，直接就卡死了它的范围，就不会出现我自己写的那些问题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    bool canJump(vector<int>& nums) {
        int cover = nums[0]; //int cover = 0;等于0，等于nums[0]都可以
        if (nums.size()==1) return true;
        for (int i=0;i<=cover;i++){
            cover = max(cover,nums[i]+i);
            if (cover>=nums.size()-1) return true;
        }
        return false;
    }
};

leetcode 45 45. 跳跃游戏 II 25.3.23

精彩的一周，没想到这周能发生让我如此印象深刻的一件事

题面

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。

每个元素 nums[i] 表示从索引 i 向后跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:

  • 0 <= j <= nums[i]
  • i + j < n

返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。

示例 1:

1
2
3
4
输入: nums = [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。
     从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。

示例 2:

1
2
输入: nums = [2,3,0,1,4]
输出: 2

提示:

  • 1 <= nums.length <= 104
  • 0 <= nums[i] <= 1000
  • 题目保证可以到达 nums[n-1]

题解：要找最少步数，就是看当每一次的cover能到达的最远的地方。如果能到最远的地方但是还到不了nums.size()-1的话，就需要将ans++。

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 jump(vector<int>& nums) {
        if (nums.size()==1) return 0 ;
        int ans=0;
        int cover=0;
        int pre_cover = 0; //用来标记在第一次能到达的最远距离，然后再依据这个更新。这一部分是跳一次之内都能达到的
        for (int i=0;i<nums.size();i++){
            cover = max(i+nums[i],cover);
            //计算在这个能达到的最远区间中延伸出去所能达到的最远，最远的那里只需要跳一次就能到
            if (i==pre_cover){ 
            //看第一次最远能到哪里，当已经遇到最远的地方的时候，它延伸出来的cover能有多少，之后再继续更新
                if (pre_cover<nums.size()-1) {
                    ans++;
                    pre_cover=cover;
                }
                else break;
            }
        }
        return ans;
        
    }
};

leetcode 274 274. H 指数 25.3.23

先看到的这题，然后才拿出的代码随想录

题面

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

示例 1：

1
2
3
4
输入：citations = [3,0,6,1,5]
输出：3 
解释：给定数组表示研究者总共有 5 篇论文，每篇论文相应的被引用了 3, 0, 6, 1, 5 次。
     由于研究者有 3 篇论文每篇 至少 被引用了 3 次，其余两篇论文每篇被引用 不多于 3 次，所以她的 h 指数是 3。

示例 2：

1
2
输入：citations = [1,3,1]
输出：1

提示：

  • n == citations.length
  • 1 <= n <= 5000
  • 0 <= citations[i] <= 1000

题解：怪我太菜了，这还是看了题解才会的，原来我没想到。直接倒叙排序一下就好了，再看一下到哪里它的下标跟i+1小了就是答案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hIndex(vector<int>& citations) {
        sort(citations.begin(),citations.end(),greater<int>()); //直接倒叙排序
        for (int i=0;i<citations.size();i++){
            if (citations[i]<i+1) return i;
        }
        return citations.size();


    }
};

leetcode LCR 134. Pow(x, n) 25.3.28

一开始直接 过了，结果一看要用快速幂，赶紧补了一下

题面

实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。

示例 1：

1
2
输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

1
2
输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

1
2
3
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • -100.0 < x < 100.0
  • -231 <= n <= 231-1
  • -104 <= xn <= 104

题解：直接放快速幂的吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    double myPow(double x, int n) {
        if (x==1||n==0) return 1;
        double ans=1;
        long num = n;
        if (n<0){
            num = - num;
            x = 1/x;
        }
        while (num){ //重点是这几行
            if (num & 1) ans *=x;
            x*=x;
            num>>=1;
        }
        return ans;
    }
};

GPT老师对于代码的解析：

1
2
3
4
5
while(num){
    if(num & 1) ans *= x;  // 如果 num 的最低位是 1，则累乘 x
    x *= x;                // x 自乘，相当于 x^(2^i)
    num >>= 1;             // 右移 num，相当于 num //= 2
}

逐行分析：

  1. while(num)
    • 只要 num 不为 0，就继续循环，即处理 num 的二进制表示的每一位。
  2. if(num & 1) ans \*= x;
    • num & 1 用于检查 num 的最低位是否为 1：
      • 如果 num 的最低位是 1，说明当前的 x 需要计入结果，因此将 x 乘入 ans。
      • 例如：3 的二进制是 11，最低位 1 说明当前的 x 需要乘入 ans。
  3. x *= x;
    • x 进行平方，x 变成 x^2，然后 x^4，x^8，依次递增。
    • 这样通过二进制的方式，可以用少量的乘法完成指数计算。
  4. num >>= 1;
    • num 右移一位，相当于 num //= 2，去掉最低位，继续处理下一位。

例子分析：

计算

计算步骤：

13 的二进制是 1101
从右到左遍历，每一位表示是否需要乘入当前的 x（即 3^(2^i)）：

num (二进制) x (当前幂) ans（累乘结果） 说明
1101 (13) 3 3 最低位是 1，乘入 ans
110 (6) 9 3 最低位是 0，跳过
11 (3) 81 3 × 81 = 243 最低位是 1，乘入 ans
1 (1) 6561 243 × 6561 = 1594323 最低位是 1，乘入 ans

最终 ans = 1594323，即 .

leetcode 134. 加油站 25.3.28

贪心ing

题面

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则 保证 它是 唯一 的。

示例 1:

1
2
3
4
5
6
7
8
9
10
输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

1
2
3
4
5
6
7
8
9
输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

提示:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

题解：在每次遇到cursum<0的时候，就证明说起点要从下一个开始

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int cursum = 0;
        int start = 0;
        int totalsum = 0;
        for (int i=0;i<gas.size();i++){
            cursum += gas[i] - cost[i];
            totalsum += gas[i] - cost[i];
            if (cursum<0){
                start = i+1;
                cursum = 0;
            }
        }
        if (totalsum<0) return -1;
        return start;
    }
};