力扣爆刷第94天之hot100五连刷56-60
一、78. 子集
题目链接：https://leetcode.cn/problems/subsets/description/?envType=study-plan-v2&envId=top-100-liked
思路：子集问题，本题集合元素无重，要求搜集所有子集，很简单，递归有起始索引，然后搜集所有节点。
class Solution {
List<List<Integer>> arrayList = new ArrayList<>();
List<Integer> list = new ArrayList<>();`在这里插入代码片`
public List<List<Integer>> subsets(int[] nums) {
backTracking(nums, 0);
return arrayList;
}
void backTracking(int[] nums, int index) {
arrayList.add(new ArrayList(list));
for(int i = index; i < nums.length; i++) {
list.add(nums[i]);
backTracking(nums, i+1);
list.remove(list.size()-1);
}
}
}
二、17. 电话号码的字母组合
题目链接：https://leetcode.cn/problems/letter-combinations-of-a-phone-number/description/?envType=study-plan-v2&envId=top-100-liked
思路：求的还是常规组合，递归不需要起始位置，只需要每次向下递归时更换集合即可。
class Solution {
List<String> list = new ArrayList<>();
StringBuilder bulider = new StringBuilder();
String[] source = {"", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
public List<String> letterCombinations(String digits) {
if(digits.length() == 0) return list;
backTracking(digits, 0);
return list;
}
void backTracking(String digits, int i) {
if(bulider.length() == digits.length()) {
list.add(bulider.toString());
return ;
}
String temp = source[digits.charAt(i)-'0'];
for(int j = 0; j < temp.length(); j++) {
bulider.append(temp.charAt(j));
backTracking(digits, i+1);
bulider.deleteCharAt(bulider.length()-1);
}
}
}
三、39. 组合总和
题目链接：https://leetcode.cn/problems/combination-sum/description/?envType=study-plan-v2&envId=top-100-liked
思路：集合元素无重，要求元素可复用，那么需要索引位置，又因为可复用，无需加1，然后掌握一点早停的策略。
class Solution {
List<List<Integer>> arrayList = new ArrayList<>();
List<Integer> list = new ArrayList<>();
int sum = 0;
public List<List<Integer>> combinationSum(int[] candidates, int target) {
Arrays.sort(candidates);
backTracking(candidates, target, 0);
return arrayList;
}
void backTracking(int[] candidates, int target, int index) {
if(sum == target) {
arrayList.add(new ArrayList(list));
return ;
}
for(int i = index; i < candidates.length && sum + candidates[i] <= target; i++) {
sum += candidates[i];
list.add(candidates[i]);
backTracking(candidates, target, i);
list.remove(list.size()-1);
sum -= candidates[i];
}
}
}
四、22. 括号生成
题目链接：https://leetcode.cn/problems/generate-parentheses/?envType=study-plan-v2&envId=top-100-liked
思路：本题也可以看做是多重集合问题，其他的没有难点，在收集元素时需要单独写一个判断函数，判断生成的括号是否合法。
下面这种采用栈判断括号是否合法的方式速度太慢。
class Solution {
List<String> list = new ArrayList<>();
StringBuilder builder = new StringBuilder();
char[] source = {'(', ')'};
public List<String> generateParenthesis(int n) {
backTracking(source, n);
return list;
}
void backTracking(char[] source, int n) {
if(builder.length() == n*2) {
if(builder.charAt(0) == ')' || builder.charAt(builder.length()-1) == '(') return;
String temp = builder.toString();
if(isTrue(temp)) {
list.add(temp);
}
return;
}
for(int i = 0; i < 2; i++) {
builder.append(source[i]);
backTracking(source, n);
builder.deleteCharAt(builder.length()-1);
}
}
boolean isTrue(String temp) {
Deque<Character> stack = new LinkedList<>();
for(int i = 0; i < temp.length(); i++) {
if(stack.isEmpty() && temp.charAt(i) == ')') return false;
if(!stack.isEmpty() && !stack.peek().equals(temp.charAt(i))) {
stack.poll();
continue;
}
stack.push(temp.charAt(i));
}
return stack.isEmpty();
}
}
稍微优化了一点：
class Solution {
List<String> list = new ArrayList<>();
StringBuilder builder = new StringBuilder();
char[] source = {'(', ')'};
public List<String> generateParenthesis(int n) {
backTracking(source, n);
return list;
}
void backTracking(char[] source, int n) {
if(builder.length() == n*2) {
if(builder.charAt(0) == ')' || builder.charAt(builder.length()-1) == '(') return;
String temp = builder.toString();
if(isTrue(temp)) {
list.add(temp);
}
return;
}
for(int i = 0; i < 2; i++) {
builder.append(source[i]);
backTracking(source, n);
builder.deleteCharAt(builder.length()-1);
}
}
boolean isTrue(String temp) {
int sum = 0;
for(char c : temp.toCharArray()) {
if(c == '(') {
sum++;
}else{
sum--;
}
if(sum < 0) return false;
}
return sum == 0;
}
}
五、79. 单词搜索
题目链接：https://leetcode.cn/problems/word-search/description/?envType=study-plan-v2&envId=top-100-liked
思路：类似于深度优先搜索，只不过需要加上回溯，和终止条件，别的没啥。
class Solution {
boolean flag = false;
public boolean exist(char[][] board, String word) {
for(int i = 0; i < board.length; i++) {
for(int j = 0; j < board[0].length; j++) {
if(flag) return flag;
if(board[i][j] == word.charAt(0)) {
dfs(board, i, j, word, 0);
}
}
}
return flag;
}
void dfs(char[][] board, int x, int y, String word, int i) {
if(i == word.length()) {
flag = true;
return;
}
if(x < 0 || x >= board.length || y < 0 || y >= board[0].length) return;
if(board[x][y] != word.charAt(i)) return;
board[x][y] = '0';
dfs(board, x-1, y, word, i+1);
dfs(board, x+1, y, word, i+1);
dfs(board, x, y-1, word, i+1);
dfs(board, x, y+1, word, i+1);
board[x][y] = word.charAt(i);
}
}
