By的博客
0%

力扣

发表于 更新于 分类于

面试题 08.11. 硬币凑整

给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。(结果可能会很大，你需要将结果模上1000000007)

示例1:

输入: n = 5

输出：2

解释: 有两种方式可以凑成总金额: 5=5 5=1+1+1+1+1

示例2:

输入: n = 10

输出：4

解释: 有四种方式可以凑成总金额: 10=10 10=5+5 10=5+1+1+1+1+1 10=1+1+1+1+1+1+1+1+1+1

说明：

你可以假设：0 <= n (总金额) <= 1000000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int waysToChange(int n) {       
        int[] dp = new int[n + 1];      
        int[] coins = new int[]{1,5,10,25};
        //刚好可以用一个硬币凑成的情况，是一种情况
        // while i == coin :
        //dp[i] = dp[i - coin] => dp[0]
        dp[0] = 1;
        /**
        * dp方程：dp[i] += dp[i - coin];
        */
        for(int coin : coins) {
            for(int i = coin; i <= n; i++) {
                dp[i] = (dp[i] + dp[i - coin]) % 1000000007;
            }
        }
        return dp[n];
    }
}

面试题51. 数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。

示例 1:

输入: [7,5,6,4]

输出: 5

限制：0 <= 数组长度 <= 50000

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 int reversePairs(int[] nums) {
        return merge(nums, 0, nums.length - 1);
    }
    int merge(int[] arr, int start, int end) {
        if (start >= end) return 0;
        int mid = start + (end - start) / 2;
        int count = merge(arr, start, mid) + merge(arr, mid + 1, end);

        int[] temp = new int[end - start + 1];
        int i = start, j = mid + 1, k = 0;
        while (i <= mid && j <= end) {
            count += arr[i] <= arr[j] ? j - (mid + 1) : 0;
            temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++];
        }
        while (i <= mid) {
            count += j - (mid + 1);
            temp[k++] = arr[i++];
        }
        while (j <= end){
            temp[k++] = arr[j++];
        }  
        System.arraycopy(temp, 0, arr, start, end - start + 1);
        return count;
    }
}

3. 无重复字符的最长子串

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”

输出: 3

解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。

示例 2:

输入: “bbbbb”

输出: 1

解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。

示例 3:

输入: “pwwkew”

输出: 3

解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

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 lengthOfLongestSubstring(String s) {
        if (s.length()==0) {
            return 0;
        }
        HashMap map = new HashMap();
        //记录最大长度
        int max = 0;
        //记录最左开始字母下标
        int left = 0;
        for(int i = 0; i < s.length(); i ++){
            if(map.containsKey(s.charAt(i))){
                //更新最左开始字母下标
                left = Math.max(left,map.get(s.charAt(i)) + 1);
            }
            map.put(s.charAt(i),i);
            max = Math.max(max,i-left+1);
        }
        return max;
    }
}

4. 寻找两个正序数组的中位数

给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1:

nums1 = [1, 3]

nums2 = [2]

则中位数是 2.0

示例 2:

nums1 = [1, 2]

nums2 = [3, 4]

则中位数是 (2 + 3)/2 = 2.5

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
class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //分配新数组
        int[] nums = new int[m + n];
        //nums1为空
        if (m == 0) {
            //判断奇偶性，分类求中位数
            if (n % 2 == 0) {
                return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
            } else {
                return nums2[n / 2];
            }
        }
        //nums2为空
        if (n == 0) {
            //判断奇偶性，分类求中位数
            if (m % 2 == 0) {
                return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
            } else {
                return nums1[m / 2];
            }
        }
        //新数组指针
        int count = 0;
        //nums1和nums2的指针
        int i = 0, j = 0;
        //遍历复制
        while (count != (m + n)) {
            //nums1数组遍历完，直接复制nums2数组
            if (i == m) {
                while (j != n) {
                    nums[count++] = nums2[j++];
                }
                break;
            }
            //nums2数组遍历完，直接复制nums1数组
            if (j == n) {
                while (i != m) {
                    nums[count++] = nums1[i++];
                }
                break;
            }
            //选择nums1中和nums2中小的加入
            if (nums1[i] < nums2[j]) {
                nums[count++] = nums1[i++];
            } else {
                nums[count++] = nums2[j++];
            }
        }
        //返回中位数
        if (count % 2 == 0) {
            return (nums[count / 2 - 1] + nums[count / 2]) / 2.0;
        } else {
            return nums[count / 2];
        }
    }
}

