剑指Offer部分题解

剑指Offer的题目大部分其实是简单的(若不考虑最最优解其实很快就能做出来),不过有些细节上的东西需要注意,也有部分难度稍大的题目(对于我这种咸鱼).下面就是部分题目的解答,主要是小细节以及最优解上的说明.

1. 用栈实现队列

使用2个栈解决即可。设有stack1和stack2：

push()：直接推入stack1;

pop()：先把stack1的内容推到stack2中，获取stack2栈顶，然后再把剩余的重新推回stack1中。

2. 旋转数组的最小数字

使用二分搜索。

设有数组[a_m+1,...,an,..., a1, a2, ..., am],取中间的数ai。

假如最小数在左边，那么ai肯定比数组两端的数字(a_m+1, am)小；

假如最小数在右边，那么ai肯定比数组两端的数字大。

只有这两种情况。这样就可以通过二分搜索来确定最小数字了。代码如下：

public int minNumberInRotateArray(int [] array)
{
	if(array.length == 0)
        return 0;
    
    int low = 0, high = array.length - 1;
    while(low < high)
    {
        int mid = (low + high) / 2;
        if(array[mid] < array[high])
            high = mid;
        else
            low = mid + 1;
    }
    return array[high];
}

3. 数值整数次幂(非递归)

直接看代码吧，就是把指数二进制化，如x^19 = x^16 * x^2 * x^1。见代码：

public double Power(double base, int exponent)
{
    if(exponent < 0)
        return Power(1 / base, -exponent);
    if(exponent == 0)
        return 1;
    if(exponent == 1)
        return base;
    /*if((exponent & 1) == 0)
     	return Power(base * base, exponent / 2);
    return Power(base * base, exponent / 2) * base;*/
    double r = 1;
    while(exponent != 0)
    {
        if((exponent & 1) == 1)
            r *= base;
        base = base * base;
        exponent >>= 1;
    }
    return r;
}

4. 链表的倒数第k个结点

使用Two-pointer，不需要创建额外的空间。创建2个指针，都指向头部。

首先让第一个指针向前走k步。然后分别让两个指针同步向前走，直到第一个指针抵达链表尾。第二个指针就是我们要的答案。

5. 通过后序遍历判断是否为BST

使用分治和递归。该题同样适用于前序和中序遍历。

首先对于从0-(n-1)的序列，先找到root，即最后一个数字。

然后再找到左子树的根，即从右到左遍历第一个比root小的数字，左边的数字都是左子树的结点。

然后再往前遍历，判断左子树的结点是否全小于root，若不满足则返回false,否则就继续判断左子树和右子树是否为BST。

核心代码如下：

private boolean verify(int[] sequence, int start, int end)
{
    if(start >= end)
        return true;
    
    int root = sequence[end];
    int leftStart = end - 1;
    while(leftStart >= start && sequence[leftStart] > root)
        leftStart--;
    int left = leftStart;
    while(left >= start)
        if(sequence[left--] > root)
            return false;
   	return verify(sequence, start, leftStart) &&
        verify(sequence, leftStart + 1, end - 1);
}

6. 将BST转化成双向链表

使用了中序遍历。递归可以，不过最好是非递归的，使用栈，代码如下，标记序号的是重点语句。若前序遍历，那么访问结点的操作应当在3-4之间：

public TreeNode Convert(TreeNode pRootOfTree)
{
    Stack<TreeNode> stack = new Stack<>();
    TreeNode previous = null;
    TreeNode head = null;
    //iterative inorder..
    while(pRootOfTree != null || !stack.isEmpty())//1
    {
        while(pRootOfTree != null)//2
        {
            stack.push(pRootOfTree);//3
            pRootOfTree = pRootOfTree.left;//4
        }
        pRootOfTree = stack.pop();//5
        if(previous == null)
            pRootOfTree.left = null;
        else
        {
            pRootOfTree.left = previous;
            previous.right = pRootOfTree;
        }
        previous = pRootOfTree;
        if(head == null)
            head = previous;
        pRootOfTree = pRootOfTree.right;//6
    }
    return head;
}

