杨辉三角 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

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

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

avatar

实现方式差别会引起较大的时间差距

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();
        if (numRows == 0) {
            return result;
        }
        result.add(Arrays.asList(1));//第一行
        for (int i = 2; i <= numRows; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(1);
            int index = result.size() - 1;//上一行的数字
            for (int j = 1; j < i - 1; j++) {
                list.add(result.get(index).get(j - 1) + result.get(index).get(j));//因为
            }
            list.add(1);
            result.add(list);
        }
        return result;
    }
}

力扣官方题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for (int i = 0; i < numRows; ++i) {
            List<Integer> row = new ArrayList<Integer>();
            for (int j = 0; j <= i; ++j) {
                if (j == 0 || j == i) {
                    row.add(1);
                } else {
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
        return ret;
    }
}

时间复杂度：O(numRows*numRows)

空间复杂度：O(1)

展开全文 >>

小鹤双拼输入法配置

小鹤双拼方案。
首先打开注册表，找到这个路径

1
计算机计算机\HKEY_CURRENT_USER\Software\Microsoft\InputMethod\Settings\CHS

然后新建一个名为 UserDefinedDoublePinyinScheme0的字符串值，数值数据为

1
小鹤双拼*2*^*iuvdjhcwfg^xmlnpbksqszxkrltvyovt

然后打开控制面板，找到微软拼音的配置页面，把新出现的小鹤双拼设置为默认值。
直接修改注册表的最大意义在于，不需要自己一个个去定义按键和音节的对应关系了。

这样配置之后输入时显示的内容仍然是全拼的字母，为了显示真正的双拼字符，需要在微软拼音输入法中——>常规——>取消自动扩展到全拼的设置

参考文献

作者：在花

链接：https://www.jianshu.com/p/02c4cf1e5225

来源：简书

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

单词接龙

127. 单词接龙

难度: 困难

字典 wordList 中从单词 beginWord 和 endWord 的 转换序列 是一个按下述规格形成的序列：

  • 序列中第一个单词是 beginWord 。
  • 序列中最后一个单词是 endWord 。
  • 每次转换只能改变一个字母。
  • 转换过程中的中间单词必须是字典 wordList 中的单词。

给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的 最短转换序列 中的 单词数目 。如果不存在这样的转换序列，返回 0。

示例 1：

1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5
解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

示例 2：

1
2
3
输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0
解释：endWord "cog" 不在字典中，所以无法进行转换。

提示：

  • 1 <= beginWord.length <= 10
  • endWord.length == beginWord.length
  • 1 <= wordList.length <= 5000
  • wordList[i].length == beginWord.length
  • beginWord、endWord 和 wordList[i] 由小写英文字母组成
  • beginWord != endWord
  • wordList 中的所有字符串 互不相同

方法一：广度优先搜索+优化建图

利用map维护一个链表，每个链表中对应当前元素的转移状态

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
class Solution {
    Map<String, Integer> wordId = new HashMap<String, Integer>();
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {//如果当前列表中没有结尾的元素，则不能完成接龙
            return 0;
        }
        int[] dis = new int[nodeNum];
        Arrays.fill(dis, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord), endId = wordId.get(endWord);
        dis[beginId] = 0;

        Queue<Integer> que = new LinkedList<Integer>();
        que.offer(beginId);//将开始节点的index加入队列
        while (!que.isEmpty()) {
            int x = que.poll();//拿出队列头部的节点的index
            if (x == endId) {//如果当前的元素是结束的那个元素
                return dis[endId] / 2 + 1;//由于添加了虚拟节点（也就是开始节点可达的几个节点）最短路径扩大了两倍，真正的最短路径需要除以2，此外没有统计开始的那个节点，所以要加上开始的那个。
            }
            for (int it : edge.get(x)) {//对于每个虚拟节点
                if (dis[it] == Integer.MAX_VALUE) {//设置从开始节点到虚拟节点的距离为1
                    dis[it] = dis[x] + 1;
                    que.offer(it);//将虚拟节点加入到队列中去
                }
            }
        }
        return 0;
    }

    public void addEdge(String word) {
        addWord(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {//设置每个位置都是*的虚拟节点列表，并设置双向可达边
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
}

方法二：双向广度优先搜索

如果使用两个同时进行的广搜可以有效地减少搜索空间。一边从 beginWord 开始，另一边从 endWord 开始。我们每次从两边各扩展一层节点，当发现某一时刻两边都访问过同一顶点时就停止搜索。这就是双向广度优先搜索，它可以可观地减少搜索空间大小，从而提高代码运行效率。

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
class Solution {
    Map<String, Integer> wordId = new HashMap<String, Integer>();
    List<List<Integer>> edge = new ArrayList<List<Integer>>();
    int nodeNum = 0;

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        for (String word : wordList) {
            addEdge(word);
        }
        addEdge(beginWord);
        if (!wordId.containsKey(endWord)) {
            return 0;
        }

        int[] disBegin = new int[nodeNum];
        Arrays.fill(disBegin, Integer.MAX_VALUE);
        int beginId = wordId.get(beginWord);
        disBegin[beginId] = 0;
        Queue<Integer> queBegin = new LinkedList<Integer>();
        queBegin.offer(beginId);
        
        int[] disEnd = new int[nodeNum];
        Arrays.fill(disEnd, Integer.MAX_VALUE);
        int endId = wordId.get(endWord);
        disEnd[endId] = 0;
        Queue<Integer> queEnd = new LinkedList<Integer>();
        queEnd.offer(endId);

        while (!queBegin.isEmpty() && !queEnd.isEmpty()) {
            int queBeginSize = queBegin.size();
            for (int i = 0; i < queBeginSize; ++i) {
                int nodeBegin = queBegin.poll();
                if (disEnd[nodeBegin] != Integer.MAX_VALUE) {
                    return (disBegin[nodeBegin] + disEnd[nodeBegin]) / 2 + 1;
                }
                for (int it : edge.get(nodeBegin)) {
                    if (disBegin[it] == Integer.MAX_VALUE) {
                        disBegin[it] = disBegin[nodeBegin] + 1;
                        queBegin.offer(it);
                    }
                }
            }

            int queEndSize = queEnd.size();
            for (int i = 0; i < queEndSize; ++i) {
                int nodeEnd = queEnd.poll();
                if (disBegin[nodeEnd] != Integer.MAX_VALUE) {
                    return (disBegin[nodeEnd] + disEnd[nodeEnd]) / 2 + 1;
                }
                for (int it : edge.get(nodeEnd)) {
                    if (disEnd[it] == Integer.MAX_VALUE) {
                        disEnd[it] = disEnd[nodeEnd] + 1;
                        queEnd.offer(it);
                    }
                }
            }
        }
        return 0;
    }

    public void addEdge(String word) {
        addWord(word);
        int id1 = wordId.get(word);
        char[] array = word.toCharArray();
        int length = array.length;
        for (int i = 0; i < length; ++i) {
            char tmp = array[i];
            array[i] = '*';
            String newWord = new String(array);
            addWord(newWord);
            int id2 = wordId.get(newWord);
            edge.get(id1).add(id2);
            edge.get(id2).add(id1);
            array[i] = tmp;
        }
    }

    public void addWord(String word) {
        if (!wordId.containsKey(word)) {
            wordId.put(word, nodeNum++);
            edge.add(new ArrayList<Integer>());
        }
    }
}



参考文献

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/word-ladder/solution/dan-ci-jie-long-by-leetcode-solution/

来源：力扣（LeetCode）

著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

路径总和2 

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
给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

示例:
给定如下二叉树，以及目标和 sum = 22，

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1
返回:

[
   [5,4,11,2],
   [5,8,4,5]
]
通过次数104,602提交次数170,873

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        deep(root, new ArrayList<>(), 0, sum);
        return result;
    }
    public void deep(TreeNode root, List<Integer> list, int sum, int target) {
        if (root != null) {
            sum += root.val;
            list.add(root.val);
            if (root.left == null && root.right == null) {//叶子节点
                if (sum == target) {//满足条件
                    result.add(new ArrayList<>(list));
                }
            }
            deep(root.left, list, sum, target);
            deep(root.right, list, sum, target);
            list.remove(list.size() - 1);//移除当前元素
            
        }

    }
}

