平衡二叉树 

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
输入一棵二叉树的根节点，判断该树是不是平衡二叉树。如果某二叉树中任意节点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

限制：

1 <= 树的结点个数 <= 10000
注意：本题与主站 110 题相同：https://leetcode-cn.com/problems/balanced-binary-tree/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/ping-heng-er-cha-shu-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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;

        int leftDepth = getDepth(root.left, 0);
        int rightDepth = getDepth(root.right, 0);
        if (Math.abs(leftDepth - rightDepth) <= 1) return isBalanced(root.left) && isBalanced(root.right);
        else return false;

    }

    public  int getDepth(TreeNode root, int depth) {
        if (root == null) return depth;
        depth += 1;
        int leftDepth = getDepth(root.left, depth);
        int rightDepth = getDepth(root.right, depth);
        return Math.max(leftDepth, rightDepth);
    }
}

自底向上

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) return true;
        return getDepth(root) == -1 ? false : true;
    }

    public int getDepth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = getDepth(root.left);
        if (leftDepth == -1) return -1;
        int rightDepth = getDepth(root.right);
        if (rightDepth == -1) return -1;
        if (Math.abs(leftDepth - rightDepth) > 1) return -1;
        return Math.max(leftDepth, rightDepth) + 1;
    }
}

展开全文 >>

俄罗斯农民乘法

考虑 A 和 B 两数相乘的时候我们如何利用加法和位运算来模拟，其实就是将 B 二进制展开，如果 B 的二进制表示下第 ii 位为 1，那么这一位对最后结果的贡献就是 A∗(1<<i) ，即 A<<i。我们遍历 B 二进制展开下的每一位，将所有贡献累加起来就是最后的答案，这个方法也被称作「俄罗斯农民乘法」，感兴趣的读者可以自行网上搜索相关资料。这个方法经常被用于两数相乘取模的场景，如果两数相乘已经超过数据范围，但取模后不会超过，我们就可以利用这个方法来拆位取模计算贡献，保证每次运算都在数据范围内。

1
2
3
4
5
6
7
8
9
10
11
12

public static int mul(int A, int B) {
    int ans = 0;
    for (; B > 0; B >>= 1) {
        if ((B & 1) == 1) {
            ans += A;
        }
        A <<= 1;
    }
    return ans;
}

参考文献

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

展开全文 >>

求1+2+3+...+n 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

示例 1：

输入: n = 3
输出: 6
示例 2：

输入: n = 9
输出: 45

限制：

1 <= n <= 10000
通过次数79,016提交次数92,650

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

使用递归+断路器机制

以逻辑运算符 && 为例，对于 A && B 这个表达式，如果 A 表达式返回 False ，那么 A && B 已经确定为 False ，此时不会去执行表达式 B。同理，对于逻辑运算符 ||， 对于 A || B 这个表达式，如果 A 表达式返回 True ，那么 A || B 已经确定为 True ，此时不会去执行表达式 B。

1
2
3
4
5
6
7
8
9

class Solution {
    public int sumNums(int n) {
        boolean flag = n > 0 && (n += sumNums(n - 1)) > 0;
        return n;
    }
}


使用递归+try catch

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int sumNums(int n) {
    int[] sum = new int[n];
        return getSum(n,sum);
    }
    private int getSum(int n,int[] sum){
        try {
            sum[n-1] = 0;
            sum[n-1] = getSum(n-1,sum)+ n;
            return sum[n-1];
        }catch (Exception e){
            return 0;
        }
    }

}

参考文献

黄金大镖客的评论

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/qiu-12n-lcof/solution/qiu-12n-by-leetcode-solution/
来源：力扣（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:

输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
示例 2:

输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

限制：

0 <= 数组长度 <= 10^5

注意：本题与主站 121 题相同：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/

通过次数55,378提交次数87,276

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

贪心算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int maxProfit(int[] prices) {
        if (prices.length < 2) return 0;
        int max = 0, buy = -1;                          //买入价格初始值设为-1（也就是手里没有股票）
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < buy || buy == -1) {         //如果手上没有股票，那么就买入一只，如果当前的价格更低，就买更低的
                buy = prices[i];
            } else {                                    //如果当前的价格大于买入的价格，就卖出，比较当前利润和最大利润的值，如果当前利润大于最大利润更新最大利润
                max = Math.max(prices[i] - buy, max);
            }
        }
        return max;
    }
}

