[3] 数组中重复的数字

题目一：找出数组中重复的数字

Description

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

Solution

第一次提交的代码：利用哈希表

public boolean duplicate ( int numbers[], int length, int[] duplication){
    if (numbers == null || length <= 1) return false;
    int[] table = new int[length];
    for (int i = 0; i < length; i++) {
        table[numbers[i]]++;
        if (table[numbers[i]] > 1) {
            duplication[0] = numbers[i];
            return true;
        }
    }
    return false;
}

第二次提交的代码：交换

public boolean duplicate(int numbers[],int length,int [] duplication) {
    if (numbers == null || length <= 1) return false;
    for(int i = 0; i < length; i++){
        if(numbers[i] < 0 || numbers[i] > length-1) return false;
    }
    int temp;
    for(int i = 0; i < length; i++){
        while(numbers[i] != i){
            if(numbers[numbers[i]] == numbers[i]){
                duplication[0] = numbers[i];
                return true;  
            }
            else{
                temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;
            }
        }
    }
    return false;
}

Note

1、Java中对整型数组默认初始化为0，因此哈希的解法中不用为table再进行初始化。
2、注意数组中元素进行交换，一定不能写成如下的形式...

temp = numbers[i];
numbers[i] = numbers[numbers[i]];
numbers[numbers[i]] = temp;

题目二：不修改数组找出重复的数字

Description

在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。

Solution

未在牛客网上提交，可能通不过。

public boolean duplicate(int numbers[], int length, int[] duplication){
    if (numbers == null || length <= 1) return false;
    for(int i = 0; i < length; i++){
        if(numbers[i] < 1 || numbers[i] > length-1) return false;
    }
    int low = 1, high = length - 1;
    int middle;
    while(low < high){
        middle = (low+high)/2;
        if(count(numbers, length, low, middle) > middle-low+1) high = middle;
        else low = middle + 1;//注意low的值
    }
    duplication[0] = low;
    return true;
}
public int count(int numbers[], int length, int low, int high){
    int count = 0;
    for(int i = 0; i < length; i++){
        if(numbers[i] >= low && numbers[i] <= high) count++;
    }
    return count;
}

参考代码：

