- 博客(26)
- 收藏
- 关注
RSS订阅原创 动态规划-面试题08.01三步问题-力扣(LeetCode)
计算四节台阶的方法需要前三阶各自的方法数，所以初始化dp[1] = 1,dp[2] = 2,dp[3] = 4。该题空间优化与第N个泰波那契数类似，如果感兴趣的朋友可以去看看我之前的博客。根据上面的分析和题目要求，dp[i]表示：到达i位置，一共有多少种方法。根据题目要求需要返回在i点的方法数，所以返回dp[n]从i-2->i dp[i-2]从i-3->i dp[i-3]dp[i] 从i-1->i dp[i-1]以i位置的状态，以最近一步划分问题。以4为起点，从左往右依次填写。
2025-05-05 00:46:32
118
原创 动态规划-1137.第N个泰波那契数-力扣(LeetCode)
填表的顺序：例先填dp[4]，dp[4] = dp[3] + dp[2] + dp[1]，为了避免所需的状态未计算，所以从3开始从左到右依次填入数据进dp表中。初始化：根据题目我们需要初始化dp[0] = 0,dp[1] = dp[2] = 1即可，其余的可以通过定义式计算出来。我们能知道时间复杂度是O(1),空间复杂度是O(N)，下面我们可以用滚动数组对其进行优化，使其空间复杂度为O(1).结合示例我们需要得出第i个泰波那契数的大小，由此我们能得出状态表示，dp[i]表示：第i个泰波那契数。
2025-05-03 18:22:41
380
原创 贪心算法-2208.将数组和减半的最小操作数-力扣(LeetCode)
我们需要将数组和减小为一半的次数最少，所以根据贪心算法，我们需要取数组中最大的数进行减半操作 ，但最优解也许不是每次都选择最大数进行减半操作，为什么贪心解就是正确的解呢？统计数组和的同时将数据插入到大根堆中，top出最大的数对其减半，然后pop掉原来数据，并将减半后的数重新插入回去，计数器++，然后重复这样的行为直到数组和减少到至少一半为止。这里要注意恰好这个字眼，说明对任意数减小一半是不需要向上取整的，所以我们需要定义double类型的数据。这里的大根堆使用 priority_queue容器。
2025-04-28 20:34:21
621
原创 贪心算法-860.柠檬水找零-力扣(LeetCode)
当20,10的时候，用了下面种补钱方式，10元就无法补钱，所以优先使用10+5的补钱方式，其次是5+5+5的补钱方式，如果两种都不满足，则返回false。我们需要注意我们是没有初始零钱的，所以当第一个顾客支付10或20时，无法找零此时返回false。当顾客支付20元时，我们有两种补钱方式(这里就用到了贪心),一种是10+5，另一种是5+5+5.当顾客支付10元时，我们要先判断是否有零钱补，如果没有则返回false，有则补5元。首先对于顾客支付的钱共有三种，5，10，20，我们需要对其分别讨论。
2025-04-27 23:47:22
823
原创 双指针-611.有效三角形的个数-力扣(LeetCode)
由于我们对数组先做排序处理，即最后的元素为最大的元素，固定最大元素，left在开头位置，right在固定最大的元素的前一个位置，通过双指针找出符合条件的三角形。这里需要得出所有符合条件的三角形组合，并且当有重复元素时，如2,3,4用的是第一个2,3,4用的第二个2一样。由于需要三个数，所以通过三层for循环，用于枚举出所有排列可能，然后根据上面的条件判断是否满足条件。枚举最大的数为n次，每次都要通过双指针遍历数组也是n，所以时间复杂度为O(n^2)解法2：根据单调性，使用双指针 O(n^2)
2025-04-26 00:51:30
192
原创 前缀和-724.寻找数组的中心下标-力扣(LeetCode)
由于计算f[0]时会发生越界访问，所以需要提前计算出f[0]的值，由于[0，-1]内没有元素，所以f[0]=0。g[n-1]同理，g[n-1]=0。而本题被i划分为了两个区间[0,i-1]和[i+1,n-1],所以我们只需要计算出[0,i-1]的前缀和,[i+1,n-1]的后缀和,比较是否相等即可。固定i，计算[0,i-1]的和，计算[i+1,n-1]的和，然后比较是否相等。遍历i为n次，每次计算n-1个数据的值，所以时间复杂度为O(n*2).解法1：暴力枚举 O(n*2)(时间复杂度)
2025-04-24 22:59:34
268
1
原创 双指针-11.盛水最多的容器-力扣(LeetCode)
当然这种解法无疑是会超时的，无论遇到什么题我们都需要知道暴力解法是怎么样的，我们的解法都是在暴力解法的基础上优化的。需要left指向起始位置，right指向末尾位置，v来计算每次枚举的容量，areamax赋值INT_MIN，用与比较和记录最大值。利用双指针，一端在开头，一端在末尾，方向相反去遍历heigh数组，当相等时结束循环，对枚举得到v做max处理得出最大的一个。结合示例我们能发现装水的多少取决于最短的直线，所以为了最大容量需要两边最大且距离长。解法2：利用单调性，使用双指针。
2025-04-22 14:41:17
253
1
原创 分治-快排-75.颜色分类-力扣(LeetCode)
给定一个数组将其元素按照0，1,，2三段式排序，并且在原地进行排序。用cur遍历数组，left记录0的最左侧，right记录2的最右侧。left初始值为-1，right的初始值为n，cur初始值为0.通过示例来得出nums[i]的三中情况。省流版，循环条件为cur<right。
2025-04-20 00:57:59
421
1
原创 数据结构之栈和队列
这里取反是为判断栈内元素是否为空，如果为空返回true，取反后为false，assert报错，不为空false，取反为true，assert不报错。这里的assert用于判断ps指针是否为空指针，capacity用于记录栈的空间大小，当top=capacity时意味着空间不够了需要扩容，这里用realloc在之前空间的基础上二倍扩容，这里的reallloc可以原地扩容，但当后面空间不够的时候就只能异地扩容了。这里的栈是用顺序表实现的，而队列则是用链表来实现的，这里的队列需要管理头指针和尾指针。
2025-04-19 00:53:23
1497
1
原创 滑动窗口-904.水果成篮-力扣(LeetCode)
在观察了数据量在10^5，可以开一个数组记录个数，然后用kinds维护水果种类，进窗口kinds++，在删除时，kinds--，从原来的76ms->4ms。fruits[i]代表果树的种类，且只有两个篮子，每个篮子只能装单一类型的水果，每个篮子能装的水果总量没有限制，要求返回可以收集的水果最大数。出窗口：把hash的fruits[left]位置的值减1，并判断hash[fruits[left]]的值是否为0，为0则erase。看到最后，如果对您有帮助，请留下一个免费的赞，期待下期再见！
2025-04-16 23:50:28
483
原创 滑动窗口-1004.最大连续1的个数III
但是看看下面的报错的样例，我们可以分析一下，放在while内，还是外面。这是我们结合示例1分析的过程，在过程中我们发现在计算长度后如果不对反转为1的0进行还原，将会影响其他的长度结果。2.进窗口：right右移，如果是1，无视，如果是0，zero计数器+1；经过上面的分析，我们将问题转化为找出最长的子数组，且0的个数不超过个。出窗口：移动left，如果是1，无视，如果是0，zero计数器-1；看到最后，如果对您有所帮助，还请留下一个免费的赞，我们下期再见！如果在循环内，len=1，如果在最后，len=3.
2025-04-14 20:55:03
474
1
原创 滑动窗口-1658.将x减到0的最小操作数-力扣(LeetCode)
我们固定left移动right的过程我们叫做进窗口，在窗口了我们还需要做判断，判断sum是否大于target，大于我们就需要出窗口，即left向右移动，这时我们还需要一个len用于记录子数组的最大长度，由于需要返回-1，所以我们可以将len赋值为-1，最后输出结果是判断，如果len == -1，则说明没有最大子数组，返回-1，若结果不为-1，则返回与数组长度的差值。通过示例1抽象的图，我们由求解x的最短长度转变为求解target(sum-x)的最大长度，降低正面解题的难度。通过示例1我们能抽象出一幅图。
2025-04-11 21:09:38
793
原创 双指针-202.快乐数-力扣(LeetCode)
我们可以知道int的最大值为2.1x10^9,我们取9999999999，这比int大的多了，这时它的平方数为9^2x10=810，所以我们得到了一个范围及int产生的平方数的范围【1,810】，当经历811次操作后，根据鸽巢原理，必然会出现一个相同的数，即会出现循环）= fast，为了避免赋值时slow和fast值相同导致不能进入循环，我们可以让fast指向下一个平方数，为了方便计算平方数，我们需要自己实现一个函数去计算平方数。我们能发现平方数是不断更新的，所以我们可以用平方数的值用于做双指针。
2025-04-10 22:02:32
454
原创 模拟算法-495.提莫攻击-力扣(LeetCode)
我们可以注意到给出的t是以区间的方式给出的，就像上面的[1,4]我们就可以理解为分别在1和4发动了攻击，4的时间是最好算的，因为它是最后一次攻击，所以它的持续时间就等于duration，而1发动的攻击的中毒时长会受到下一次攻击的影响，题目上说攻击可以重置中毒计时器，所以我们需要注意给出的两次攻击的间隔时间或多次攻击的其中二次的间隔时间，这里可以用x代替间隔的时间。到这里就可以根据解析自己去实现代码了,
2025-04-07 21:38:54
427
原创 58.最后一个单词的长度-力扣(LeetCode)
还有示例2，这里与示例1不同的地方是最后是空格而不是英文字符，这时我们的pos就失去作用了，我们需要新的变量，pos1，pos2，其中pos1用于接收find_last_of在pos位置的基础上，去找二十六个字母大写或小写其中的一个并返回下标，pos2则是在pos1的基础上接收rfind找kong个的下标，这时我们就锁定了最后一个单词的区间位置，它的长度为pos1-pos2。这里用num来接收计算出来的单词长度，而最后的三目操作符意思是当num为0时返回pos1-pos2，否则就返回num本身。
2025-04-06 19:58:56
607
原创 917.仅仅反转字母-力扣(LeetCode)
通过遍历字符串找到\0’之前的位置记为tail，将s赋值给cur。然后由于两两交换，所以循环的条件是cur<dest。然后只有当*cur(对cur指针解引用，即cur指针指向的内容)和*dest都为英文字母时，才开始交换；否则根据判断如果*cur是英文字母，则对*dest是非英文字母，所以对dest--；如果*dest是英文字母，则*cur是非英文字母，cur++。非英文字母保持原位，英文字母不管大小写都要交换，所以需要判断是否为英文字母。这里Swap函数需要我们自己实现，如果是c++的话则不需要。
2025-04-04 23:30:00
316
原创 二分查找-704.二分查找-力扣(LeetCode)
这里加一操作对数据个数为奇数时没有影响，当数据为偶数时，二分点有两个，上面没加一的mid是靠近left的那个二分点，而加一的mid则是靠近right的按个二分点。由于是循环进行的，所以我们还需要确定循环的条件。回到我们的二分查找，我们需要以下几个变量，left(左区间),right(右区间),mid(二分点),会遇到三种情况，大于target，小于target，或等于target。这里可以不局限于找中间点，三分点，四分点等等都是可以的，不过，根据概率学的数学期望，二分点无疑是最好的。解法二:二分查找算法。
2025-04-01 15:15:56
541
原创 滑动窗口-209.长度最小的数组-力扣(LeetCode)
一、题目解析 二、算法原理解法1:暴力枚举出所有的子数组的和0(n^2) 这里有两个点要注意，第一，我们可以观察到当sum>=target时，继续枚举是没有意义的，因为我们要找的是最短子数组，所以我们只需要枚举到right第一次满足条件时，就可以移动left了。第二点呢，我们在数组的遍历中需要维护好sum的值，当left移动过后，新的sum没必要在次遍历求和，只需要在之前的基础上减去之前left指向的值即可。解法2:利用上面第一点的发现，我们可以使用“滑动窗口”也叫“同向双指针”优化暴力枚举我们需要初始化几
2025-03-31 23:49:52
570
原创 双指针-283.移动零-力扣(LeetCode)
结合实例来看，该题需要完成对元素的移动，将0元素放在最右边，最左边为非0元素且相对顺序不变。当cur到n时，这时就只有两个区间:[0,dest],[dest+1,cur-1],也就和题目要求的一样左边为非0，右边为0元素。这里有两个指针，一个是cur：用于从左往右遍历数组，dest：已处理的区间内，非0元素的最后一个位置。2、当cur遇到非0 元素，Swap(dest+1,cur),cur++.dest++可以得到三个区间：[0,dest],[dest+1,cur-1],[cur,n-1]
2025-03-30 21:33:00
353
原创 每日一题:3046.分割数组-力扣(LeetCode)
同时注意到它们是均分的，分割的两个数组都要求包含互不相同的元素。所以这里小编提供一个思路，那就是借用简单的哈希表，来统计每个数字出现的次数，根据次数来判断是否成功分割。因为不需要返回分割数组，所以我们可以不做实际分割操作，但假设它们已被分割，去找成功分割的条件。这里根据题目的提示我们可以知道数组中的数据大小范围在1~100，所以我们需要开一个大小为101的数组，通过绝对映射将Hash[nums[i]]加一，来得到数组中数据出现的个数。因为是均分的，为奇数的话必定有一个存在相同的数据，所以不行；
2025-03-23 00:52:58
221
原创 带头双向循环单链表
将tail-.>-next指向newnode，newnode的prev指向tail，这时newnode成为新的尾，所以将newnode的next指向头结点也就是pHead，最后将pHead的prev指向newnode，恢复循环。通过pHead的next找到第一个节点或哨兵位本身并保存下来， 将pHead的next指向newnode，newnode的prev指向pHead，newnode的next指向prev，prev的prev指向newnode。11、双向链表删除pos位置的节点。
2025-03-22 01:02:26
686
原创 237.删除链表中的节点-力扣(LeetCode)
由图所示，我们没有头节点用于遍历链表，所以我们可以将pos指向的节点(即要被删除的节点)与pos的下一个节点交换值。这第一步的依据来源于上面的分析，即pos的后面必然存在节点，所以可以放心交换。第二步将pos->next->next赋值给pos->next，这样就改变了链接的指向(符合了分析条件中的第三点)，实现了没有头节点完成给定位置节点的删除。第二，被删除的节点存在于链表中且不属于尾节点；第三，要保证链表的顺序不变且删除的节点并未释放，即节点存在但不存在于原来链表中。
2025-03-04 23:35:25
105
原创 数据结构之单链表
答案是肯定的，直接将newnode赋值给我们的*pplist就可以：第二种情况，当链表不为空时，这时候尾插我们就要去找它的尾节点了，定义一个tail从头开始遍历链表找尾，找到后将newnode赋值给tail->next，完成尾插。当不给头节点时，我们又该怎么完成呢？根据前面的assert断言来看，我们能遇到的就只有pos存在且pos的next不为空，所以我们只需要用tmp保存pos下一个节点的地址，通过tmp找到tmp的下一个节点并将其赋值给pos->next，释放掉tmp并置空，完成pos位置后的删除。
2025-03-04 00:04:54
578
原创 9.回文数-力扣(LeetCode)
snprintf格式化类型和可变参数生成字符串，将其复制到s中，并在末尾添加空字符\0.若要写入的字符数(不包括\0)小于n，则正常写入并返回写入的字符数(不包括\0);若要写入的字符数大于等于n，则会截断字符串，只写入n-1个字符并添加\0，返回应该写入的字符数(不包括\0).此时，如果x等于ret，或者x等于ret除以10(这是针对整数位为奇数的情况，中间的数字不影响回文的判断)，那么x是回文数。在while循环中当x大于ret时，ret乘10并加上x的个位数字(x%10).x除以10(x/=10).
2025-02-04 20:52:26
343
原创 28.找出字符串中第一个匹配的下标-LeetCode
1.在题中已经给出char* haystack, char* needle，strstr会返回地址，所以我们要创建一个指针变量来接收strstr的返回值。2.由于char*haystack是可以改变的，所以通过strstr返回的地址与haystack来比较是否相等，对指针和计数器进行自加，实现指针的移动和下标的记录。上面所表达的大概含义为：在str1字符串中找str2这个字符串，并返回第一次出现的位置的地址：如果没有找到，则返回NULL。
2025-01-25 21:00:46
193
原创 c语言格式化输入与输出
1.%d 用于整型，%f 用于float类型浮点数，%lf用于double类型的浮点数，%Lf用于long diuble ，%c用于字符，%s用于字符串，%p用于地址，还有%zd用于sizeof的返回值等一系列格式化。2.在%f和%lf的%后加上一个点（.），在点的前面加上数可以控制数据的长度，在点后加上数则可以控制小数点的后几位。如，%.2f是保留为小数点后两位，%8.2f则是总长度为8，不够则前面加空格补满。1.除了%c以外，%d，%f，%lf等都会忽略空白字符。这只是基本的玩法，还有进阶的内容。
2025-01-22 08:32:41
531
3
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人