2023.3.26
剑指 Offer 03. 数组中重复的数字
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
1.暴力枚举
class Solution {
public int findRepeatNumber(int[] nums) {
int w = -1;
for(int i=0;i<nums.length-1;i++){
for(int j = i+1;j<nums.length;j++){
if(nums[i]==nums[j]){
w= nums[i];
break;
}
}
}
return w;
}
}
但是时间超了，这也正常
所以要换方法
2(我也不知道叫什么名字)
class Solution {
public int findRepeatNumber(int[] nums) {
int a[] = new int[nums.length];
int b[] = new int[1000000] ;
int w = -1;
Arrays.fill(b,0);
for(int i =0 ;i<nums.length;i++){
a[i] = nums[i];
if(b[a[i]]>0){
w = a[i];
break;
}
b[a[i]]++;
}
return w;
}
}
用了一种类似桶排序的方法,a[]可有可无,主要是b[]这个数组是用来存储一个数出现的次数,次数超过我设定的值,就返回
2023.3.27
剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
方法一:
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
int x = matrix.length-1;
int y = 0;
while(x>=0&&y<=matrix[0].length-1){
if(matrix[x][y]>target){
x--;
}
else if(matrix[x][y]<target){
y++;
}
else{
return true;
}
}
return false;
}
}
2023.3.28
剑指 Offer 12. 矩阵中的路径
相关企业
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
例如，在下面的 3×4 的矩阵中包含单词 "ABCCED"（单词中的字母已标出）。
示例 1：
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true
示例 2：
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false
class Solution {
public boolean exist(char[][] board, String word) {
char[] words = word.toCharArray();
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(dfs(board, words, i, j, 0)) return true;
}
}
return false;
}
public boolean dfs(char[][]board,char[]words,int i,int j,int length){
if(i<0||j<0||i>=board.length||j>=board[0].length|| board[i][j] != words[length]){
return false;
}
if(length==words.length-1){
return true;
}
board[i][j] = '\0';
boolean what = dfs(board,words,i+1,j,length+1)||dfs(board,words,i,j+1,length+1)
||dfs(board,words,i-1,j,length+1)||dfs(board,words,i,j-1,length+1);
board[i][j] = words[length];
return what;
}
}
board[i] [j] = '\0';
这一步是把扫描过的全部变为'\0'
board[i] [j] = word[k];这一步是将当前位置 (i, j) 上的字符重新设置为原来的字符 word[k]，在回溯时恢复状态。这是为了在下一次搜索中继续使用当前位置上的字符。
在搜索过程中，程序使用了一个标记技术，将访问过的字符设置为一个特殊的字符（例如 '\0'），以避免在搜索时重复访问同一个字符。当回溯到上一个状态时，程序需要将已经访问过的字符重新设置为原来的字符，以便在下一次搜索时再次使用。这就是这一行代码的作用。
上面的是用chatgpt写出来的,下面的是我自己的理解
直接看dfs里面的代码:
i表示的是x坐标,j表示的是y坐标
第一个if语句中x坐标小于0或者大于board.length-1或者y小于0或者大于board[0].length-1或者board[i] [j] != words[length]则返回false
第二个if语句length ==word.length-1的时候返回false
board[i] [j] = words[length];这句是因为 之前写过board[i] [j] = '\0';把匹配的这个置为'\0'
但是为了不影响其他线路,需要回溯一下。
2023.3.29
剑指 Offer 14- I. 剪绳子
不太熟练
给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问 k[0]*k[1]*...*k[m-1] 可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。
示例 1：
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1
示例 2:
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36
提示：
2 <= n <= 58
1.动态规划
class Solution {
public int cuttingRope(int n) {
int dp[] = new int[n+1];
for(int i = 2;i<=n;i++){
int max = 0;
for(int j = 1;j<i;j++){
max = Math.max(max,Math.max(j*(i-j),j*dp[i-j]));
}
dp[i] = max;
}
return dp[n];
}
}
我原本以为第一个for循环没有什么用,就把它和dp[i] = max这两句话给删除了
最后只过了一点点的样例
2023.3.30
剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1:
输入:
[
[1,3,1],
[1,5,1],
[4,2,1]
]
输出: 12
解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
1.动态规划
class Solution {
public int maxValue(int[][] grid) {
int dp[][] = new int[grid.length][grid[0].length];
for(int i = 0;i<grid.length;i++){
for(int j = 0;j<grid[0].length;j++){
if(i==0&&j==0){
dp[i][j] = grid[i][j];
}
else if((i==0&&j!=0)){
dp[i][j] = dp[i][j-1]+grid[i][j];
}
else if((i!=0&&j==0)){
dp[i][j] = dp[i-1][j]+grid[i][j];
}
else{
dp[i][j] = Math.max(dp[i-1][j]+grid[i][j],dp[i][j-1]+grid[i][j]);
}
}
}
return dp[grid.length-1][grid[0].length-1];
}
}
Comments | NOTHING