public int duplicate(int numbers[], int length, int[] duplication){
    if (numbers == null || length <= 0) return -1;
    int start = 1;
    int end = length - 1;
    while(end >= start){
        int middle = (end-start)/2 + start;
        int count = countRange(numbers,length,start,middle);
        if(end == start){ //考虑到给定的数组中无重复的元素
            if(count > 1) return start;
            else break;
        }
        if(count > (middle-start+1)) end = middle;
        else start = middle + 1;
    }
    return -1;
    
}
public int countRange(int numbers[], int length, int low, int high){
    if(numbers == null) return 0; //子函数也要注意异常的判断
    int count = 0;
    for(int i = 0; i < length; i++){
        if(numbers[i] >= low && numbers[i] <= high) count++;
    }
    return count;

Note

在不改变原有数组、不申请额外空间的情况下，找出数组中重复的值——二分查找算法。这道题不涉及到有序，但仍然可以使用二分法的思想。

[4] 二维数组中的查找

Description

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

Solution

public boolean findValues (int[][] array, int target){
    if(array == null || array.length == 0 ||array[0].length == 0) return false;
    int m = array.length, n = array[0].length;
    int a = 0, b = n - 1;
    while(true){
        if(array[a][b] < target){
            if(a == m-1) return false;
            else a++;
        }
        else if(array[a][b] > target){
            if(b == 0) return false;
            else b--;
        }
        else return true;
    }
}

看了参考代码后，可以改成如下：

public boolean findValues (int[][] array, int target){
    if(array == null || array.length == 0 ||array[0].length == 0) return false;
    int m = array.length, n = array[0].length;
    int a = 0, b = n - 1;
    while(a < m && b >= 0){ //while是有条件的
        if(array[a][b] == target) return true;
        else if(array[a][b] < target) a++;
        else b--;
    }
    return false;
}

Note

1、首次做这道题时，由于二维数组是有序的，所以使用了二分查找的思路，矩阵左上角和右下角的横纵坐标/2，用这个值与target进行比较，再依次二分...最后定位到target在某两行内，再对第一行的后部分和第二行的前部分进行二分查找，搜索target...后来把这种做法提交到牛客网上，发现通过率貌似只有50%左右，而且未通过的测试用例，利用这个方法是找不到的，才发现...这个方法不可行。

2、注意二维数组，判断数组内有无元素，不仅需要判断array.length，还需要判断array[0].length，例如 {% raw %} int[][] array= new int[][]{{}}; {% endraw %} ，它的array.length为1，但array[0].length为0。

[5] 替换空格

Description

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy，则经过替换之后的字符串为We%20Are%20Happy。

Solution

public String replaceSpace(StringBuffer str){
    if(str == null) return null;
    int n = str.length(), spaceNumber = 0;
    for(int i = 0; i < n; i++){
        if(str.charAt(i) == ' ') spaceNumber++;
    }
    int m = n+2*spaceNumber;
    str.setLength(m);
    for(int i = n-1, j = m-1; i >= 0; i--, j--){
        char temp = str.charAt(i);
        if(temp != ' ') str.setCharAt(j, temp);
        else{
            str.setCharAt(j, '0');
            str.setCharAt(j-1, '2');
            str.setCharAt(j-2, '%');
            j-=2;
        }
    }
    return str.toString();
}

Note

1、StringBuffer、StringBuilder的用法

• toString()：将StringBuffer，StringBuilder对象转换为String字符串，常用在需要输出的时候，因为StringBuffer和StringBuilder的对象不能直接输出。
• append()：用于在字符串的后面追加字符串
• charaAt()：返回指定索引位置的字符，索引从0开始
• deleteCharAt()：删除指定索引位置的字符
• delete()：删除从开始索引到结束索引的字符串
• insert()：在指定索引位置之前插入字符串
• indexOf()：返回指定字符串的开始字符索引位置，还可以从某个字符索引位置开始向后匹配，没有找到匹配的就会返回-1
• lastIndexOf()：和indexOf()的用法一样，只不过是从后往前匹配，也支持从指定索引开始从后往前去匹配
• reverse()：反转字符串
• length()：返回字符串的长度
• setCharAt()：设置指定索引处的字符
• setLength()：设置字符序列的长度
• substring：返回一个新的 String ，其中包含此序列中当前包含的字符的子序列。

2、String、StringBuffer、StringBuilder的区别

• 从性能、速度方面来说：StringBuilder > StringBuffer > String

• 从线程安全的角度去看，StringBuffer是线程安全的，而StringBuilder是线程不安全的

• 总结：

  String适用于少量的字符串操作的情况
  StringBuilder适用于单线程下在字符缓冲区进行大量操作的情况
  StringBuffer适用多线程下在字符缓冲区进行大量操作的情况

2、往前遍历时，不一定需要遍历到第一个字符，只要两个指针重合即可。

[6] 从尾到头打印链表

Description

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

Solution

/*
public class ListNode { 
    int val;
    ListNode next = null;
    
    ListNode(int val) {
        this.val = val;
    }
}
*/

递归写法：

import java.util.ArrayList;
public class Solution {
    ArrayList<Integer> array = new ArrayList<>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode == null){
            return array;
        }else{
            printListFromTailToHead(listNode.next);
            array.add(listNode.val);
        }
        return array;
    }
}

我写得不够简洁...

参考牛客网上某回答...

public class Solution {
    ArrayList<Integer> arrayList=new ArrayList<Integer>();
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        if(listNode!=null){
            this.printListFromTailToHead(listNode.next);
            arrayList.add(listNode.val);
        }
        return arrayList;
    }
}  

用栈实现：

import java.util.ArrayList;
import java.util.Stack;
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
    ArrayList<Integer> array = new ArrayList<>();
    Stack<Integer> stack = new Stack<>();
    while(listNode != null){
        stack.push(listNode.val);
        listNode = listNode.next;
    }
    while(!stack.empty()){
        array.add(stack.peek());
        stack.pop();
    }
    return array;
}

Note

1、Stack的用法

