删除链表的节点 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

注意：此题对比原题有改动

示例 1:

输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:

输入: head = [4,5,1,9], val = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
 

说明：

题目保证链表中节点的值互不相同
若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点
通过次数83,399提交次数142,039

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shan-chu-lian-biao-de-jie-dian-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return head;
        }
        ListNode first = head;
        ListNode pre = head;//遍历节点的前一个节点
        while (head != null) {

            if (head.val == val) {
                if (head.next != null) {//将后面的元素的值复制到当前要删除的元素，释放掉后面的那个节点
                    head.val = head.next.val;
                    head.next = head.next.next;
                } else {//如果要替换的节点是最后一个节点，那么要用pre节点释放
                    pre.next = null;
                }
                break;

            } else {
                pre = head;
                head = head.next;
            }
        }
        return first;
    }
}

展开全文 >>

旋转数组的最小数字第三次

剑指 Offer 11. 旋转数组的最小数字

难度简单294

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

示例 1：

1
2
输入：[3,4,5,1,2]
输出：1

示例 2：

1
2
输入：[2,2,2,0,1]
输出：0

注意：本题与主站 154 题相同：https://leetcode-cn.com/problems/find-minimum-in-rotated-sorted-array-ii/

通过次数176,968

提交次数359,125

第N次做

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int minArray(int[] nums) {
        int l=0,r=nums.length-1,mid = 0;
        while(l<=r){
            mid = l+(r-l)/2;
            // 这里有可能mid就是最小值，所以不能 mid - 1
            if(nums[mid] < nums[r]){
                // mid在右边升序部分
                r = mid;
            }else if(nums[mid] > nums[r]){
                // mid在左边升序部分
                l = mid + 1;
            }else{
                r--;
            }
        }
        return nums[mid];
    }
}

官方题解二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minArray(int[] numbers) {
        int low = 0;
        int high = numbers.length - 1;
        while (low < high) {
            int pivot = low + (high - low) / 2;
            if (numbers[pivot] < numbers[high]) {
                high = pivot;
            } else if (numbers[pivot] > numbers[high]) {
                low = pivot + 1;
            } else {
                high -= 1;
            }
        }
        return numbers[low];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution{
    public static int minArray(int[] numbers) {
        int left = 0, right = numbers.length - 1, mid = 0;

        while (left <= right) {
            mid = (left + right) / 2;

            if (numbers[left] < numbers[mid] && numbers[mid] > numbers[right]) {//左边递增，并且中间值大于右边的值
                left = mid;//左指针右移
            } else if (numbers[left] > numbers[mid] && numbers[mid] < numbers[right]) {//在右半边递增部分
                right = mid;//右指针左移
            } else {
                return getMIn(numbers, left, right);
            }
        }
        return numbers[left];
    }
    //顺序查找
    public static int getMIn(int[] number, int start, int end) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < number.length; i++) {
            min = Math.min(min, number[i]);
        }
        return min;
    }
}

清晰题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int m = (l + r) / 2;
            // 如果中间的大于右边，说明更小的值在右边
            if (numbers[m] > numbers[r]) l = m + 1;
            // 如果中间的小于右边，说明更小的值可能在中间或者中间往左边的部分
            else if (numbers[m] < numbers[r]) r = m;
            // 否则数字是相同的，不是递增或者递减的，右边界收缩
            else r--;
        }
        return numbers[l];
    }
}

作者：jyd
链接：https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/solution/mian-shi-ti-11-xuan-zhuan-shu-zu-de-zui-xiao-shu-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

青蛙跳台阶 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。

答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

示例 1：

输入：n = 2
输出：2
示例 2：

输入：n = 7
输出：21
示例 3：

输入：n = 0
输出：1
提示：

0 <= n <= 100
注意：本题与主站 70 题相同：https://leetcode-cn.com/problems/climbing-stairs/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这个问题与斐波那契数列问题基本相同

假设有10个台阶需要跳，那么到达第10阶台阶的步骤只有两种即step(9)和step(8)两种,两种方法相互独立，即到达第10阶台阶的路线数量等于到达第9阶台阶的数量加上到达第8阶台阶的数量，即step[10]=step[9]+step[8]

1
step[N]=step[N-1]+step[N-2],其中（N>=3）

