Java日记2018-05-29

先补充昨天的
12 矩阵中的路径

public static boolean haspath(char[] matrix,int row,int col,char[] str) {
        if(matrix==null) return false;
        boolean[] visit = new boolean[matrix.length];
        for (int i = 0; i < visit.length; i++) {
            visit[i] = false;
        }
        for(int i=0;i<row;i++) {
            for(int j=0;j<col;j++) {
                if(haspathcore(matrix,row,col,i,j,str,0,visit)) return true;
            }
        }
        return false;
    }
    public static boolean haspathcore(char[] matric,int row,int col,int r,int c,char[] str,int k,boolean[] visit) {
        if(r<0||r>row||c<0||c>col||matric[r*col+c]!=str[k] || !visit[r*col+c]) return false;
        //搜索路径完成，返回true
        if(str.length==k) return true;
        //搜索路径中，当前矩阵设置为true，代表属于在搜索的路径
        visit[r*col+c] = true;
        if(haspathcore(matric,row,col,r-1,c,str,k+1,visit)||haspathcore(matric,row,col,r,c-1,str,k+1,visit)|| haspathcore(matric,row,col,r+1,c,str,k+1,visit)|| haspathcore(matric,row,col,r,c+1,str,k+1,visit))
            return true;
        //搜索路径失败，回退一步
        visit[r*col+c] = false;
        return false;
    }

13. 机器人的运动范围
    这题的条件是位数之和不能大于k，假设k=15,也就是进入坐标(23,24),位数之和2+3+2+4=11不大于15
    重新观察了一下，这个牛客网上的答案与众不同

`public` `class` `Solution {`

`boolean``[][] flag;`

`int` `count =` `0``;`

`int` `rows;`

`int` `cols;`

`public` `int` `movingCount(``int` `threshold,` `int` `rows,` `int` `cols){`

`if``(threshold <` `0``)`

`return` `0``;`

`flag =` `new` `boolean``[rows][cols];`

`this``.rows = rows;`

`this``.cols = cols;`

`go(``0``,` `0``, threshold);`

`return` `count;`

`}`

`private` `void` `go(``int` `i,` `int` `j,` `int` `t){`

`if``(i>=rows || j >= cols || flag[i][j]==``true` `|| getSum(i)+getSum(j)>t)`

`return``;`

`flag[i][j] =` `true``;`

`count++;`

`go(i, j+``1``, t);``//go left`

`go(i+``1``, j, t);``//go down`

`}`

`private` `int` `getSum(``int` `index){`

`int` `sum =` `0``;`

`while``(index !=` `0``){`

`sum += index%``10``;`

`index = index/``10``;`

`}`

`return` `sum;`

`}`

`}`

14. 剪绳子
    写的时候还是出错了的，循环的判断条件要注意

public static int integerBreak(int n) {
        if (n < 4)
            return n;
        int[] res = new int[n + 1];
        res[0] = 0;
        res[1] = 1;
        res[2] = 2;
        res[3] = 3;

        int temp = 0;
        for (int i = 4; i <= n; i++) {
            int max = 0;
            for (int j = 1; j <= i / 2; j++) {
                temp = res[j] * res[i - j];
                // System.out.println(temp);
                res[i] = Math.max(temp, max);
            }
        }
        System.out.println(res[n]);
        return res[n];

    }

15. 二进制中 1 的个数
    通过与运算的次数来算，算法还是蛮奇妙，容易忘

public int NumberOf1(int n) {
    int cnt = 0;
    while (n != 0) {
        cnt++;
        n &= (n - 1);
    }
    return cnt;
}