5. 最长回文子串

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1：

输入: “babad”

输出: “bab”

注意: “aba” 也是一个有效答案。

示例 2：

输入: “cbbd”

输出: “bb”

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
class Solution {
    public String longestPalindrome(String s) {
        if(s == null || s.equals("")){
            return s;
        }
        
        //字符串s[i⋯j]是否为回文子串，如果是，dp[i][j]=true，如果不是，dp[i][j]=false
        boolean[][] dp = new boolean[s.length()][s.length()];
        
        //记录最长回文字串的左右下标
        int min = 0, max = 0;
        
        //初始化，单个字符都是回文子串
        for(int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        
        //开始遍历
        for(int i = s.length() - 1; i >= 0; i--){
            for(int j = i + 1; j < s.length(); j++){
                if(s.charAt(i) == s.charAt(j)) {
                    //考虑“cbba”这种情况
                    if(j - i == 1){
                        dp[i][j] = true;
                    }else{
                    //只要dp[i+1][j-1]是回文子串，那么dp[i][j]也就是回文子串
                        dp[i][j] = dp[i+1][j-1]; 
                    }
                }else{
                    dp[i][j] = false;
                }

                if(dp[i][j]){
                    //找到更长字串，则更新
                    if(max - min <= j - i){
                        min = i;
                        max = j;
                    }
                }
            }
        }
        return s.substring(min, max + 1);
    }
}

11. 盛最多水的容器

给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

img

图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

说明：你不能倾斜容器，且 n 的值至少为 2。

示例：

输入：[1,8,6,2,5,4,8,3,7]

输出：49

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
在每一个状态下，无论长板或短板收窄1格，都会导致水槽底边宽度−1：
若向内移动短板，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 可能变大，因此水槽面积 S(i, j)S(i,j) 可能增大。
若向内移动长板，水槽的短板 min(h[i], h[j])min(h[i],h[j]) 不变或变小，下个水槽的面积一定小于当前水槽面积。
因此，向内收窄短板可以获取面积最大值。
*/
class Solution {
    public int maxArea(int[] height) {
        int res = 0, i = 0, j = height.length - 1;
        while (i < j){
            if(height[i] <= height[j]){
                res = Math.max(res, height[i] * (j - i));
                i++;
            }else{
                res = Math.max(res, height[j] * (j - i));
                j--;
            }
        }
        return res;
    }
}

23. 合并K个排序链表

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
1->4->5,
1->3->4,
2->6
]

输出: 1->1->2->3->4->4->5->6

利用堆做排序

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0) {
            return null;
        }
        //创建一个堆，并设置元素的排序方式
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val - o2.val);
            }
        });

		//遍历链表数组，然后将每个链表的每个节点都放入堆中
		for(int i = 0;i < lists.length; i++) {
			while(lists[i] != null) {
				queue.add(lists[i]);
				lists[i] = lists[i].next;
			}
		}   
        ListNode dummy = new ListNode(-1);
        ListNode head = dummy;
        //从堆中不断取出元素，并将取出的元素串联起来
        while( !queue.isEmpty() ) {
            dummy.next = queue.poll();
            dummy = dummy.next;
        }
        dummy.next = null;
        return head.next;
    }
}

堆排序优化

