77、组合
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new LinkedList<>();
public List<List<Integer>> combine(int n, int k) {
int index = 1;
travesal(n,k,index);
return result;
}
public void travesal(int n, int k, int index){
// 终止条件，得到k个数的组合
if(temp.size() == k){
result.add(new ArrayList<>(temp));
return;
}
for (int i = index; i <= n - (k - temp.size()) + 1; i++) {
temp.add(i);
travesal(n,k,i+1);//递归
temp.remove(temp.size() - 1);//回溯
}
}
}
216、组合总和 III
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new LinkedList<Integer>();
public List<List<Integer>> combinationSum3(int k, int n) {
// 边界条件，不存在有效的组合
int sum = 0;
for(int i = 1; i <= k; i++){
sum += i;
}
if(sum > n){
return result;
}
int index = 1;
combinationSumHelper(k,n,index);
return result;
}
public void combinationSumHelper(int k, int n,int index){
if(temp.size() == k){
// 判断找出的组合是否满足相加之和为n的条件
int sum = 0;
for(Integer i : temp){
sum += i;
}
if(sum == n){
result.add(new ArrayList<>(temp));
}
return;
}
for(int i = index; i <= 9 - (k - temp.size()) + 1; i++){
temp.add(i);
combinationSumHelper(k,n,i+1);//递归
temp.remove(temp.size() - 1);//回溯
}
}
}
17、电话号码的字母组合
class Solution {
public List<String> result = new ArrayList<String>();
public StringBuffer str = new StringBuffer();
public List<String> letterCombinations(String digits) {
// 边界条件
if(digits == null || digits.length() == 0){
return result;
}
char[] digitsArr = digits.toCharArray();
// 映射关系
String[] find = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
int index = 0;
letterCombinationsHelper(digitsArr, find, index);
return result;
}
public void letterCombinationsHelper(char[] digitsArr, String[] find, int index){
if(index == digitsArr.length){
result.add(new String(str));
return;
}
// 第index个数字对应的字母
String strTemp = find[digitsArr[index] - '0'];
for(int i = 0; i < strTemp.length(); i++){
str.append(strTemp.charAt(i));//加入第Index个数字对应的字母的第i个
letterCombinationsHelper(digitsArr,find,index+1);
str.deleteCharAt(str.length() - 1);
}
}
}
39、组合总和
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
int sum = 0;
int index = 0;
Arrays.sort(candidates);
combinationSumHelper(candidates,index,sum,target);
return result;
}
public void combinationSumHelper(int[] candidates, int index, int sum,int target){
if(sum >= target){
if(sum == target){
result.add(new ArrayList<Integer>(temp));
}
return;
}
for(int i = index; i < candidates.length; i++){
sum += candidates[i];
temp.add(candidates[i]);
combinationSumHelper(candidates,i,sum,target);
temp.remove(temp.size() - 1);
sum -= candidates[i];
}
}
}
40、 组合总和 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int sum = 0;
int index = 0;
Arrays.sort(candidates);
combinationSumHelper(candidates, target, index, sum);
return result;
}
public void combinationSumHelper(int[] candidates, int target, int index, int sum){
if(sum >= target){
if(sum == target){
result.add(new ArrayList<>(temp));
}
return;
}
// 每个数字在每个组合中只能使用一次
for(int i = index; i < candidates.length; i++){
// 去重逻辑，同层剪枝，同枝可取
if(i > 0 &&i > index && candidates[i] == candidates[i - 1]){
continue;
}
temp.add(candidates[i]);
sum += candidates[i];
combinationSumHelper(candidates, target, i + 1, sum);
temp.remove(temp.size() - 1);
sum -= candidates[i];
}
}
}
131、分割回文串
class Solution {
public List<List<String>> result = new ArrayList<List<String>>();
public List<String> temp = new ArrayList<String>();
public List<List<String>> partition(String s) {
int index = 0;
partitionHelper(s, index);
return result;
}
public void partitionHelper(String s, int index){
if(index == s.length()){
result.add(new ArrayList<>(temp));
return;
}
for(int i = index; i < s.length(); i++){
String s1 = s.substring(index, i + 1);
if(!check(s1,0,s1.length() - 1)){
continue;//字符子串不回文的话直接跳过该次分割方案
}
temp.add(s1);
partitionHelper(s,i+1);
temp.remove(temp.size() - 1);
}
}
// 判断是否回文
public boolean check(String s1, int left, int right){
while(left < right){
if(s1.charAt(left) == s1.charAt(right)){
left++;
right--;
}else{
return false;
}
}
return true;
}
}
93、复原 IP 地址
class Solution {
public List<String> result = new ArrayList<String>();
public StringBuilder stringBuilder = new StringBuilder();
public List<String> restoreIpAddresses(String s) {
restoreIpAddressesHelper(s,0,0);
return result;
}
public void restoreIpAddressesHelper(String s, int index,int count){
if (index == s.length() && count == 4) {
result.add(stringBuilder.toString());
return;
}
if (index == s.length() || count == 4) {
return;
}
for (int i = index; i < s.length() && i - index < 3 && Integer.parseInt(s.substring(index, i + 1)) >= 0
&& Integer.parseInt(s.substring(index, i + 1)) <= 255; i++) {
if (i + 1 - index > 1 && s.charAt(index) - '0' == 0) {
continue;
}
stringBuilder.append(s.substring(index, i + 1));
if (count < 3) {
stringBuilder.append(".");
}
count++;
restoreIpAddressesHelper(s,i+1,count);
count--;
stringBuilder.delete(index + count, i + count + 2);
}
}
}
78、子集
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsets(int[] nums) {
subsetsHandler(nums, 0);
return result;
}
public void subsetsHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
temp.add(nums[i]);
subsetsHandler(nums,i+1);
temp.remove(temp.size() - 1);
}
}
}
90、子集 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> subsetsWithDup(int[] nums) {
Arrays.sort(nums);
subsetsWithDupHandler(nums, 0);
return result;
}
public void subsetsWithDupHandler(int[] nums, int index){
if(index == nums.length){
result.add(new ArrayList<>(temp));
return;
}
result.add(new ArrayList<>(temp));
for(int i = index; i < nums.length; i++){
// 不能 包含重复的子集
if(i > 0 &&i > index && nums[i] == nums[i - 1]){
continue;
}
temp.add(nums[i]);
subsetsWithDupHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
491、递增子序列
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> findSubsequences(int[] nums) {
// 递增子序列中 至少有两个元素
findSubsequencesHandler(nums, 0);
return result;
}
public void findSubsequencesHandler(int[] nums, int index){
if(temp.size() > 1){
result.add(new ArrayList<>(temp));
}
int[] used = new int[201];
for(int i = index; i < nums.length; i++){
if(temp.size() != 0 && nums[i] < temp.get(temp.size() - 1) || (used[nums[i] + 100] == 1)){
continue;
}
used[nums[i] + 100] = 1;
temp.add(nums[i]);
findSubsequencesHandler(nums, i + 1);
temp.remove(temp.size() - 1);
}
}
}
46、全排列
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> permute(int[] nums) {
// 有序
int[] used = new int[30];
permuteHandler(nums, used);
return result;
}
public void permuteHandler(int[] nums, int[] used){
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(used[nums[i]+10] == 1){
continue;
}
used[nums[i]+10] = 1;
temp.add(nums[i]);
permuteHandler(nums,used);
used[temp.get(temp.size() - 1)+10] = 0;
temp.remove(temp.size() - 1);
}
}
}
47、全排列 II
class Solution {
public List<List<Integer>> result = new ArrayList<List<Integer>>();
public List<Integer> temp = new ArrayList<Integer>();
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
Arrays.fill(used, false);
Arrays.sort(nums);
permuteHandler(nums, used);
return result;
}
public void permuteHandler(int[] nums, boolean[] used){
if(temp.size() == nums.length){
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < nums.length; i++){
if(i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false){
continue;
}
if(used[i] == false){
used[i] = true;
temp.add(nums[i]);
permuteHandler(nums,used);
used[i] = false;
temp.remove(temp.size() - 1);
}
}
}
}
332、重新安排行程
//基本参考代码随想录
class Solution {
public LinkedList<String> result;
public LinkedList<String> path = new LinkedList<String>();
public List<String> findItinerary(List<List<String>> tickets) {
Collections.sort(tickets,(a,b)->a.get(1).compareTo(b.get(1)));
path.add("JFK");
int[] used = new int[tickets.size()];
findItineraryHanlder(tickets, used);
return result;
}
public boolean findItineraryHanlder(List<List<String>> tickets, int[] used){
if(path.size() == tickets.size() + 1){
result = new LinkedList<String>(path);
return true;
}
for(int i = 0; i < tickets.size(); i++){
if(used[i] != 1 && tickets.get(i).get(0).equals(path.getLast())){
path.add(tickets.get(i).get(1));
used[i] = 1;
if(findItineraryHanlder(tickets,used)){
return true;
}
path.removeLast();
used[i] = 0;
}
}
return false;
}
}
51、N 皇后
class Solution {
public List<List<String>> result = new ArrayList<>();
public List<String> temp = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
int[] arr = new int[n];
Arrays.fill(arr, -1);
find(arr, 0, n);
return result;
}
public void find(int[] arr, int index,int n){
if(index == n){
result.add(new ArrayList<>(temp));
return;
}
for(int i = 0; i < n; i++){
arr[index] = i;
if(judge(arr,index)){
temp.add(setString(n,i));
find(arr, index+1,n);
arr[index]=-1;
temp.remove(temp.size() - 1);
}
}
}
public boolean judge(int[] arr, int index){
for(int i = 0; i < index; i++){
if(arr[i] == arr[index] || Math.abs(index - i)==Math.abs(arr[index]-arr[i])){
return false;
}
}
return true;
}
public String setString(int n, int m){
StringBuffer str1 = new StringBuffer();
for(int i = 0; i < n; i++){
if(i == m){
str1.append("Q");
}else{
str1.append(".");
}
}
return new String(str1);
}
}
37、解数独
class Solution {
public void solveSudoku(char[][] board) {
solveSudokuHander(board);
}
public boolean solveSudokuHander(char[][] board){
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++){
if(board[i][j] != '.'){
continue;
}
for(char k = '1'; k <= '9'; k++){
if(judge(board,i,j,k)){
board[i][j] = k;
if(solveSudokuHander(board)){
return true;
}
board[i][j] = '.';
}
}
return false;
}
}
return true;
}
public boolean judge(char[][] board, int i, int j, char k){
for(int m = 0; m < 9; m++){
if(board[i][m]==k){
return false;
}
}
for(int n = 0; n < 9; n++){
if(board[n][j]==k){
return false;
}
}
int startRow = (i/3)*3;
int startCol = (j/3)*3;
for(int m = startRow; m < startRow+3; m++){
for(int n = startCol; n < startCol+3; n++){
if(board[m][n]==k){
return false;
}
}
}
return true;
}
}