leetcode77 组合

  1. class Solution {
  2.     public List<List<Integer>> combine(int n, int k) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         if(n<k||k<=0) return res;
  5.         Deque<Integer> path = new LinkedList<Integer>();
  6.         dfs(res,path,1,n,k);
  7.         return res;
  8.     }
  9.     private void dfs(List<List<Integer>> list, Deque<Integer> path, int i,int n, int k){
  10.         if(path.size()==k){
  11.             list.add(new ArrayList<Integer>(path));
  12.             return;
  13.         }
  14.         //利用剪枝的思想
  15.         for(int j=i;j<=n+1-(k-path.size());j++){
  16.             path.addLast(j);
  17.             dfs(list,path,j+1,n,k);
  18.             path.removeLast();//回溯
  19.         }
  20.     }
  21. }

leetcode39 组合总和

  1. //回溯+剪枝优化
  2. class Solution {
  3.     public List<List<Integer>> combinationSum(int[] candidates, int target) {
  4.         List<List<Integer>> res = new ArrayList<>();
  5.         Arrays.sort(candidates);
  6.         if(candidates[0]>target) return res;
  7.         Deque<Integer> path = new LinkedList<>();
  8.         int index = 0;
  9.         dfs(res, path, candidates, index, target);
  10.         return res;
  11.     }
  12.     private void dfs(List<List<Integer>> res, Deque<Integer> path, int[] candidates, int index, int target){
  13.         if(target==0){
  14.             res.add(new ArrayList<Integer>(path));
  15.             return;
  16.         }
  17.         for(int i=index;i<candidates.length;i++){
  18.             if(target-candidates[i]<0) break;
  19.             path.addLast(candidates[i]);
  20.             dfs(res,path,candidates,i,target-candidates[i]);
  21.             path.removeLast();
  22.         }        
  23.     }
  24. }

leetcode40 组合总和II

  1. class Solution {
  2.     public List<List<Integer>> combinationSum2(int[] candidates, int target) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         Deque<Integer> path = new LinkedList<>();        
  5.         Arrays.sort(candidates);
  6.         dfs(candidates,res,path,0,target);
  7.         return res;
  8.     }
  9.     private void dfs(int[] candidates,List<List<Integer>> res,Deque<Integer> path, int begin, int target){
  10.         if(target==0){
  11.             List<Integer> list = new ArrayList<>(path);
  12.             res.add(list);  
  13.             return;
  14.         }
  15.         for(int i=begin;i<candidates.length;i++){
  16.             if(target-candidates[i]<0) break;
  17.             //保证在本层不重复，在不同层可重复
  18.             if(i>begin&&candidates[i]==candidates[i-1]){
  19.                 continue;
  20.             }
  21.             path.addLast(candidates[i]);
  22.             dfs(candidates,res,path,i+1,target-candidates[i]);
  23.             path.removeLast();
  24.         }
  25.     }
  26. }

leetcode46 全排列

  1. class Solution {
  2.     public List<List<Integer>> permute(int[] nums) {
  3.         int len = nums.length;
  4.         boolean[] flag = new boolean[len];
  5.         List<List<Integer>> res = new ArrayList<>();
  6.         LinkedList<Integer> path = new LinkedList<>();
  7.         backtrack(res, path, flag, nums);
  8.         return res;
  10.     }
  12.     public void backtrack(List<List<Integer>> res, LinkedList<Integer> path, boolean[] flag, int[] nums){
  13.         int len = nums.length;
  14.         if(path.size()==len){
  15.             res.add(new ArrayList<>(path));
  16.             return; //剪枝
  17.         }
  18.         for(int i=0;i<len;i++){
  19.             if(!flag[i]){
  20.                 path.add(nums[i]);
  21.                 flag[i] = true;
  22.                 backtrack(res, path, flag, nums);
  23.                 path.removeLast();
  24.                 flag[i] = false;
  25.             }
  26.         }
  28.     }
  29. }

