請設計一個函數，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑。路徑可以從矩陣中的任意一格開始，每一步可以在矩陣中向左、右、上、下移動一格。如果一條路徑經過了矩陣的某一格，那么該路徑不能再次進入該格子。例如，在下面的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.board=board;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都是整數，n>1并且m>1），每段繩子的長度記為 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都是整數，n>1并且m>1），每段繩子的長度記為 k[0],k[1]...k[m] 。請問 k[0]*k[1]*...*k[m] 可能的最大乘積是多少？例如，當繩子的長度是8時，我們把它剪成長度分別為2、3、3的三段，此時得到的最大乘積是18。
答案需要取模 1e9+7（1000000007），如計算初始結果為：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 ans=1;double temp=x;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 i=0;i<sum-1;i++){num[i] = i+1;}return num;}
}?
