1. 矩阵中的路径

给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。

单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

例如，在下面的 3×4 的矩阵中包含单词 “ABCCED”（单词中的字母已标出）。
image.png

  1. 示例 1：
  3. 输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
  4. 输出：true
  5. 示例 2：
  7. 输入：board = [["a","b"],["c","d"]], word = "abcd"
  8. 输出：false
  10. 提示：
  12. 1 <= board.length <= 200
  13. 1 <= board[i].length <= 200
  14. board 和 word 仅由大小写英文字母组成

思路：

  • 使用广度优先搜索DFS

  • 以暴力的方法从一个位置进行开始探索，当对应到字符串对应位置的字符之后，然后进行进一步探索，上下左右所有位置，依次进行，最终以探索到字符串中所有字符结束。

    • 注意当前字符探索成功后，需要改变该位置字符，表示已经探索过，防止后面的重复探索。
    • 当当前元素已经探索，需要将该位置元素进行还原，以便于后续可能的探索。

  • 这里的“下一次探索”使用递归来实现

  • 递归结束的标志是，计数值达到了给定字符串的长度，表示已经找到了。向上一层返回true。最终一层一层进行返回到第一层将最终结果返回。
  • 这里注意递归时参数的传递。
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;
    }

    // i,j元素探索的位置，k为计数器(用于成功时停止递归)
    private boolean dfs(char[][] board,char[] words,int i,int j,int k){
        // 失败，当索引越界或者当前元素不为字符串对应位置元素，返回false给上一层，进行下一步探索
        if(i<0 || i>board.length-1 || j<0 || j>board[0].length-1 || board[i][j]!=words[k]) return false;
        if(k==words.length-1) return true; // 成功，每个元素都已按顺序找到，返回true给上一层，逐层返回，最终结束递归
        char tmp = board[i][j];
        board[i][j] = '\0'; // 修改元素，防止重复探索
        // 递归判断
        boolean res = dfs(board,words,i+1,j,k+1) || dfs(board,words,i-1,j,k+1) ||
            dfs(board,words,i,j+1,k+1) || dfs(board,words,i,j-1,k+1);
        board[i][j] = tmp; // 还原
        return res;
    }
}

2. 剪绳子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

思路：

  • 这里需要考虑的问题：截成多少段？相应的匹配每段绳子的长度是多少？
  • 思想：贪心算法
  • 举例：多个例子最后证明当截断后3越多则乘积越大。
    • 但是需要考虑的问题，当多个3匹配上的是4，那么这个4不应该分成3+1，而是分成2+2乘积会更大。
    • 所以需要判断当总长度>4的情况，需要判断取余后的长度是多少，进而分类进行计算结果。
      class Solution {
public int cuttingRope(int n) {
   // 尽可能多3 ,当存在4进行分解的时候,优先考虑2+2
   if(n==1 || n==2) return 1;
   if(n==3) return 2;
   // n>=4
   int a = n%3;
   int b = n/3;
   if(a==1){
       return (int)Math.pow(3,b-1)*4;
   }else if(a==2){
       return (int)Math.pow(3,b)*2;
   }
   return (int)Math.pow(3,b);
}
}