第17节
题目1:在有序二维数组中查找目标值
给定一个每一行有序、每一列也有序,整体可能无序的二维数组
再给定一个数num,
返回二维数组中有没有num这个数
例子
数组如下,找 6 是否存在。
1 3 5 7
2 4 6 13
3 9 14 14
思路
力扣上做过原题。
从左下角开始,向右上角走。如果当前小于 target,则向右走。如果当前大于 target,则向上走。
题目2:
给定一个每一行有序、每一列也有序,整体可能无序的二维数组
在给定一个正数k,
返回二维数组中,整体第 k 小的数
Leetcode原题:
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/
思路
1 3 5 7
2 4 6 13
3 9 14 14
假设我先任意选一个数字10,想要求出所有小于10的数有多少个。从右上角向左下角走,如果当前数小于10,就往下走(此时当前位置左方全是小于10的数),如果大于10,就往左走。沿途通过下标计算,累加所有小于10的数,假设有m个。
根据上述方式,我可以知道小于某个数字的数有多少个。
而整体来看,我知道整个数组最小值是左上角的 min,最大值是右下角的 max,这样我就可以通过二分查找的方式,让 mid=min+(max-min)/2,求出比 mid 小的数有 m 个,如果 m < k,就让 max = mid 继续二分;否则如果 m>k,让 min = mid 继续二分。
如果最后得到答案是 res,而整个数组中没有 res 这个数字,你需要找到距离 res 最近,并且比 res 小的数。
题目3
Leetcode原题:
https://leetcode.com/problems/palindrome-pairs/
题目4:等于目标字符串的子序列个数(DP)
给定两个字符串S和T
返回S的所有子序列中
有多少个子序列的字面值等于T
思路
样本对应模型,可能性根据结尾字符来划分。
假设S的长度为i,T的长度为j,则 dp[i][j]
表示:从 S 序列 [0…i] 范围上随便选,有多少个子序列的字面值等于 T[0…j] 这个前缀字符串。
dp 表的右下角,就表示了 S 整体字符串有多少个子序列的字面值等于 T 字符串。
状态怎么转移?当我来到 dp[i][j]
的时候,
- 可能性1:不使用 i 位置的字符,则
dp[i][j] = dp[i-1][j]
- 可能性2:只有在 S[i] == T[j] 的情况下才可以,使用 S 字符串 i 位置的字符来匹配 T 字符串 j 位置的字符,则
dp[i][j] = dp[i-1][j-1]
考虑上述两种可能性,相加,得到 dp[i][j] = dp[i-1][j] + dp[i-1][j-1]
public static int dp(String S, String T) {char[] s = S.toCharArray();char[] t = T.toCharArray();int N = s.length;int M = t.length;int[][] dp = new int[N][M];// s[0..0] T[0..0] dp[0][0]dp[0][0] = s[0] == t[0] ? 1 : 0;for (int i = 1; i < N; i++) {dp[i][0] = s[i] == t[0] ? (dp[i - 1][0] + 1) : dp[i - 1][0];}for (int i = 1; i < N; i++) {for (int j = 1; j <= Math.min(i, M - 1); j++) {dp[i][j] = dp[i - 1][j];if (s[i] == t[j]) {dp[i][j] += dp[i - 1][j - 1];}}}return dp[N - 1][M - 1];
}
题目5
给定一个字符串Str
返回Str的所有子序列中有多少不同的字面值
Leetcode原题:
https://leetcode.com/problems/distinct-subsequences-ii/
思路
主要是观察规律。
题目6
给定一个数组arr,长度为N,arr中的值只有1,2,3三种
arr[i] == 1,代表汉诺塔问题中,从上往下第i个圆盘目前在左
arr[i] == 2,代表汉诺塔问题中,从上往下第i个圆盘目前在中
arr[i] == 3,代表汉诺塔问题中,从上往下第i个圆盘目前在右
那么arr整体就代表汉诺塔游戏过程中的一个状况
如果这个状况不是汉诺塔最优解运动过程中的状况,返回-1
如果这个状况是汉诺塔最优解运动过程中的状况,返回它是第几个状况
题目7
Leetcode 原题:
https://leetcode.com/problems/shortest-bridge/