earlene_wyl-CSDN博客

原创 leetcode 377. 组合总和 Ⅳ medium

leetcode377. 组合总和 Ⅳ medium 题目描述：解题思路：因为顺序不同的序列会被视作不同的组合，也就是求排列，所以不能用完全背包来求解（求组合数可以用完全背包）,有些题解里说这是特殊的完全背包，我觉得好牵强啊因为完全背包求组合数的状态转移方程是 dp[n][v] = dp[n-1][v]+dp[n][v-nums[i]]。我们可以假设dp[n][v]表示用前n个nums【i】元素，目标和恰为v的排列数，但是 +dp[n][v-nums[i]...

2022-01-05 23:47:23 222

原创 leetcode 714. 买卖股票的最佳时机含手续费 medium

leetcode714. 买卖股票的最佳时机含手续费 medium 题目描述：解题思路：手续费，可以在买入扣，也可以在卖出的时候扣，只不过应该是第0天初始化，而不再是第-1天。否则可能值越界，或者有别的什么问题，没想好 oRZ代码：//class Solution {public: int maxProfit(vector<int>& prices, int fee) { if (prices.si...

2022-01-04 22:53:46 590

原创 leetcode 673. 最长递增子序列的个数 medium

leetcode673. 最长递增子序列的个数 medium 题目描述：解题思路：只想到了O（n^2）的 dp，贪心的没想到，不过u1s1，应该也不会考到代码：dp版//class Solution {public: int findNumberOfLIS(vector<int>& nums) { vector<int> dp_nums(nums.size(), 1); ...

2022-01-04 11:36:51 333

原创刷题（11）图和并查集

有空再补充最小生成树和最小路径树基本概念图的分类有向/无向加权/不加权两两组合，一共有4种图图的表示邻接表邻接链表数组， A【2】里面放的是一个链表，是和节点2相连的节点适用于稀疏图，也就是顶点数大于边数的情况代码表示：vector<vector> adjsadjs【i】是一个vector，里面存着第i个节点所有边的另一个节点编号邻接矩阵二维矩阵，n个节点，nxn个矩阵。假如无向图， i和j相连，那么A【i】【j】, A【j】【i】为tr

2021-12-30 21:17:37 178

原创 leetcode 785. 判断二分图 medium

leetcode785. 判断二分图 medium 题目描述：解题思路：代码：//class Solution {public: bool isBipartite(vector<vector<int>>& graph) { vector<int> colors(graph.size(), UNKNOW); for (int i = 0;...

2021-12-30 19:24:37 282

原创 leetcode 210. 课程表 II && 207 课程表

leetcode210. 课程表 IImedium题目描述：解题思路：拓扑排序，用kahn算法+ 算法流程 0. 设置邻接表，入度数组（nums[i] 表示第i个节点的入度），结果数组Ret 1. 初始化队列，将入度为0的顶点全都入队（顺序不重要） 2. 出队队首元素，放入ret数组，同时把这个元素的所有邻接点入度减-1，假如入度为0，就入队。 3. 循环步骤2 直到队列为空 4. 如果ret数组长度与节点数目一...

2021-12-30 18:36:16 223

原创 leetcode 797. 所有可能的路径 medium

leetcode797. 所有可能的路径 medium 题目描述：解题思路：dfs，因为是无环图，所以不需要visited数组代码：//class Solution {public: vector<vector<int>> allPathsSourceTarget(vector<vector<int>>& graph) { vector<vector<i...

2021-12-30 16:12:25 138

原创 leetcode 面试题 04.01. 节点间通路 medium

leetcode面试题 04.01. 节点间通路 medium 题目描述：解题思路：求两点可达性，用BFS和DFS均可，注意这里给的是边的矩阵，所以需要转为邻接表形式代码：class Solution {public: bool findWhetherExistsPath(int n, vector<vector<int>>& graph, int start, int target) { ...

2021-12-30 15:51:40 414

原创 leetcode 二分 - 山脉数组 941 && 852 && 1095

leetcode941. 有效的山脉数组 easymedium 题目描述：解题思路：线性扫描即可，但其实这题我觉得是3道里面最难的 orz代码：//class Solution {public: bool validMountainArray(vector<int>& arr) { int n = arr.size(); if (n < 3) re...

2021-12-17 17:51:35 208

原创 leetcode 面试题 10.03. 搜索旋转数组 medium

leetcode面试题 10.03. 搜索旋转数组 medium 题目描述：解题思路：首先多次旋转，最后还是两段递增的序列，也就是跟leetcode 81一样的。因为要求返回索引值最小的，所以需要删除结尾重复的（让最后找到的下标是在前面）代码：//class Solution {public: int search(vector<int>& arr, int target) { if (arr....

2021-12-17 16:33:51 241

原创 leetcode 704. 二分查找 easy

leetcode704. 二分查找 easy 题目描述：解题思路：练二分模板的套路题代码：//class Solution {public: int search(vector<int>& nums, int target) { if (nums.empty()) return -1; int l = 0, r = nums.size()-1;...

2021-12-17 16:26:18 220

原创 leetcode 242 && 349 && 202 & 383

这些题都挺无聊的 ORZleetcode 242. 有效的字母异位词easy 题目描述：解题思路：hash表统计词频代码：//class Solution {public: bool isAnagram(string s, string t) { int count[26] = {}; for (char c: s) count[c - 'a']++; fo...

2021-12-16 22:15:52 80

原创 leetcode 41. 缺失的第一个正数 hard

leetcode 41. 缺失的第一个正数hard 题目描述：解题思路：爷就是神，hard题大概几分钟就想到了解法。。其实跟剑指 Offer 03. 数组中重复的数字的思路是一样的。确实有点哈希的感觉，或许真可以叫原地哈希？代码：//class Solution {public: int firstMissingPositive(vector<int>& nums) { int n = nums.si...

2021-12-16 21:39:12 75

原创 leetcode 594 && 128

leetcode594. 最长和谐子序列 easy 题目描述：解题思路：hash表统计每个数出现过的次数，然后遍历hash，求以当前数为最小值的最长和谐子序列，其实也就是求当前数和（当前数+1）的次数之和。代码：class Solution {public: int findLHS(vector<int>& nums) { unordered_map<int, int> hash;...

2021-12-16 20:37:18 76

原创 leetcode 190. 颠倒二进制位 easy

leetcode190. 颠倒二进制位 easy 题目描述：解题思路：逐位颠倒代码：//class Solution {public: uint32_t reverseBits(uint32_t n) { uint32_t res = 0; for (int i = 0; i < 32; i++){ res <<= 1; ...

2021-12-16 00:40:17 62

原创 leetcode 231 && 342 && 371 && 318 && 338

leetcode231. 2 的幂 easy题目描述：解题思路：n大于0，且二进制表示只有一个1即可代码：//class Solution {public: bool isPowerOfTwo(int n) { return n > 0 && (n & (n -1)) == 0; // n 大于0，且只有一个1 }};leetcode342. 4的幂 easy ...

2021-12-16 00:40:10 627

原创 leetcode 260. 只出现一次的数字 III medium

leetcode260. 只出现一次的数字 III medium 题目描述：解题思路：两个不相等的元素在位级表示上必定会有一位存在不同。将数组的所有元素异或得到的结果为不存在重复的两个元素异或的结果。flag &= -flag 得到出 flag 最右侧不为 0 的位，也就是不存在重复的两个元素在位级表示上最右侧不同的那一位，利用这一位就可以将两个元素区分开来。代码：class Solution {public: vect...

2021-12-15 19:12:40 188

原创 leetcode 268. 丢失的数字 easy

leetcode268. 丢失的数字 easy 题目描述：解题思路：还是利用异或的性质，先得到【0，n】异或的值，再挨个异或数组里的值代码：//class Solution {public: int missingNumber(vector<int>& nums) { int res = 0; for (int i = 0; i <= nums.size(); i++) ...

2021-12-15 18:55:15 762

原创 leetcode 136. 只出现一次的数字 easy

leetcode136. 只出现一次的数字 easy 题目描述：解题思路：a^a = 0, a^0 = a 异或满足交换律结合律代码：class Solution {public: int singleNumber(vector<int>& nums) { int res = 0; for (auto num: nums) res ^= num; ret...

2021-12-15 18:47:23 181

原创 leetcode 461. 汉明距离 easy

leetcode461. 汉明距离 easy 题目描述：解题思路：异或，然后n&（n-1）把最后一个1变为0来统计1的个数代码：//class Solution {public: int hammingDistance(int x, int y) { int cur = x^y; int res = 0; while(cur){ res += 1; ...

2021-12-15 18:43:55 188

原创 leetcode 524. 通过删除字母匹配到字典里最长单词 medium

leetcode524. 通过删除字母匹配到字典里最长单词medium 题目描述：解题思路：实际两个问题的组合：1. 如何判断字符串s2是s1的子序列2. 如何得到长度最长且字母序最小的结果问题1可以用双指针来判断，问题2可以先给dictionary 排序来优化c++ sort 之后的结果是，调用comp（i, i+n）的结果是true。所以要想长度最长且字母序最小autocmp=[](conststring...

2021-12-15 15:21:53 1068

原创 leetcode 680. 验证回文字符串 Ⅱ easy

leetcode680. 验证回文字符串 Ⅱ easy 题目描述：解题思路：贪心+双指针。。不过简单题确实想一想就会代码：//class Solution {public: bool validPalindrome(string s) { int l = 0, r = s.size()-1; while (l < r){ if (s[l] != s[r]) ...

2021-12-15 14:27:23 53

原创 leetcode 345. 反转字符串中的元音字母 easy

leetcode345. 反转字符串中的元音字母 easy 题目描述：解题思路：双指针遍历到元音字母，交换代码：//class Solution {public: string reverseVowels(string s) { int l = 0, r = s.size()-1; unordered_set<char> hash = {'a', 'e', 'i', 'o', 'u'}; ...

2021-12-15 14:11:48 57

原创 leetcode 283. 移动零 easy

leetcode283. 移动零 easy 题目描述：解题思路：因为只要保证非零元素的相对顺序，借鉴快排的partition。代码：//class Solution {public: void moveZeroes(vector<int>& nums) { int tail = 0; // 表示下一个非0 要放的下标 // 【0, tail-1】表示非0区域【tail，i】是0区域 ...

2021-12-15 13:35:33 326

原创【无标题】

leetcode611. 有效三角形的个数 medium 题目描述：解题思路：首先对数组排序。固定最长的一条边，运用双指针扫描可能对这种排完序的数组，就得想想双指针？代码：class Solution {public: int triangleNumber(vector<int>& nums) { if (nums.size() < 3) return 0; ...

2021-12-15 13:10:44 870

原创 leetcode 27. 移除元素 easy

leetcode27. 移除元素 easy 题目描述：解题思路：双指针代码：//class Solution {public: int removeElement(vector<int>& nums, int val) { int pre = -1; for (int i = 0; i < nums.size(); i++){ if (nums[i] !=...

2021-12-15 10:32:05 578

原创 leetcode 633. 平方数之和 medium

leetcode 633. 平方数之和medium 题目描述：解题思路：双指针， i从0开始取，j从可取的最大数sqrt(c)开始代码：//class Solution {public: bool judgeSquareSum(int c) { int i = 0; int j = sqrt(c); while (i<=j){ long long cur ...

2021-12-14 21:50:54 70

原创 leetcode 912. 排序数组 medium （验证各种排序）

leetcode 912. 排序数组medium 题目描述：解题思路：用来验证各种排序算法，写的对不对代码：快排class Solution {public: vector<int> sortArray(vector<int>& nums) { quick_sort(nums, 0, nums.size()-1); return nums; } v...

2021-12-14 17:03:12 95

原创 leetcode 451. 根据字符出现频率排序 medium

leetcode 451. 根据字符出现频率排序 medium 题目描述：解题思路：hash表统计词频+ 桶排（堆排也可）代码：//class Solution {public: string frequencySort(string s) { int max_cnt = 0; unordered_map<char, int> hash; for (char &c: s)...

2021-12-14 16:39:51 68

原创 leetcode 215. 数组中的第K个最大元素 medium

leetcode215. 数组中的第K个最大元素 medium 题目描述：解题思路：方法一：快速选择（时间复杂度 O（n）空间复杂度O（1））方法二：求第k个最大，用最小堆（时间复杂度 O（nlogk），空间O（k））代码：// 快速选择class Solution {public: int findKthLargest(vector<int>& nums, int k) { if ...

2021-12-14 15:54:02 354

原创 leetcode 503. 下一个更大元素 II medium

leetcode503. 下一个更大元素 II medium 题目描述：解题思路：方法一：循环数组：我们可以把这个循环数组「拉直」，即复制该序列的前n-1n−1个元素拼接在原序列的后面。这样循环数组就变成了普通数组，所以我们就可以用单调栈，求右边第一个比它大的。方法二：还是用单调栈，但是这次不用从右向左那个模板，而是从左向右求右边第一个比它大的。代码：// 方法一class Solution {public: ...

2021-12-13 21:07:05 167

原创 leetcode 739. 每日温度 medium

leetcode 739. 每日温度 medium 题目描述：解题思路：单调栈，求右边最近比它大的。所以从右向左遍历，并且栈顶的元素得是大于当前元素，才能入栈，否则栈顶出栈。代码：class Solution {public: vector<int> dailyTemperatures(vector<int>& temperatures) { if (temperatures....

2021-12-13 20:18:44 166

原创 leetcode 946. 验证栈序列 medium

leetcode 946. 验证栈序列 medium 题目描述：解题思路：建立一个辅助栈，按压栈顺序压栈，按出栈顺序出栈具体办法：遍历入栈顺序：假如当前栈顶和当前被比较的出栈数字一样，那就出栈，直到不一样为止。否则继续入栈。代码：class Solution {public: bool validateStackSequences(vector<int>& pushed, vector<int>&a...

2021-12-13 16:27:34 170

原创 leetcode 225. 用队列实现栈 easy

leetcode225. 用队列实现栈 easy题目描述：解题思路：可以用一个队列实现， push的时候，把之前的元素都pop，push回去代码：class MyStack {public: MyStack() { } void push(int x) { int len = que.size(); que.push(x); for (int i = 0; i < len...

2021-12-13 15:42:44 553

原创 leetcode 460. LFU 缓存 hard

leetcode460. LFU 缓存 hard 题目描述：请你为最不经常使用（LFU）缓存算法设计并实现数据结构。实现 LFUCache 类：LFUCache(int capacity) - 用数据结构的容量capacity 初始化对象int get(int key)- 如果键存在于缓存中，则获取键的值，否则返回 -1。void put(int key, int value)- 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在...

2021-12-12 12:34:38 262

原创 leetcode n数之和 1 && 167 && 15 && 16 && 18 && 454

leetcode1. 两数之和 easy_speargod的博客-CSDN博客leetcode167. 两数之和 II - 输入有序数组 easy_speargod的博客-CSDN博客leetcode15. 三数之和 medium_speargod的博客-CSDN博客leetcode16. 最接近的三数之和 medium_speargod的博客-CSDN博客 leetcode 18. 四数之和 medium_speargod的博客-CSDN博客 leetcode...

2021-11-05 18:39:11 66

原创 leetcode 18. 四数之和 medium

leetcode18. 四数之和 medium题目描述：给你一个由 n 个整数组成的数组nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：0 <= a, b, c, d< na、b、c 和 d 互不相同nums[a] + nums[b] + nums[c] + nums[d] == target你可以按...

2021-11-05 16:01:03 65

原创 leetcode 454. 四数相加 II medium

leetcode454. 四数相加 IImedium题目描述：给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：0 <= i, j, k, l < nnums1[i] + nums2[j] + nums3[k] + nums4[l] == 0解题思路：我们可以将四个数组分成两部分，AA 和 BB 为一组，CC 和 DD 为另外一组。对于 AA 和 BB，我们使用...

2021-11-05 15:58:07 100

原创 leetcode 725. 分隔链表 meidum

leetcode725. 分隔链表meidum题目描述：给你一个头结点为 head 的单链表和一个整数 k ，请你设计一个算法将链表分隔为 k 个连续的部分。每部分的长度应该尽可能的相等：任意两部分的长度差距不能超过 1 。这可能会导致有些部分为 null 。这 k 个部分应该按照在链表中出现的顺序排列，并且排在前面的部分的长度应该大于或等于排在后面的长度。返回一个由上述 k 部分组成的数组。解题思路：模拟这个过程即可代码：///** * Defi...

2021-11-04 18:47:36 108

原创 leetcode 234. 回文链表 easy

leetcode234. 回文链表easy题目描述：给你一个单链表的头节点head，请你判断该链表是否为回文链表。如果是，返回true；否则，返回false。解题思路：快慢指针找到中间位置，右半区逆序，比较完之后再恢复回来代码：///** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * Li...

2021-11-04 14:21:45 68

空空如也

空空如也