计算时可采用自底向上的方式，减少计算量，节省内存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
    public int numWays(int n) {
        if (n < 2) return 1;
        if (n == 2) return 2;
        int first = 1, second = 2;
        int ways = 0;
        for (int i = 3; i <= n; i++) {
            ways = (first + second)%1000000007;
            first = second;
            second = ways;
        }
        return ways;
    }
}


展开全文 >>

用两个栈实现队列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

 

示例 1：

输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：

输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
提示：

1 <= values <= 10000
最多会对 appendTail、deleteHead 进行 10000 次调用
通过次数114,123提交次数157,064

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

用stack效率不高,原因的话是Stack继承了Vector接口，而Vector底层是一个Object[]数组，那么就要考虑空间扩容和移位的问题了。 可以使用LinkedList来做Stack的容器，因为LinkedList实现了Deque接口，所以Stack能做的事LinkedList都能做，其本身结构是个双向链表，扩容消耗少。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class CQueue {
        private Stack<Integer> stack1 = null;
        private Stack<Integer> stack2 = null;
    public CQueue() {
            stack1 = new Stack<>();
            stack2 = new Stack<>();
    }
    
    public void appendTail(int value) {
        stack1.push(value);
    }
    
    public int deleteHead() {
        while (!stack1.isEmpty()) {
            stack2.push(stack1.pop());
        }
        int res = -1;
        if (stack2.size() > 0) {
            res = stack2.pop();
        }
        while (!stack2.isEmpty()) {
            stack1.push(stack2.pop());
        }
        return res;
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

删除元素对应方法 deleteHead

如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里
如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回

第一个栈只负责接收元素，第二个栈只负责删除元素，只有当第二个栈中的元素为空时，才把第一个栈中的元素放进第二个栈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
static class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    public CQueue() {
        stack1 = new LinkedList<Integer>();
        stack2 = new LinkedList<Integer>();
    }
    public void appendTail(int value) {
        stack1.push(value);
    }
    public int deleteHead() {
        // 如果第二个栈为空
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        if (stack2.isEmpty()) {
            return -1;
        } else {
            int deleteItem = stack2.pop();
            return deleteItem;
        }
    }
}

参考文献

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/solution/mian-shi-ti-09-yong-liang-ge-zhan-shi-xian-dui-l-3/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

Summer1121的评论

展开全文 >>

树的子结构 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)

B是A的子结构， 即 A中有出现和B相同的结构和节点值。

例如:
给定的树 A:

     3
    / \
   4   5
  / \
 1   2
给定的树 B：

   4 
  /
 1
返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。

示例 1：

输入：A = [1,2,3], B = [3,1]
输出：false
示例 2：

输入：A = [3,4,5,1,2], B = [4,1]
输出：true
限制：

0 <= 节点个数 <= 10000

通过次数59,027提交次数128,655

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

先把节点遍历出来，再一一比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        List<Integer> list1 = new ArrayList<>();
        List<Integer> list2 = new ArrayList<>();


        deep(A, list1);
        deep(B, list2);

        int countNode = 0;
        for (int i = 0; i < list2.size(); i++) {
            if (list2.get(i) != null) {
                countNode++;
            }
        }

        int list2Index = 0;
        int sameCount = 0;
        for (int i = 0; i < list1.size(); i++) {
            if (list1.get(i) == list2.get(list2Index)) {
                if (list2.get(list2Index) != null) {
                    sameCount++;
                    if (sameCount == countNode) {
                        return true;
                    }
                }
                list2Index++;

            } else if (list1.get(i) != null && list2.get(list2Index) != null)  {
                list2Index = 0;
                sameCount = 0;
            }
        }
        return false;
    }
    public void deep(TreeNode root, List<Integer> list) {

        if (root != null) {
            list.add(root.val);
            deep(root.left, list);
            deep(root.right, list);
        } else {
            list.add(null);
        }

    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        //特判
        if(A == null || B == null) {
            return false;
        }
        return helper(A,B) || isSubStructure(A.left,B) || isSubStructure(A.right,B);
    }
    
    private boolean helper(TreeNode A, TreeNode B){
        if(B == null) return true; //说明越过叶子节点了，也就是B已经遍历结束了
        if(A == null) return false; //B还没结束，A越过叶子节点了，很显然A不包含B结构；
        return A.val == B.val
            && helper(A.left,B.left)
            && helper(A.right,B.right);
    }    
}

