栈与队列

232. 用栈实现队列

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）：

实现 MyQueue 类：

  • void push(int x) 将元素 x 推到队列的末尾
  • int pop() 从队列的开头移除并返回元素
  • int peek() 返回队列开头的元素
  • boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明：

  • 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
  • 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。

示例 1：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyQueue", "push", "push", "peek", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]

解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：

  • 1 <= x <= 9
  • 最多调用 100 次 push、pop、peek 和 empty
  • 假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

进阶：

  • 你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 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
class MyQueue {

    Stack<Integer> stackIn;
    Stack<Integer> stackOut;

    public MyQueue() {
        stackIn = new Stack<>(); // 负责进栈
        stackOut = new Stack<>(); // 负责出栈
    }
    //将一个元素放入队列的尾部
    public void push(int x) {
        stackIn.push(x);
    }
    //从队列首部移除元素
    public int pop() {
        dumpstackIn();
        return stackOut.pop();
    }
    //返回队列首部的元素
    public int peek() {
        dumpstackIn();
        return stackOut.peek();
    }
    //判断队列是否为空
    public boolean empty() {
        return stackIn.isEmpty() && stackOut.isEmpty();
    }
    // 如果stackOut为空，那么将stackIn中的元素全部放到stackOut中
    private void dumpstackIn(){
        if (!stackOut.isEmpty()) return; 
        while (!stackIn.isEmpty()){
                stackOut.push(stackIn.pop());
        }
    }
}

/**
 * Your MyQueue object will be instantiated and called as such:
 * MyQueue obj = new MyQueue();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.peek();
 * boolean param_4 = obj.empty();
 */

225. 用队列实现栈

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

  • void push(int x) 将元素 x 压入栈顶。
  • int pop() 移除并返回栈顶元素。
  • int top() 返回栈顶元素。
  • boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

  • 你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
  • 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：

1
2
3
4
5
6
7
8
9
10
11
12
13
输入：
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

提示：

  • 1 <= x <= 9
  • 最多调用100 次 push、pop、top 和 empty
  • 每次调用 pop 和 top 都保证栈不为空

进阶：你能否仅用一个队列来实现栈。

解题

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 MyStack {

    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList<>();
    }

    //每 offer 一个数（A）进来，都重新排列，把这个数（A）放到队列的队首
    public void push(int x) {
        queue.offer(x);
        int size = queue.size();
        //移动除了 A 的其它数
        while (size-- > 1)
            queue.offer(queue.poll());
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

20. 有效的括号

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。
  3. 每个右括号都有一个对应的相同类型的左括号。

示例 1：

1
2
输入：s = "()"
输出：true

示例 2：

1
2
输入：s = "()[]{}"
输出：true

示例 3：

1
2
输入：s = "(]"
输出：false

提示：

  • 1 <= s.length <= 10^4
  • s 仅由括号 '()[]{}' 组成

解题

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 boolean isValid(String s) {
        if (s.length() % 2 != 0) {
            return false;
        }

        Stack<Character> stack = new Stack<Character>();

        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '{') {
                stack.push('}');
            } else if (c == '[') {
                stack.push(']');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }

        return stack.isEmpty();
    }
}

1047. 删除字符串中的所有相邻重复项

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：

1
2
3
4
输入："abbaca"
输出："ca"
解释：
例如，在 "abbaca" 中，我们可以删除 "bb" 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 "aaca"，其中又只有 "aa" 可以执行重复项删除操作，所以最后的字符串为 "ca"。

提示：

  1. 1 <= S.length <= 20000
  2. S 仅由小写英文字母组成。

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public String removeDuplicates(String s) {
        Stack<Character> stack = new Stack<>();
        char c;
        for (int i = 0; i < s.length(); i++) {
            c = s.charAt(i);
            if( stack.isEmpty() || stack.peek() != c ){
                stack.push(c);
            }else {
                stack.pop();
            }
        }
        String ans = "";
        while(!stack.isEmpty()){
            ans = stack.pop() + ans;
        }
        return ans;
    }
}

150. 逆波兰表达式求值

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

  • 有效的算符为 '+'、'-'、'*' 和 '/' 。
  • 每个操作数（运算对象）都可以是一个整数或者另一个表达式。
  • 两个整数之间的除法总是 向零截断 。
  • 表达式中不含除零运算。
  • 输入是一个根据逆波兰表示法表示的算术表达式。
  • 答案及所有中间计算结果可以用 32 位 整数表示。