7. 找数组中出现次数超过一半的数字

不需要建立HashTable来存储记录。我们只要维护2个变量：currentNum, count。

我们先把currentNum设为第一个数字，count设为1。然后后遍历。如果遍历的数字和currentNum一样，那么count++，否则count--。如果count为0了，就把currentNum置换成当前的数字，并将count置为1。最后遍历后的当前currentNum就是结果。

可知当某个数字次数超过一半的时候，其它所有数字次数和小于该数字的次数。而上面的操作，等价于——摩尔投票算法：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

代码：

//将数组中两个不同的数进行去除，最后剩下的那个数就是数组中出现次数超过一半的数字
public int MoreThanHalfNum_Solution(int [] array) 
{
	int currentNum = 0, count = 0;
    for(int n : array)
    {
        if(count == 0)
            currentNum = n;
        
        if(n != currentNum)
        	count--;
        else
            count++;
          
    }
    int freq = 0;
    for(int n : array)
    	if(n == currentNum)
            freq++;
    if(freq > array.length / 2)
        return currentNum;
    return 0;
}

8. 最小K个数

思路1：基于堆排序。

将给的数组重建堆，这里重建一个最小堆。首先找到最后的非叶结点，然后往下层遍历调整生成子最小堆，然后找上一个（不是上一层）非叶结点，直到调整了根结点。时间复杂度为O(n)，代码如下：

//build min head
private void percUp(int[] input)
{
    int lastIndex = input.length / 2 - 1;
    int val = input[lastIndex];
    for(; lastIndex >= 0; lastIndex--)
        percDown(input, input.length, lastIndex);
}
//build sub min heap from index
private void percDown(int[] input, int size, int index)
{
    int rootVal = input[index];
    int current = index;
    for(int child = index * 2 + 1; child < size; current = child, child = 2 * child + 1)
    {
        if(child + 1 < size && input[child] > input[child + 1])
            child++;
        if(input[child] < rootVal)
        	input[current] = input[child];
        else
            break;
	}
    input[current] = rootVal;
}

然后就把堆顶和最后一个元素交换，然后重新调整堆（堆大小要减去1）。重复k次，则数组后k个数字就是最小的k个数字了。（O(k*logN)）

或者先创建一个最大堆。然后插入k个元素。接下来遍历数组，若数字比堆顶小，弹出堆顶，插入数字。最后得到的最大堆保存了最小的k个元素。（O(Nlogk)）

思路2：基于快排算法

根据Quick Select算法，将前k个数放在前面，大的数放在后面，O(N)。

这里使用的pivot是数组的最后一个。然后遍历前面的数组，假如比pivot小，那么就放在数组的前面。最后交换pivot的位置以将其放在正确位置。若pivot位置<k，那么需要要对后半部分继续快速选择，否则要向前半部分快速选择。代码如下：

private void quickSelect(int[] input, int k, int start, int end)
{
    if(start >= end)
        return;
    int pivot = input[end];
    int i = start, j = start;//i: iter, j: to fill the smaller number
    for(; i < end; i++)
    {
        if(input[i] <= pivot)
        {
            int temp = input[i];
            input[i] = input[j];
            input[j++] = temp; //put the smaller number at the front
            i++;
        }                
    }
    int temp = input[j];//put pivot at the correct position
    input[j] = pivot;
    input[end] = temp;
    if(j < k - 1)
        quickSelect(input, k, j + 1, end); // min-k is at back
    else if(j >= k)
        quickSelect(input, k, start, j - 1); //min-k is at front       
}

附上快速排序的一种写法（没有使用书上的Median3和Cutoff）：

class Solution
{

       public static void quickSort(int[] array)
       {
            quickSortHelper(array, 0, array.length - 1);
       }

       private static void quickSortHelper(int[] array, int start, int end)
       {
           if(start >= end)
               return;
           int pivot = array[end];
           int i = start, j = start;

           for(; i < end; i++)
           {
               if(array[i] <= pivot)
               {
                   int temp = array[i];
                   array[i] = array[j];
                   array[j] = temp;
                   j++;
               }
           }
           int temp = array[j];
           array[j] = pivot;
           array[end] = temp;

           quickSortHelper(array, start, j - 1);
           quickSortHelper(array, j + 1, end);
       }
}