参考文献

1
2
3
4
作者：xmblgt
链接：https://leetcode-cn.com/problems/shu-de-zi-jie-gou-lcof/solution/zhe-yao-qing-xi-de-si-lu-huan-kan-bu-dong-qing-la-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

数值的整数次幂 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
实现函数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] 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zhi-de-zheng-shu-ci-fang-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

avatar

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
public static double myPow(double x, int n) {
    if (n == 0) {
        return 1;
    }
    long exp = n;//转化成long防止溢出
    if (exp < 0) {
        exp = -exp;
    }
    double res = recursion(x, exp);

    if (n > 0) {
        return res;
    } else {
        if (res != 0)
            return 1 / res;
        else//这里不确定怎么处理
            return 0;
    }
}

//快速幂
public static double recursion(double x, long n) {
    if (n == 0) return 1;
    if (n == 1) return x;

    double result = recursion(x, n >> 1);

    result = result * result;
    if (n % 2 == 1) result = result * x;
    return result;
}


展开全文 >>

剪绳子 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给你一根长度为 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
提示：

2 <= n <= 58
注意：本题与主站 343 题相同：https://leetcode-cn.com/problems/integer-break/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/jian-sheng-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

自顶向下的动态规划

对于一根长度为n的绳子，当n为1和2时，结果只能是1，当n大于2时，有两种处理方式：

  • 先把它在i处切一刀，然后将继续切割剩下的绳子，当前的值是$i*cut（n-i）$;
  • 把它在i处切一刀，不再继续切割剩下的绳子，当前的值是$i（n-i）$;
    为了最大化乘积，需要选择二者中较大的那种切割方法因此$Math.max(i*cut(n-i),i    (n-i))$;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
   int[] mem = null;//备忘录
    public int cuttingRope(int n) {
        mem = new int[n + 1];
        return dp(n);
    }

    public int dp(int len) {
        if (mem[len] != 0) {//如果已经计算过，无需再次计算
            return mem[len];
        }
        int max = 0;
        if (len ==1||len==2) {
            return 1;
        } else {
            for (int i = 1; i < len; i++) {
                max = Math.max(Math.max(i * dp(len - i), i * (len - i)), max);
            }

        }
        mem[len] = max;
        return max;
    }
}

非递归实现

  • 切的时候，当前的问题是切下来的长度i乘以剩余部分的子问题dp[i-j]的结果
  • 不切的时候，当前的问题是j*(i-j)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int cuttingRope(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, 1);

        //dp[i]=max(max(j*dp[i-j],j*(i-j)),dp[i]);//当j<i时dp[j]*(n-j)代表在j处切，dp[i]代表不切
        // i枚举绳子的长度
        for (int i = 2; i <= n; i++) {
            // j枚举的是切的位置
            for (int j = 1; j < i; j++) {
                dp[i] = Math.max(Math.max(j * dp[i - j], j * (i - j)), dp[i]);
            }
        }
        return dp[n];
    }
}

相关题目

整数拆分

好因子的最大数目

参考文献

贪心算法见sophia_fez题解

剪绳子

展开全文 >>

机器人的运动范围 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

 

示例 1：

输入：m = 2, n = 3, k = 1
输出：3
示例 2：

输入：m = 3, n = 1, k = 0
输出：1
提示：

1 <= n,m <= 100
0 <= k <= 20
通过次数81,929提交次数161,443

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