展开全文 >>

二叉搜索树的第k大节点 

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
给定一棵二叉搜索树，请找出其中第k大的节点。

示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 4
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 4
 

限制：

1 ≤ k ≤ 二叉搜索树元素个数

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

从大到小算第K大的数

非递归中序遍历（正向）+小根堆

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        LinkedList<TreeNode> stack = new LinkedList<>();
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o1 - o2;
            }
        });
        int count = 0;
        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();

                //////////////////////////
                if (count < k) {
                    queue.offer(root.val);
                } else {
                    int temp = queue.peek();
                    if (root.val > temp) {
                        queue.poll();
                        queue.offer(root.val);
                    }
                }
                count++;
                //////////////////////////

                root = root.right;
            }
        }

        return queue.isEmpty() ? 0 : queue.poll();
    }
}

非递归中序遍历（逆向）

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int kthLargest(TreeNode root, int k) {
        LinkedList<TreeNode> stack = new LinkedList<>();

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.right;
            }
            if (!stack.isEmpty()) {
                root = stack.pop();
                if (--k == 0) return root.val;
                root = root.left;
            }
        }
        return 0;
    }
}

二叉搜索树的性质：二叉搜索树的中序遍历为递增序列 。

根据以上性质，易得二叉搜索树的 中序遍历倒序为递减序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right);//先从右子树开始，也就是从最大值开始
        if(k == 0) return;
        if(--k == 0) res = root.val;
        dfs(root.left);
    }
}



参考文献

1
2
3
4
作者：jyd
链接：https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/solution/mian-shi-ti-54-er-cha-sou-suo-shu-de-di-k-da-jie-d/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

0-n-1中缺失的数字 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2
示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：
1 <= 数组长度 <= 10000
通过次数74,996提交次数170,733

二分查找方法

  • 如果当前的数字的值大于index的值，说明在其左边有缺失的值。

  • 如果当前的数字的值等于index的值，说明在其右边可能有缺失的值。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    import java.util.*;
    public class Solution {
        public int solve (int[] a) {
            int n = a.length;
            int l = 0, r = n-1;
            while(l<=r){
                int m = l+(r-l)/2;
                if(a[m] > m){
                    r = m-1;
                }else{
                    l = m+1;                
                }
            }
            return l;
        }
    }

    二分查找方法

  • 如果index和数字相同时，那么缺失的数字一定在当前位置的后面

  • 如果index和数字不同时（index<数字），那么缺失的数字是定在当前位置的前面

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class Solution{
        public static int missingNumber(int[] nums) {
            int left = 0, right = nums.length - 1, mid = 0;
            while (left <= right) {
                mid = (left + right) / 2;
                if (nums[mid] == mid) left = mid + 1;           //当index和数字相同时，缺少的数字一定在右边
                else right = mid - 1;                           //当index和数字不同时（数字大于index），缺少的数字一定在左边
            }
            return left;
        }
    }

    顺序查找（不好）

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int missingNumber(int[] nums) {
        if (nums[0] != 0) return 0;
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] - nums[i - 1] > 1) {
                return nums[i] - 1;
            }
        }
        return nums[nums.length-1]+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
41
42
43
44
45
输入两个链表，找出它们的第一个公共节点。
如下面的两个链表：

在节点 c1 开始相交。


示例 1：


输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
 

示例 2：



输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。
 

示例 3：



输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。
 

注意：

如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
本题与主站 160 题相同：https://leetcode-cn.com/problems/intersection-of-two-linked-lists/
通过次数63,638提交次数100,800

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

