大部分为抄答案，看解析，且跳过困难的题目，希望能学到点东西

  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
大佬递归确实强

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */

//根节点写的不太顺利，但做出来了
struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    struct ListNode *use;
    // struct ListNode root;
    struct ListNode* root = (struct ListNode*)malloc(sizeof(struct ListNode));
    // root = list2;
    // use = root->next;
    root->next = NULL;
    use = root;
    int temp = 0;
    while (list1 || list2) {
        if (!list1) { // list1 null
            use->next = list2;
            list2 = list2->next;
            use = use->next;
        } else if (!list2) { // list2 null
            use->next = list1;
            list1 = list1->next;
            use = use->next;
        } else { // compare
            if (list1->val < list2->val) {
                use->next = list1;
                list1 = list1->next;
                use = use->next;
            } else {
                use->next = list2;
                list2 = list2->next;
                use = use->next;
            }
        }
    }
    return root->next;
}


struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
    if (list1 == NULL) {
        return list2;
    }
    if (list2 == NULL) {
        return list1;
    }
    
    struct ListNode* mergedList;
    
    if (list1->val <= list2->val) {
        mergedList = list1;
        mergedList->next = mergeTwoLists(list1->next, list2);
    } else {
        mergedList = list2;
        mergedList->next = mergeTwoLists(list1, list2->next);
    }
    
    return mergedList;
}

作者：tt-1103
链接：https://leetcode.cn/problems/merge-two-sorted-lists/solutions/2512813/he-bing-you-xu-lian-biao-by-tt-1103-74r9/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  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
// 链表递归 https://leetcode.cn/problems/add-two-numbers/description/
struct ListNode *helper(struct ListNode *l1, struct ListNode *l2, int carry)
{
    if (l1 == NULL && l2 == NULL && carry == 0)
    {
        return NULL;
    }

    int sum = carry;
    if (l1 != NULL)
    {
        sum += l1->val;
        l1 = l1->next;
    }
    if (l2 != NULL)
    {
        sum += l2->val;
        l2 = l2->next;
    }

    struct ListNode *l = malloc(sizeof(struct ListNode));
    l->val = sum % 10;
    l->next = helper(l1, l2, sum / 10);

    return l;
}

struct ListNode *addTwoNumbers(struct ListNode *l1, struct ListNode *l2)
{
    return helper(l1, l2, 0);
}

20. 有效的括号
大佬的答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
bool isValid(char* s) {
    char mp[128] = {};
    mp[')'] = '(';
    mp[']'] = '[';
    mp['}'] = '{';

    int top = 0; // 直接把 s 当作栈
    for (int i = 0; s[i]; i++) {
        char c = s[i];
        if (mp[c] == 0) {                           // c 是左括号
            s[top++] = c;                           // 入栈
        } else if (top == 0 || s[--top] != mp[c]) { // c 是右括号
            return false; // 没有左括号，或者左括号类型不对
        }
    }
    return top == 0; // 所有左括号必须匹配完毕
}

15. 三数之和

能猜到双指针我就很知足了，
image

48. 旋转图像

难点在原地

看答案，找规律，转置+翻转，完成

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
void rotate(int** matrix, int matrixSize, int* matrixColSize) {

    int temp;

    // 转置

    for (int i = 0; i < matrixSize; i++) {

        for (int j = i + 1; j < matrixSize; j++) {

            temp = matrix[i][j];

            matrix[i][j] = matrix[j][i];

            matrix[j][i] = temp;

        }

    }

    // 翻转

    for (int i = 0; i < matrixSize; i++) { // 行

        for (int j = 0; j < matrixSize/2; j++) { //列

            temp = matrix[i][j];

            matrix[i][j] = matrix[i][matrixSize-j-1];

            matrix[i][matrixSize-j-1] = temp;

        }

    }

}

238. 除自身以外数组的乘积（做出了，但耗时，再做）

380. O(1) 时间插入、删除和获取随机元素（再看看吧）
45. 跳跃游戏 II（再做）

55. 跳跃游戏（想耍小聪明降低运算时间，但是各种漏洞）

121. 买卖股票的最佳时机（做了，耗时，脑子不够灵活再做）

189. 轮转数组 (做出来了，比我预期的好得多)

169. 多数元素 (做了，但耗时再做)

80. 删除有序数组中的重复项 II

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 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
int removeDuplicates(int* nums, int numsSize) {

if (numsSize <= 2) {

return numsSize;

}

int slow = 2, fast = 2;

while (fast < numsSize) {

if (nums[slow - 2] != nums[fast]) {

nums[slow] = nums[fast];

++slow;

}

++fast;

}

return slow;

}

26. 删除有序数组中的重复项

　双指针问题做的越来越舒服了
　还不错，很快做完了；

27. 移除元素 (work 1.5)

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例 1：

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例 2：

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,3,0,4]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

88. 合并两个有序数组 (work 1)

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

image

53. 最大子数组和

coolBoy 我觉得这道题目的思想是： 走完这一生如果我和你在一起会变得更好，那我们就在一起，否则我就丢下你。我回顾我最光辉的时刻就是和不同人在一起，变得更好的最长连续时刻

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

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

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]

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

示例 2：

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

示例 3：

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

提示：

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

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

15. 三数之和

复制粘贴

25. K 个一组翻转链表

复制粘贴

215. 数组中的第K个最大元素

复制粘贴

LRU 缓存机制

提交记录

是先去b站看了解析视频然后自己写的，很多cpp的内容还是不熟悉，要继续。