计算递推+回溯

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
class Solution {
    public int movingCount(int m, int n, int k) {
        step = new boolean[m][n];
        if (k == 0) {
            return 1;
        }
        int[] row = new int[m];//每一列的index
        int[] col = new int[n];//每一行的index

        row[0] = 0;
        col[0] = 0;
        //通过维护一个最大值和一个最小值来计算这个维度上的位计算和，生成位计算递推数
        //第一行的值分别为0，1，2，3，4，5，6，7，8，9，1，2，3，4，5，6，7，8，9，10，2，3，4，5，6，7，8，9，10，11，3，4，5，6，7，8，9，10，11，12，4
        //第一列的值也按照这个顺序
        int min = 1;
        int max = 10;
        int val = 1;
        for (int i = 1; i < m; i++) {
            row[i] = val;
            val++;
            if (val == max) {
                val = min;
                min++;
                max++;
            }
        }

        min = 1;
        val = 1;
        max = 10;
        for (int j = 1; j < n; j++) {
            col[j] = val;
            val++;
            if (val == max) {
                val = min;
                min++;
                max++;
            }
        }

        backtrack(row, col, k, 0, 0);
        return count;
    }
     int count = 0;
     boolean[][] step = null;
    //通过回溯上下左右移动，遍历所有可以到达的坐标
    //这里不可以直接用循环来做，因为有些路径是不连通的
    public void backtrack(int[] row, int[] col, int k, int i, int j) {

        if (i >= row.length || j >= col.length || i < 0 || j < 0 || row[i] + col[j] > k || step[i][j]) {
            return;
        } else {
            if (row[i] + col[j] <= k) {
                count++;
                step[i][j] = true;
                backtrack(row, col, k, i + 1, j);
                backtrack(row, col, k, i, j + 1);
                backtrack(row, col, k, i - 1, j);
                backtrack(row, col, k, i, j - 1);
            }
        }
    }


}

广度优先遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        Queue<int[]> queue = new LinkedList<int[]>();
        // 向右和向下的方向数组
        int[] dx = {0, 1};
        int[] dy = {1, 0};
        boolean[][] vis = new boolean[m][n];
        queue.offer(new int[]{0, 0});
        vis[0][0] = true;
        int ans = 1;
        while (!queue.isEmpty()) {
            int[] cell = queue.poll();
            int x = cell[0], y = cell[1];
            for (int i = 0; i < 2; ++i) {
                int tx = dx[i] + x;
                int ty = dy[i] + y;
                if (tx < 0 || tx >= m || ty < 0 || ty >= n || vis[tx][ty] || get(tx) + get(ty) > k) {
                    continue;
                }
                queue.offer(new int[]{tx, ty});
                vis[tx][ty] = true;
                ans++;
            }
        }
        return ans;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}

递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
    public int movingCount(int m, int n, int k) {
        if (k == 0) {
            return 1;
        }
        boolean[][] vis = new boolean[m][n];
        int ans = 1;
        vis[0][0] = true;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if ((i == 0 && j == 0) || get(i) + get(j) > k) {
                    continue;
                }
                // 边界判断
                if (i - 1 >= 0) {
                    vis[i][j] |= vis[i - 1][j];
                }
                if (j - 1 >= 0) {
                    vis[i][j] |= vis[i][j - 1];
                }
                ans += vis[i][j] ? 1 : 0;
            }
        }
        return ans;
    }

    private int get(int x) {
        int res = 0;
        while (x != 0) {
            res += x % 10;
            x /= 10;
        }
        return res;
    }
}

参考文献

1
2
3
4
5
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/ji-qi-ren-de-yun-dong-fan-wei-lcof/solution/ji-qi-ren-de-yun-dong-fan-wei-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

重建二叉树

剑指 Offer 07. 重建二叉树

难度中等423

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

1
2
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

1
2
3
4
5
  3
 / \
9  20
  /  \
 15   7

限制：

1
0 <= 节点个数 <= 5000

注意：本题与主站 105 题重复：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

递归法

每次递归中从前序遍历中选择第一个元素作为根节点，递归地生成左子树和右子树。在前序遍历中要想获取左子树的节点数目和右子树的节点的数目，需要借助中序遍历的根的index计算，计算完成后，即可正确获得左子树的根的位置和右子树的根的位置，从而可以递归的进行生成其左右子树。
avatar