9. 1~n中1出现的次数

这里需要公式推导。我们把每一位出现1的次数进行统计，这会有个公式：

对于数字n，从低到高第d位(从0开始)的1出现次数为：

(n/(i*10))*i + min(max(n%(i*10)-i+1, 0), i), i = 10^d

所以时间复杂度为log(N)。

代码如下：

public int NumberOf1Between1AndN_Solution(int n) 
{
	int count = 0;
    for(int i = 1; i <= n; i *= 10)
        count += (n/(i*10))*i +
        	Math.min(Math.max(n % (i * 10) - i + 1, 0)
                    , i);
    return count;
    
}

10. 输出第n个丑数

本题使用动态规划。

易知，假如n为丑数，那么n/2, n/3或n/5至少有1个是丑数，所以马上想到的是保存已经得到的丑数。

所以我们维护3个指针：ptr2, ptr3, ptr5，分别用于乘以2, 3, 5得到下一个丑数用。并维护已知丑数列表dp。

我们要得到下一个最小的丑数，则该数字为next = min(dp[ptr2]*2, dp[ptr3]*3, dp[ptr5]*5)，并将其添加到dp列表中去。

接下来要更新3个指针，要保证下一个的丑数一定要大于刚得到的next，只要将3个指针向前移动，使得dp[ptr_x]*x > next即可。

大体思路如上，时间复杂度为O(n)，代码如下：

public int GetUglyNumber_Solution(int index) //using dp.
{
    //ugly_next = min(ugly[ptr2] * 2, ugly[ptr3] * 3, ugly[ptr5] * 5)
    if(index <= 6)
        return index;
    List<Integer> uglyList = new ArrayList<Integer>();
    uglyList.add(1);
    int ptr2 = 0;
    int ptr3 = 0;
    int ptr5 = 0;
    for(int i = 1; i < index; i++)
    {
        int nextUgly = Math.min(Math.min(uglyList.get(ptr2) * 2, uglyList.get(ptr3) * 3),
                               uglyList.get(ptr5) * 5);
        uglyList.add(nextUgly);
        while(nextUgly >= uglyList.get(ptr2) * 2)
            ptr2++; //next iteration to ensure uglyList.get(ptrX) * X > currentUgly
        while(nextUgly >= uglyList.get(ptr3) * 3)
            ptr3++;
        while(nextUgly >= uglyList.get(ptr5) * 5)
            ptr5++;
    }
    return uglyList.get(uglyList.size() - 1);
}

11. 求数组逆序对的数量

假如暴力求解，时间复杂度为O(n^2)，太慢。

这里使用分治法，并借鉴了归并排序。

这里总体的公式为n = n_left + n_right + n_cross,前两项可以通过递归解决，主要是第三项。

如何求第三项，一种方便的做法就是首先让左右两侧的数组排好序，然后再利用two-pointer统计。记左侧为ptr1, 右侧为ptr2。假如array[ptr1] > array[ptr2]，则count += mid - ptr1 + 1，其中mid为左侧最后一个元素的下标，这里就是认为array[ptr1]后面的数字都比array[ptr2]大，所以新逆序对数量很好获得。在遍历期间，对数组进行归并排序。

代码如下：

//divide & conquer!!
//with merge sort!
//1. Divide the array with 2 halves
//2. Get left part inverse count
//3. Get right part inverse count
//4. Get cross inverse count
//5. merge sort, merge left & right part, so that 2 & 3 part arrays are sorted.
private long mergeAndCount(int[] array, int left, int mid, int right)
{
    if(right <= left)
        return 0;
    int[] temp = new int[right - left + 1];
    int i = 0, ptr1 = left, ptr2 = mid + 1;
    long count = 0;
    while(ptr1 <= mid && ptr2 <= right)
    {
        if(array[ptr1] > array[ptr2])
        {
            count += (mid - ptr1 + 1);
            temp[i++] = array[ptr2++];
        }
        else
            temp[i++] = array[ptr1++];
    }
    while(ptr1 <= mid)
        temp[i++] = array[ptr1++];
    while(ptr2 <= right)
        temp[i++] = array[ptr2++];
    for(i = left; i <= right; i++)
        array[i] = temp[i - left];
    return count;
}

