文章采集网站,个人域名做企业网站,合肥建设网官方网站,wordpress用户等级请设计一个函数#xff0c;用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始#xff0c;每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格#xff0c;那么该路径不能再次进入该格子。例如#xf…请设计一个函数用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一格开始每一步可以在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格那么该路径不能再次进入该格子。例如在下面的3×4的矩阵中包含一条字符串“bfce”的路径路径中的字母用加粗标出。
[[a,b,c,e], [s,f,c,s], [a,d,e,e]]
但矩阵中不包含字符串“abfb”的路径因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后路径不能再次进入这个格子。 示例 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 提示
1 board.length 200 1 board[i].length 200
dfs
/*
思路
主方法对每个点dfs
dfs方法1、结束条件 2、记录并做标记 3、尝试周围 4、回溯恢复原样 5、返回值
*/
class Solution {char[] words;char[][] board;public boolean exist(char[][] board, String word) {this.boardboard;words word.toCharArray();for(int i 0; i board.length; i) {for(int j 0; j board[0].length; j) {if(dfs(i, j, 0)) return true;}}return false;}boolean dfs(int i, int j, int k) {if(i board.length || i 0 || j board[0].length || j 0 || board[i][j] ! words[k]) return false;if(k words.length - 1) return true;char tmp board[i][j];board[i][j] /;boolean res dfs(i 1, j, k 1) || dfs(i - 1, j, k 1) || dfs(i, j 1, k 1) || dfs(i , j - 1, k 1);board[i][j] tmp;return res;}
} 给你一根长度为 n 的绳子请把绳子剪成整数长度的 m 段m、n都是整数n1并且m1每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少例如当绳子的长度是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
leetcode343. 整数拆分
class Solution {public int cuttingRope(int n) {int[] dp new int[n 1];dp[1]1;for (int i 2; i n; i)for (int j 1; j i; j)dp[i] Math.max(dp[i], Math.max(j,dp[j]) * (i - j));return dp[n];}
} 给你一根长度为 n 的绳子请把绳子剪成整数长度的 m 段m、n都是整数n1并且m1每段绳子的长度记为 k[0],k[1]...k[m] 。请问 k[0]*k[1]*...*k[m] 可能的最大乘积是多少例如当绳子的长度是8时我们把它剪成长度分别为2、3、3的三段此时得到的最大乘积是18。
答案需要取模 1e971000000007如计算初始结果为1000000008请返回 1。 示例 1
输入: 2 输出: 1 解释: 2 1 1, 1 × 1 1 示例 2:
输入: 10 输出: 36 解释: 10 3 3 4, 3 × 3 × 4 36
提示
2 n 1000
思路
和上一题的区别的数范围很大。
动态规划不好比较大小因为会取模。
如果用大数类太麻烦而且失去意义。
我们首先考虑对于一段长n的绳子我们可以切出的结果包含什么
1会包含吗 不会因为1 * (k - 1) k, 只要把1和任何一个其他的片段组合在一起就有个更大的值 2可以 3可以 4可以吗 它拆成两个2的效果和本身一样因此也不考虑 5以上可以吗 不可以这些绳子必须拆因为总有一种拆法比不拆更优比如拆成 k / 2 和 k - k / 2
综上, 最后的结果只包含2和3(当然当总长度为2和3时单独处理), 那么很显然n 5时 3*(n - 3) 2 * (n - 2) 因此我们优先拆成3最后剩余的拆成2。最后的结果一定是由若干个3和1或2个2组成.
class Solution {public int cuttingRope(int n) {if(n 2) {return 1;}if(n 3){return 2;}int mod (int)1e9 7;long res 1;while(n 4) {res * 3;res % mod;n - 3;}return (int)(res * n % mod);}
} 请实现一个函数输入一个整数输出该数二进制表示中 1 的个数。例如把 9 表示成二进制是 1001有 2 位是 1。因此如果输入 9则该函数输出 2。
示例 1
输入00000000000000000000000000001011 输出3 解释输入的二进制串 00000000000000000000000000001011 中共有三位为 1。 示例 2
输入00000000000000000000000010000000 输出1 解释输入的二进制串 00000000000000000000000010000000 中共有一位为 1。 示例 3
输入11111111111111111111111111111101 输出31 解释输入的二进制串 11111111111111111111111111111101 中共有 31 位为 1。
思路对每一位判断即可。
public class Solution {public int hammingWeight(int n) {int res 0;while(n ! 0) {res n 1;n 1;}return res;}
} 实现函数double Power(double base, int exponent)求base的exponent次方。不得使用库函数同时不需要考虑大数问题。 示例 1:
输入: 2.00000, 10 输出: 1024.00000 示例 2:
输入: 2.10000, 3 输出: 9.26100 示例 3:
输入: 2.00000, -2 输出: 0.25000 解释: 2-2 1/22 1/4 0.25
说明:
-100.0 x 100.0 n 是 32 位有符号整数其数值范围是 [−231, 231 − 1] 。
快速幂
temp是每一位是多少ans是答案。注意都是幂关系全是乘
class Solution {public double myPow(double x, int n) {if (n 0) {x 1 / x;n -n;}double ans1;double tempx;while(n ! 0) {if((n 1) 1)ans*temp;n 1;temp*temp;}return ans;}
} 输入数字 n按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n 1 输出: [1,2,3,4,5,6,7,8,9]
说明
用返回一个整数列表来代替打印 n 为正整数
估计是想考大数呢。但是无脑直接过了。
class Solution {public int[] printNumbers(int n) {int sum (int)Math.pow(10,n);int[] num new int[sum-1];for(int i0;isum-1;i){num[i] i1;}return num;}
}