• empty()：测试此栈是否为空
• peek()：查看此栈顶部的对象，但不删除它
• pop()：删除此栈顶部的对象，并将该对象作为此函数的值返回
• push()：将对象存入此栈的顶部
• search()：返回一个对象在此栈上的基于1的位置

[7] 重建二叉树

Description

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

Solution

我的写法：

public TreeNode reConstructBinaryTree(int[] pre,int[] in) {
    if(pre == null || in == null || pre.length == 0 || in.length == 0) return null;
    return func(pre,in,0,pre.length-1,0,in.length-1);
}
public TreeNode func(int[] pre, int[] in, int preLow, int preHigh, int inLow, int inHigh){
    int inMid = 0;
    TreeNode node = null;
    for(int i = inLow; i <= inHigh; i++){
        if(in[i] == pre[preLow]){
            inMid = i;
            node = new TreeNode(in[inMid]); 
            node.left = null;
            node.right = null;
            break;
        }
    }
    if(inLow <= inMid-1){
        node.left = func(pre,in,preLow+1,preLow+inMid-inLow,inLow,inMid-1);
    }
    if(inMid+1 <= inHigh){
        node.right = func(pre,in,preLow+inMid-inLow+1,preHigh,inMid+1,inHigh);
    }
    return node;
}

参考写法：

public TreeNode reConstructBinaryTree(int[] pre,int[] in) throws Exception{
    if(pre == null || in == null || pre.length == 0 || in.length == 0) return null;
    return func(pre,in,0,pre.length-1,0,in.length-1);
}
public TreeNode reconstructCore(int[] pre, int[] in, int preLow, int preHigh, int inLow, int inHigh) throws Exception{
    int rootValue = pre[0];
    TreeNode root = new TreeNode(rootValue);
    root.left = null;
    root.right = null;
    if(preLow == preHigh){
        if(inLow == inHigh && pre[preLow] == in[inLow]) return root;
        else throw new Exception("Invalid input.");
    }
    //在中序遍历序列中找到根节点的值
    int inRoot = inLow;
    while(inRoot <= inHigh && in[inRoot] != rootValue) ++inRoot;
    if(inRoot == inHigh && in[inRoot] != rootValue) throw new Exception("Invalid input.");
    int leftLength = inRoot - inLow;
    int leftPreHigh = preLow + leftLength;
    if(leftLength > 0){
        //构建左子树
        root.left = reconstructCore(pre,in,preLow+1,leftPreHigh,inLow,inRoot-1);
    }
    if(leftLength < preHigh - preLow){
        //构建右子树
        root.right = reconstructCore(pre,in,leftPreHigh+1,preHigh,inRoot+1,inHigh);
    }
    return root;
}

Note

1、前序遍历序列的第一个数字是根节点的值，因此一进函数就可以根据该值新建节点，不用等在中序遍历序列中找到它才建。
2、异常处理！异常输入可能有（1）前序遍历和中序遍历的节点个数不相等（2）在中序遍历中找不到前序遍历中的节点。即使测试用例几乎都是正常的或一些边界数据，但是我们的函数应该考虑到异常的情况，并通过条件来抛出异常。
3、代码要具有可读性，学习下参考代码中leftLength等变量的建立以及在适当的位置写文字注释。

[8] 二叉树的下一个结点

Description

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

Solution

/*
public class TreeLinkNode {
    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null;

    TreeLinkNode(int val) {
        this.val = val;
    }
}
*/

我的写法：

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) return null;        
        if(pNode.right != null){
            TreeLinkNode leftNode = pNode.right;
            while(leftNode.left != null){
                leftNode = leftNode.left;
            }
            return leftNode;
        }else{
            TreeLinkNode nextNode = pNode.next;
            while(true){
                if(nextNode == null) return null;
                else{
                    if(nextNode.left == pNode) return nextNode;
                    else{
                        pNode = nextNode;
                        nextNode = nextNode.next;                  
                    }
                }
            }
            
        }
    }
}

参考写法：

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode)
    {
        if(pNode == null) return null;
        TreeLinkNode pNext = null;
        if(pNode.right != null){
            TreeLinkNode pRight = pNode.right;
            while(pRight.left != null){
                pRight = pRight.left;
            }
            pNext = pRight;
        }else if(pNode.next != null){
            TreeLinkNode pCurrent = pNode;
            TreeLinkNode pParent = pNode.next;
            while(pParent != null && pCurrent == pParent.right){
                pCurrent = pParent;
                pParent = pParent.next; 
            }
            pNext = pParent; 
        }
        return pNext;
    }
}