我们建立完k个大小的堆后，就不断的从堆中获取节点，如果获取到的节点不为空，即还有下一个节点，那么就将下一个节点放到堆中。利用这个特点我们就可以优化空间了，将原先的O(N)的空间复杂度优化到O(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
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0) {
            return null;
        }
        //创建一个小根堆，并定义好排序函数
        PriorityQueue queue = new PriorityQueue(new Comparator() {
            public int compare(ListNode o1, ListNode o2) {
                return (o1.val - o2.val);
            }
        });
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        //这里跟上一版不一样，不再是一股脑全部放到堆中
        //而是只把k个链表的第一个节点放入到堆中
        for(int i = 0; i < lists.length; i++) {
            ListNode head = lists[i];
            if(head!=null) {
                queue.add(head);
            }
        }
        //之后不断从堆中取出节点，如果这个节点还有下一个节点，
        //就将下个节点也放入堆中
        while(queue.size() > 0) {
            ListNode node = queue.poll();
            cur.next = node;
            cur = cur.next;
            if(node.next!=null) {
                queue.add(node.next);
            }
        }
        cur.next = null;
        return dummy.next;
    }
}

两两合并

对于这四个链表，我们先合并A1和A2，将这两个链表变成A1-A2，然后再按照两两合并的方式，合并A1-A2和A3，这三个链表就合并成了A1-A2-A3，最后将A1-A2-A3跟A4两两合并，四个链表就合并完了。

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
class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        if(lists==null || lists.length==0) {
            return null;
        }
        //将lists[0]作为最终合并的链表，然后将list[0]和lists[1]合并成lists[0-1]
        //再将lists[0-1]和lists[2]合并，如此反复最终lists[0]就是最终结果
        ListNode res = lists[0];
        for(int i=1;i
            res = merge(res,lists[i]);
        }
        return res;
    }

    //合并两个有序链表
    private ListNode merge(ListNode a, ListNode b) {
        if(a==null || b==null) {
            return (a==null) ? b : a;
        }
        if(a.val<=b.val) {
            a.next = merge(a.next,b);
            return a;
        } else {
            b.next = merge(a,b.next);
            return b;
        }
    }
}

35. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

示例 3:

输入: [1,3,5,6], 7

输出: 4

示例 4:

输入: [1,3,5,6], 0

输出: 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int searchInsert(int[] nums, int target) {
        //下标小于low的值都小于target
        int low = -1;
        //下标大于high的值都大于target
        int high = nums.length;
        //当low和high之间有值时不断循环
        while(low + 1 < high){
            int mid = (low + high) / 2;
            if(nums[mid] >= target){
                high = mid;
            }else{
                low = mid;
            }
        }
        return high;
    }
}

46. 全排列

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]

输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,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
class Solution {
    List> res = new LinkedList<>();

    /* 主函数，输入一组不重复的数字，返回它们的全排列 */
    public List> permute(int[] nums) {
        // 记录「路径」
        LinkedList track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素
    // 结束条件：nums 中的元素全都在 track 中出现
    void backtrack(int[] nums, LinkedList track) {
        // 触发结束条件
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (track.contains(nums[i]))
                continue;
            // 做选择
            track.add(nums[i]);
            // 进入下一层决策树
            backtrack(nums, track);
            // 取消选择
            track.removeLast();
        }
    }
}

55. 跳跃游戏

给定一个非负整数数组，你最初位于数组的第一个位置。

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个位置。

示例 1:

输入: [2,3,1,1,4]

输出: true

解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

示例 2:

输入: [3,2,1,0,4]

输出: false

解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean canJump(int[] nums) {
        //记录当前最大跳跃距离
        int maxLen = 0;
        for(int i = 0; i < nums.length; i++){
            //如果当前坐标大于最大跳跃距离，则当前坐标不可达，返回false
            if(i > maxLen){
                return false;
            }
            //否则更新最大跳跃距离
            maxLen = Math.max(maxLen, i + nums[i]);
        }
        return true;
    }
}

76. 最小覆盖子串

给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = “ADOBECODEBANC”, T = “ABC”

输出: “BANC”

说明：