private long getInversePairNum(int[] array, int left, int right)
{
    if(left >= right)
        return 0;
    
    int mid = (left + right) / 2;
    long leftNum = getInversePairNum(array, left, mid);//return the sorted subarray
    long rightNum = getInversePairNum(array, mid + 1, right);
    long crossNum = mergeAndCount(array, left, mid, right);
    
    return (leftNum + rightNum + crossNum) % 1000000007;
}

public int InversePairs(int [] array) 
{
    if(array.length < 2)
        return 0;
    return (int)getInversePairNum(array, 0, array.length - 1);
}

12. 数组中只出现一次的数字（2个）

一种办法使用Set记录，太简单，不再叙述。

另一种采用Bit操作，依据是n XOR n = 0。

首先遍历一遍数组，连续进行异或操作，最后得到的是两个数字异或的结果：xorResult = num1 XOR num2。

然后需要分解它们。首先找到xorResult二进制中1的位置，生成一个mask。1代表2个数字在该位是不相同的，因此可以分成2个组。

我们进行第二次遍历，初始化num1和num2为0，假如data[i] & mask为0，那么异或到num1上，否则异或到num2上。遍历过程中，重复的元素依旧会抵消，但是不同的元素就被分组到2个不同的数上，即得到了我们需要的结果。

代码如下：

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) 
{
    int xorResult = 0;
    for(int n : array)
        xorResult ^= n; //get num1 XOR num2
    int flag = 1;
    while((flag & xorResult) == 0) //find bit pos where num1 is different from num2
        flag <<= 1;//Get mask
    num1[0] = 0;
    num2[0] = 0;
    for(int n : array)
    {
        if((n & flag) == 0)
            num1[0] ^= n;
        else
            num2[0] ^= n;
    }        
}

13. 和为S的连续正数序列

使用Two-pointer，记录low, high，根据高斯求和公式计算序列和，若大了，则low++，若小了否则high++。可以设置upbound为target/2+1。代码略。

14. 左旋字符串n位

不用substring与concat函数。只要逆转字符串3次：

第一次：逆转前n位；第二次：逆转后面全部；第三次：逆转整个字符串。

右旋也可以类似做，本质上是一样的。

15. 不用乘除法和控制流程关键字计算1+2+…+n

考察逻辑短路和递归。sum(n) = n + sum(n-1), sum(0) = 0。代码如下：

public int Sum_Solution(int n) 
//recursion
//with logic short 
{
    int result = 0;
	boolean status = (n > 0) && ((result = n + Sum_Solution(n - 1)) > 0);
    return result;
}

16. 数组中重复的数字

数组长度为n，范围为0~n-1，里面有几个数字是重复的。

这里使用表排序的思想。先访问索引为index的数字array[index]若两数相同则跳过循环，否则访问下一个array[array[index]]，假如两个数字不同，则交换，这样可以保证在array[index]位置下的数字就是array[index]，由于范围是0~n-1,长度为n，则可以保证根据排序后的数组，array[index]上的数字位置是正确的；假如相同，则就是重复数字。循环到index == array[index]结束，这表明整个循环遍历的数字都已经到了正确的位置上了，可以进行下一波循环(即index++)。

例子：

数字：2 3 1 0 2 5 3

下标：0 1 2 3 4 5 6

第一轮循环(先交换a[0]与a[a[0]])：1 3 2 0 2 5 3 -> 3 1 2 0 2 5 3 -> 0 1 2 3 2 5 3 -> 发现0 == a[0]，进入下一轮循环；

第二轮循环(再交换a[4]与a[a[4]]，前面的已经排号了，忽略了)：发现a[4] = 2，而a[a[4]] = a[2] = 2，发现相同，则2就是重复的数字。

代码如下:

public boolean duplicate(int numbers[],int length,int [] duplication) 
{
    //using the thoughts of table sort
	//example:
    //index:   0 1 2 3 4 5 6
    //element: 2 3 1 0 2 5 3
    //exchange a[0] and a[a[0]] -> 1 3 2 0 2 5 3 -> 3 1 2 0 2 5 3 -> 0 1 2 3 2 5 3, end with a[i] == i (self loop)
    //that means that the elements in the loop are sorted at the right place
    //no found, go on exchanging..a[4] & a[a[4]]: found duplicated -> return result.
    
    for(int i = 0; i < length; i++)
    {
        while(i != numbers[i])
        {
            if(numbers[i] == numbers[numbers[i]])
            {
                duplication[0] = numbers[i];
                return true;
            }
            else
                exchange(numbers, i, numbers[i]);
        }
    }
    return false;
}

private void exchange(int[] numbers, int index1, int index2)
{
    int temp = numbers[index1];
    numbers[index1] = numbers[index2];
    numbers[index2] = temp;
}

17. 正则表达式匹配

递归向前匹配，代码如下：

public boolean match(char[] str, char[] pattern) 
{
    if (str == null || pattern == null) 
        return false;

    int strIndex = 0;
    int patternIndex = 0;
    return matchCore(str, strIndex, pattern, patternIndex);
}
  
public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) 
{
    //有效性检验：str到尾，pattern到尾，匹配成功
    if (strIndex == str.length && patternIndex == pattern.length) {
        return true;
    }
    //pattern先到尾，匹配失败
    if (strIndex != str.length && patternIndex == pattern.length) {
        return false;
    }
    //模式第2个是*，且字符串第1个跟模式第1个匹配,分3种匹配模式；如不匹配，模式后移2位
    if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') 
    {
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) 
        {
            return matchCore(str, strIndex, pattern, patternIndex + 2)//模式后移2，视为x*匹配0个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//视为模式匹配1个字符
                    || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
        } 
        else
            return matchCore(str, strIndex, pattern, patternIndex + 2);

    }
	//模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
    if ((strIndex != str.length && pattern[patternIndex] == str[strIndex]) || (pattern[patternIndex] == '.' && strIndex != str.length)) 
        return matchCore(str, strIndex + 1, pattern, patternIndex + 1);

    return false;
}

18. 链表中环入口结点

使用快慢指针。(也可以用Set)

首先让slow和fast都指向链表头结点，然后slow每次走1步，fast每次走2步，只到两个指针重合，则说明链表有环。

然后让fast再次指向链表头结点，然后让两个指针每次一步，那么到两个指针再次重合的时候，指向的结点就是入口结点。

代码如下：

//https://www.cnblogs.com/snake-hand/p/3148328.html - 1. fast slow pointer
// or 2. hashset
public ListNode EntryNodeOfLoop(ListNode pHead)
{
    /*Set<ListNode> set = new HashSet<>();
    while(pHead != null)
    {
        if(set.contains(pHead))
            return pHead;
        set.add(pHead);
        pHead = pHead.next;
	}
    
    return null;*/
    if(pHead == null || pHead.next == null)
        return null;
    ListNode slow = pHead, fast = pHead;
    do
    {
        slow = slow.next;
        fast = fast.next.next;
    }while(slow != fast);
    
    fast = pHead;
    while(fast != slow)
    {
        fast = fast.next;
        slow = slow.next;
    }
    return fast;
}

19. 二叉树的下一个结点

给定一个二叉树的某个结点，找到其中序遍历的下一个结点。结点信息包括其左右结点和父结点。

可以这么分类：

1) 若该结点有右儿子，那么直接返回右子树的最左结点

2) 若该结点没有右儿子，那么假如它是父亲结点的左儿子，那么直接返回父结点

3) 若该结点(假设名字叫a)没有右儿子，且它是父亲结点的右儿子，那么向上找，直到找到一个祖先结点，a在其左子树里。若找到则返回该祖先结点，否则返回空。

代码略。

20. 序列化/反序列化二叉树

这里采用前序遍历序列化/反序列化。

序列化很简单，只需前序遍历（遍历不仅仅是有效结点，而且包括NIL），若是数字，则打印数字并递归遍历，否则打印null并返回。每个节点以空格分隔。