示例 1：

1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

示例 2：

1
2
3
输入：tokens = ["4","13","5","/","+"]
输出：6
解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

示例 3：

1
2
3
4
5
6
7
8
9
10
输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22
解释：该算式转化为常见的中缀算术表达式为：
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

提示：

  • 1 <= tokens.length <= 10^4
  • tokens[i] 是一个算符（"+"、"-"、"*" 或 "/"），或是在范围 [-200, 200] 内的一个整数

逆波兰表达式：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

  • 平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) * ( 3 + 4 ) 。
  • 该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) * ) 。

逆波兰表达式主要有以下两个优点：

  • 去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + * 也可以依据次序计算出正确结果。
  • 适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

解题

拓展：中缀表达式转后缀表达式

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 evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();
        for (String token : tokens) {
            if("+".equals(token)){
                stack.push(stack.pop() + stack.pop());
            }else if("-".equals(token)){
                stack.push(- stack.pop() + stack.pop());
            }else if("*".equals(token)){
                stack.push(stack.pop() * stack.pop());
            }else if("/".equals(token)){
                int temp1 = stack.pop();    //后者
                int temp2 = stack.pop();    //前者
                stack.push(temp2 / temp1);
            }else {
                stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }
}

回溯算法

77. 组合

给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。

你可以按 任何顺序 返回答案。

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

示例 2：

1
2
输入：n = 1, k = 1
输出：[[1]]

提示：

  • 1 <= n <= 20
  • 1 <= k <= n

解题

path.size() ： 已经找的个数
k-path.size() ：还需找的个数
【x, n】的数组长度起码应该是k-path.size()才有继续搜索的可能， 那么就有 n-x+1 = k-path.size() ， 解方程得 x = n+1 - (k-path.size()), 而且这个x是可以作为起点往下搜的 也就是for(i = s; i<=x; i++) 这里的x是可以取到的

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

    List<List<Integer>> list = new  ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtracking(n,k,1);
        return list;
    }

    public void backtracking(int n ,int k,int startIndex){
        if(path.size()==k){
            list.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i = startIndex;i<=n-(k-path.size())+1;i++){
            path.add(i);
            backtracking(n,k,i+1);
            path.remove(path.size()-1);
        }
    }
}

216. 组合总和 III

找出所有相加之和为 n 的 k 个数的组合，且满足下列条件：

  • 只使用数字1到9
  • 每个数字 最多使用一次

返回 所有可能的有效组合的列表 。该列表不能包含相同的组合两次，组合可以以任何顺序返回。

示例 1:

1
2
3
4
5
输入: k = 3, n = 7
输出: [[1,2,4]]
解释:
1 + 2 + 4 = 7
没有其他符合的组合了。

示例 2:

1
2
3
4
5
6
7
输入: k = 3, n = 9
输出: [[1,2,6], [1,3,5], [2,3,4]]
解释:
1 + 2 + 6 = 9
1 + 3 + 5 = 9
2 + 3 + 4 = 9
没有其他符合的组合了。

示例 3:

1
2
3
4
输入: k = 4, n = 1
输出: []
解释: 不存在有效的组合。
在[1,9]范围内使用4个不同的数字，我们可以得到的最小和是1+2+3+4 = 10，因为10 > 1，没有有效的组合。

提示:

  • 2 <= k <= 9
  • 1 <= n <= 60

解题

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 {

    List<List<Integer>> list = new ArrayList<>();
    List<Integer> path =new ArrayList<>();

    public List<List<Integer>> combinationSum3(int k, int n) {
        backtracking(k,n,1,0);
        return list;
    }

    void backtracking(int k,int n,int startIndex,int sum){
        if (sum > n) { // 剪枝操作
            return; // 如果path.size() == k 但sum != targetSum 直接返回
        }
        if(path.size()==k){
            if(sum==n)  list.add(new ArrayList<Integer>(path));
            return;
        }
        for(int i = startIndex;i<=9-(k-path.size())+1;i++){
            sum+=i;
            path.add(i);
            backtracking(k,n,i+1,sum);
            path.remove(path.size()-1);
            sum-=i;
        }

    }
}

17. 电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

示例 1：

1
2
输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

示例 2：