Note

1、注意是while(true)不是...while(1)，并且一般情况下while当中是有内容的 ，不会是无条件循环。
2、拿到这种题，首先通过画图，分情况（最开始看到这道题...想法是往上找到根节点后再用中序遍历...服了自己
3、如果函数中有多个可能return的地方，可以不用在每个地方写return，应该在开始时定义一个变量，在各个分支进行赋值，在函数的结尾再return。

[9] 用两个栈实现队列

Description

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

Solution

我的写法：

import java.util.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        int val;
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.peek());
                stack1.pop();
            }          
        }
        val = stack2.peek();
        stack2.pop();
        return val;
    }
}

参考写法：

import java.util.Stack;
 
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() throws RuntimeException{
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

Note

1、如果栈为空，此时再pop，应该抛出异常。
2、stack.pop()函数既会弹出栈顶元素又会返回该元素。

[10] 斐波那契数列

Description

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39

Solution

public int fibonacci(int n){
    if(n < 2) return n == 0 ? 0 : 1;
    int[][] array = {{1,1},{1,0}};
    array = calculate(array,n-1);
    return array[0][0];
}

public int[][] calculate(int[][] array, int n){
    if(n == 1) return array;
    int[][] value;
    value = calculate(array,n/2);
    value = matrixMulti(value,value);
    if(n%2 != 0) value = matrixMulti(value,array);
    return value;
}

//矩阵的乘法
public int[][] matrixMulti(int[][] x, int[][] y){
    if(x == null || y == null || x.length == 0 || y.length == 0 || x[0].length != y.length) return null;
    int a = x.length, b = y[0].length;
    int c = x[0].length;
    int[][] result = new int[a][b];
    for(int i = 0; i < a; i++){
        for(int j = 0; j < b; j++){
            for(int k = 0; k < c; k++){
                result[i][j] += x[i][k] * y[k][j];
            }
        }
    }
    return result;
}

补充：快速排序

Solution

public void quickSort(int[] array, int start, int end){
    if(start == end) return;
    int index = findPosition(array,start,end);
    if(index < start) quickSort(array,start,index-1);
    if(index < end) quickSort(array,index+1,end);
}
public int findPosition(int[] array, int start, int end){
    if(array==null || array.length==0 || start<0 || end>=array.length){
        throw new RuntimeException("Invalid Parameters.");
    }
    int index = array[start];
    while(start < end){
        while(start < end && array[end] > index){
            end--;
        }
        array[start] = array[end];
        while(start < end && array[start] <= index){
            start++;
        }
        array[end] = array[start];
    }
    array[start] = index;
    return start;
}

Note

还是严奶奶的写法比较容易记...没有想到快排居然忘了QAQ
核心是，先在数组中选择一个数字作为基准元素，接下来把数组中的数字分为两部分，比基准元素小的数字移到数组的左边，比基准元素大的数字移到数组的右边。每次排序实际上就是把基准元素放到正确的位置上。

[11] 旋转数组中的最小数字

Description

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

Solution

我的写法...

public int minNumberInRotateArray(int[] array) {
    if(array == null || array.length == 0) return 0;
    int result = keyFunc(array,0,array.length-1);
    return result == 0 ? array[0] : result;
}
public int keyFunc(int[] array, int start, int end){
    int result = 0;
    if(end-1 == start){
        if(array[start] > array[end]) result = array[end];
    }
    else{
        int middle = (start+end)/2;
        if(array[start] >= array[middle]) result = keyFunc(array,start,middle);
        if(array[middle] >= array[end]) result = result == 0 ? keyFunc(array,middle,end) : result;
    }
    return result;
}

参考写法：

public static int minNumberInRotateArray(int [] array) {
    if(array == null || array.length == 0) return 0;
    int start = 0, end = array.length-1;
    int middle = start;
    while(array[start] >= array[end]){
        // 如果start和index2指向相邻的两个数，
        // 则start指向第一个递增子数组的最后一个数字，
        // index2指向第二个子数组的第一个数字，也就是数组中的最小数字
        if(end-start == 1){
            middle = end;
            break;
        }
        // 如果下标为start、index2和indexMid指向的三个数字相等，
        // 则只能顺序查找
        middle = (start+end)/2;
        if(array[start] == array[end] && array[start] == array[middle]){
            return findMinNumber(array,start,end);
        }
        // 缩小查找范围
        if(array[middle] >= array[start]){
            start = middle;
        }
        if(array[middle] < array[end]){
            end = middle;
        }
    }
    return array[middle];
}
public static int findMinNumber(int[] array, int start, int end){
    int value = array[start];
    for(int i = start+1; i <= end; i++){
        if(value > array[i]) value = array[i];
    }
    return value;
}

Note

第一反应居然是顺序遍历...摔...
由于考虑到start/end/middle相等的情况，不知道该从哪边找，于是写成了递归...在不知道往哪边找的时候就往两边找..看了参考代码，原来不知道往哪边找的时候，就顺序找...

[12] 矩阵中的路径

Description

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

Solution

我的写法...

public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
    if(matrix == null || matrix.length == 0 || rows == 0 || cols == 0 || str == null || str.length == 0 || matrix.length != rows*cols){
        throw new RuntimeException("invalid input");
    }
    int length = rows*cols;
    boolean result = false;
    int[] flag = new int[length];
    for(int i = 0; i < length; i++){
        if(matrix[i] == str[0]){
            flag[i] = 1;
            result = keyFunc(matrix,rows,cols,str,flag,1,i);
            flag[i] = 0;
        }
        if(result == true) break;
    }
    return result;
}
public boolean keyFunc(char[] matrix, int rows, int cols, char[] str, int[] flag, int count, int i){
    boolean result = false;
    if(count == str.length) result = true;
    if(!result && count<str.length && i%cols>0 && flag[i-1]==0 && matrix[i-1]==str[count]) {
        flag[i-1] = 1;
        result = keyFunc(matrix, rows, cols, str, flag, ++count, i-1);
        count--;
        flag[i-1] = 0;
    }
    if(!result && count<str.length && i%cols<cols-1 && flag[i+1]==0 && matrix[i+1]==str[count]){
        flag[i+1] = 1;
        result = keyFunc(matrix,rows,cols,str,flag,++count,i+1);//count++
        count--;
        flag[i+1] = 0;
    }
    if(!result && count<str.length && i/cols>0 && flag[i-cols]==0 && matrix[i-cols]==str[count]){
        flag[i-cols] = 1;
        result = keyFunc(matrix,rows,cols,str,flag,++count,i-cols);
        count--;
        flag[i-cols] = 0;
    }
    if(!result && count<str.length && i/cols<rows-1 && flag[i+cols]==0 && matrix[i+cols]==str[count]){
        flag[i+cols] = 1;
        result = keyFunc(matrix,rows,cols,str,flag,++count,i+cols);
        count--;
        flag[i+cols] = 0;
    }
    return result;
}