力扣官方深度优先

时间复杂度O(N*N)

空间复杂度O(N)

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 {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Deque<Integer> path = new LinkedList<Integer>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        dfs(root, sum);
        return ret;
    }

    public void dfs(TreeNode root, int sum) {
        if (root == null) {
            return;
        }
        path.offerLast(root.val);
        sum -= root.val;
        if (root.left == null && root.right == null && sum == 0) {
            ret.add(new LinkedList<Integer>(path));
        }
        dfs(root.left, sum);
        dfs(root.right, sum);
        path.pollLast();
    }
}

力扣官方广度优先

时间复杂度O(N*N)

空间复杂度O(N)

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
class Solution {
    List<List<Integer>> ret = new LinkedList<List<Integer>>();
    Map<TreeNode, TreeNode> map = new HashMap<TreeNode, TreeNode>();

    public List<List<Integer>> pathSum(TreeNode root, int sum) {
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queueNode = new LinkedList<TreeNode>();
        Queue<Integer> queueSum = new LinkedList<Integer>();
        queueNode.offer(root);
        queueSum.offer(0);

        while (!queueNode.isEmpty()) {
            TreeNode node = queueNode.poll();
            int rec = queueSum.poll() + node.val;

            if (node.left == null && node.right == null) {
                if (rec == sum) {
                    getPath(node);
                }
            } else {
                if (node.left != null) {
                    map.put(node.left, node);
                    queueNode.offer(node.left);
                    queueSum.offer(rec);
                }
                if (node.right != null) {
                    map.put(node.right, node);
                    queueNode.offer(node.right);
                    queueSum.offer(rec);
                }
            }
        }

        return ret;
    }