如果 S 中不存这样的子串，则返回空字符串 “”。

如果 S 中存在这样的子串，我们保证它是唯一的答案。

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
class Solution {
    public static String minWindow(String s, String t) {
        if (s == null || s == "" || t == null || t == "" 
        || s.length() < t.length()) {
            return "";
        }

        //用来统计t中每个字符出现次数
        int[] needs = new int[128];

        //用来统计滑动窗口中每个字符出现次数
        int[] window = new int[128];

        //初始化
        for (int i = 0; i < t.length(); i++) {
            needs[t.charAt(i)]++;
        }

        //滑动窗口左右边界
        int left = 0;
        int right = 0;

        String res = "";

        //目前有多少个字符
        int count = 0;

        //用来记录最短需要多少个字符。
        int minLength = s.length() + 1;

        while (right < s.length()) {
            char ch = s.charAt(right);
            window[ch]++;
            if (needs[ch] > 0 && needs[ch] >= window[ch]) {
                count++;
            }

            //移动到不满足条件为止
            while (count == t.length()) {
                ch = s.charAt(left);
                if (needs[ch] > 0 && needs[ch] >= window[ch]) {
                    count--;
                }
                if (right - left + 1 < minLength) {
                    minLength = right - left + 1;
                    res = s.substring(left, right + 1);

                }
                window[ch]--;
                left++;

            }
            right++;

        }
        return res;
    }
}

84. 柱状图中最大的矩形

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。

求在该柱状图中，能够勾勒出来的矩形的最大面积。

img

以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。

img

图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]

输出: 10

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
/*
通过观察，可以发现，最大面积矩形存在于以下几种情况：

1.确定了最矮柱子以后，矩形的宽尽可能往两边延伸。
2.在最矮柱子左边的最大面积矩形（子问题）。
3.在最矮柱子右边的最大面积矩形（子问题）。
*/
class Solution {
    public int largestRectangleArea(int[] heights) {
        return largestRectangleArea(heights, 0, heights.length-1);
    }
    public int largestRectangleArea(int[] heights, int left, int right) {
        if (left > right) {
            return 0;
        }
        if (right == left) {
            return heights[left];
        }
        //存储最小高度
        int minHeight = heights[left];
        //存储最小高度下标
        int minHeightIndex = left;
        //遍历找出最小高度
        for (int i = left; i <= right; i++) {
            if (heights[i] < minHeight) {
                minHeight = heights[i];
                minHeightIndex = i;
            }
        }
        //递归求解最大值
        return Math.max(
            minHeight * (right - left + 1), 
            Math.max(largestRectangleArea(heights, left, minHeightIndex - 1),                          							 largestRectangleArea(heights, minHeightIndex + 1, right)));
    }
}

101. 对称二叉树

给定一个二叉树，检查它是否是镜像对称的。

例如，二叉树 [1,2,2,3,4,4,3] 是对称的。

1
2
3
4
5
	1
   / \
  2   2
 / \ / \
3  4 4  3

但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:

1
2
3
4
5
1
  / \
 2   2
  \   \
  3    3
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        } else {
            return isMirrorBTree(root.left, root.right);
        }
    }
    
    boolean isMirrorBTree(TreeNode root1, TreeNode root2) {
        if(null == root1 && null == root2) {
            return true;
        }else if(null == root1 || null == root2) {
            return false;
        }
        if(root1.val != root2.val) {
            return false;
        }
        //此处注意相反比较
        return isMirrorBTree(root1.left,root2.right)
            && isMirrorBTree(root1.right,root2.left);
    }
}

105. 从前序与中序遍历序列构造二叉树

根据一棵树的前序遍历与中序遍历构造二叉树。

注意：你可以假设树中没有重复的元素。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