递归写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
    
    Map<Integer,Integer> indexMap ;
    int []pre;
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        this.pre = pre;
        indexMap = new HashMap<>();
        for(int i=0;i<in.length;i++){
            indexMap.put(in[i],i);
        }
        
        TreeNode root = build(0,pre.length-1,0,in.length-1);
        return root;
    }
    
    public TreeNode build(int pStart,int pEnd,int inStart,int inEnd){
        if(pStart>pEnd)return null;
        TreeNode root = new TreeNode(pre[pStart]);
        if(pStart==pEnd)return root;
        
        int rootIndex = indexMap.get(pre[pStart]);
        int leftNum = rootIndex - inStart;
        int rightNum = inEnd - rootIndex;
        // 构建左子树
        TreeNode left = build(pStart+1, pStart + leftNum, inStart, rootIndex - 1);
        // 构建右子树
        TreeNode right = build(pEnd - rightNum + 1, pEnd, rootIndex+1, inEnd);
        root.left = left;
        root.right = right;
        return root;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0) {
            return null;
        }
        Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>();
        int length = preorder.length;
        for (int i = 0; i < length; i++) {//将值与下标进行一一映射，加快查找过程
            indexMap.put(inorder[i], i);
        }
        TreeNode root = buildTree(preorder, 0, length - 1, inorder, 0, length - 1, indexMap);
        return root;
    }

    public TreeNode buildTree(int[] preorder, int preorderStart, int preorderEnd, int[] inorder, int inorderStart, int inorderEnd, Map<Integer, Integer> indexMap) {
        if (preorderStart > preorderEnd) {
            return null;
        }
        int rootVal = preorder[preorderStart];//前序遍历的第一个节点是该子树的根节点
        TreeNode root = new TreeNode(rootVal);
        if (preorderStart == preorderEnd) {
            return root;
        } else {
            int rootIndex = indexMap.get(rootVal);//获取中序遍历中根节点的下标
            int leftNodesNumber = rootIndex - inorderStart;//计算左子树的节点的数量
            int rightNodesNumber = inorderEnd - rootIndex;//计算右子树节点的数量
            TreeNode leftSubtree = buildTree(preorder, preorderStart + 1, preorderStart + leftNodesNumber, inorder, inorderStart, rootIndex - 1, indexMap);//左子树的preorder开始位置是preorderStart + 1，结束位置是preorderStart + leftNodesNumber,inorder的开始位置是inorderStart，结束位置是rootIndex-1
            TreeNode rightSubtree = buildTree(preorder, preorderEnd - rightNodesNumber + 1, preorderEnd, inorder, rootIndex + 1, inorderEnd, indexMap);
            root.left = leftSubtree;
            root.right = rightSubtree;
            return root;
        }
    }
}

参考文献 

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/mian-shi-ti-07-zhong-jian-er-cha-shu-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

单调递增的数字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定一个非负整数 N，找出小于或等于 N 的最大的整数，同时这个整数需要满足其各个位数上的数字是单调递增。

（当且仅当每个相邻位数上的数字 x 和 y 满足 x <= y 时，我们称这个整数是单调递增的。）

示例 1:

输入: N = 10
输出: 9
示例 2:

输入: N = 1234
输出: 1234
示例 3:

输入: N = 332
输出: 299
说明: N 是在 [0, 10^9] 范围内的一个整数。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/monotone-increasing-digits
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] num = Integer.toString(N).toCharArray();
        for (int i = 0; i + 1 < num.length; i++) {
            if (num[i] > num[i + 1]) {//如果前一位大于后一位
                num[i]--;//前一位减一
                for (int j = i; j - 1 >= 0; j--) {//去查看当前位之前的元素是不是小于当前的位，如果不满足，要修改更靠前的位
                    if (num[j - 1] > num[j]) {
                        num[j - 1]--;
                        num[j] = '9';
                    }else {
                        break;
                    }
                }
                for (int j = i + 1; j < num.length; j++) {//i后面的所有元素都要变成9
                    num[j] = '9';
                }
                break;
            }
        }

        String s = String.valueOf(num);
        return Integer.valueOf(s);
    }
}

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int monotoneIncreasingDigits(int N) {
        char[] strN = Integer.toString(N).toCharArray();
        int i = 1;
        while (i < strN.length && strN[i - 1] <= strN[i]) {//先跳到第一个前一位大于后一位的位置
            i += 1;
        }
        if (i < strN.length) {
            while (i > 0 && strN[i - 1] > strN[i]) {//在这一位向前检查修改后的数字是否小于更前一位的数字，如果小于继续向前
                strN[i - 1] -= 1;
                i -= 1;
            }
            for (i += 1; i < strN.length; ++i) {//对这一位往后的元素都变成最大数字9
                strN[i] = '9';
            }
        }
        return Integer.parseInt(new String(strN));
    }
}


参考文献

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/monotone-increasing-digits/solution/dan-diao-di-zeng-de-shu-zi-by-leetcode-s-5908/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走