leetcode 刷题记录（倒序）

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

有效的字母异位词还是两个哈希表，不过我把它弄成了一个
同构字符串两个哈希表，还不错啦；
对称二叉树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool compare(struct TreeNode* left, struct TreeNode* right) {
    if ((left == NULL && right != NULL)
        || (left != NULL && right == NULL)) {   /* 单个节点为空，匹配失败 */
            return false;
    } else if (left == NULL && right == NULL) { /* 都为空，匹配成功 */
        return true;
    } else if (left->val != right->val) {   /* 都不为空，节点值不相同，匹配失败 */
        return false;
    }
    /* 运行到此表示当前节点不为空，且节点值相等，开始递归 */
    bool outside    = compare(left->left, right->right);
    bool inside     = compare(left->right, right->left);
    /* 返回递归结果 */
    return outside && inside;
}

bool isSymmetric(struct TreeNode* root){
    /* 根节点为空，则对称 */
    if (root == NULL) {
        return true;
    }
    /* 递归判断 */
    return compare(root->left, root->right);
}

相同的树蛮顺利的
合并两个有序链表

大佬递归确实强

/**
 * 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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

两数相加

// 链表递归 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. 有效的括号大佬的答案

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. 三数之和

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

48. 旋转图像

难点在原地

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

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) 额外空间的条件下完成。

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 中。

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

自己的最终代码#

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优化#

#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不熟，改天重写一遍

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

/
 * 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 无重复字符的最长子串#

独立编写

代码#

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;
}

使用到的函数#

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++ 很多特性还不会用要继续学习

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

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

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

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

27. 移除元素 (work 1.5)#

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

53. 最大子数组和#

15. 三数之和#

25. K 个一组翻转链表#

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

LRU 缓存机制#

提交记录#

自己的最终代码#

ai优化#

206. 反转链表#

3 无重复字符的最长子串#

代码#

使用到的函数#

思路#

总结#

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

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

53. 最大子数组和 #