反序列化也很简单。将字符串按空格分隔成数组，然后传入一个全局变量index记录反序列化对应的结点下标。首先创建根结点，然后递归创建左子树和右子树。

为何反序列化能成功，是因为根据序列化的结果，当遍历到null结点时，就知道要切换到右子树上了（相对于最近的祖先结点），因此递归能成功。

代码如下：

String Serialize(TreeNode root) 
{
        if(root == null)
            return "null";
        String res = "";
        res += root.val;
        res += " ";
        res += Serialize(root.left);
        res += " ";
        res += Serialize(root.right);
        return res; //pre-iter serialize
}   

TreeNode Deserialize(String str) 
{
        if(str.equals("null") || str.length() == 0)
            return null;
        
       	String[] nodes = str.split("\\s+");
        int[] index = new int[1];
       	return dfs(nodes, index);

}  

private TreeNode dfs(String[] node, int[] index) //recursive pre-order deserialize
{
        if(index[0] >= node.length||node[index[0]].equals("null"))
        	return null;
        TreeNode root = new TreeNode(Integer.parseInt(node[index[0]]));
        index[0]++;
        root.left = dfs(node, index);
        index[0]++;
        root.right = dfs(node, index);
        return root;
}

21. 滑动窗口的最大值

这里考察优先队列的使用。

我们首先把数组中的前n个加入到最大堆中，堆顶就是当前窗口的最大数字。然后窗口移动的时候，删除堆中不在窗口的数字，添加新进入的数字。如此循环到窗口末尾即可。

代码：

public ArrayList<Integer> maxInWindows(int [] num, int size)
{
    //Another heap example!!, if you want median, use 2 heaps!
    ArrayList<Integer> list = new ArrayList<>();
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
    	(o1, o2) -> {return o2 - o1;}	
    );
    if(num.length < size || size == 0)
        return list;
    
    for(int i = 0; i < size; i++)
        maxHeap.add(num[i]);
    list.add(maxHeap.peek());
    for(int i = size; i < num.length; i++)
    {
        maxHeap.remove(num[i - size]);
        maxHeap.add(num[i]);
        list.add(maxHeap.peek());
    }
    
    return list;
}

22. 数据流的中位数

又一个使用优先队列的例子。

这里使用了2个队列，一个最大堆H1（存比中位数小的数字），一个最小堆H2（存比中位数大的数字）。要保证H1和H2的数量相等或者数量相差1（这里我们让最大堆H1结点更多一点）。

插入的时候，若原来有偶数个数字，那么先插入到最小堆H2中，并把最小堆H2的堆顶移动到最大堆H1中；若原来有奇数个数字，则反过来做。

求中位数时，若有偶数个数字，直接取2个堆的堆顶求中位数；若有奇数个数字，直接返回最大堆H1堆顶。

代码如下：

// using priority queue..
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //with numbers larger than median 

private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(
        (o1, o2) -> o2 - o1
); //with numbers smaller than median

int count = 0;

public void Insert(Integer num)
{
    if(count % 2 == 0)
    {
        minHeap.add(num);
        maxHeap.add(minHeap.poll());//balance the number of elements in 2 heaps
    }
    else
    {
        maxHeap.add(num);
        minHeap.add(maxHeap.poll());
    }
    count++;
}

public Double GetMedian() 
{
    if(count % 2 == 0)
        return 0.5 * (minHeap.peek() + maxHeap.peek());
    else
        return (double)maxHeap.peek();
}

23. 机器人的运动范围

给定m行n列的方格，机器人从原点移动，一次可往4个方向移动一个单位。不能进入横坐标和列坐标数位之和大于k的格子。问可以达到多少个格子。

假如移动方向只能向下和向右，那么可以直接使用动态规划。但是本题不一样，不能使用动态规划。所以我们这么做：

遍历所有的格子。假如格子无法到达，直接跳过。
假如格子可以到达（就仅限于满足数位和小于等于k），那么判断周围的格子是否已经确定可以到达，如果可以，那么直接判断该格子可以到达，计数+1
假如不可以，那么就必须从原点开始搜索（可以使用DFS和BFS），判断是否可以到达该点。