    public void getPath(TreeNode node) {
        List<Integer> temp = new LinkedList<Integer>();
        while (node != null) {
            temp.add(node.val);
            node = map.get(node);
        }
        Collections.reverse(temp);
        ret.add(new LinkedList<Integer>(temp));
    }
}


参考文献

作者：LeetCode-Solution

链接：https://leetcode-cn.com/problems/path-sum-ii/solution/lu-jing-zong-he-ii-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
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7
返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]
通过次数223,974提交次数351,300

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-tree-level-order-traversal
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        ArrayDeque<TreeNode> queue = new ArrayDeque<>();
        List<List<Integer>> result = new ArrayList<>();

        if (root != null) {//如果树为空，直接返回空
            queue.add(root);
        } else {
            return result;
        }

        while (!queue.isEmpty()) {//队列中如果还有元素
            List<Integer> list = new ArrayList<>();

            int size = queue.size();//这一层的节点的数量
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                list.add(node.val);
                if (node.left != null) {//将左子树的节点加入到队列尾部
                    queue.add(node.left);
                }
                if (node.right != null) {//将右子树的节点加入到队列尾部
                    queue.add(node.right);
                }
            }
            result.add(list);//本层的节点遍历完毕，加入到结果集
        }
        return result;
    }
}

展开全文 >>

子集2 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。

说明：解集不能包含重复的子集。

示例:

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

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

