【LeetCode 热题 HOT 100】题解笔记 —— Day02

❤ 作者主页：欢迎来到我的技术博客😎
❀ 个人介绍：大家好，本人热衷于Java后端开发，欢迎来交流学习哦！(￣▽￣)~*
🍊 如果文章对您有帮助，记得关注、点赞、收藏、评论⭐️⭐️⭐️
📣 您的支持将是我创作的动力，让我们一起加油进步吧！！！🎉🎉

文章目录

  • 一、有效的括号
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 二、合并两个有序列表
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 三、括号生成
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 四、合并K个升序链表
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 五、下一个排序
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 六、最长有效括号
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 七、搜索旋转排序数组
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 八、在排序数组中查找元素的第一个和最后一个位置
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 九、组合总和
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现
  • 十、接雨水
    • 1. 题目描述
    • 2. 思路分析
    • 3. 代码实现

一、有效的括号

1. 题目描述

在这里插入图片描述

2. 思路分析

从前往后枚举每个字符

  1. 当遇到左括号，则将元素压进栈中;
  2. 当遇到右括号
  • 如果栈为空，return false。
  • 如果栈顶元素是对应的左括号，说明这是匹配的字符，将栈顶元素pop 出即可。
    否则，匹配不成功，return false.
  1. 最后，若栈是空栈，表示所有的字符都已经匹配好了，若不是空栈，表示还存在未能匹配好的字符。

注意: 由于'{'和' }'以及'('和')'他们的字符值只相差1, 而'['和'']的字符值只相差2，所以可以通过这个来判断字符是否匹配。

3. 代码实现

class Solution {
public:
    bool isValid(string s) {
        stack<char> stk;

        for (auto c : s) {
            if (c == '(' || c == '{' || c == '[') stk.push(c);
            else {
                if (stk.size() && abs(stk.top() - c) <= 2) stk.pop();
                else return false;
            }
        }
        return stk.empty();
    }
};

二、合并两个有序列表

1. 题目描述

在这里插入图片描述

2. 思路分析

(线性合并) O(n)

  1. 新建头部的保护结点dummy，设置cur 指针指向dummy。
  2. 若当前 l 1 l_1 l1​指针指向的结点的值val比 l 2 l_2 l2​指针指向的结点的值val小 ，则令cur的next指针指向 l 1 l_1 l1​，且 l 1 l_1 l1​后移；否则指向 l 2 l_2 l2​，且 l 2 l_2 l2​后移。
  3. 然后cur指针按照上一部设置好的位置后移。
  4. 循环以上步骤直到 l 1 l_1 l1​或 l 2 l_2 l2​为空。
  5. 将剩余的 l 1 l_1 l1​或 l 2 l_2 l2​接到cur指针后边。

3. 代码实现

