3107 字
16 分钟
leetcode 刷题记录（倒序）
2023-06-08
💻Code
💻Code
/
🙂Leetcode

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

  1. 有效的字母异位词 还是两个哈希表，不过我把它弄成了一个

  2. 同构字符串 两个哈希表，还不错啦；

  3. 对称二叉树

/**
 * 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);
}

  1. 相同的树 蛮顺利的

  2. 合并两个有序链表

大佬递归确实强

/**
 * 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. 两数相加
// 链表递归 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. 三数之和

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

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

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.10C++372 ms161.7 MB官方题解
通过2023.10.10C++372 ms161.4 MBai 优化
通过2023.10.10C++476 ms170.7 MB
通过2023.10.10C++488 ms170.8 MB
超出时间限制2023.10.10C++N/AN/A
超出时间限制2023.10.10C++N/AN/A
执行出错2023.10.09C++N/AN/A
执行出错2023.10.09C++N/AN/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++ 很多特性还不会用 要继续学习

leetcode 刷题记录（倒序）
https://f.undf.top/posts/post/code/others/leetcode/
作者
沐印
发布于
2023-06-08
许可协议
CC BY-NC-SA 4.0
QtCreator 一键打包你的APP
旭日 x3PI RealSense人体关键点识别