代码如下：

    private boolean[][] canVisited;

    private int count = 0;

    private boolean[][] visited;

    private boolean isOverThreshold(int threshold, int x, int y)
    {
        int sum = 0;
        while(x != 0)
        {
            sum += x % 10;
            x /= 10;
        }
        while(y != 0)
        {
            sum += y % 10;
            y /= 10;
    	}
        return sum <= threshold;
    }
    
    private void dfs(int rows, int cols, int x, int y, int targetX, int targetY, int threshold)
    {
        if(x == targetX && y == targetY)
        {
            canVisited[x][y] = true;
            return;
        }
        
        if(canVisited[targetX][targetY])
            return;
        
        if(x > 0)
        {
            if(!visited[x - 1][y] && isOverThreshold(threshold, x - 1, y))
            {
                visited[x - 1][y] = true;
                dfs(rows, cols, x - 1, y, targetX, targetY, threshold);
                visited[x - 1][y] = false;
            }
    	}
        
        if(x < rows - 1)
        {
            if(!visited[x + 1][y] && isOverThreshold(threshold, x + 1, y))
            {
                visited[x + 1][y] = true;
                dfs(rows, cols, x + 1, y, targetX, targetY, threshold);
                visited[x + 1][y] = false;
            }
    	}
        
        if(y > 0)
        {
            if(!visited[x][y - 1] && isOverThreshold(threshold, x, y - 1))
            {
                visited[x][y - 1] = true;
                dfs(rows, cols, x, y - 1, targetX, targetY, threshold);
                visited[x][y - 1] = false;
            }
    	}
        
        if(y < cols - 1)
        {
            if(!visited[x][y + 1] && isOverThreshold(threshold, x, y + 1))
            {
                visited[x][y + 1] = true;
                dfs(rows, cols, x, y + 1, targetX, targetY, threshold);
                visited[x][y + 1] = false;
            }
    	}
    }
    
    public int movingCount(int threshold, int rows, int cols) //dfs with dp optimitation
    {
        if(threshold < 0 || rows == 0 || cols == 0)
            return 0;
       	canVisited = new boolean[rows][cols];
        visited = new boolean[rows][cols];
        canVisited[0][0] = true;
        count = 1;
        for(int i = 0; i < rows; i++)
        {
            for(int j = 0; j < cols; j++)
            {
                if(i == 0 && j == 0)
                    continue;
                
                if(isOverThreshold(threshold, i, j))
                {
                    if((i > 0 && canVisited[i - 1][j])
                      || (i < rows - 1 && canVisited[i + 1][j])
                      || (j > 0 && canVisited[i][j - 1])
                      || (j < cols - 1 && canVisited[i][j - 1]))
                    {
                        canVisited[i][j] = true;
                        count++;
                    }
                    else
                    {
                        for(boolean[] v : visited)
                            Arrays.fill(v, false);
                        visited[0][0] = true;
                        dfs(rows, cols, 0, 0, i, j, threshold);
                        count = canVisited[i][j] ? count + 1 : count;
                    }
                }
    		}
    	}
        
        return count;
    }

剑指Offer部分题解

剑指Offer部分题解

1. 用栈实现队列

2. 旋转数组的最小数字

3. 数值整数次幂(非递归)

4. 链表的倒数第k个结点

5. 通过后序遍历判断是否为BST

6. 将BST转化成双向链表

7. 找数组中出现次数超过一半的数字

8. 最小K个数

9. 1~n中1出现的次数

10. 输出第n个丑数

11. 求数组逆序对的数量

12. 数组中只出现一次的数字（2个）

13. 和为S的连续正数序列

14. 左旋字符串n位

15. 不用乘除法和控制流程关键字计算1+2+…+n

16. 数组中重复的数字

17. 正则表达式匹配

18. 链表中环入口结点

19. 二叉树的下一个结点

20. 序列化/反序列化二叉树

21. 滑动窗口的最大值

22. 数据流的中位数

23. 机器人的运动范围

CATALOG

FEATURED TAGS