先分别统计链表的长度，等长的那个先走Math.abs(len1-len2)步再同时走，如果两个链表有交点一定会在交点相遇。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int list1Len = 0, list2Len = 0;
        if (headA == null || headB == null) return null;

        ListNode node = headA;
        ListNode node1 = headB;
        while (node != null) {
            list1Len++;
            node = node.next;
        }
        while (node1 != null) {
            list2Len++;
            node1 = node1.next;
        }

        int count = 0;

        if (list1Len > list2Len) {
            node = headA;
            node1 = headB;
        } else {
            node = headB;
            node1 = headA;
        }

        while (node != null && node1 != null) {
            if (node != null && node1 != null && node.equals(node1)) {
                return node;
            }
            node = node.next;                                       //node是长的那个链表，node1是短的那个链表
            if (count >= Math.abs(list1Len - list2Len)) {           //长的先走，等一样长了再一起走
                node1 = node1.next;
            }
            count++;
        }
        return null;
    }
}

先让一个指针PA走A，一个指针PB走B，两个节点同时走，A走到末尾时，切换到B上，B走到末尾时切换到A上，这时如果链表有交点，两个指针将会在交点相遇。

1
2
3
4
5
相遇时两个指针走过的路程相同：

PA走过路程为链表A单独的+链表B单独的+公共部分
PB走过的路程为链表B单独的+链表A单独的+公共部分

你变成我，走过我走过的路。

我变成你，走过你走过的路。

然后我们便相遇了..

或许这就是程序员的浪漫吧

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //tempA和tempB我们可以认为是A,B两个指针
        ListNode tempA = headA;
        ListNode tempB = headB;
        while (tempA != tempB) {
            //如果指针tempA不为空，tempA就往后移一步。
            //如果指针tempA为空，就让指针tempA指向headB（注意这里是headB不是tempB）
            tempA = tempA == null ? headB : tempA.next;
            //指针tempB同上
            tempB = tempB == null ? headA : tempB.next;

            //可以理解为两条链表最后都指向了同一个 null （None）节点，代替了不相交的特殊情况，所以不会陷入死循环。 非常的巧妙
        }
        //tempA要么是空，要么是两链表的交点
        return tempA;
    }
}

参考文献

集合，双指针等3种解决方式，后两种击败了100%的用户

淡淡的扯淡的评论

展开全文 >>

最长不含重复字符的子字符串 

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
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
提示：

s.length <= 40000
注意：本题与主站 3 题相同：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-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
class Solution{
    public static int lengthOfLongestSubstring(String s) {
        Set<Character> set = new HashSet<Character>();
        int max = 0;
        int count = 0;                                      //字串的字符数量
        int start = 0;                                      //字串开始时的位置
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (!set.contains(c)) {
                set.add(c);
                count++;
            } else {
                max = Math.max(max, count);                 //每一次遇到重复元素，本次字符达到最大长度
                while (s.charAt(start) != c) {              //删掉集合中上一个与本次元素重复的元素之前的所有字符
                    set.remove(s.charAt(start));            //从集合删掉元素
                    start++;                                //起始位置后移一个
                    count--;                                //每删掉一个元素，减去一个计数
                }
                start++;                                    //从下一个字符开始
            }
        }
        max = Math.max(count, max);                         //判断最后一次的count和上一次的max哪个大
        return max;
    }
}

动态规划解法

状态转移如下:

  1. 如果当前的字符串与先前的字符串重复了，那么找到当前字符串j的上一个位置i，当前最大的字符串的长度是j-i;

  2. 如果当前的字符串与先前的字符串没有重复，那么最大字符串的长度是先前最大字符串长度+1

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> dic = new HashMap<>();
        int res = 0, tmp = 0;
        for(int j = 0; j < s.length(); j++) {
            int i = dic.getOrDefault(s.charAt(j), -1);          // 获取索引 i  
            dic.put(s.charAt(j), j);                            // 更新哈希表
            tmp = tmp < j - i ? tmp + 1 : j - i;                // dp[j - 1] -> dp[j]    当获取的i的值为-1时(即不重复)，temp一定小于j-i,temp=temp+1,如果i的值不为-1，肯定有一个字符与j相同，这个字符在的位置应该在计算temp的开头或者往后的一个，这样的话temp的值应当大于等于j-i，去除重复元素之前的元素后的长度是j-i
            res = Math.max(res, tmp);                           // max(dp[j - 1], dp[j])
        }
        return res;
    }
}

参考文献

jyd

