这道题目只保证了矩阵从左到右、从上到下分别是单调递增，没有保证全局，所以没办法将下标映射成一维数组来做，但是矩阵的右上角和左下角保证了往不同的两个方向移动分别是减少和增加，所以可以从这两个地方开始搜索，达到类似二分的效果。func searchMatrix(matrix [][]int, target int) bool { n := len(matrix) m := len...
Articles in the category of Leetcode
- Home
- Leetcode
这两道题虽然粗看感觉挺简单的，但是需要考虑到的东西比较多，比如如果用dfs，需要通过记忆之前计算的答案进行剪枝，否则时间复杂度是指数级别，会导致超时，用动...
最长公共子序列（LCS）定义 dpi 为 text1[0..i-1]和text2[0..j-1]的最大公共子序列，那么有转移方程如下：其实这个也非常的好理解，因为只有 text1[i-1] == text2[j-1] 的时候才能对答案做贡献，所以第一条方程就出来了，而第二条就是因为没有办法做贡献，只能在之前的部分中取一个最大的值。于是得到代码如下：func longestCommonSubs...
我们知道 $x^y$ 其实就是 x 乘了 y 次，但是我们如何减少乘的次数来节省时间复杂度呢？其实可以让 y 每次都减半，x 基数变大即可。比如 $2^{...
每日温度这道题最难想到的就是如何利用单调栈来记录状态，需要存储的实际上就是温度单调递减的数组下标，然后当碰到温度比栈顶高的值时，就可以将单调栈内的部分弹出，两个下标的差就是对应的天数了。func dailyTemperatures(temperatures []int) []int { n := len(temperatures) res := make([]int, n) ...