• LeetCode Hot 100

    文章目录

    17. 电话号码的字母组合

    给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

    • 回溯题，与经典组合题不同的是需要对多个数组进行组合；
    • 递归时到底传入start还是传入i，主要是看是否可以往回选取元素，如果可以则传入start，不可以则传入 i。
    public List<String> letterCombinations(String digits) {
        if ("".equals(digits)) {
            return new ArrayList<String>();
        }
        List<List<String>> list = new ArrayList<>();
        list.add(Arrays.asList("a", "b", "c"));
        list.add(Arrays.asList("d", "e", "f"));
        list.add(Arrays.asList("g", "h", "i"));
        list.add(Arrays.asList("j", "k", "l"));
        list.add(Arrays.asList("m", "n", "o"));
        list.add(Arrays.asList("p", "q", "r", "s"));
        list.add(Arrays.asList("t", "u", "v"));
        list.add(Arrays.asList("w", "x", "y", "z"));
        char[] arr = digits.toCharArray();
        List<List<String>> dic = new ArrayList<>();
        for (char c : arr) {
            int digit = c - '2';
            List<String> tmpList = list.get(digit);
            dic.add(tmpList);
        }
        List<String> resList = new ArrayList<>();
        StringBuilder res = new StringBuilder();
        sort(dic, resList, res, 0, 0);
        return resList;
    }
    //这里 num 表示取第几个数组，start 表示当前数组的第几个元素
    public void sort(List<List<String>> dicList, List<String> resList, StringBuilder res, int num, int start) {
        if (num == dicList.size()) {
            resList.add(res.toString());
            return;
        }
        for (int i = start; i < dicList.get(num).size(); i++) {
            res.append(dicList.get(num).get(i));
            //递归时数组往后推移，start 不变
            sort(dicList, resList, res, num+1, start);
            res.deleteCharAt(res.length()-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

    22. 括号生成

    数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

    • 如何拼接有效括号，无需全排列再去判断，只需要拼接时左括号有的话可以拼接左括号，右括号数量大于左括号时可以拼接右括号；
    • 无需将括号都实际摆出来，只需要计数就行。
    public List<String> generateParenthesis(int n) {
        List<String> resList = new ArrayList<>();
        dfs(resList, "", n, n);
        return resList;
    }

    public void dfs(List<String> resList, String res, int left, int right) {
        if (left == 0 && right == 0) {
            resList.add(res);
            return;
        }
        if (left > 0) {
            dfs(resList, res + "(", left-1, right);
        }
        if (right > left) {
            dfs(resList, res + ")", left, right-1);
        }
    }

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

    31. 下一个排列

    找到下一个比当前数组排列大的排列，例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列。

    • 这道题其实没有什么技巧，观察如何得到下一个更大的排列。
    • 从后往前先找到一个nums[i]
    public void nextPermutation(int[] nums) {
        if (nums.length == 1) {
            return;
        }
        boolean flag = false;
        int i = 0;
        for(i = nums.length - 2; i >= 0; i--) {
            if (nums[i] < nums[i+1]) {
                flag = true;
                break;
            }
        }
        if (flag) {
            int min = 101;
            int idx = nums.length;
            for (int j = i+1; j < nums.length; j++) {
                if (nums[j] > nums[i] && min > nums[j]) {
                    min = nums[j];
                    idx = j;
                }
            }
            int tmp = nums[i];
            nums[i] = nums[idx];
            nums[idx] = tmp;
            Arrays.sort(nums, i+1, nums.length);
        } else {
            Arrays.sort(nums);
        }
    }

    • 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

    39. 组合总和

    给你一个 无重复元素的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。candidates 中的同一个数字可以无限制重复被选取 。

    • 数组中的所有数都可以被重复使用， 第一反应这是一道无限背包问题，用dp来做，但是马上发现需要输出所有可能组合，而不仅是数量，因此需要用回溯来做；
    • 一般回溯都不会允许重复选取数字，如何解决这个问题呢？其实就是在递归时仍然传入 i 而不是 i+1。
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        int n = candidates.length;
        List<List<Integer>> resList = new ArrayList<>();
        combine(resList, new ArrayList<Integer>(), candidates, 0, target);
        return resList;
    }

    public void combine(List<List<Integer>> resList, List<Integer> res, int[] candidates, int start, int target) {
        if (target < 0) {
            return;
        }
        if (target == 0) {
            resList.add(new ArrayList(res));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            res.add(candidates[i]);
            //由于可以重复选择数字，因此这里递归还是传入 i
            combine(resList, res, candidates, i, target-candidates[i]);
            res.remove(res.size()-1);
        }
    }

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

    49. 字母异位词分组

    给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

    • 第一时间想到了要用26位数组存储每个字符出现的次数，但是却不知道如何比较每个字符串的26位数组是否匹配；
    • 可以将26位数组用字符串编码作为map的键，值则是满足此条件的字符串。
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            int[] dic = new int[26];
            //字典中存储每个字母出现的个数
            for (int j = 0; j < arr.length; j++) {
                dic[arr[j] - 'a'] ++;
            }
            //将字典编码作为map的键
            StringBuilder str = new StringBuilder();
            for (int k = 0; k < 26; k++) {
                if (dic[k] > 0) {
                    str.append(dic[k]);
                    str.append((char)(k + 'a'));
                }
            }
            List<String> list = map.getOrDefault(str.toString(), new ArrayList<>());
            list.add(strs[i]);
            map.put(str.toString(), list);
        }
        return new ArrayList<List<String>>(map.values());
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 还可以不用数组计数，直接对字符串排序，以排序后的字符串作为key存储
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (int i = 0; i < strs.length; i++) {
            char[] arr = strs[i].toCharArray();
            Arrays.sort(arr);
            String key = new String(arr);
            List<String> list = map.getOrDefault(key, new ArrayList<>());
            list.add(strs[i]);
            map.put(key, list);
        }
        return new ArrayList<List<String>>(map.values());
    }

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

    55. 跳跃游戏

    给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。判断你是否能够到达最后一个下标。

    • 这道题不难，开始第一反应是用dp，双层循环很慢；
    • 看了题解以后发现其实贪心就可以，只要最远跳跃距离能大于最后一个下标就行。
    public boolean canJump(int[] nums) {
        int max = nums[0];
        for (int i = 1; i < nums.length; i++) {
            if (i > max) return false;
            max = Math.max(max, nums[i] + i);
        }
        return true;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8

    96 不同的二叉搜索树

    给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

    • 这道题目找规律，不过规律挺难找的，是卡特兰数公式。G(n)=G(0)∗G(n−1)+G(1)∗(n−2)+…+G(n−1)∗G(0)
    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10

    98. 验证二叉搜索树

    • 最简单的中序遍历结果顺序。
    • 还可以不断递归判断子树是否是二叉搜索树，这里千万要注意不能只判断当前节点大于左节点，小于右节点，因为这不能保证当前节点大于左子树中所有节点值，小于右子树中所有节点值；
    • 因此引入两个边界值，判断当前节点值是否在边界内，递归时根据二叉搜索树的性质更新边界。
    class Solution {
    public boolean isValidBST(TreeNode root) {
        return validate(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }  

    public boolean validate(TreeNode node, long min, long max) {
        if (node == null) {
            return true;
        }
        if (node.val <= min || node.val >= max) {
            return false;
        }
        return validate(node.left, min, node.val) && validate(node.right, node.val, max);
    }
}

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

    146 LRU 缓存

    请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
    实现 LRUCache 类：
    LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
    int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
    void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该逐出 最久未使用的关键字。
    函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

    • 方法一，由于时间复杂度需要为 O(1)，因此可以想到需要使用 hashMap，又由于需要逐出最久未使用的关键字，因此需要使用链表有序。结合两者，LinkedHashMap 可以完全满足要求。
    • 继承 LinkedHashMap，重写它的一些方法即可。
    class LRUCache extends LinkedHashMap<Integer, Integer> {

    private int capacity;
    public LRUCache(int capacity) {
        super(capacity, 0.75F, true);
        this.capacity = capacity;
    }
    //不存在返回-1
    public int get(int key) {
        return super.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        super.put(key, value);
    }

	/**
	* 重写移除最久未使用元素所需满足条件的方法
	*/
    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity; 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 方法二，哈希表 + 双向链表；
    • 直接用 LinkedHashMap 有点偷懒，自己实现一个双向链表，再用哈希表存储节点；每次调用 get 或 put 方法以后就将节点移动到头部，如果节点数量超过容量，则移除尾部节点。
    class LRUCache {
	//双向链表节点结构
    class Node {
        Node prev;
        Node next;
        int key;
        int value;
        Node (int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
	// map 存储链表节点，方便快速找到节点位置
    private Map<Integer, Node> map = new HashMap<>();
    private Node head = new Node(-1, -1);
    private Node tail = new Node(-2, -1);
    private int capacity;
    public LRUCache(int capacity) {
    	//初始化头尾节点，避免边界出错
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            //找到节点，移动其到head后
            Node node = map.get(key);
            moveToHead(node);
            return node.value;
        } else {
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)) {
            //找到节点，变更节点值
            Node node = map.get(key);
            node.value = value;
            map.put(key, node);
            moveToHead(node);
        } else {
            //插入head后
            Node node = new Node(key, value);
            insertHead(node);
            map.put(key, node);
        }
        if (map.size() > capacity) {
            removeTail();
        }
    }

    private void insertHead(Node node) {
        //插入head后
        Node next = head.next;
        head.next = node;
        node.prev = head;
        node.next = next;
        next.prev = node;
    }

    private void moveToHead(Node node) {
        //断开原关联
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        next.prev = prev;
        insertHead(node);
    }

    private void removeTail() {
        if (map.size() <= 0) {
            return;
        }
        Node node = tail.prev;
        Node prev = node.prev;
        int key = node.key;
        prev.next = tail;
        tail.prev = prev;
        node.next = null;
        node.prev = null;
        map.remove(key);
    }
}

    • 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

    152. 乘积最大子数组

    • 这道题初看很简单，动态规划 dp 存储以 i 结尾的最大乘积，很容易忽略由于负负得正，乘积可能出现最小值翻身变成最大值的情况，所以需要分别记录最小值和最大值。
    public int maxProduct(int[] nums) {
        int max = 1;
        int min = 1;
        int res = Integer.MIN_VALUE;
        for(int i = 0; i < nums.length; i++) {
            //如果当前数小于0，交换最大最小值
            if (nums[i] < 0) {
                int tmp = max;
                max = min;
                min = tmp;
            }
            max = Math.max(nums[i], max * nums[i]);
            min = Math.min(nums[i], min * nums[i]);
            res = Math.max(max, res);
        }
        return res;
    }

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

    283. 移动零

    给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。

    • 将0往后移，其实也是将数字往前移，想成将数字往前移就不需要考虑数组逐个往后挪动；
    • 两个指针，i 遍历数组，j 指向可以被后面的元素替换的元素（比如0，或者已经前移的元素）
    public void moveZeroes(int[] nums) {
        int i = 0;
        int j = 0;
        for (i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                nums[j++] = nums[i];
            }
        }
        while (j < nums.length) {
            nums[j++] = 0;
        }
        
    }

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

    207. 课程表

    你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

    • 方法一，和课程表II 一样，拓扑排序构造邻接表，维护入度，找到课程排序，最后判断排序的课程数和总课程数是否相等；
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] list = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            indegree[pre[0]] ++;
            if (list[pre[1]] == null) {
                list[pre[1]] = new ArrayList<>();
            }
            list[pre[1]].add(pre[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }
        int num = 0;
        while (!queue.isEmpty()) {
            int course = queue.poll();
            num ++;
            if (list[course] != null) {
                List<Integer> tmp = list[course];
                for (int t : tmp) {
                    indegree[t]--;
                    if (indegree[t] == 0) {
                        queue.offer(t);
                    }
                }
            }
        }
        return num == numCourses;
    }

    • 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
    • 方法二，深度优先判断是否有环。同样构造邻接表，然后从每个节点开始遍历，判断是否有环；
    • 这里要注意剪枝，否则会超时。剪枝的方法是将判断是否遍历过的 boolean 型 isVisited 换成 int 型 flag，存储三个状态，flag == 0 表示未遍历过，flag == 1 表示在本轮dfs过程中已经被遍历过（有环，直接返回false），flag == -1 表示在前轮dfs遍历过程中已经被判断过了无环（这里就是剪枝，可以直接返回true）
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<Integer>[] list = new ArrayList[numCourses];
        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            indegree[pre[0]] ++;
            if (list[pre[1]] == null) {
                list[pre[1]] = new ArrayList<>();
            }
            list[pre[1]].add(pre[0]);
        }
        int[] flag = new int[numCourses];
        for (int i = 0 ; i < numCourses; i++) {
            if (!dfs(list, i, flag)) {
                return false;
            }
        }
        return true;
    }
    public boolean dfs(List<Integer>[] list, int i, int[] flag) {
        if (flag[i] == 1) {
            return false;
        }
        if (flag[i] == -1 || list[i] == null) {
            return true;
        }
        flag[i] = 1;
        for (int tmp : list[i]) {
            if (!dfs(list, tmp, flag)) {
                return false;
            }
        }
        flag[i] = -1;
        return true;
    }

    • 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

    337. 打家劫舍 III

    小偷又发现了一个新的可行窃的地区。这个地区只有一个入口，我们称之为 root 。除了 root 之外，每栋房子有且只有一个“父“房子与之相连。一番侦察之后，聪明的小偷意识到“这个地方的所有房屋的排列类似于一棵二叉树”。 如果 两个直接相连的房子在同一天晚上被打劫 ，房屋将自动报警。给定二叉树的 root 。返回 在不触动警报的情况下 ，小偷能够盗取的最高金额 。

    • 先层次遍历再用 dp 的思路是错的， 如 [2,1,3,null,4]，结果是 7 不是 6；
    • dfs 要么偷当前节点，要么偷子节点，可惜超时；
    class Solution {
    public int rob(TreeNode root) {
        TreeNode node = root;
        if (node == null) {
            return 0;
        }
        //偷当前节点
        int v1 = node.val;
        if (node.left != null) {
            v1 += rob(node.left.left) + rob(node.left.right);
        }
        if (node.right != null) {
            v1 += rob(node.right.left) + rob(node.right.right);
        }
        //不偷当前节点
        int v2 = 0;
        v2 = rob(node.left) + rob(node.right);
        return Math.max(v1, v2);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • dfs 超时是因为有太多重复遍历，改进方法是使用动态规划，对每个节点记录其状态，res[0] 表示不偷该节点能偷到的最多的钱，res[1]表示偷该节点能偷到的最大值，从当前节点开始能偷到的最大值取res[0]、res[1] 中的最大值。
    class Solution {
    //dp，有两种偷法，要么偷当前节点，要么偷两个子节点之和
    public int rob(TreeNode root) {
        int[] res = dfs(root);
        return Math.max(res[0], res[1]);
    }
    
    public int[] dfs(TreeNode node) {
        if (node == null) {
            return new int[2];
        }
        int[] left = dfs(node.left);
        int[] right = dfs(node.right);
        int[] res = new int[2];
        res[0] = Math.max(left[0], left[1]) + Math.max(right[0], right[1]);
        res[1] = node.val + left[0] + right[0];
        return res;  
    }
}

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

    394. 字符串解码

    给定一个经过编码的字符串，返回它解码后的字符串。编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

    • 由于先要计算最里面的括号，因此可以使用递归或栈；
    • 使用栈时，在栈里存储一对元素，分别是 ‘[’ 前所有的数字和所有的字母，遇到 ‘[’ 入栈，遇到 ‘]’ 出栈；想到在栈中存储什么元素很重要！！！
    • 如 abc3[de]，则遇到第一个左括号时入栈 (‘3’, ‘abc’)，遇到右括号时出栈，然后计算 abc + 3 *(de)，嵌套的括号也适用。
    public String decodeString(String s) {
        Stack<String[]> stack = new Stack<>();
        char[] arr = s.toCharArray();
        StringBuilder num = new StringBuilder();
        StringBuilder abc = new StringBuilder();
        int i = 0;
        while (i < arr.length) {
            if (arr[i] == '[') {
                String[] str = new String[]{num.toString(), abc.toString()};
                stack.push(str);
                num = new StringBuilder();
                abc = new StringBuilder();
            } else if (arr[i] == ']') {
                String[] tmp = stack.pop();
                int n = Integer.valueOf(tmp[0]);
                String str = abc.toString();
                while (n > 1) {
                    abc.append(str);
                    n--;
                }
                abc.insert(0, tmp[1]);
            } else if (arr[i] >= 'a' && arr[i] <= 'z') {
                abc.append(arr[i]);
            } else {
                num.append(arr[i]);
            }
            i++;
        }
        return abc.toString();
    }

    • 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
    • 还看到一种简单的栈思路，将元素一个一个入栈，直到遇到第一个右括号，再弹出元素处理左括号与右括号中间的字符，并入栈。这种思路更容易想到。

    438. 找到字符串中所有字母异位词

    给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

    • 判断两个单词是否是异位词不需要组合成1a1b1c的模式，直接数组比较即可；Arrays.equal(arr1, arr2);
    • 还可以用滑动窗口；
        public List<Integer> findAnagrams(String s, String p) {
        List<Integer> res = new ArrayList<>();
        char[] parr = p.toCharArray();
        int[] pdic = new int[26];
        for(char c : parr) {
            pdic[c -  'a'] ++;
        }
        char[] sarr = s.toCharArray();
        int[] sdic = new int[26];
        int left = 0;
        int right = 0;
        //滑动窗口
        while(right < sarr.length) {
        	//不断移动右边界
            int tmp = sarr[right] - 'a';
            sdic[tmp] ++;
            //如果移入窗口内的有不符合要求的字符则缩短左边界直至窗口为0
            while (sdic[tmp] > pdic[tmp]) {
                sdic[sarr[left] - 'a'] --;
                left ++;
            }
            //如果窗口内的字符数等于p中字符数，则是异位词
            if (right - left + 1 == parr.length) {
                res.add(left);
            }
            right ++;
        }
        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

    581. 最短无序连续子数组

    给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。

    • 开始想着遍历数组，维护最大最小值，更新左右边界，但需要考虑的细节很多；
    • 方法一，可以拷贝一份数组进行排序，分别找左右两端第一个数不同的位置即是左右边界；
    • 方法二，从左到右遍历，不断更新最大值，如果当前值比最大值要小，则该位置需要排序，是右边界；从右到左遍历，不断更新最小值，如果当前值比最小值要大，则该位置需要排序，是左边界。
    public int findUnsortedSubarray(int[] nums) {
        if (nums.length <= 1) {
            return 0;
        }
        int max = nums[0];
        int min = nums[nums.length-1];
        int left = nums.length-1;
        int right = 0;
        //从左到右遍历，不断更新最大值，如果当前值比最大值要小，则该位置需要排序，是右边界
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= max) {
                max = nums[i];
            } else {
                right = i;
            }
        }
        //从右到左遍历，不断更新最小值，如果当前值比最小值要大，则该位置需要排序，是左边界
        for (int i = nums.length - 1; i >= 0; i--) {
            if (nums[i] <= min) {
                min = nums[i];
            } else {
                left = i;
            }
        }
        return right - left + 1 >= 0 ? right - left + 1 : 0;
    }

    • 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

    621. 任务调度器

    给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。你需要计算完成所有任务所需要的 最短时间 .

    • 很有技巧的一道题，可以套公式。首先利用 26 位数组统计每个字符出现的频数并排序，得到最大频数和最大频数的个数，则公式为 (max-1) * (n + 1) + numMax，其中 max 为最大频数，numMax 为最大频数的个数。
    • 解释一下公式的含义，如 [A, A, A, A, A, A, B, C, D, E, F, G]，n = 2，出现次数最多的是 A，则首先考虑排 A，6 个 A 中 5 个 A 都需要分别搭配 n 个不同的任务或者待命，即 (max - 1) * (n + 1)，最后剩下的一个 A 的还需要加上，但是如果最大频数的个数不止 1 个，则需要加 numMax，即 (max-1) * (n + 1) + numMax。但是，要注意的是，如果任务数远大于 n，不需要插入待命状态，那么此公式计算出来的结果会小于任务长度，因此结果取两者之间更大的那个.
    public int leastInterval(char[] tasks, int n) {
        if (n == 0) {
            return tasks.length;
        }
        int[] arr = new int[26];
        for (char task : tasks) {
            arr[task - 'A'] ++;
        }
        Arrays.sort(arr);
        //最大频数
        int max = arr[25];
        //最大频数的个数
        int numMax = 1;
        for (int i = 24; i >= 0; i--) {
            if (arr[i] == arr[i+1]) {
                numMax ++;
            } else {
                break;
            }
        }
        return Math.max((max-1) * (n+1) + numMax, tasks.length);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
  • 相关阅读:
    Golang 切片删除指定元素的几种方法
    python画图
    Unity中Shader纹理的环绕方式
    ILS解析漏洞复现
    Linux进程
    针对直播痛点的关键技术解析——首帧秒开、清晰度、流畅度
    英特尔® NUC迷你电脑设置带电自启
    Ubuntu 无法定位软件包 yum （添加镜像后还出现）
    关于#华为#的问题：二、半导体设备：半导体封装设备、半导体扩散设备、半导体焊接设备、半导体清洗设备、半导体 测试设备、半导体制冷设备、半导体氧化设备等（相关搜索：人工智能）
    计算机毕业设计Java中医药院校科研会议系统（源码+系统+mysql数据库+Lw文档）
  • 原文地址：https://blog.csdn.net/weixin_39505091/article/details/125820188