利用回溯去重

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
class Solution {
    private List<List<Integer>> result = new ArrayList<>();
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);//排序为了去重
        List<Integer> list = new ArrayList<>();

        for (int i = 2; i < nums.length; i++) {
            backtrack(nums, list, 0, i);
        }
        for (int i = 0; i < nums.length; i++) {//添加单个元素
            if (!result.contains(Arrays.asList(nums[i]))) {
                result.add(Arrays.asList(nums[i]));
            }
        }
        
        List<Integer> list1 = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {//添加所有元素
            list1.add(nums[i]);
        }

        if(!result.contains(list1)){
            result.add(list1);
        }

        result.add(Arrays.asList());//添加空元素
        return result;
    }
    
    /**
     * 从数组nums中选取n个数字
     * @param nums 带选取的数组
     * @param tmpList 当前选取的数字集合
     * @param start 当前遍历的开始位置
     * @param n 要选取的数字的数量
     */
    public void backtrack(int[] nums, List<Integer> tmpList, int start, int n) {
        if (tmpList.size() == n) {
            if (!result.contains(tmpList)) {
                result.add(new ArrayList<>(tmpList));
            }
            return;
        }
        for (int i = start; i < nums.length; i++) {
            tmpList.add(nums[i]);
            backtrack(nums, tmpList, i + 1, n);
            tmpList.remove(tmpList.size() - 1);
        }
    }
}

回溯的精简写法

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 {
    List<List<Integer>> ans;
    List<Integer> tmp;

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        ans = new ArrayList<>();
        tmp = new ArrayList<>();
        int l = nums.length;
        if (l == 0) return ans;
        Arrays.sort(nums);
        dfs(0, nums);
        return ans;
    }
    private void dfs(int i, int[] nums) {
        ans.add(new ArrayList<>(tmp));
        for (int j = i; j < nums.length; j++) {
            if (j > i && nums[j] == nums[j-1]) continue;
            tmp.add(nums[j]);
            dfs(j+1, nums);
            tmp.remove(tmp.size()-1);
        }
    }
}

参考文献

IRVLIN的题解

展开全文 >>

任务调度器 

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
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表。其中每个字母表示一种不同种类的任务。任务可以以任意顺序执行，并且每个任务都可以在 1 个单位时间内执行完。在任何一个单位时间，CPU 可以完成一个任务，或者处于待命状态。

然而，两个 相同种类 的任务之间必须有长度为整数 n 的冷却时间，因此至少有连续 n 个单位时间内 CPU 在执行不同的任务，或者在待命状态。

你需要计算完成所有任务所需要的 最短时间 。

 

示例 1：

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8
解释：A -> B -> (待命) -> A -> B -> (待命) -> A -> B
     在本示例中，两个相同类型任务之间必须间隔长度为 n = 2 的冷却时间，而执行一个任务只需要一个单位时间，所以中间出现了（待命）状态。 

示例 2：

输入：tasks = ["A","A","A","B","B","B"], n = 0
输出：6
解释：在这种情况下，任何大小为 6 的排列都可以满足要求，因为 n = 0
["A","A","A","B","B","B"]
["A","B","A","B","A","B"]
["B","B","B","A","A","A"]
...
诸如此类
示例 3：

输入：tasks = ["A","A","A","A","A","A","B","C","D","E","F","G"], n = 2
输出：16
解释：一种可能的解决方案是：
     A -> B -> C -> A -> D -> E -> A -> F -> G -> A -> (待命) -> (待命) -> A -> (待命) -> (待命) -> A
 

提示：