1
2
输入：digits = ""
输出：[]

示例 3：

1
2
输入：digits = "2"
输出：["a","b","c"]

提示：

  • 0 <= digits.length <= 4
  • digits[i] 是范围 ['2', '9'] 的一个数字。

解题

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 {
    String[] strings ={"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
	
	List<String> list = new ArrayList<>();
	
	public List<String> letterCombinations(String digits) {
		if(digits==null||digits.length()==0) return list;
		StringBuffer sb =new StringBuffer();
		backtracking(sb, digits);
        return list;
        
    }
	public void backtracking(StringBuffer sb,String digits) {
		if(sb.length()==digits.length()) {
			list.add(sb.toString());
			return;
		}
		int current = digits.charAt(sb.length())-'0';
		String curString= strings[current];
		for(char i :curString.toCharArray()) {
			sb.append(i);
			backtracking(sb, digits);
			sb.deleteCharAt(sb.length()-1);
		}
	}
}

39. 组合总和

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

candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。

对于给定的输入，保证和为 target 的不同组合数少于 150 个。

示例 1：

1
2
3
4
5
6
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。

示例 2：

1
2
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

示例 3：

1
2
输入: candidates = [2], target = 1
输出: []

提示：

  • 1 <= candidates.length <= 30
  • 2 <= candidates[i] <= 40
  • candidates 的所有元素 互不相同
  • 1 <= target <= 40

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> list = new ArrayList<>();
	
	List<Integer> path = new ArrayList<>();

	public List<List<Integer>> combinationSum(int[] candidates, int target) {
		backtracking(target, candidates, 0);
		return list;
    }
    public void backtracking(int target,int[] candidates,int start){
    	if(target<0) return;
    	if(target==0) {
    		list.add(new ArrayList<>(path));
    		return;
    	}
        for(int i = start;i<candidates.length;i++) {
        	path.add(candidates[i]);
        	backtracking(target-candidates[i], candidates, i);
        	path.remove(path.size()-1);
        }
    }
}

40. 组合总和 II

给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。

candidates 中的每个数字在每个组合中只能使用 一次 。

注意：解集不能包含重复的组合。

示例 1:

1
2
3
4
5
6
7
8
输入: candidates = [10,1,2,7,6,1,5], target = 8,
输出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例 2:

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

提示:

  • 1 <= candidates.length <= 100
  • 1 <= candidates[i] <= 50
  • 1 <= target <= 30

解题

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 {

    List<List<Integer>> list=new ArrayList<>();
    List<Integer> path=new ArrayList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        boolean[] used =new boolean[candidates.length];
        Arrays.sort(candidates);
        backtracking(0,target,candidates,0,used);
        return list;
    }
    public void backtracking(int sum,int target,int[] candidates,int start,boolean[] used){
        if(sum>target) return;
        if(sum==target){
            list.add(new ArrayList<>(path));
            return;
        }
        for(int i =start;i<candidates.length;i++){
            if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
                continue;
            }
            path.add(candidates[i]);
            used[i]=true;
            backtracking(sum+candidates[i],target,candidates,i+1,used);
            used[i]=false;
            path.remove(path.size()-1);
        }
    }
}

131. 分割回文串

给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。

回文串 是正着读和反着读都一样的字符串。

示例 1：

1
2
输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

示例 2：

1
2
输入：s = "a"
输出：[["a"]]

提示：

  • 1 <= s.length <= 16
  • 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
class Solution {

    List<List<String>> lists = new ArrayList<>();
    List<String> path = new ArrayList<>();

    public List<List<String>> partition(String s) {
        backTracking(s,0);
        return lists;
    }
    private void backTracking(String s, int startIndex) {
        //如果起始位置大于s的大小，说明找到了一组分割方案
        if (startIndex >= s.length()) {
            lists.add(new ArrayList(path));
            return;
        }
        for (int i = startIndex; i < s.length(); i++) {
            //如果是回文子串，则记录
            if (isPalindrome(s, startIndex, i)) {
                String str = s.substring(startIndex, i + 1);
                path.add(str);
            } else {
                continue;
            }
            //起始位置后移，保证不重复
            backTracking(s, i + 1);
            path.remove(path.size()-1);
        }
    }
    //判断是否是回文串
    private boolean isPalindrome(String s, int startIndex, int end) {
        for (int i = startIndex, j = end; i < j; i++, j--) {
            if (s.charAt(i) != s.charAt(j)) {
                return false;
            }
        }
        return true;
    }
}