/**
 * 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) {
        auto dummy = new ListNode(-1), cur = dummy;

        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur = cur->next = l1;
                l1 = l1->next;
            } else {
                cur = cur->next = l2;
                l2 = l2->next;
            }
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return dummy->next;
    }
};

三、括号生成

1. 题目描述

在这里插入图片描述

2. 思路分析

(直接生成合法发括号序列)

  1. 使用dfs。
  2. 每次可以放置左括号的条件是当前左括号的数目不超过 n n n。
  3. 每次可以放置右括号的条件是当前右括号的数目不超过 n n n 并且不超过左括号的数目。

3. 代码实现

class Solution {
public:
    vector<string> ans;

    vector<string> generateParenthesis(int n) {
        dfs(n, 0, 0, "");
        return ans;
    }

    void dfs(int n, int lc, int rc, string path) {
        if (lc == n && rc == n) ans.push_back(path);
        else {
            if (lc < n) dfs(n, lc + 1, rc, path + '(');
            if (rc < n && lc > rc) dfs(n, lc, rc + 1, path + ')');
        }
    }
};

四、合并K个升序链表

1. 题目描述

在这里插入图片描述

2. 思路分析

（优先队列）

  1. 一开始先用小根堆存储 k k k 个排序链表的头指针，每次操作后用小根堆维护 k k k 个链表当前最小的指针，并以指针对应的值进行排序。
  2. 操作过程中，当小根堆不为空时，堆顶元素即当前 k k k 个排序链表当前最小的元素的指针 t t t，将该值加入到 d u m m y dummy dummy 链表的后面，并把 t t t 指针往后移动一位，使得 t t t 指针指向的值变大，再加入到小根堆中。

3. 代码实现

/**
 * 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:

    struct Cmp {
        bool operator() (ListNode* a, ListNode* b) {
            return a->val > b->val;
        }
    };

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;

        auto dummy = new ListNode(-1), tail = dummy;
        for (auto l : lists) if (l) heap.push(l);

        while (heap.size()) {
            auto t = heap.top();
            heap.pop();

            tail =  tail->next = t;
            if (t->next) heap.push(t->next);
        }
        return dummy->next;
    }
};

五、下一个排序

1. 题目描述

在这里插入图片描述

2. 思路分析

(找规律) O ( n ) O(n) O(n)

找下一个序列就是从后往前找第一个出现降序的地方，把这个地方的前一个数字与后边某个比它大的数字交换，再把该位置之后整理为升序。

  1. 从数组末尾往前找，找到第一个位置 k k k， 使得 nums[k] > nums[k - 1]；
  2. 如果不存在这样的 j j j，说明数组是递减的，则直接将数组进行翻转即可；
  3. 如果存在这样的 j j j，则从末尾找到第一个位置 t t t，使得 nums[t] > nums[k];
  4. 交换 nums[t - 1] 和 nums[k - 1]，然后将数组从 k + 1 k + 1 k+1 到末尾部分继续逆转。

3. 代码实现

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int k = nums.size() - 1;
        while (k > 0 && nums[k - 1] >= nums[k]) k --;
        if (k <= 0) {
            reverse(nums.begin(), nums.end());
        } else {
            int t = k;
            while (t < nums.size() && nums[t] > nums[k - 1]) t ++;
            swap(nums[t - 1], nums[k - 1]);
            reverse(nums.begin() + k, nums.end());
        }
    }
};

六、最长有效括号

1. 题目描述

在这里插入图片描述

2. 思路分析

已知每个有限的括号字符串必须是连续的，那么可以用栈来寻找以某个字符结尾最长的有限长度。

具体做法是我们始终保持栈底元素为当前已经遍历过的元素中 最后一个没有被匹配的右括号的下标，这样的做法主要是考虑了边界条件的处理，栈里其他元素维护左括号的下标：

  • 对于遇到的每个 ‘(’ ，我们将它的下标放入栈中
  • 对于遇到的每个 ‘)’ ，我们先弹出栈顶元素表示匹配了当前右括号：
    • 如果栈为空，说明当前的右括号为没有被匹配的右括号，我们将其下标放入栈中来更新我们之前提到的 最后一个没有被匹配的右括号的下标；
    • 如果栈不为空，当前 右括号的下标减去栈顶元素 即为 以该右括号为结尾的最长有效括号的长度；

我们从前往后遍历字符串并更新答案即可。

注意： 如果一开始栈为空，第一个字符为左括号的时候我们会将其放入栈中，这样就不满足提及的 最后一个没有被匹配的右括号的下标，为了保持统一，我们在一开始的时候往栈中放入一个值为 − 1 −1 −1 的元素。

3. 代码实现

class Solution {
public:
    int longestValidParentheses(string s) {
        stack<int> stk;
        int res = 0;
        stk.push(-1);

        for (int i = 0; i < s.size(); i ++) {
            if (s[i] == '(') stk.push(i);
            else {
                stk.pop();
                if (stk.empty()) stk.push(i);
                else res = max(res, i - stk.top());
            }
        }
        return res;
    }
};

七、搜索旋转排序数组

1. 题目描述

在这里插入图片描述

2. 思路分析

  1. 首先二分找出哪个点是将数组分割成两段的；
  2. 确定 t a r g e t target target 是在哪一段的，划分条件是 t a r g e t target target 与 n u m s [ 0 ] nums[0] nums[0] 的大小关系；
  3. 最后在确定的分段中二分查找 t a r g e t target target 即可。

3. 代码实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if (nums.empty()) return -1;

        // 二分找分割点, 这里用性质>=nums[0], 所以当找到边界时, 它将是最后一个比nums[0]大的数
        int l = 0, r = nums.size() - 1;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] >= nums[0]) l = mid;
            else r = mid - 1; 
        }

        //确定target在哪一段
        if (target >= nums[0]) l = 0;
        else l = r + 1, r = nums.size() - 1;

        //二分查找目标值
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }

        // 这里写成nums[r], 当数组只有一个元素时, 两个二分查找代码都没有走, 而l在上面被+1, 这时会越界, 而r是length-1还是0, 不会产生越界
        if (nums[r] == target) return r;
        else return -1;
    }
};

八、在排序数组中查找元素的第一个和最后一个位置

1. 题目描述

在这里插入图片描述

2. 思路分析

直接进行二分查找即可找到目标值的第一个位置以及最后一个位置。

3. 代码实现

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty()) return {-1, -1};

        int l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= target) r = mid;
            else l = mid + 1;
        }
        if (nums[l] != target) return {-1, -1};

        int L = r;

        l = 0, r = nums.size() - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (nums[mid] <= target) l = mid;
            else r = mid - 1;
        }
        return {L, r};
    }
};

九、组合总和

1. 题目描述

在这里插入图片描述

2. 思路分析

直接进行深度优先搜索即可。
在这里插入图片描述

3. 代码实现

class Solution {
public:
    vector<vector<int>> ans;
    vector<int> path;

    vector<vector<int>> combinationSum(vector<int>& c, int target) {
        dfs(c, 0, target);
        return ans;
    }

    void dfs(vector<int>& c, int u, int target) {
        if (target == 0) {
            ans.push_back(path);
            return;
        }
        if (u == c.size()) return;

        //枚举一下当前的数可以选几个,可以选0个，或者选i个总和不超过target的个数
        for (int i = 0; c[u] * i <= target; i ++ ) {
            //第一次选了0个，也就是什么都没选，不需要记录此次的路径，所以直接dfs下一个
            dfs(c, u + 1, target - c[u] * i);
            path.push_back(c[u]);
        }

        // 回溯，恢复现场
        for (int i = 0; c[u] * i <= target; i ++ ) {
            path.pop_back();
        }
    }
};

十、接雨水

1. 题目描述

在这里插入图片描述

2. 思路分析

单调栈是本文想要重点说明的一个方法。

因为本题是一道典型的单调栈的应用题。

简单来说就是当前柱子如果小于等于栈顶元素，说明形不成凹槽，则将当前柱子入栈；反之若当前柱子大于栈顶元素，说明形成了凹槽，于是将栈中小于当前柱子的元素pop出来，将凹槽的大小累加到结果中。

3. 代码实现

class Solution {
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        // 遍历每个柱体
        for (int i = 0; i < height.length; i++) {
           while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
                int bottomIdx = stack.pop();
                // 如果栈顶元素一直相等，那么全都pop出去，只留第一个。
                while (!stack.isEmpty() && height[stack.peek()] == height[bottomIdx]) {
                    stack.pop();
                }
                if (!stack.isEmpty()) {
                    // stack.peek()是此次接住的雨水的左边界的位置，右边界是当前的柱体，即i。
                    // Math.min(height[stack.peek()], height[i]) 是左右柱子高度的min，减去height[bottomIdx]就是雨水的高度。
                    // i - stack.peek() - 1 是雨水的宽度。
                    res += (Math.min(height[stack.peek()], height[i]) - height[bottomIdx]) * (i - stack.peek() - 1);
                }
            }
            stack.push(i);
        }
        return res;
    }
}

 
非常感谢您阅读到这里，如果这篇文章对您有帮助，希望能留下您的点赞👍 关注💖 分享👥 留言💬thanks！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/192281.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

「媒体邀约」三农，农业类媒体资源有哪些？

「媒体邀约」三农，农业类媒体资源有哪些？

传媒如春雨&#xff0c;润物细无声&#xff0c;大家好&#xff0c;我是51媒体网胡老师。 农业在我国国民经济中的地位是基础&#xff0c;农业是国民经济建设和发展的基础产业&#xff0c;因此围绕三农发展有很多的公司和企业&#xff0c;每年全国都有大大小小关于农业的展览&a…
阅读更多...
浅谈联网汽车安全漏洞

浅谈联网汽车安全漏洞

“智能网联汽车存在内生共性问题&#xff0c;即软硬件的漏洞后门&#xff0c;基于此进行的网络攻击可以直接带来勒索、盗窃、大规模车辆恶意操控风险&#xff0c;还有数据泄露等网络安全事件。如果内生的漏洞后门问题不解决&#xff0c;系统自身难保&#xff0c;很难谈系统安全…
阅读更多...
Oracle Linux 9.3 发布

Oracle Linux 9.3 发布

导读Oracle Linux 9 系列发布了第 3 个版本更新&#xff0c;支持 64 位 Intel 和 AMD (x86_64) 以及 64 位 Arm (aarch64) 平台。与所有的 Oracle Linux 版本一样&#xff0c;此版本与相应 RHEL 版本 100% 应用二进制兼容。 对于 x86_64 和 aarch64 架构&#xff0c;Oracle Li…
阅读更多...
HT97220与HT97230耳机放大器芯片对比

HT97220与HT97230耳机放大器芯片对比

HT97230有两个不同开启时间(tON)版本&#xff0c;版本A、C和E的导通时间tON为5.5ms&#xff0c;用于耳机驱动&#xff1b;B和D则具有130ms的tON&#xff0c;用于机顶盒设计&#xff08;目前仅提供A版本&#xff0c;其他版本需预定&#xff09;。内部电荷泵对输入电源反相&#…
阅读更多...
校园虚拟化部署与横向扩展统一存储

校园虚拟化部署与横向扩展统一存储

项目背景 这所隶属教育部直属重点大学&#xff0c;学校设有11个学科体系&#xff0c;现有本硕博学生共29000余人&#xff0c;为积极响应“中国教育现代化2023战略部署”&#xff0c;校方制定教育信息化2.0发展目标&#xff0c;通过平台融合&#xff0c;数据驱动、技术赋能等措…
阅读更多...
开发测试利器之Fiddler网络调试工具详细安装使用教程(包含汉化脚本)

开发测试利器之Fiddler网络调试工具详细安装使用教程(包含汉化脚本)

一、Fiddler简介 Fiddler 是一款功能强大的网络调试工具&#xff0c;可以帮助开发人员和测试人员分析和调试网络流量。它通过截取计算机和服务器之间的HTTP/HTTPS请求&#xff0c;并提供详细的请求和响应信息来帮助我们理解和诊断网络通信。 Fiddler 可以用于各种用途&#x…
阅读更多...
qgis配的样式保存到postgis中

qgis配的样式保存到postgis中

--查看图层与样式的关联关系 SELECT * FROM layer_styles; 先从postgis导入数据到qgis中&#xff0c;没有样式 在qgis设置样式后&#xff0c;将样式保存到数据库 再次查询数据库表样式&#xff0c;刚才的样式就进来了 再次从数据库加载图层时会自带上样式
阅读更多...
accelerate的使用说明

accelerate的使用说明

1 多卡(GPU)使用方法 终端输入指令&#xff0c;生成问答页面 accelerate config 这个方法也是可以的 2 后面修改直接找到这个yaml文件进行修改即可 cd ~/.cache/huggingface/accelerate vim default_config.yaml 进入vim进行修改 3 单卡(GPU)使用方法 vim default_config.…
阅读更多...
内衣洗衣机怎么选？内衣洗衣机便宜好用的牌子推荐

内衣洗衣机怎么选？内衣洗衣机便宜好用的牌子推荐

相信不少用户并不太在意衣服和内衣裤裤能不能同时洗&#xff0c;每次清洗都是把内衣裤与其他衣服一起放入洗衣机清洗&#xff0c;其实内衣裤不能直接跟大件的衣物一起放入洗衣机洗的&#xff0c;很容易会造成我们皮肤的瘙痒&#xff0c;我们大部分时间都在户外&#xff0c;暴露…
阅读更多...
sCrypt 在英国伦敦 Exeter 大学讲学

sCrypt 在英国伦敦 Exeter 大学讲学

6月5日&#xff0c;sCrypt CEO晓晖和他的两位同事在英国伦敦Exeter大学举行了一场精彩的讲座。刘晓晖向听众们详细介绍了sCrypt智能合约开平台&#xff0c;并演示了如何使用sCrypt来开发基于比特币的智能合约。他用生动形象的语言&#xff0c;深入浅出地解释了这个领域复杂而又…
阅读更多...
Arch Linux 安装 dwm 窗口管理器

Arch Linux 安装 dwm 窗口管理器

窗口管理器是管理桌面上各种窗口的组件&#xff0c;主要功能有&#xff1a;窗口堆叠方式&#xff0c;窗口移动规则等。大多数人接触到的是堆叠式窗口管理器&#xff0c;一个窗口可以叠放在其他窗口之上&#xff0c;调整窗口的主要方式是鼠标。而dwm&#xff08;Dynamic Window …
阅读更多...
Leetcode—907.子数组的最小值之和【中等】

Leetcode—907.子数组的最小值之和【中等】

2023每日刷题&#xff08;四十二&#xff09; Leetcode—907.子数组的最小值之和 算法思想 参考自y神思想 实现代码 class Solution { public:int sumSubarrayMins(vector<int>& arr) {long long ans 0;const int mod 1e97;int n arr.size();stack<int>…
阅读更多...
应用Web3.0的5种方法提升你的点击量

应用Web3.0的5种方法提升你的点击量

Web3.0早已成为互联网的全新方向标&#xff0c;为用户带来全新的手机上网感受。它也变成吸引住点击量疯涨的秘密武器。我们将要详细介绍Web3.0的五种使用方法&#xff0c;帮助你更好的了解并应用Web3.0技术性&#xff0c;以提升你的点击量。 1.可靠的身份认证Web3.0技术性提供了…
阅读更多...
汽车转向桥设计转向节转向桥机械设计

汽车转向桥设计转向节转向桥机械设计

wx供重浩&#xff1a;创享日记 对话框发送&#xff1a;转向桥 获取完整报告说明书工程源文件 转向节图 装配图 本文设计的是JY1061A型采用前置后轮驱动的载货汽车转向桥&#xff0c;因此该转向桥为从动桥。从动桥的功用&#xff1a;从动桥也称非驱动桥&#xff0c;又称从动车轴…
阅读更多...
在 Banana Pi BPI-R2 PRO RK3568开源路由器上安装 OpenWrt 23 快照固件

在 Banana Pi BPI-R2 PRO RK3568开源路由器上安装 OpenWrt 23 快照固件

这是在 BPI-R2 Pro&#xff08;到内部 eMMC&#xff09;上安装 OpenWrt 23 快照固件的快速指南。该固件已预装 LuCI 和一些软件包。这是 2023 年 9 月 2 日的屏幕截图。 LuCI 主页概述。Linux内核是6.1.50 网络接口概述。PPPoE 连接已启动并正在运行 速度测试和 CPU 使用情况…
阅读更多...
【触想智能】无风扇工控电脑一体机使用优势分析

【触想智能】无风扇工控电脑一体机使用优势分析

无风扇工控电脑一体机是属于工控一体机分类中的其中一种&#xff0c;看名字&#xff0c;很明显就是没有散热风扇的工控电脑一体机&#xff0c;而平常我们使用的电脑主机是带有电源风扇、CPU散热风扇的。 无风扇工控电脑一体机的配置组成和商用电脑主机的配置基本一样&#xff0…
阅读更多...
【Linus】进程的等待

【Linus】进程的等待

进程等待的必要性 如果子进程退出了&#xff0c;父进程没有对子进程进行回收&#xff0c;子进程就会进入僵尸进程&#xff0c;占用内存&#xff0c;导致内存泄漏如果程序进入僵尸状态&#xff0c;那么kill -9 也无法强制杀死进程子进程是父进程创建出来&#xff0c;完成父进程…
阅读更多...
minio客户端基本操作

minio客户端基本操作

minio客户端基本操作 桶 创建桶 如果要创建新的桶 输入名称&#xff0c;点击创建即可&#xff0c;默认权限就行 删除桶 点击要删除的桶 点击删除 修改桶 如果哪天需要修改桶的权限或者其他信息&#xff0c;还是先点击这个桶进入详情 然后点击要修改的属性&#xff0c;选择…
阅读更多...
Star History 十月开源精选 ｜AI for Postgres

Star History 十月开源精选 ｜AI for Postgres

在 2023 年 Stack Overflow 开发者调查中&#xff0c;Postgres 顶替了 MySQL 被评为最受欢迎的数据库。一个重要因素应该是 Postgres 支持扩展&#xff1a;可扩展的架构 Postgres 仍然由社区拥有&#xff0c;Postgres 生态近年来蓬勃发展。 扩展可以看作是内置功能&#xff0c…
阅读更多...
智能优化算法应用：基于被囊群算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用：基于被囊群算法无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于被囊群算法无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于被囊群算法无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.被囊群算法4.实验参数设定5.算法结果6.参考文献7.…
阅读更多...
最新文章

Copyright @ 2022~2023