状态 日期 语言 时间 空间 优化
通过 2023.10.10 C++ 372 ms 161.7 MB 官方题解
通过 2023.10.10 C++ 372 ms 161.4 MB ai 优化
通过 2023.10.10 C++ 476 ms 170.7 MB
通过 2023.10.10 C++ 488 ms 170.8 MB
超出时间限制 2023.10.10 C++ N/A N/A
超出时间限制 2023.10.10 C++ N/A N/A
执行出错 2023.10.09 C++ N/A N/A
执行出错 2023.10.09 C++ N/A N/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
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
class LRUCache {
public:
    LRUCache (int capacity) {
        __cap = capacity;
    }
    
    int get (int key) {
        //key = 0;
        if (hashmap.find (key) == hashmap.end ()){ // 没找到
            return -1;
        } else {
                        // 添加
            key_value kv;
            kv.key = key;
            kv.value = hashmap [key]->value;



            value_list.erase (hashmap [key]);
            value_list.push_front (kv);
            hashmap [key] = value_list.begin ();
            return kv.value;
        }
        return key;
    }
    
    void put (int key, int value) {
        if (hashmap.find (key) == hashmap.end ()){ // 没找到
            // 满了吗？

            if (__cap == hashmap.size ()){
                hashmap.erase ( value_list.back ().key);
                value_list.pop_back ();
            }
            // 添加
            key_value kv;
            kv.key = key;
            kv.value = value;
            value_list.push_front ( kv);
            hashmap [key] = value_list.begin ();




        } else { // 找到了
            // 删除并添加到头

            value_list.erase (hashmap [key]);
            // 添加
            key_value kv;
            kv.key = key;
            kv.value = value;
            value_list.push_front ( kv);
            hashmap [key] = value_list.begin ();

        }
    }
private:
    int __cap;
    struct key_value {
        int key;
        int value;
        bool operator==(const key_value& kv){
            return key == kv.key;
        }
    };
    map<int, list<key_value>::iterator> hashmap;
    list<key_value> value_list;

};

ai优化

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
#include <iostream>
#include <unordered_map>
#include <list>

class LRUCache {
public:
    LRUCache (int capacity) : capacity (capacity) {
    }

    int get (int key) {
        if (cache_map.find (key) == cache_map.end ()) {
            return -1; // 未找到
        } else {
            // 将键值对移到链表头部表示最近使用
            moveToFront (key);
            return cache_map [key]->second;
        }
    }

    void put (int key, int value) {
        if (cache_map.find (key) == cache_map.end ()) {
            if (cache_map.size () >= capacity) {
                // 缓存已满，删除最久未使用的项目
                int lru_key = lru_list.back ().first;
                cache_map.erase (lru_key);
                lru_list.pop_back ();
            }
            // 添加新项目到链表头部
            lru_list.push_front (std::make_pair (key, value));
            cache_map [key] = lru_list.begin ();
        } else {
            // 更新已存在的键值对的值，然后移到链表头部表示最近使用
            cache_map [key]->second = value;
            moveToFront (key);
        }
    }

private:
    int capacity;
    std::unordered_map<int, std::list<std::pair<int, int>>::iterator> cache_map;
    std::list<std::pair<int, int>> lru_list;

    // 将键值对移到链表头部
    void moveToFront (int key) {
        auto it = cache_map [key];
        lru_list.splice (lru_list.begin (), lru_list, it);
        cache_map [key] = lru_list.begin ();
    }
};

206. 反转链表

看了下提交记录，应该是复制粘贴，主要是cpp不熟，改天重写一遍

这里就记录一下官方答案吧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/
 * 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) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* ret = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return ret;
    }
};


3 无重复字符的最长子串

独立编写

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
int lengthOfLongestSubstring(string s)
{
    string temp;
    int ftemp = 0;
    for(int i = s.length(); i > 0; i--)
    {
        if (temp.find(s[s.length() - i]) > temp.length()) // 无重复  temp.find(s[s.length() - i]) == -1 但会很大 所以
        {
            // 无重复
            temp.push_back(s[s.length() - i]);
            ftemp = temp.length() > ftemp ? temp.length() : ftemp;
        }
        else
        {
            // 有重复
            i += (temp.length() - temp.find(s[s.length() - i]) - 1);
            temp.clear();
            temp.push_back(s[s.length() - i]);
            ftemp = temp.length() > ftemp ? temp.length() : ftemp;
        }
    }
    return ftemp;
}

使用到的函数

1
2
3
4
string::find(char c) // 返回c在string中的位置 无则返回string::npos
string::length() // 返回string的长度
string::push_back(char c) // 在string的末尾添加c
string::clear() // 清空string

思路

刚开始看错了题

做完去看评论 发现这个题的思路是滑动窗口 然鹅我不知道那是什么东东 只是大概理解字面意思

这道题主要用到思路是：滑动窗口

什么是滑动窗口？

其实就是一个队列,比如例题中的 abcabcbb，进入这个队列（窗口）为 abc 满足题目要求，当再进入 a，队列变成了 abca，这时候不满足要求。所以，我们要移动这个队列！

如何移动？

我们只要把队列的左边的元素移出就行了，直到满足题目要求！

一直维持这样的队列，找出队列出现最长的长度时候，求出解！

时间复杂度：O(n)O(n)O(n)

作者：powcai
链接：https://leetcode.cn/problems/longest-substring-without-repeating-characters/solutions/3982/hua-dong-chuang-kou-by-powcai/

来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

总结

c++ 很多特性还不会用 要继续学习

许可协议

本文采用 署名-非商业性使用-相同方式共享 4.0 国际 许可协议，转载请注明出处。

分享文章

快来聊5毛的吧！