93. 复原 IP 地址

有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。

  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。

给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。

示例 1：

1
2
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]

示例 2：

1
2
输入：s = "0000"
输出：["0.0.0.0"]

示例 3：

1
2
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

提示：

  • 1 <= s.length <= 20
  • 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
class Solution {

    List<String> list = new ArrayList<>();
    public List<String> restoreIpAddresses(String s) {
        backTracking(0,s,0);
        return list;
    }
    public void backTracking(int start,String s,int point){
        if(point==3){
            if (isValid(s,start,s.length()-1)) {
                list.add(s);
            }
            return;
        }
        for(int i=start;i<s.length();i++){

            if (isValid(s, start, i)) {
                s = s.substring(0, i + 1) + "." + s.substring(i + 1);
                point++;
                backTracking(i + 2,s,point);
                point--;
                s = s.substring(0, i + 1) + s.substring(i + 2);
            } else {
                break;
            }
        }
    }
    private Boolean isValid(String s, int start, int end) {
        if (start > end) {
            return false;
        }
        if (s.charAt(start) == '0' && start != end) { // 0开头的数字不合法
            return false;
        }
        int num = 0;
        for (int i = start; i <= end; i++) {
            if (s.charAt(i) > '9' || s.charAt(i) < '0') { // 遇到⾮数字字符不合法
                return false;
            }
            num = num * 10 + (s.charAt(i) - '0');
            if (num > 255) { // 如果⼤于255了不合法
                return false;
            }
        }
        return true;
    }
}

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 10
  • nums 中的所有元素 互不相同

解题

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

    List<List<Integer>> list =new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsets(int[] nums) {
        backtracking(nums,0);
        return list;
    }
    public void backtracking(int[] nums,int start){
        list.add(new ArrayList(path));
        if(start>=nums.length){
            return;
        }
        for(int i=start;i<nums.length;i++){
            path.add(nums[i]);
            backtracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

示例 1：

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

示例 2：

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

提示：

  • 1 <= nums.length <= 10
  • -10 <= nums[i] <= 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
class Solution {

    List<List<Integer>> list =new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> subsetsWithDup(int[] nums) {
        boolean [] used = new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(nums,0,used);
        return list;
    }
    public void backtracking(int[] nums,int start,boolean[] used){
        list.add(new ArrayList(path));
        if(start>=nums.length){
            return;
        }
        for(int i=start;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;
            used[i]=true;
            path.add(nums[i]);
            
            backtracking(nums,i+1,used);
            used[i]=false;
            path.remove(path.size()-1);
        }
    }
}

491. 递增子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

示例 1：

1
2
输入：nums = [4,6,7,7]
输出：[[4,6],[4,6,7],[4,6,7,7],[4,7],[4,7,7],[6,7],[6,7,7],[7,7]]

示例 2：

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

提示：

  • 1 <= nums.length <= 15
  • -100 <= nums[i] <= 100

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    List<List<Integer>> list =new ArrayList<>();
    List<Integer> path = new ArrayList<>();

    public List<List<Integer>> findSubsequences(int[] nums) {
        backtracking(nums,0);
        return list;
    }
    public void backtracking(int[] nums,int start){ 
        if(path.size()>1){
            list.add(new ArrayList(path));
        }
        int[] used=new int[201];
        for(int i=start;i<nums.length;i++){
            if(!path.isEmpty()&&nums[i]<path.get(path.size()-1)||used[nums[i] + 100] == 1) continue;
            used[nums[i]+100]=1;
            path.add(nums[i]);       
            backtracking(nums,i+1);
            path.remove(path.size()-1);
        }
    }
}

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 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]]

示例 2：

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

示例 3：

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

提示：

  • 1 <= nums.length <= 6
  • -10 <= nums[i] <= 10
  • 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
class Solution {
    List<List<Integer>> list = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    

    public List<List<Integer>> permute(int[] nums) {
        boolean[] used = new boolean[nums.length];
        backtracking(nums,used);
        return list;
    }
    public void backtracking(int[] nums,boolean[] used){
        if(path.size()==nums.length){
            list.add(new ArrayList(path));
            return;
        }
        for(int i =0;i<nums.length;i++){
            if(used[i]) continue;
            used[i]=true;
            path.add(nums[i]);
            backtracking(nums,used);
            used[i]=false;
            path.remove(path.size()-1);
        }
    }
}

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

