苏州加基森网站建设,扶风高端企业网站建设,杭州 网站外包,网页游戏网站模压板第17节
题目1#xff1a;在有序二维数组中查找目标值
给定一个每一行有序、每一列也有序#xff0c;整体可能无序的二维数组
再给定一个数num#xff0c;
返回二维数组中有没有num这个数
例子
数组如下#xff0c;找 6 是否存在。
1 3 5 7
2 4 6 13
3 9 14 …第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这样我就可以通过二分查找的方式让 midmin(max-min)/2求出比 mid 小的数有 m 个如果 m k就让 max mid 继续二分否则如果 mk让 min mid 继续二分。
如果最后得到答案是 res而整个数组中没有 res 这个数字你需要找到距离 res 最近并且比 res 小的数。
题目3
Leetcode原题
https://leetcode.com/problems/palindrome-pairs/ 题目4等于目标字符串的子序列个数DP
给定两个字符串S和T
返回S的所有子序列中
有多少个子序列的字面值等于T
思路 样本对应模型可能性根据结尾字符来划分。 假设S的长度为iT的长度为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长度为Narr中的值只有123三种 arr[i] 1代表汉诺塔问题中从上往下第i个圆盘目前在左 arr[i] 2代表汉诺塔问题中从上往下第i个圆盘目前在中 arr[i] 3代表汉诺塔问题中从上往下第i个圆盘目前在右 那么arr整体就代表汉诺塔游戏过程中的一个状况 如果这个状况不是汉诺塔最优解运动过程中的状况返回-1 如果这个状况是汉诺塔最优解运动过程中的状况返回它是第几个状况
题目7
Leetcode 原题
https://leetcode.com/problems/shortest-bridge/