参考写法：

public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
{
    if(matrix==null || matrix.length==0 || rows<1 || cols<1 || str==null || str.length==0 || matrix.length!=rows*cols
        throw new RuntimeException("invalid input");
    }
    int[] flag = new int[rows*cols];
    for(int row = 0; row < rows; row++){
        for(int col = 0; col < cols; col++){
            if(keyFunc(matrix,rows,cols,str,flag,0,row,col)) return true;
        }
    }
    return false;
}
public boolean keyFunc(char[] matrix, int rows, int cols, char[] str, int[] flag, int count, int row, int col)
    if(count == str.length) return true;
    boolean result = false;
    if(row>=0 && row<rows && col>=0 && col<cols && flag[cols*row+col]==0 && matrix[cols*row+col]==str[count]){
        flag[cols*row+col] = 1;
        count++;
        result = keyFunc(matrix,rows,cols,str,flag,count,row,col-1) ||
                keyFunc(matrix,rows,cols,str,flag,count,row,col+1) ||
                keyFunc(matrix,rows,cols,str,flag,count,row-1,col) ||
                keyFunc(matrix,rows,cols,str,flag,count,row+1,col);
        if(!result){
            flag[cols*row+col] = 0;
            count--;
        }
    }
    return result;
}

Note

虽然之前在LeetCode上也刷过类似的题，但还是耗时比较久，由于没考虑清楚，比如递归传参count++与++count的区别，以及回溯过程中count也需要--。
参考写法判断的是当前坐标是否满足条件，对于相邻坐标的判断，通过递归传参到下次判断。这样代码简单多了...