[3,9,20,15,7]

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.Arrays;
class Solution {
    public TreeNode buildTree(int[] pre, int[] in) {
        if(pre.length == 0 || in.length == 0){
            return null;
        }
        //前序遍历的第一个节点为根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < in.length; i++){
            //找到中序遍历中根节点的位置
            if(pre[0] == in[i]){
                root.left = buildTree
                    (Arrays.copyOfRange(pre, 1, i+1), 
                     Arrays.copyOfRange(in, 0, i));
                root.right = buildTree
                    (Arrays.copyOfRange(pre, i+1, pre.length), 
                     Arrays.copyOfRange(in, i+1, in.length));
                break;
            }
        }
        return root;
    }
}

146. LRU缓存机制

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

  • 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

  • 写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

1
2
3
4
5
6
7
8
9
10
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4
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
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
class LRUCache {
    /**
     * Node类用于抽象链表的节点
     * key、value存储键、值，
     * before、after分别指向当前节点的前后Node节点；
     */
    class Node {
        int key;
        int value;
        Node before;
        Node after;
    }
    /**
     * 使用HashMap缓存Node节点
     */
    private HashMap cache = new HashMap();
    /**
     * 最大容量，超过capacity时继续插入会触发删除最老未被使用的节点
     */
    private int capacity;
    /**
     * 头节点、尾节点（注意这两个节点不存储实际的数据）
     */
    private Node head, tail;

    public LRUCache(int capacity) {
        this.capacity = capacity;

        head = new Node();
        head.before = null;

        tail = new Node();
        tail.after = null;

        head.after = tail;
        tail.before = head;
    }
    
    public int get(int key) {
        Node node = cache.get(key);
        if (node == null) {
            return -1;
        }
        // 如果获取到数据，则将获取到的节点移动到队列头部;
        moveToHead(node);
        return node.value;
    }

    /**
     * 将节点移动到有效数据头部
     * @param node
     */
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    /**
     * 删除队列中的一个节点
     * @param node
     */
    private void removeNode(Node node) {
        Node before = node.before;
        Node after = node.after;
        before.after = after;
        after.before = before;
    }

    /**
     * 将节点插入队列头部
     * @param node
     */
    private void addToHead(Node node) {
        node.before = head;
        node.after = head.after;
        head.after.before = node;
        head.after = node;
    }

    public void put(int key, int value) {
        Node node = cache.get(key);
        if (node == null) {
            Node newNode = new Node();
            newNode.key = key;
            newNode.value = value;
            cache.put(key, newNode);
            addToHead(newNode);
            if (cache.size() > capacity) {
                // 删除队尾有效数据节点
                Node tail = this.popTail();
                this.cache.remove(tail.key);
            }
        } else {
            node.value = value;
            // 在使用get方法获取值之后，需要将当前获取的节点移动到队列头部
            moveToHead(node);
        }
    }

    /**
     * 删除有效数据尾节点
     * @return 尾节点
     */
    private Node popTail() {
        Node res = tail.before;
        this.removeNode(res);
        return res;
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

152. 乘积最大子数组

给你一个整数数组 nums ，请你找出数组中乘积最大的连续子数组（该子数组中至少包含一个数字），并返回该子数组所对应的乘积。

示例 1:

输入: [2,3,-2,4]

输出: 6

解释: 子数组 [2,3] 有最大乘积 6。

示例 2:

输入: [-2,0,-1]

输出: 0

解释: 结果不能为 2, 因为 [-2,-1] 不是子数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProduct(int[] nums) {
        int max = nums[0], min = nums[0], result = nums[0];
        //由于数组中含有负数，需要同时维护max和min
        for (int i = 1; i < nums.length; i++) {
            int temp = max;
            //max 取 max * nums[i]、min * nums[i]、nums[i]中的最大值
            max = Math.max(Math.max(max * nums[i], min * nums[i]), nums[i]);
            //min 取 temp * nums[i]、min * nums[i]、nums[i]中的最小值
            min = Math.min(Math.min(temp * nums[i], min * nums[i]), nums[i]);
            //记录最大值
            if (max > result) result = max;
        }
        return result;
    }
}

198. 打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1:

输入: [1,2,3,1]

输出: 4

解释: 偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
偷窃到的最高金额 = 1 + 3 = 4 。

示例 2:

输入: [2,7,9,3,1]

输出: 12

解释: 偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
偷窃到的最高金额 = 2 + 9 + 1 = 12 。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if(len == 0)
            return 0;
        int[] dp = new int[len + 1];
        dp[0] = 0;
        dp[1] = nums[0];
        for(int i = 2; i <= len; i++) {
            //动态规划方程：dp[n] = MAX( dp[n-1], dp[n-2] + num )
            dp[i] = Math.max(dp[i-1], dp[i-2] + nums[i-1]);
        }
        return dp[len];
    }
}

