leetcode 22. 括号生成
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。例如,给出 n = 3,生成结果为:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
List<String> list = new ArrayList<>();
public List<String> generateParenthesis(int n) {
if (n <= 0) {
return list;
}
process(0, 0, n, "");
return list;
}
private void process(int left, int right, int sum, String tmp) {
if (2 * sum == tmp.length()) {
list.add(tmp);
return;
}
//左括号的个数小于n
if (left < sum) {
process(left + 1, right, sum, tmp + "(");
}
//右括号的个数不能超过左括号的个数
if (left > right) {
process(left, right + 1, sum, tmp + ")");
}
}
leetcode 39组合总和
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0 || target < 0) {
return lists;
}
List<Integer> list = new ArrayList<>();
process(0, candidates, target, list);
return lists;
}
private void process(int start, int[] candidates, int target, List<Integer> list) {
//递归的终止条件
if (target < 0) {
return;
}
if (target == 0) {
lists.add(new ArrayList<>(list));
} else {
for (int i = start; i < candidates.length; i++) {
list.add(candidates[i]);
//因为每个数字都可以使用无数次,所以递归还可以从当前元素开始
process(i, candidates, target - candidates[i], list);
list.remove(list.size() - 1);
}
}
}
leetcode 40. 组合总和 II
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates == null || candidates.length == 0 || target < 0) {
return lists;
}
Arrays.sort(candidates);
List<Integer> list = new ArrayList<>();
process(0, candidates, target, list);
return lists;
}
private void process(int start, int[] candidates, int target, List<Integer> list) {
if (target < 0) {
return;
}
if (target == 0) {
lists.add(new ArrayList<>(list));
} else {
for (int i = start; i < candidates.length; i++) {
//因为这个数和上个数相同,所以从这个数开始的所以情况,在上个数里面都考虑过了,需要跳过
if (i > start && candidates[i] == candidates[i - 1]) {
continue;
}
list.add(candidates[i]);
process(i + 1, candidates, target - candidates[i], list);
list.remove(list.size() - 1);
}
}
}
二叉树中和为某一值的路径
public static ArrayList<ArrayList<Integer>> pathSum(TreeNode root, int target) {
ArrayList<ArrayList<Integer>> lists = new ArrayList<ArrayList<Integer>>();
Stack<Integer> stack = new Stack<>();
int pathValue = 0;
preOrder(root, pathValue, target, stack, lists);
return lists;
}
private static void preOrder(TreeNode node, int pathValur, int sum, Stack<Integer> path, ArrayList<ArrayList<Integer>> result) {
if (node == null) {
return;
}
pathValur += node.val;
path.add(node.val);
if (node.left == null && node.right == null && pathValur == sum) {
result.add(new ArrayList<>(path));
}
preOrder(node.left, pathValur, sum, path, result);
preOrder(node.right, pathValur, sum, path, result);
//回退 剪枝
pathValur -= node.val;
path.pop();
}
leetcode 46. 全排列
回溯法
List<List<Integer>> lists = new ArrayList<>();
boolean[] visted;
public List<List<Integer>> permute(int[] nums) {
if(nums == null || nums.length == 0){
return lists;
}
List<Integer> list = new ArrayList<>();
visted = new boolean[nums.length];
process(list,nums);
return lists;
}
private void process( List<Integer> list, int[] nums) {
//终止条件
if(list.size() == nums.length){
lists.add(new ArrayList<>(list));
return;
}
for (int i = 0; i < nums.length ; i++) {
if(!visted[i]){
visted[i] = true;
list.add(nums[i]);
process(list,nums);
list.remove(list.size()-1);
visted[i] = false;
}
}
}
交换法
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> permute(int[] nums) {
process(nums,0);
return lists;
}
private void process(int[] nums, int start) {
//如果起始位置已经到达了末尾,那么这就是一组解。
if(start == nums.length){
List<Integer>list = new ArrayList<>();
for(int num:nums){
list.add(num);
}
lists.add(list);
}
for (int i = start; i < nums.length ; i++) {
//把第一个元素分别与后面的元素进行交换,递归的调用其子数组进行排序
swap(nums,i,start);
process(nums,start+1);
swap(nums,i,start);
}
}
private void swap(int[] nums, int index1, int index2){
int tmp = nums[index1];
nums[index1] = nums[index2];
nums[
leetcode 47. 全排列 II
回溯写法
List<List<Integer>> lists = new ArrayList<>();
boolean[] visited;
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0) {
return lists;
}
Arrays.sort(nums);
visited = new boolean[nums.length];
List<Integer>list = new ArrayList<>();
process(nums, 0,list);
return lists;
}
private void process(int[] nums, int start, List<Integer>list){
if(list.size() == nums.length){
lists.add(new ArrayList<>(list));
return;
}
//为什么从0开始
/**
* Perms( nums[0…n-1] ) = {取出一个数字} +
* * Perms( nums[{0…n-1} - 这个数字] )
*/
for (int i = 0; i < nums.length ; i++) {
if(visited[i]){
continue;
}
//i-1和i的值相等,且i-1没被用过(之后可能会被用就产生重复)
//基本难点就是要去掉重复的
//以这个[1,1,2]为例
//正常会返回6个结果:其中第一行是以下标为0的1开始,而第二行是以下标为1的1开始。
//1,1,2;1,2,1
//1,1,2;1,2,1
//2,1,1;2,1,1
//去重做法就是,在dfs时要判断i和i-1是否相等和i-1这个值是否被用。
//相等和没有被用就跳过这个i的情况,直接去i+1判断。
//因为没被用的话,之后就可以再用这个i-1,那就会出现重复的情况。
//比如说第二行是i=1时的判断,此时i和i-1的值相等,且i-1的值没被用
//那么跳过i=1这个情况,直接去i=2,所以我们就去掉了第二行所有重复的。
if(i>0 && nums[i] == nums[i-1] &&!visited[i-1]){
continue;
}
visited[i] = true;
list.add(nums[i]);
process(nums,start+1,list);
visited[i] = false;
list.remove(list.size()-1);
}
}
交换法
List<List<Integer>> lists = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0) {
return lists;
}
Arrays.sort(nums);
process(nums, 0);
return lists;
}
private void process(int[] nums, int start) {
if (start == nums.length) {
List<Integer> list = new ArrayList<Integer>();
for (int num : nums) {
list.add(num);
}
lists.add(new ArrayList<>(list));
return;
}
HashSet<Integer>set = new HashSet<>(); //保存当前要交换的位置已经有过哪些数字了
for (int i = start; i < nums.length; i++) {
if (set.contains(nums[i])) { //如果存在了就跳过,不去交换
continue;
}
set.add(nums[i]);
swap(nums, start, i);
//这里是start+1
process(nums, start + 1);
swap(nums, start, i);
}
}
private void swap(int[] nums, int i, int j) {
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
leetcode 51. N皇后
public static void main(String[] args) {
new Nqueue51().solveNQueens(4);
}
List<List<String>> res = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
if(n < 1){
return res;
}
List<Integer> list = new ArrayList<>();
help(0,n,list);
return res;
}
private void help(int row, int n, List<Integer> list){
if(row == n){
List<String> strList = new ArrayList<>();
for(Integer num:list){
char[] t = new char[n];
Arrays.fill(t,'.');
t[num] = 'Q';
strList.add(new String(t));
}
res.add(strList);
return;
}
//每一列都尝试一下
for (int col = 0; col < n; col++) {
//当前列是否合法
if (!list.contains(col)) {
//左斜与右协是否哈法
if(!isDiagonalAttack(list,col)){
list.add(col);
help(row+1,n,list);
//回溯
list.remove(list.size()-1);
}
}
}
}
private boolean isDiagonalAttack(List<Integer> currentQueen, int i) {
int currentRow = currentQueen.size();
int currentCol = i;
//判断每一行的皇后的情况
for (int row = 0; row < currentQueen.size(); row++) {
//左上角的对角线和右上角的对角线,差要么相等,要么互为相反数,直接写成了绝对值
if (Math.abs(currentRow - row) == Math.abs(currentCol - currentQueen.get(row))) {
return true;
}
}
return false;
}
leetcode 52. N皇后 II
int cnt = 0;
public int totalNQueens(int n) {
if(n < 1){
return 0;
}
List<Integer>list = new ArrayList<>();
help(0,n,list);
return cnt;
}
private void help(int row, int n, List<Integer> list){
if(row == n){
cnt++;
return;
}
//每一列都尝试一下
for (int col = 0; col < n; col++) {
//当前列是否合法
if (!list.contains(col)) {
//左斜与右协是否哈法
if(!isDiagonalAttack(list,col)){
list.add(col);
help(row+1,n,list);
//回溯
list.remove(list.size()-1);
}
}
}
}
private boolean isDiagonalAttack(List<Integer> currentQueen, int i) {
int currentRow = currentQueen.size();
int currentCol = i;
//判断每一行的皇后的情况
for (int row = 0; row < currentQueen.size(); row++) {
//左上角的对角线和右上角的对角线,差要么相等,要么互为相反数,直接写成了绝对值
if (Math.abs(currentRow - row) == Math.abs(currentCol - currentQueen.get(row))) {
return true;
}
}
return false;
}
leetcode 78 :
已知一个数组(其中无重复元素),求这组数可以组成的所有子集。
public static void main(String[] args) {
int[] nums = {1, 2, 3};
Stack<Integer> stack = new Stack<>();
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
generate(0, nums, stack, result);
System.out.println(result);
}
private static void generate(int i, int[] nums, Stack<Integer> stack, ArrayList<ArrayList<Integer>> result) {
if (i >= nums.length) {
return;
}
stack.push(nums[i]);
result.add(new ArrayList<>(stack));
//放入nums[i]的情况
generate(i + 1, nums, stack, result);
stack.pop();
//不放入nums[i]的情况
generate(i + 1, nums, stack, result);
}
public class Partition131 {
public static void main(String[] args) {
new Partition131().partition("aad");
}
List<List<String>> lists = new ArrayList<>();
public List<List<String>> partition(String s) {
if(s == null || s.length() == 0){
return lists;
}
List<String> list = new ArrayList<>();
process(s,list,0);
return lists;
}
private void process(String s, List<String> list, int index){
if(index == s.length()){
lists.add(new ArrayList<>(list));
return;
}
for (int i = index+1; i <=s.length() ; i++) {
String str = s.substring(index,i);
if(isParlindrome(str)){
list.add(str);
process(s,list,i);
//list相当于引用传递,所以需要回退
list.remove(list.size()-1);
}
}
}
private boolean isParlindrome(String s){ //判断是否为回文串
if(s==""||s.length()==0){
return false;
}
int len=s.length();
for(int i=0;i<=len/2;++i){
if(s.charAt(i)!=s.charAt(len-1-i)){
return false;
}
}
return true;
}
}