给个offer行不行x

分类

sql(46) 算法题(26) 题解(2)

/ 注册

全部文章（共22篇）

题解 | JZ46 把数字翻译成字符串

这个题可以看作是带约束的走台阶一共有多少种走法。转移方程为： f[i] = f[i-1](nums[i]!='0') + f[i-2](nums[i-1] == '1' or (nums[i-1] == '2' and nums[i] <= '6')) c++ python ...

Python3 C++

2022-01-03

0 402

题解 | JZ48 最长不含重复字符的子字符串

这道题虽然放在动态规划里，但是其实是一道经典的尺取法（双指针）的题目。我们把两个指针都放在最左端，让R指针先移动。当R指针发现，移动到这个元素发现有重复元素了，那么我们需要移动L指针。为什么？因为我们始终维护的是这一段区间，也就是说当发现有重复值了，这一段区间是没法使用的，那么只要包括了这段...

Python3 C++

2022-01-02

0 424

题解 | JZ47 礼物的最大价值

这道题是二维动态规划的经典题，我们把0行和0列的值更新好了，就可以用下面的动态规划的方程来求解了。 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) + grid[i][j]; c++ python class Solution { public: ...

Python3 C++

2022-01-01

0 407

题解 | JZ63 买卖股票的最好时机(一)

这个题看一眼就会想到是动态规划的解法，但是我们发现它只能买卖一次股票，这个限制条件很强。而且下面也给出了空间复杂度为O(1),也就意味着DP的解法并不是最优的。所以我们想到一个方法，就是拿后面的最大值，来减去前面的最小值，就可以知道了。这里面需要注意有一个次序在里面，不是随便找一个最大值和最小值...

Python3 C++

2022-01-01

0 385

题解 | JZ85 连续子数组的最大和(二)

这题比上一题，增加了条件，需要我们把答案相同，最长的序列返回回来。所以，我们不能直接两行完事了，需要在比较的时候做一下判断。还是分为两个部分，第一部分更新dp[i]，第二部分更新ans。在第一部分中， sum+a[i] >= a[i] 这里特别要注意，要≥就可以更新，因为我们需要找到...

C++ Python3

2021-12-29

0 371

题解 | JZ42 连续子数组的最大和

这道题可以从标准的动态规划(DP)推过来。我们可以假设dp[i]表示以位置i为结尾的子数组的最大和是多少？所以对于我们要求的答案就是max(dp[0], dp[1], ..., dp[n]) 在这n个数中找到一个最大值就是我们最后的答案。而对于单独的dp[i]，我们可以递推得到： dp[i]...

Python3 C++

2021-12-28

0 358

题解 | JZ44 数字序列中某一位的数字

提示：力扣的数据更强，试试提交到力扣里。这个题意思挺清晰的，但是边界条件处理有点麻烦。可以通过找规律发现： 0 ... 9 每个数字都是一个字符共(101−100)×1(10^1-10^0) \times 1(101−100)×1个字符 10 ... 99 每个数字都是两个字符 (102−1...

C++ Python3

2021-12-27

0 315

题解 | JZ38 字符串的排列

因为本题的答案不看顺序，所以，也不用对初始数据进行预处理。本题最核心的函数就是dfs，关键看里面是怎么操作的。因为要N!把所有情况都遍历一遍，所以我们想到要配合一个done[]数组，来记录我们当前已经把哪些字符算进去了，这样好做到不重复。同时，我们还需要一个num变量记录一下当前已经加入了多少个...

C++ Python3

2021-12-26

0 495

题解 | JZ53 数字在升序数组中出现的次数

这题对于C++来说是很好写的,因为C++已经帮我们实现好了在一个排好序中的数组中二分查找某个数。 lower_bound()函数对应着查找给数第一次出现的位置，upper_bound()函数对应着查找大于给定数出现第一次出现的位置。因此，upper_bound()-lower_bound()的值，...

Python3 C++

2021-12-25

0 414

题解 | JZ59 滑动窗口的最大值

滑动窗口这道题是一道经典的题，需要用到双端队列，能在两头进行更新。这里C++代码中选用了vector作为双端队列的实现。我们需要记录两个数组，一个是位置的队列，另一个是值的队列。我们需要把这两个信息都记录住才能完成在队列里维护区间最大值的功能。我们在值的队列中，完成的是维护单调队列的操作。我...

C++ Python3

2021-12-24

0 421