210. 课程表 II

现在你总共有 n 门课需要选，记为 0 到 n-1。在选修某些课程之前需要一些先修课程。 例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示他们: [0,1]

给定课程总量以及它们的先决条件，返回你为了学完所有课程所安排的学习顺序。

可能会有多个正确的顺序，你只要返回一种就可以了。如果不可能完成所有课程，返回一个空数组。

示例 1:

输入: 2, [[1,0]]

输出: [0,1]

解释: 总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2:

输入: 4, [[1,0],[2,0],[3,1],[3,2]]

输出: [0,1,2,3] or [0,2,1,3]

解释: 总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

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
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        //课程数为0，直接返回空数组
        if (numCourses == 0) return new int[0];
        // 建立入度表
        int[] inDegrees = new int[numCourses];
        // 对于有先修课的课程，计算有几门先修课
        for (int[] p : prerequisites) { 
            inDegrees[p[0]]++;
        }
        Queue queue = new LinkedList<>();
        // 入度为0的节点,加入队列，表示可以直接学习
        for (int i = 0; i < inDegrees.length; i++) {
            if (inDegrees[i] == 0) queue.offer(i);
        }
        // 记录学完的课程数量
        int count = 0;
        // 记录学完的课程
        int[] res = new int[numCourses];
        // 根据提供的先修课列表，删除入度为0的节点
        while (!queue.isEmpty()){
            //将可以学完的课程加入结果当中
            int curr = queue.poll();
            res[count++] = curr;
            for (int[] p : prerequisites) {
                //将先修课程为curr的节点入度减1
                if (p[1] == curr){
                    inDegrees[p[0]]--;
                    //如果节点入度为0，则加入队列，代表可以直接学习
                    if (inDegrees[p[0]] == 0) queue.offer(p[0]);
                }
            }
        }
        //如果已学习课程数count等于总数numCourses，则返回结果res
        if (count == numCourses) return res;
        //否则返回空数组
        return new int[0];
    }
}

287. 寻找重复数

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

示例 1:

输入: [1,3,4,2,2]

输出: 2

示例 2:

输入: [3,1,3,4,2]

输出: 3

说明：

  1. 不能更改原数组（假设数组是只读的）。
  2. 只能使用额外的 O(1) 的空间。
  3. 时间复杂度小于 O(n2) 。
  4. 数组中只有一个重复的数字，但它可能不止重复出现一次。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findDuplicate(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        Map map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if (map.get(nums[i]) == null){
                map.put(nums[i],1);
            } else {
               return nums[i];
            }
        }
        return 0;
    }
}

394. 字符串解码

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例:

s = “3[a]2[bc]”, 返回 “aaabcbc”.

s = “3[a2[c]]”, 返回 “accaccacc”.

s = “2[abc]3[cd]ef”, 返回 “abcabccdcdcdef”.

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
/*
① 找到第一对匹配的括号开始和结束的索引位置
② 从"["括号的开始位置向前扫描，找到数字出现的起始坐标
③ 把出现在数字之前的字符复制到StringBuilder中
④ 复制括号中的字符到StringBuilder中
⑤ 复制"]"括号后的字符到StringBuilder中
⑥ s赋值为StringBuilder中的字符串，并将StringBuilder清空，重复上述过程，指导s字符串中找不到括号为止；
*/
class Solution {
    public String decodeString(String s) {
        if(s == null || s.length() == 0){
            return "";
        }
        StringBuilder sb = new StringBuilder();
        while (s.contains("[")) {
            
            //记录第一对括号的起始位置和结束位置
            int startEqual = 0, endEqual = 0;
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '[') {
                    startEqual = i;
                }
                if (s.charAt(i) == ']') {
                    endEqual = i; 
                    break;
                }
            }