1 <= task.length <= 104
tasks[i] 是大写英文字母
n 的取值范围为 [0, 100]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/task-scheduler
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public int leastInterval(char[] tasks, int n) {
        if (n == 0) {
            return tasks.length;
        }

        int hashTable[] = new int[26];
        for (int i = 0; i < tasks.length; i++) {//哈希表统计每个数字的数量
            hashTable[tasks[i] - 'A']++;
        }
        //利用最大堆维护数量最多的任务
        PriorityQueue<Character> queue = new PriorityQueue<Character>(new Comparator<Character>() {
            public int compare(Character letter1, Character letter2) {
                return hashTable[letter2 - 'A'] - hashTable[letter1 - 'A'];
            }
        });
        for (char c = 'A'; c <= 'Z'; c++) {
            if (hashTable[c - 'A'] > 0) {
                queue.offer(c);
            }
        }
        int count = 0;//每一轮中调度的任务的数量
        int lastQueueSize = 0;//最后一轮调度的任务的数量
        while (queue.size() > 0) {
            char[] letters = new char[queue.size()];
            int index = 0;//统计每一轮中有几个任务被调度
            count++;
            while (!queue.isEmpty()) {
                letters[index] = queue.poll();
                hashTable[letters[index] - 'A']--;
                index++;
                if (index > n) {//如果大于最小间隔，返回继续调度旧任务
                    break;
                }
            }
            lastQueueSize = index;

            for (int i = 0; i < index; i++) {//维护最大堆
                int idx = letters[i] - 'A';
                if (hashTable[idx] > 0) {
                    queue.offer(letters[i]);
                }
            }
        }
        count = (n + 1) * count - (n + 1 - lastQueueSize);//统计所有调度消耗的时间（每一轮（满足最小间隔的）*最小间隔所消耗的时间-最后一轮多加的消耗时间）
        return count;
    }
}

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
class Solution {
    /**
     * 解题思路：
     * 1、将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
     * 2、对数组进行排序，优先排列个数（count）最大的任务，
     *      如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
     * 3、再排序下一个任务，如果下一个任务B个数和最大任务数一致，
     *      则retCount++ ==> A->B->X->A->B->X->A->B
     * 4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，在这种情况下就是任务的总数是最小所需时间
     *
     * @param tasks
     * @param n
     * @return
     */
    public int leastInterval(char[] tasks, int n) {
        if (tasks.length <= 1 || n < 1) return tasks.length;
        //步骤1
        int[] counts = new int[26];
        for (int i = 0; i < tasks.length; i++) {//哈希表计数
            counts[tasks[i] - 'A']++;
        }
        //步骤2
        Arrays.sort(counts);//按照任务数量进行排序
        int maxCount = counts[25];
        int retCount = (maxCount - 1) * (n + 1) + 1;
        int i = 24;
        //步骤3
        while (i >= 0 && counts[i] == maxCount) {
            retCount++;
            i--;
        }
        //步骤4
        return Math.max(retCount, tasks.length);
    }

}


参考文献
最好的安排的题解

展开全文 >>

全排列2 

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
给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

示例 2：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

 

提示：

    1 <= nums.length <= 8
    -10 <= nums[i] <= 10

通过次数123,743
提交次数198,637

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

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
class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<Integer> list = new ArrayList<>();

        for (int val : nums) {
            list.add(val);
        }

        backtrack(nums.length, list, 0);
        return result;
    }

    private List<List<Integer>> result = new ArrayList<>();
    public void backtrack(int n, List<Integer> tmpList, int start) {
        if (start == n) {
            if (!result.contains(tmpList)) {//去重
                result.add(new ArrayList<>(tmpList));
            }
            return;
        }
        for (int i = start; i < n; i++) {
            Collections.swap(tmpList, start, i);//交换元素
            backtrack(n, tmpList, start + 1);
            Collections.swap(tmpList, start, i);//换回来

        }
    }
}

要解决重复问题，我们只要设定一个规则，保证在填第 idx 个数的时候重复数字只会被填入一次即可。而在本题解中，我们选择对原数组排序，保证相同的数字都相邻，然后每次填入的数一定是这个数所在重复数集合中「从左往右第一个未被填过的数字」

1
2
3
if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
     continue;
 }
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
class Solution {
    boolean[] vis;

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> ans = new ArrayList<List<Integer>>();
        List<Integer> perm = new ArrayList<Integer>();
        vis = new boolean[nums.length];
        Arrays.sort(nums);
        backtrack(nums, ans, 0, perm);
        return ans;
    }

    public void backtrack(int[] nums, List<List<Integer>> ans, int idx, List<Integer> perm) {
        if (idx == nums.length) {
            ans.add(new ArrayList<Integer>(perm));
            return;
        }
        for (int i = 0; i < nums.length; ++i) {
            if (vis[i] || (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1])) {
                continue;
            }
            perm.add(nums[i]);
            vis[i] = true;
            backtrack(nums, ans, idx + 1, perm);
            vis[i] = false;
            perm.remove(idx);
        }
    }
}


