- 博客(74)
- 收藏
- 关注
RSS订阅原创 2021-10-18 力扣3-无重复字符的最长子串
初看此题是要找子串，那一般使用滑动窗口，问题在于如何记录已经出现的和判断当前字符是否跟前面的重复了，以及重复了后怎么处理。对于问题一，如何记录，我们可以采用数组的方式记录。对于问题二，如何判断该字符是否出现过，只要判断当前字符是否在问题一中记录过即可，由于问题三中，当我们判断了该字符出现过时，那滑动窗口的左边界应该为出现过的位置的后一个位置，所以问题一中数组记录的最好是字符出现的位置。int lengthOfLongestSubstring(char * s){ int locatio.
2021-10-18 23:28:01
84
原创 2021-10-14 力扣616 给字符串添加加粗标签
看到题目时就想到了用strstr在字符串中查找字典中的字符串，因为strstr返回的是第一次出现的首地址，所以没想好怎么去找到Index,所以就停滞了，看了答案后恍然大悟，答案写的很巧妙，用返回的地址与字符串s的首地址做差再除以CHR类型的大小。index = (sptr - targetPtr)/sizeof(char);再一个就是找到了index后如何去利用。题目中要求对于能连续的子串要连续加粗，所以可以将字典中的所有出现的字符在原串S中做好标记，用flag[len]去做标记，以便后面遍历还有..
2021-10-14 00:19:20
257
原创 2021-10-10 二分查找
/* 查找大于或等于target的最小值*/int Search_1(int *nums, int len, int target){ int left = 0; int right = len - 1; if (nums[right] < target) { return -1; } while (left < right) { // 大于等于向下取整 int mid = left + (right -
2021-10-10 16:50:19
65
原创 2021-09-26力扣424-替换后的最长重复字符
一看到最长字串长度一般都是用双指针或者滑动窗口。本题可以转换下思路，既然滑动窗口中的字符可以被替换k次，那么只要滑动窗口中的除了出现组多的那个字符外的其他字符出现的次数少于K那么窗口就可以扩大。如果大于K，那么证明// 可以转换下思路，在一个滑动窗口内，除了出现次数最多的那个外的其他字符的出现次数小于等于k,那么窗口就可以扩大int characterReplacement(char * s, int k){ int len = strlen(s); int left = 0; .
2021-09-26 23:56:21
48
原创 2021-09-13 力扣567-字符串的排列
bool equals(int* cnt1, int* cnt2) { for (int i = 0; i < 26; i++) { if (cnt1[i] != cnt2[i]) { return false; } } return true;}bool checkInclusion(char* s1, char* s2) { int n = strlen(s1), m = strlen(s2); ..
2021-09-13 23:04:51
49
原创 0906-力扣826-安排工作以达到最大收益
1.这个题第一反应就是要对难度进行排序，但是如果只对难度进行排序，那后面取收益的的时候就找不到对应的了，所以要对难度和收益进行绑定再对难度排序。2.有了单调递增的难度后，就是根据工人的能力选择对应的工作了，工人的能力要小于或等于工作的难度，次数用二分法进行优化查找，但是要注意两种情况，工人的能力小于最小难度或大于最大难度。3.此外本题没有指出难度大收益大，所以在每一项维护一个最大收益typedef struct { int diffcult; int prof; int ma.
2021-09-07 00:18:12
157
原创 2021-09-02
解题思路动态规划思想是希望连续的，也就是说上一个状态和下一个状态(自变量)之间有关系而且连续。公共子数组相当于子串：是连续的dp[i][j]：表示第一个数组 A 前 i 个元素和数组 B 前 j 个元素组成的最长公共子数组(相当于子串)的长度。我们在计算 dp[i][j] 的时候：若当前两个元素值相同，即 A[i] == B[j]，则说明当前元素可以构成公共子数组，所以还要加上它们的前一个元素构成的最长公共子数组的长度(在原来的基础上加 1)，此时状态转移方程：dp[i][j] = dp[i -.
2021-09-02 22:52:09
54
原创 2021-09-01 力扣165 - 比较版本号
一开始想的是逐位比较，但是需要考虑的例外比较多，考虑用strtok分割也比较麻烦。后来想到可以结合一下，只不过是用指针去分割，遇到点就比较。int compareVersion(char * version1, char * version2){ int v1Index = 0; int v2Index = 0; int v1Len = strlen(version1); int v2Len = strlen(version2); while (v1Index .
2021-09-01 23:34:42
104
原创 2021-08-29 剑指 Offer II 010. 和为 k 的子数组
一开始看到连续子数组就考虑用滑动窗口，滑动窗口模板如下# 滑动窗口模板left,right = 0, (0 or 1)ret = total = 0while right < len(nums): 更新total值 while 窗口内数据不满足要求 1. 更新total值 2. 收缩左边界 更新ret最大值返回 ret代码int subarraySum(int* nums, int numsSize, int k){ int res .
2021-08-29 23:26:50
114
原创 2021-08-17 力扣643-子数组最大平均数
遇到这种连续子数组的问题用双指针或滑动窗口是比较方便的。一个长度为n的数组，有n-k+1个连续大小的子数组，如果每次去计算则耗时太久，采用滑动窗口，不断的向右滑动，找到和最大的子数组即为答案。i > k时，sums[i] = sums[i-1] - nums[i-k] + nums[i];double findMaxAverage(int* nums, int numsSize, int k){ double sum = 0; for (int i = 0; i < k.
2021-08-17 23:57:35
63
原创 2021-08-11 力扣162-寻找峰值
方法一：线性扫描本方法利用了连续的两个元素 nums[j]nums[j] 和 nums[j + 1]nums[j+1] 不会相等这一事实。于是，我们可以从头开始遍历 numsnums 数组。每当我们遇到数字 nums[i]nums[i]，只需要检查它是否大于下一个元素 nums[i+1]nums[i+1] 即可判断 nums[i]nums[i] 是否是峰值。可以通过分别讨论问题的全部三种可能情况来理解本方法的思路。降序排列对于降序排列，第一个元素就是峰值升序排列线性排序中一直比较num.
2021-08-11 23:25:53
70
原创 力扣457
这道题要好好读题，意思就是有一个环形数组，重点是这个环形数组，之前有个判断是否环形链表的题目，定义快慢指针，慢的每次走一步，快的走两步，一旦存在相等的情况，那么一定成环。本题就是在判断成环的过程中添加限制条件。/* 题目中给的是一个环形数组，环形数组，那么快慢指针是一定能相遇的，程序要判断的是如果按照题目中的限制条件去走的话能不能相遇*/int GetNextIndex(int *nums, int numsSize, int curIndex){ return (((curIndex .
2021-08-07 23:57:17
46
原创 2021-08-05 力扣809
对于这种中间有重复字母的匹配，可以顺序记录字母并且记录字母重复的个数，匹配字母如果能匹配则首先必须顺序上具有和目标字符串相同的字母顺序，其次再考虑题目中给的个数限制，如题所述，目标字符必须达到3或者3以上且比匹配字符个数大。在字母顺序相同的前提下，令目标字符串中顺序字符的个数为C1,匹配字符串中顺序字符的个数为C2，那么能匹配的情况如下，C1 == C2 —匹配C1 > C2 && C1 > 3 —p匹配C1 < C2 --不匹配bool IsMatch(C.
2021-08-06 00:01:56
58
原创 2021-08-03 力扣209 长度最小子数组
做这个题真的是无语了，审错题目了，题目说的连续子数组，我一直在按非连续的去分析，导致一直再搞深搜。。。对于这种连续子数组问题，双指针是最简单的办法了。。。int minSubArrayLen(int target, int* nums, int numsSize){ int sum = 0; int left = 0; int right = 0; int resLen = INT_MAX; while(right < numsSize) { .
2021-08-04 00:00:23
48
原创 2021-08-02 力扣201. 数字范围按位与
看到这道题，第一反应是暴力解，但肯定会超时。。。后来想到了类似前缀和的方法res[i] = res[i-1] & num[i]，分析了一下无法得到区间值。后来看了下答案，害，发现自己分析的深度太浅了。。。讨论区分析如下：只要找到前面公共的即可，后面的补0.记录工作后辛苦刷题的一天。。。...
2021-08-02 22:47:02
72
转载 背包问题模板
背包问题：背包问题是动态规划非常重要的一类问题，它有很多变种，但题目千变万化都离不开我根据力扣上背包问题的题解和一些大佬的经验总结的解题模板背包定义：那么什么样的问题可以被称作为背包问题？换言之，我们拿到题目如何透过题目的不同包装形式看到里面背包问题的不变内核呢？我对背包问题定义的理解：给定一个背包容量target，再给定一个数组nums(物品)，能否按一定方式选取nums中的元素得到target注意：1、背包容量target和物品nums的类型可能是数，也可能是字符串2、target可能题
2021-06-16 23:23:01
82
原创 leetcoed[C]--反转整数
整数反转的这个题目，一开始想的是先判断是否为负数，如果为负数就转为整数，但是测试用例中给了一个-2147483648，转化为正后直接就超了有符号整数最大值 2147483647，所以还是不这么做了。原来是这么做的，此方法中还存在一个问题，就是结果res可能超过无符号整数的范围，所以用Long 比较好。下面是修改后的代码int reverse(int x){ if (x == 0) { return 0; } int flag = 0; long in.
2020-08-03 09:52:36
111
原创 leetcode4寻找两个正序数组的中位数
方法一：将两个数组合并寻找中位数，时间复杂度O（m+n）方法二：二分法主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 进行比较，这里的 “/” 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 … k/2-2] 共计 k/2-1 个* nums2 中小于等于 pivot2 的元素有 nums2[0 … k/2-2] 共计 k/2-1 个* 取 pivot = min.
2020-05-25 16:00:09
283
1
转载 leetcode76 最小覆盖字串
详细解答见：https://leetcode-cn.com/problems/minimum-window-substring/solution/hua-dong-chuang-kou-suan-fa-tong-yong-si-xiang-by-/
2020-05-23 23:52:16
117
转载 Leetcode. 1371 每个元音包含偶数次的最长字符串
Leetcode. 1371 每个元音包含偶数次的最长字符串解题思路对于代码中一些变量的解释，这里由于只考虑每个元音奇偶次数，因此考虑用二进制来记录；定义特征，aeiou分别对应二进制00001，00010，00100，01000，10000其中0表示对应元音出现了偶数次数，1表示奇数从左往右遍历字符串，不断更新dp；dp[pattern]的作用是用来记录当前索引值下对应的元音奇偶次数组合特征；例如：如果pattern为10，也就是对应二进制 01010，dp[pattern] = 8
2020-05-20 17:29:28
215
转载 套路解决递归问题
相信不少同学和我一样，在刚学完数据结构后开始刷算法题时，遇到递归的问题总是很头疼，而一看解答，却发现大佬们几行递归代码就优雅的解决了问题。从我自己的学习经历来看，刚开始理解递归思路都很困难，更别说自己写了。我一直觉得刷算法题和应试一样，既然是应试就一定有套路存在。在刷题中，我总结出了一套解决递归问题的模版思路与解法，用这个思路可以秒解很多递归问题。递归解题三部曲何为递归？程序反复...
2019-10-20 22:21:06
187
转载 智能指针
本文介绍c++里面的四个智能指针: auto_ptr, shared_ptr, weak_ptr, unique_ptr 其中后三个是c++11支持，并且第一个已经被c++11弃用。为什么要使用智能指针：我们知道c++的内存管理是让很多人头疼的事，当我们写一个new语句时，一般就会立即把delete语句直接也写了，但是我们不能避免程序还未执行到delete时就跳转了或者在函数中没有执行到最后的d...
2019-09-01 22:48:50
147
转载 数据库的锁
转自： https://blog.csdn.net/aluomaidi/article/details/52460844什么是事务（Transaction）？是指作为单个逻辑工作单元执行的一系列操作，要么完全地执行，要么完全地不执行。 事务处理可以确保除非事务性单元内的所有操作都成功完成，否则不会永...
2019-08-29 18:59:58
128
转载 关系型数据库与非关系型数据库
一、关系型数据库 关系型数据库，是指采用了关系模型来组织数据的数据库。 关系模型是在1970年由IBM的研究员E.F.Codd博士首先提出的，在之后的几十年中，关系模型的概念得到了充分的发展并逐渐成为主流数据库结构的主流模型。 简单来说，关系模型指的就是二维表格模型，而一个关系型数据库...
2019-08-29 18:00:08
178
转载 联合索引最左前缀匹配
前言之前在网上看到过很多关于mysql联合索引最左前缀匹配的文章，自以为就了解了其原理，最近面试时和面试官交流，发现遗漏了些东西，这里自己整理一下这方面的内容。最左前缀匹配原则在mysql建立联合索引时会遵循最左前缀匹配的原则，即最左优先，在检索数据时从联合索引的最左边开始匹配，示例：对列col1、列col2和列col3建一个联合索引KEY test_col1_col2_col3 on ...
2019-08-29 11:16:48
159
原创 最大递增子序列
【题目】：给定数组arr，返回arr的最长递增子序列。【例子】：arr=[10,22,9,33,21,50,41,60,80],返回的最长递增子序列为[10,22,33,41,60,80]长度为6思路：动态规划dp[i]为以下标为i的元素结尾的子数组的长度。开始将dp所有元素初始化为1。为得到dp[i]，需向前遍历，找到比a[i]小而且使dp[i]最大的那个数。/*. 生成长度为N...
2019-08-16 10:59:17
1421
原创 最少数量货物装箱问题
题目描述有重量分别为3，5，7公斤的三种货物，和一个载重量为X公斤的箱子（不考虑体积等其它因素，只计算重量）需要向箱子内装满X公斤的货物，要求使用的货物个数尽可能少（三种货物数量无限）输入描述:输入箱子载重量X(1 <= X <= 10000)，一个整数。输出描述:如果无法装满，输出 -1。如果可以装满，输出使用货物的总个数。示例1输入4输出-1说明无法装满...
2019-08-14 16:51:11
1624
原创 寻找距离最小的点对
问题描述：给定平面上N个点的坐标，找出距离最近的两个点。解决方法：参考编程之美书上所介绍的解法三（分治思想）。方法框架： 1. 将点按照x坐标排序，找到中间点M将所有点分成两个部分，Left和Right。找出Left和Right区域分别最小的两点距离DisL, DisR, 则最短距离为DisMin=Min(DisL, DisR);在所有节点中找到x属于(M.x-DisMin,...
2019-08-13 16:10:28
1348
原创 最长回文子串--动态规划（O(N^2)）
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。示例 1：输入: “babad”输出: “bab”注意: "aba"也是一个有效答案。示例 2：输入: “cbbd”输出: “bb”回文串的定义我就不啰嗦了。对于这道题，我的第一反应是用动态规划方法解。假设字符串s的长度为length，建立一个length*length的矩阵dp。dp[i][...
2019-08-09 16:43:40
112
原创 求最大回文子串长度的一种方法（非最优，时间复杂度为O(N^2)）
#include "iostream"#include "string"#include "sstream"#include "vector"#include "algorithm"using namespace std;int LongestPalindrome1(string s, int n){ int i, j, max, c; if (s =="" || n <...
2019-08-09 13:57:02
141
原创 魔法深渊
题目描述前几个月放映的头号玩家简直火得不能再火了，作为一个探索终极AI的研究人员，月神自然去看了此神剧。由于太过兴奋，晚上月神做了一个奇怪的梦，月神梦见自己掉入了一个被施放了魔法的深渊，月神想要爬上此深渊。已知深渊有N层台阶构成（1 <= N <= 1000)，并且每次月神仅可往上爬2的整数次幂个台阶(1、2、4、…)，请你编程告诉月神，月神有多少种方法爬出深渊输入描述:输入...
2019-08-08 16:02:21
304
原创 将满二叉树转换为求和树
将满二叉树转换为求和树给满出二叉树，编写算法将其转化为求和树什么是求和树：二叉树的求和树， 是一颗同样结构的二叉树，其树中的每个节点将包含原始树中的左子树和右子树的和。二叉树：10/ -2 6/ \ / \8 -4 7 5求和树：20(4-2+12+6)/ 4(8-4) 12(7+5)/ \...
2019-08-08 14:02:15
884
转载 数组右移
下面我们来看下题目的要求。题目要求：设计一个算法，把一个含有N个元素的数组循环右移K位，要求时间复杂度为O(N)O(N)，且只允许使用两个附加变量。题目解答我们来自己给个例子，来帮助自己思考。如数组为[1, 2, 3, 4, 5, 6, 7, 8]，循环移位4次。 原始序列：[1, 2, 3, 4, 5, 6, 7, 8] 右移1位：[8, 1, 2, 3, 4, 5, 6, 7] ...
2019-08-07 15:13:52
328
原创 小数转分数
理论在这里https://blog.csdn.net/puqutogether/article/details/43267101#include "iostream"#include "vector"#include "string"#include "math.h"#include "algorithm"using namespace std;int gcd(long x, l...
2019-08-06 16:03:14
378
原创 求最大公约数
最大公约数两种求法#include "iostream"#include "algorithm"using namespace std;int flag = 0;//解法1：辗转相除法//假设用f(x,y),x > y,表示x,y的最大公约数，取k = x/y,b = x%y//则x = ky+b,如果一个数能同时整除x,y则必能同时整除y,b;int gcd(int x,...
2019-08-06 00:02:50
192
原创 最大乘积子数组
最大乘积子数组这个问题可以采用和求序列的最大和子数组同样的动态规划，不同的是此类问题除了记录以上一个为结尾的子序列的最大乘积外还应记录最小乘积，因为下一个可能是负数，负负得正。核心代码如下以当前数为结尾的子序列的乘积的最大值和最小值cur_max = max(max(last_max * a[i], last_min*a[i]),a[i]);cur_min = min(min(last_...
2019-08-05 22:03:17
168
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人