示例 1：

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

示例 2：

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

解题

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 {

    List<List<Integer>> list = new ArrayList<>();
    List<Integer> path =new ArrayList<>();

    public List<List<Integer>> permuteUnique(int[] nums) {
        boolean[] used=new boolean[nums.length];
        Arrays.sort(nums);
        backtracking(nums,used);
        return list;
    }
    public void backtracking(int[] nums,boolean[] used){
        if(path.size()==nums.length){
            list.add(new ArrayList(path));
            return;
        }
        for(int i=0;i<nums.length;i++){
            if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;
            if(used[i]==true) continue;
            used[i]=true;
            path.add(nums[i]);
            backtracking(nums,used);
            used[i]=false;
            path.remove(path.size()-1);
            
        }
    }
}

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例 1：


1
2
3
输入：n = 4
输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。

示例 2：

1
2
输入：n = 1
输出：[["Q"]]

提示：

  • 1 <= n <= 9

解题

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
class Solution {

    List<List<String>> list = new ArrayList<>();

    public List<List<String>> solveNQueens(int n) {
        char[][] chess = new char[n][n];
        for (char[] c : chess) {
            Arrays.fill(c, '.');
        }
        backtracking(n,chess,0);
        return list;
    }
    public void backtracking(int n,char[][] chess,int row){
        if(row==n){
            list.add(Array2List(chess));
            return;
        }
        for(int i=0;i<n;i++){
            if(isValid(row,i,n,chess)){
                chess[row][i]='Q';
                backtracking(n,chess,row+1);
                chess[row][i]='.';
            }
        }
    }
    public boolean isValid(int row,int col,int n,char[][] chess){
        for(int i =0;i<n;i++){
            if(chess[row][i]=='Q') return false;
            if(chess[i][col]=='Q') return false;
        }
        // 检查45度对角线
        for (int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }

        // 检查135度对角线
        for (int i=row-1, j=col+1; i>=0 && j<=n-1; i--, j++) {
            if (chess[i][j] == 'Q') {
                return false;
            }
        }
        return true;

    }
    public List Array2List(char[][] chessboard) {
        List<String> list = new ArrayList<>();

        for (char[] c : chessboard) {
            list.add(String.copyValueOf(c));
        }
        return list;
    }

    
}

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

示例 1：


1
2
3
输入：board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
输出：[["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：

提示：

  • board.length == 9
  • board[i].length == 9
  • board[i][j] 是一位数字或者 '.'
  • 题目数据 保证 输入数独仅有一个解

解题

代码有点长，我主要是将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
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 void solveSudoku(char[][] board) {
        backtracking(board);
    }

    public boolean backtracking(char[][] board){
        for(int i=0;i<board.length;i++){
            for(int j =0;j<board[0].length;j++){
                if(board[i][j]!='.') continue;
                int[] num = collectNumber(board,i,j);
                for(char k='1';k<='9';k++){
                    if(num[k-'0']!=1){
                        board[i][j]=k;
                        if(backtracking(board)) return true;
                        board[i][j]='.';
                    }

                }
                return false;
            }

        }
        return true;
    }

    public int[] collectNumber(char[][] board,int row,int col){
        int[] num =new int[10];
        for(int i=row;i<9;i++){
            char n= board[i][col];
            if(n>'0'&&n<='9') num[n-'0']=1;
        }
        for(int i=col;i<9;i++){
            char n= board[row][i];
            if(n>'0'&&n<='9') num[n-'0']=1;
        }
        int x=row;
        int y=col;
        while(--row>=0){
            char n= board[row][y];
            if(n>'0'&&n<='9') num[n-'0']=1;
        }
        while(--col>=0){
            char n= board[x][col];
            if(n>'0'&&n<='9') num[n-'0']=1;
        }
        // 9宫格里是否重复
        int startRow = (x / 3) * 3;
        int startCol = (y / 3) * 3;
        for (int i = startRow; i < startRow + 3; i++){
            for (int j = startCol; j < startCol + 3; j++){
                char n= board[i][j];
                if(n>'0'&&n<='9') num[n-'0']=1;
            }
        }
        return num;
    }
}

动态规划