1
2
3
4
作者：jyd
链接：https://leetcode-cn.com/problems/zui-chang-bu-han-zhong-fu-zi-fu-de-zi-zi-fu-chuan-lcof/solution/mian-shi-ti-48-zui-chang-bu-han-zhong-fu-zi-fu-d-9/
来源：力扣（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
数组的每个索引作为一个阶梯，第 i个阶梯对应着一个非负数的体力花费值 cost[i](索引从0开始)。

每当你爬上一个阶梯你都要花费对应的体力花费值，然后你可以选择继续爬一个阶梯或者爬两个阶梯。

您需要找到达到楼层顶部的最低花费。在开始时，你可以选择从索引为 0 或 1 的元素作为初始阶梯。

示例 1:

输入: cost = [10, 15, 20]
输出: 15
解释: 最低花费是从cost[1]开始，然后走两步即可到阶梯顶，一共花费15。
 示例 2:

输入: cost = [1, 100, 1, 1, 1, 100, 1, 1, 100, 1]
输出: 6
解释: 最低花费方式是从cost[0]开始，逐个经过那些1，跳过cost[3]，一共花费6。
注意：

cost 的长度将会在 [2, 1000]。
每一个 cost[i] 将会是一个Integer类型，范围为 [0, 999]。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        if (cost.length <2) return 0;
        int[][] dp = new int[cost.length][2];                                       //dp[i][0]指代不走第i个台阶,dp[i][1]指代走第i个台阶
        dp[0][0] = 0;                                                               //不走第一个台阶
        dp[0][1] = cost[0];                                                         //走第一个台阶
        dp[1][0] = cost[0];                                                         //走第二个台阶
        dp[1][1] = Math.min(cost[1] + dp[0][0], cost[1] + dp[0][1]);                //走第二个台阶（可能没走第一个台阶，也有可能走了第一个台阶）
        for (int i = 2; i < cost.length; i++) {
            dp[i][0] = dp[i - 1][1];                                                //本阶梯不走，那么上一个阶梯一定走了（每次最多两个阶梯）
            dp[i][1] = Math.min(dp[i - 1][1] + cost[i], dp[i - 1][0] + cost[i]);    //本阶梯走，上一个阶梯可能走了，也可能没走，选取最小cost
        }
        return Math.min(dp[cost.length - 1][0], dp[cost.length - 1][1]);            //走最后一个阶梯和不走最后一个阶梯的代价（包含前面的累计代价）
    }
}

假设数组cost 的长度为 n，则 n 个阶梯分别对应下标 0 到 n−1，楼层顶部对应下标 n，问题等价于计算达到下标 n 的最小花费。可以通过动态规划求解。

创建长度为 n+1 的数组 dp，其中 dp[i] 表示达到下标 i 的最小花费。

由于可以选择下标 0 或 1 作为初始阶梯，因此有 dp[0]=dp[1]=0。

当 2≤i≤n 时，可以从下标i−1 使用 cost[i−1] 的花费达到下标 i，或者从下标 i−2 使用cost[i−2] 的花费达到下标 i。为了使总花费最小，dp[i] 应取上述两项的最小值，因此状态转移方程如下：

1
dp[i]=min(dp[i−1]+cost[i−1],dp[i−2]+cost[i−2])

依次计算 dp 中的每一项的值，最终得到的dp[n] 即为达到楼层顶部的最小花费。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        if (n < 2) return 0;
        int[] dp = new int[n + 1];
        dp[0] = dp[1] = 0;
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        return dp[n];
    }
}

参考文献

1
2
3
4
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/min-cost-climbing-stairs/solution/shi-yong-zui-xiao-hua-fei-pa-lou-ti-by-l-ncf8/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

第一个只出现一次的字符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "
 

限制：

0 <= s 的长度 <= 50000

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public char firstUniqChar(String s) {
        int[] hash = new int[26];
        for (int i = 0; i < s.length(); i++) {
            hash[s.charAt(i) - 'a']++;
        }

        for (int i = 0; i < s.length(); i++) {
            if (hash[s.charAt(i) - 'a'] == 1) {
                return s.charAt(i);
            }
        }

        return ' ';
    }
}

展开全文 >>

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>希望有一天被领走