参考文献

作者：LeetCode-Solution

展开全文 >>

全排列 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

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

通过次数225,202
提交次数291,591

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

回溯+去重

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 {
    public List<List<Integer>> permute(int[] nums) {
        arrange(nums, new ArrayList<>(), 0);
        return resultList;
    }
    private List<List<Integer>> resultList = new ArrayList<>();
    public void arrange(int[] nums, List<Integer> tmpList, int start) {
        if (tmpList.size() == nums.length) {
            resultList.add(new ArrayList<>(tmpList));
            return;
        }
        for (int i = start; i < start + nums.length; i++) {
            int index = i % nums.length;//循环
            if (tmpList.contains(nums[index])) {
                continue;
            }
            tmpList.add(nums[index]);
            arrange(nums, tmpList, index + 1);
            tmpList.remove(tmpList.size() - 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

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);//把已经加入的元素放到数组的左边，把没有加入的元素放到数组的右边
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);//即再换回来
        }
    }
}

时间复杂度为 O(n∗n!)

空间复杂度O(n)

展开全文 >>

分割数组为连续子序列 

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
给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个子序列，其中每个子序列都由连续整数组成且长度至少为 3 。

如果可以完成上述分割，则返回 true ；否则，返回 false 。

 

示例 1：

输入: [1,2,3,3,4,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3
3, 4, 5

 

示例 2：

输入: [1,2,3,3,4,4,5,5]
输出: True
解释:
你可以分割出这样两个连续子序列 : 
1, 2, 3, 4, 5
3, 4, 5

 

示例 3：

输入: [1,2,3,4,4,5]
输出: False

 

提示：

    输入的数组长度范围为 [1, 10000]

 

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

哈希表+贪心算法

哈希表统计每个数字的数量和以某个数字为结尾的序列的数量，
贪心序列中数字的数量，应越大越好（因为剩余的一个数字新建一个序列的失败可能性更大）

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 {
    public boolean isPossible(int[] nums) {
        
        Map<Integer, Integer> countMap = new HashMap<Integer, Integer>();//某个数字剩余的数量
        Map<Integer, Integer> endMap = new HashMap<Integer, Integer>();//以某个数字为结尾的序列的数量
        for (int x : nums) {//利用哈希表统计每个数字的数量
            int count = countMap.getOrDefault(x, 0) + 1;
            countMap.put(x, count);
        }
        for (int x : nums) {
            int count = countMap.getOrDefault(x, 0);
            if (count > 0) {//如果一个数字还没被用完
                int prevEndCount = endMap.getOrDefault(x - 1, 0);//查看以它前面的元素结尾的序列是否存在
                if (prevEndCount > 0) {//如果以它前面那个元素结尾的序列存在
                    countMap.put(x, count - 1);//将这个元素的数量减去1
                    endMap.put(x - 1, prevEndCount - 1);//以前面为结尾的序列的数量减去1
                    endMap.put(x, endMap.getOrDefault(x, 0) + 1);//以x为结尾的序列的数量加1
                } else {//如果以它前面的那个元素为结尾的序列不存在，那么这个元素是新序列的第一个元素，要想凑够3个元素
                    int count1 = countMap.getOrDefault(x + 1, 0);//后面的第一个元素的数量应该大于0
                    int count2 = countMap.getOrDefault(x + 2, 0);//后面的第二个元素的数量应该大于0
                    if (count1 > 0 && count2 > 0) {//如果后面的两个元素的数量都大于0，那么可以凑成
                        countMap.put(x, count - 1);
                        countMap.put(x + 1, count1 - 1);
                        countMap.put(x + 2, count2 - 1);
                        endMap.put(x + 2, endMap.getOrDefault(x + 2, 0) + 1);
                    } else {//后面的两个元素中有不大于0的，那么无法满足条件
                        return false;
                    }
                }
            }
        }
        return true;
    }
}

参考文献

官方题解

展开全文 >>

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