            //括号中的字符串sub
            String sub = s.substring(startEqual + 1, endEqual);

            //向前扫描，找到数字开始的位置;
            int numIndex = startEqual - 1;
            while (numIndex >= 0 && Character.isDigit(s.charAt(numIndex))){
                numIndex--;
            }                          

            //需要重复的次数，求出数字的值
            int times = Integer.parseInt(s.substring(numIndex + 1, startEqual));

            //将"["括号数字之前的字符添加到sb中
            sb.append(s, 0, numIndex + 1);
            while (times-- > 0){
                sb.append(sub);
            }
                
            //将"]"右括号之后的字符添加到sb中
            sb.append(s, endEqual + 1, s.length());

            s = sb.toString();
            sb = new StringBuilder();
        }
        return s;
    }
}

402. 移掉K位数字

给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。

注意:

num 的长度小于 10002 且 ≥ k。

num 不会包含任何前导零。

示例 1 :

输入: num = “1432219”, k = 3

输出: “1219”

解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。

示例 2 :

输入: num = “10200”, k = 1

输出: “200”

解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。

示例 3 :

输入: num = “10”, k = 2

输出: “0”

解释: 从原数字移除所有的数字，剩余为空就是0。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public String removeKdigits(String num, int k) {
        if (num.length() == k) {
            return "0";
        } 
        StringBuilder s = new StringBuilder(num);
        //共删除k次
        for (int i = 0; i < k; i++) {
            int idx = 0;
            //找到持续增加的区间最后的数字，也就是最大的数字下标idx
            for (int j = 1; j < s.length() && s.charAt(j) >= s.charAt(j - 1); j++) {
                idx = j;
            }
            //删除idx
            s.delete(idx, idx + 1);
            //特殊情况：删除最大数后第一位为0
            while (s.length() > 1 && s.charAt(0) == '0'){
                s.delete(0, 1);
            }
        }
        return s.toString();
    }
}

680. 验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

示例 1:

输入: “aba”

输出: True

示例 2:

输入: “abca”

输出: True

解释: 你可以删除c字符。

注意:

字符串只包含从 a-z 的小写字母。字符串的最大长度是50000。

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 {
    char[] array;

    public boolean validPalindrome(String s) {
        //将字符串转换为字符数组
        array = s.toCharArray();
        //双指针
        for (int low = 0, high = array.length - 1; low < high; low++, high--){
            if (array[low] != array[high]){
                return isSub(low + 1, high) || isSub(low, high - 1);
            }
        }
        //这种情况是没有删除字符
        return true;
    }

    public boolean isSub(int low, int high){
        while(low < high){
            if (array[low++] != array[high--]){
                return false;
            }
        }
        return true;
    }
}

974. 和可被 K 整除的子数组

给定一个整数数组 A，返回其中元素之和可被 K 整除的（连续、非空）子数组的数目。

示例：

输入：A = [4,5,0,-2,-3,1], K = 5

输出：7

解释：

有 7 个子数组满足其元素之和可被 K = 5 整除：

[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

提示：

1 <= A.length <= 30000

-10000 <= A[i] <= 10000

2 <= K <= 10000

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int N = A.length, sum = 0, ans = 0;
        int[] map = new int[K];
        map[0] = 1;
        for (int i = 1; i <= N; i++) {
            //前缀和
            sum = sum + A[i-1]; 
            //将key定义为sum[i]%K
            int key = (sum % K + K) % K;
            ans += map[key];
            map[key]++;
        }
        return ans;
    }
}