leetcode47 全排列 II

  1. class Solution {
  2.     public List<List<Integer>> permuteUnique(int[] nums) {
  3.         int len = nums.length;
  4.         boolean[] used = new boolean[len];
  5.         List<List<Integer>> res = new ArrayList<>();
  6.         Deque<Integer> path = new LinkedList<>();
  7.         Arrays.sort(nums);
  8.         dfs(nums,res,path,used);
  9.         return res;
  10.     }
  11.         private void dfs(int[] nums, List<List<Integer>> res, Deque<Integer> path,boolean[] used){
  12.         if(path.size()==nums.length) {
  13.             res.add(new ArrayList<Integer>(path));
  14.             return;
  15.             }
  16.         for(int i=0;i<nums.length;i++){
  17.             if(i>0&&nums[i]==nums[i-1]&&!used[i-1]) continue;//去重
  18.             if(used[i]==false){
  19.                 used[i] = true;
  20.                 path.addLast(nums[i]);
  21.                 dfs(nums,res,path,used);
  22.                 used[i] =false;//关键
  23.                 path.removeLast();
  24.             }
  25.         }
  26.     }
  27. }

leetcode 22 括号生成

  1. class Solution {
  2.     public List<String> generateParenthesis(int n) {
  3.         List<String> res = new ArrayList<>();
  4.         if(n==0) return res;
  5.         dfs("",0,0,n,res);
  6.         return res;
  8.     }
  10.     public void dfs(String path,int left,int right,int n,List<String> res){
  11.         if(left==n&&right==n){
  12.             res.add(path);
  13.             return;
  14.         }
  15.         //如果左括号用的比右括号少，则返回
  16.         if(left<right){
  17.             return;
  18.         }
  19.         if(left<n){
  20.             dfs(path+"(",left+1,right,n,res);
  21.         }
  23.         if(right<n){
  24.             dfs(path+")",left,right+1,n,res);
  25.         }
  27.     }
  28. }

leetcode79 单词搜索

  1. class Solution {
  2.     public boolean exist(char[][] board, String word) {
  3.         for(int i=0;i<board.length;i++){
  4.             for(int j=0;j<board[0].length;j++){
  5.                 if(search(board, word, i, j, 0)){
  6.                     return true;
  7.                 }
  8.             }
  9.         }
  10.         return false;
  12.     }
  13.     public boolean search(char[][] board, String word, int i, int j, int k){
  14.         if(k>=word.length()){
  15.             return true;
  16.         }
  17.         if(i>=board.length||i<0||j<0||j>=board[0].length||board[i][j]!=word.charAt(k)){
  18.             return false;
  19.         }
  20.         board[i][j]+=100;
  21.         boolean res = search(board, word, i+1, j, k+1)||search(board, word, i-1, j, k+1)||search(board, word, i, j+1, k+1)||search(board, word, i, j-1, k+1);
  22.         board[i][j]-=100;
  23.         return res;
  24.     }
  25. }

leetcode 17 电话号码的字母组合

  1. class Solution {
  2.     // 存放电话按键对应的字母
  3.     String[] map = {"abc", "def", "ghi", "jkl", "mno", "qprs", "tuv", "wxyz"};
  4.     public List<String> res = new ArrayList<>();
  5.     public List<String> letterCombinations(String digits) {
  6.         // 判断是否为空
  7.         if(digits.isEmpty()){
  8.             return res;
  9.         }
  10.         StringBuilder path = new StringBuilder();
  11.         backtrack(0,digits,path);
  12.         return res;
  13.     }
  15.     public void backtrack(int i, String digits, StringBuilder path){
  16.         if(path.length()==digits.length()){
  17.             res.add(path.toString());
  18.             return;
  19.         }
  20.         String str = map[digits.charAt(i)-'2'];
  21.         for(int m=0;m<str.length();m++){
  22.             path.append(str.charAt(m));
  23.             backtrack(i+1,digits,path);
  24.             path.deleteCharAt(path.length()-1);
  25.         }
  26.     }
  27. }

leetcode 24 括号生成

  1. class Solution {
  2.     public List<String> res;
  3.     public List<String> generateParenthesis(int n) {
  4.         res = new ArrayList<>();
  5.         generate("", 0,0,n);
  6.         return res;
  8.     }
  9.     public void generate(String str, int leftCount, int rightCount, int n){
  10.         if(leftCount>n||rightCount>n){
  11.             return;
  12.         }
  13.         if(leftCount==n&&rightCount==n){
  14.             res.add(str);
  15.         }
  16.         if(leftCount>=rightCount){
  17.             String newStr = new String(str);
  18.             generate(newStr+"(",leftCount+1,rightCount,n);
  19.             generate(newStr+")",leftCount,rightCount+1,n);
  20.         }
  21.     }
  22. }