栈与队列 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(); } private void dumpstackIn () { if (!stackOut.isEmpty()) return ; while (!stackIn.isEmpty()){ stackOut.push(stackIn.pop()); } } }
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 <>(); } public void push (int x) { queue.offer(x); int size = queue.size(); 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(); } }
20. 有效的括号 给定一个只包括 '('
,')'
,'{'
,'}'
,'['
,']'
的字符串 s
,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
示例 1:
示例 2:
示例 3:
提示:
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 <= S.length <= 20000
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]]
提示:
解题
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:
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,没有有效的组合。
提示:
解题
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 ; } 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:
示例 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 <= 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) { 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) { 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 ) { 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 <= 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 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 ; } for (int i=row-1 , j=col-1 ; i>=0 && j>=0 ; i--, j--) { if (chess[i][j] == 'Q' ) { return false ; } } 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-9
在每一行只能出现一次。
数字 1-9
在每一列只能出现一次。
数字 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 ; } 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; } }
动态规划