[13] 机器人的运动范围

Description

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

Solution

我的写法：

public int movingCount(int threshold, int rows, int cols)
{
    int[] visited = new int[rows*cols];
    return movingCountCore(threshold,rows,cols,0,0,0,visited);
}
public int movingCountCore(int threshold, int rows, int cols, int row, int col, int count, int[] visited){
    if(row>=0 && row<rows && col>=0 && col<cols && visited[row*cols+col] == 0){
        if(countSum(row)+countSum(col) > threshold){
            visited[row*cols+col] = -1;
        }else{
            count++;
            visited[row*cols+col] = 1;
            count = movingCountCore(threshold,rows,cols,row,col-1,count,visited);
            count = movingCountCore(threshold,rows,cols,row,col+1,count,visited);
            count = movingCountCore(threshold,rows,cols,row-1,col,count,visited);
            count = movingCountCore(threshold,rows,cols,row+1,col,count,visited);
        }
    }
    return count;
}
public int countSum(int row){
    int sum = 0;
    while(row != 0){
        sum += row%10;
        row /= 10;
    }
    return sum;
}

参考写法：

public int movingCountCore(int threshold, int rows, int cols, int row, int col, boolean[] visited){
    int count = 0;
    if(check(threshold,rows,cols,row,col,visited))
    {
        visited[row*cols+col]=true;
        
        count = 1 + movingCountCore(threshold,rows,cols,row,col-1,visited)
            + movingCountCore(threshold,rows,cols,row,col+1,visited)
            + movingCountCore(threshold,rows,cols,row-1,col,visited)
            + movingCountCore(threshold,rows,cols,row+1,col,visited);
    }
}
boolean check(...)//判断机器人能否进入当前坐标

Note

对于此类从某个格子出发可以到达多少格子的问题，在递归时可以为每个格子设置一个count的值，该count值表示从该格子出发能够到达的格子数（包括自己）。

[14] 剪绳子

Description

给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

Solution

public int cutRope(int target) {
    if(target < 2) return 0;
    if(target == 2 || target == 3) return target-1;
    int[] result = new int[target+1];
    result[1] = 1;
    result[2] = 2;
    result[3] = 3;
    for(int i = 4; i <= target; i++){
        for(int j = 1; j <= i/2; j++){
            int temp = result[j]*result[i-j];
            result[i] = result[i] < temp ? temp : result[i];
        }
    }
    return result[target];
}

[15] 二进制中1的个数

Description

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

Solution

我的写法...

public int getNumberOf1(int n){
    char[] charArray = Integer.toBinaryString(n).toCharArray();
    int length = charArray.length;
    int count = 0;
    for(int i = 0; i < length; i++){
        if(charArray[i] == '1') count++;
    }
    return count;
}

参考写法1：

public int getNumberOf1(int n){
    int count = 0;
    while(n != 0){
        if((n&1) == 1){
            count++;
        }
        n = n>>>1;//注意是无符号右移，如果是>>，则遇到负数时，全部补1，会进入死循环
    }
    return count;
}

参考写法2：

public int getNumberOf1(int n){
    int count = 0;
    int x = 1;
    while(x != 0){
        if((n&x) == x){
            count++;
        }
        x = x<<1;
    }
    return count;
}

参考写法3：

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

Note

1、在参考写法2中，循环的次数等于整数二进制的位数，32位的整数需要循环32次。效率不够高。而参考写法3中，根据：把一个整数减去1，再和原整数做与运算，会把该整数最右边的1变成0.那么一个整数的二进制表示中有多少个1，就可以进行多少次这样的操作。
2、if(n&1==1)这样的写法是错误的，需要加上括号，即if((n&1) == 1)