devbox
小蓝xlanll
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode回溯算法题

作者：小蓝xlanll | 2024-02-26 18:49:12

赞

踩

leetcode回溯算法题

46. 全排列

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

  1. class Solution {
  2.     public List<List<Integer>> permute(int[] nums) {
  3.         List<List<Integer>> list = new ArrayList<>();
  4.         dfs(nums,new boolean[nums.length],new LinkedList<Integer>(),list);
  5.         return list;
  6.     }
  7.  
  8.     public void dfs(int[] nums , boolean[] isVisited , LinkedList<Integer> stack , List<List<Integer>> list){
  9.         if(stack.size() == nums.length){
  10.             list.add(new ArrayList(stack));
  11.             return;
  12.         }
  13.         for(int i = 0 ; i < nums.length ; i++){
  14.             if(!isVisited[i]){
  15.                 isVisited[i] = true;
  16.                 stack.push(nums[i]);
  17.                 dfs(nums , isVisited , stack , list);
  18.                 stack.pop();
  19.                 isVisited[i] = false;
  20.             }
  21.         }
  22.     }
  23. }

47. 全排列 II

给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。

  1. class Solution {
  2.     public List<List<Integer>> permuteUnique(int[] nums) {
  3.         Arrays.sort(nums);
  4.         List<List<Integer>> list = new ArrayList<>();
  5.         dfs(nums,new boolean[nums.length],new LinkedList<Integer>(),list);
  6.         return list;
  7.     }
  8.  
  9.         public void dfs(int[] nums , boolean[] isVisited , LinkedList<Integer> stack , List<List<Integer>> list){
  10.         if(stack.size() == nums.length){
  11.             list.add(new ArrayList(stack));
  12.             return;
  13.         }
  14.         for(int i = 0 ; i < nums.length ; i++){
  15.             if (i > 0 && nums[i] == nums[i - 1] && !isVisited[i-1]) {
  16.                 continue;
  17.             }
  18.             if(!isVisited[i]){
  19.                 isVisited[i] = true;
  20.                 stack.push(nums[i]);
  21.                 dfs(nums , isVisited , stack , list);
  22.                 stack.pop();
  23.                 isVisited[i] = false;
  24.             }
  25.         }
  26.     }
  27. }

78. 子集

给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         res.add(new ArrayList<>());
  5.         for(int i = 1; i <= nums.length;i++){
  6.             res = getSub(0,new LinkedList<>(),nums,i,res);
  7.         }
  8.         return res;
  9.     }
  10.     private List<List<Integer>> getSub(int begin, LinkedList<Integer> list,int[] nums,int full,List<List<Integer>> res){
  11.         if(list.size() == full){
  12.             res.add(new ArrayList<>(list));
  13.         }
  14.         for(int i = begin; i < nums.length; i++){
  15.             list.push(nums[i]);
  16.             getSub(i+1,list,nums,full,res);
  17.             list.pop();
  18.         }
  19.         return res;
  20.     }
  21. }

90. 子集 II

给你一个整数数组 nums ，其中可能包含重复元素，请你返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。返回的解集中，子集可以按 任意顺序 排列。

  1. class Solution {
  2.     List<Integer> t = new ArrayList<Integer>();
  3.     List<List<Integer>> ans = new ArrayList<List<Integer>>();
  4.  
  5.     public List<List<Integer>> subsetsWithDup(int[] nums) {
  6.         Arrays.sort(nums);
  7.         dfs(false, 0, nums);
  8.         return ans;
  9.     }
  10.  
  11.     public void dfs(boolean choosePre, int cur, int[] nums) {
  12.         if (cur == nums.length) {
  13.             ans.add(new ArrayList<Integer>(t));
  14.             return;
  15.         }
  16.         dfs(false, cur + 1, nums);
  17.         if (!choosePre && cur > 0 && nums[cur - 1] == nums[cur]) {
  18.             return;
  19.         }
  20.         t.add(nums[cur]);
  21.         dfs(true, cur + 1, nums);
  22.         t.remove(t.size() - 1);
  23.     }
  24. }

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. class Solution {
  2.     public List<String> restoreIpAddresses(String s) {
  3.         List<String> res = new ArrayList<>();
  4.         char[] zArr = s.toCharArray();
  5.         if (zArr.length < 4) return res;
  6.         back(zArr, new LinkedList<>(),res);
  7.         return res;
  8.     }
  9.  
  10.     private void back(char[] zArr, LinkedList<Integer> list, List<String> res) {
  11.         if (list.size() == 4) {
  12.             if (list.peekLast() == zArr.length - 1) {
  13.                 StringBuilder curr = new StringBuilder();
  14.                 int index = 0;
  15.                 for (int i = 0; i < 4; i++) {
  16.                     int num = list.get(i);
  17.                     while (index <= num) {
  18.                         curr.append(zArr[index++]);
  19.                     }
  20.                     if (i != 3) {
  21.                         curr.append('.');
  22.                     }
  23.                 }
  24.                 res.add(curr.toString());
  25.             } else {
  26.                 return;
  27.             }
  28.         }
  29.         if (list.isEmpty()) {
  30.             if (zArr[0] == '0') {
  31.                 list.add(0);
  32.                 back(zArr, list, res);
  33.                 list.removeLast();
  34.             } else {
  35.                 for (int i = 0; i < 3; i++) {
  36.                     if (inRange(zArr, 0, i)) {
  37.                         list.add(i);
  38.                         back(zArr, list, res);
  39.                         list.removeLast();
  40.                     } else {
  41.                         return;
  42.                     }
  43.                 }
  44.             }
  45.         } else {
  46.             int pre = list.peekLast();
  47.             if (pre < zArr.length - 1) {
  48.                 int curr = pre + 1;
  49.                 if (zArr[curr] == '0') {
  50.                     list.add(curr);
  51.                     back(zArr, list, res);
  52.                     list.removeLast();
  53.                 } else {
  54.                     for (int i = curr; i < zArr.length; i++) {
  55.                         if (!inRange(zArr, curr, i)) {
  56.                             return;
  57.                         } else {
  58.                             list.add(i);
  59.                             back(zArr, list, res);
  60.                             list.removeLast();
  61.                         }
  62.                     }
  63.                 }
  64.             }
  65.         }
  66.     }
  67.  
  68.     private boolean inRange(char[] zArr, int pre, int curr) {
  69.         int jud = 0;
  70.         while (pre <= curr) {
  71.             jud *= 10;
  72.             jud += (zArr[pre] - '0');
  73.             pre++;
  74.         }
  75.         return jud >= 0 && jud <= 255;
  76.     }
  77. }

491. 非递减子序列

给你一个整数数组 nums ，找出并返回所有该数组中不同的递增子序列，递增子序列中 至少有两个元素 。你可以按 任意顺序 返回答案。

数组中可能含有重复元素，如出现两个整数相等，也可以视作递增序列的一种特殊情况。

  1. class Solution {
  2.     public List<List<Integer>> findSubsequences(int[] nums) {
  3.         List<List<Integer>> res = new ArrayList<>();
  4.         List<List<Integer>> container = new ArrayList<>();
  5.         Map<List<Integer>, TreeSet<Integer>> map = new HashMap<>();
  6.         TreeSet<Integer> set = new TreeSet<>();
  7.         for (int num : nums) {
  8.             int size = container.size();
  9.             for (int i = 0; i < size; i++) {
  10.                 List<Integer> list = container.get(i);
  11.                 if (list.get(list.size() - 1) <= num) {
  12.                     TreeSet<Integer> treeSet = map.get(list);
  13.                     if (treeSet.add(num)) {
  14.                         List<Integer> addList = new ArrayList<>(list);
  15.                         addList.add(num);
  16.                         container.add(addList);
  17.                         map.put(addList, new TreeSet<>());
  18.                     }
  19.                 }
  20.             }
  21.             if (set.add(num)) {
  22.                 ArrayList<Integer> list = new ArrayList<>(List.of(num));
  23.                 container.add(list);
  24.                 map.put(list, new TreeSet<>());
  25.             }
  26.         }
  27.         for (List<Integer> list : container) {
  28.             if (list.size() >= 2) res.add(list);
  29.         }
  30.         return res;
  31.     }
  32. }

37. 解数独

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

数独部分空格内已填入了数字，空白格用 '.' 表示。

  1. class Solution {
  2.     public void solveSudoku(char[][] board) {
  3.         boolean[][] row = new boolean[9][9];//行
  4.         boolean[][] column = new boolean[9][9];//列
  5.         boolean[][] block = new boolean[9][9];//块
  6.         //填充数组
  7.         for(int i = 0; i < 9; i++){
  8.             for(int j = 0; j < 9; j++){
  9.                 if(board[i][j]  != '.'){
  10.                     int curr = (int)(board[i][j] - '1');
  11.                     row[i][curr] = true;
  12.                     column[j][curr] = true;
  13.                     block[bloNums(i,j)][curr] = true;
  14.                 }
  15.             }
  16.         }
  17.         dfs(board,0,0,row,column,block);
  18.     }
  19.     private boolean dfs(char[][] board, int i, int j, boolean[][] row, boolean[][] column, boolean[][] block){
  20.         if(i >= 9)  return true;
  21.         if(j >= 9){ return dfs(board,i+1,0,row,column,block);}
  22.         if(board[i][j] != '.'){return dfs(board,i,j+1,row,column,block);}
  23.  
  24.         for(int curr = 0; curr < 9; curr++){
  25.             if(!row[i][curr] && !column[j][curr] && !block[bloNums(i,j)][curr]){
  26.                 board[i][j] = (char)(curr+'1');
  27.                 row[i][curr] = true;
  28.                 column[j][curr] = true;
  29.                 block[bloNums(i,j)][curr] = true;
  30.                 if(dfs(board,i,j+1,row,column,block)){
  31.                     return true;
  32.                 }
  33.                 board[i][j] = '.';
  34.                 row[i][curr] = false;
  35.                 column[j][curr] = false;
  36.                 block[bloNums(i,j)][curr] = false;
  37.             }
  38.         }
  39.         return false;
  40.     }
  41.     private int bloNums(int row, int column){
  42.         return row/3*3 + column/3;
  43.     }
  44. }

51. N 皇后

按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。

n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。

每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

  1. class Solution {
  2.    public List<List<String>> solveNQueens(int n) {
  3.         List<List<String>> res = new ArrayList<>();
  4.         char[][] chs = new char[n][n];
  5.         for (char[] ch : chs) {
  6.             Arrays.fill(ch, '.');
  7.         }
  8.         boolean[] column = new boolean[n];//列
  9.         boolean[] left = new boolean[2 * n - 1];//左斜线 - /   i+j
  10.         boolean[] right = new boolean[2 * n - 1];//右斜线 - \  n-1-(i-j)
  11.  
  12.         dfs(chs,0,column,left,right,res);
  13.         return res;
  14.     }
  15.  
  16.     static void dfs(char[][] chs, int i, boolean[] column, boolean[] left, boolean[] right, List<List<String>> res) {
  17.         if (i == chs.length){
  18.             List<String> list = new ArrayList<>();
  19.             for (char[] ch : chs) {
  20.                 list.add(new String(ch));
  21.             }
  22.             res.add(list);
  23.             return;
  24.         }
  25.  
  26.         for (int j = 0; j < chs.length; j++) {
  27.             if (column[j] || left[i + j] || right[chs.length + j - i - 1]) continue;
  28.  
  29.  
  30.             chs[i][j] = 'Q';
  31.             column[j] = left[i + j] = right[chs.length + j - i - 1] = true;
  32.             dfs(chs, i + 1, column, left, right, res);
  33.             chs[i][j] = '.';
  34.             column[j] = left[i + j] = right[chs.length + j - i - 1] = false;
  35.         }
  36.  
  37.     }
  38. }

332. 重新安排行程

给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。

所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。

  • 例如，行程 ["JFK", "LGA"] 与 ["JFK", "LGB"] 相比就更小，排序更靠前。

假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。

  1. class Solution {
  2.     boolean over = false;
  3.     List<String> res = new ArrayList<>();
  4.  
  5.     public List<String> findItinerary(List<List<String>> tickets) {
  6.         Map<String, TreeMap<String, Integer>> map = new HashMap<>();
  7.         int sum = tickets.size();
  8.  
  9.         for (List<String> ticket : tickets) {
  10.             String from = ticket.get(0);
  11.             String to = ticket.get(1);
  12.             if (map.get(from) == null) {
  13.                 TreeMap<String, Integer> treeMap = new TreeMap<>();
  14.                 treeMap.put(to, 1);
  15.                 map.put(from, treeMap);
  16.             } else {
  17.                 TreeMap<String, Integer> treeMap = map.get(from);
  18.                 treeMap.merge(to, 1, Integer::sum);
  19.             }
  20.         }
  21.         res.add("JFK");
  22.         dfs("JFK",sum,map);
  23.         return res;
  24.     }
  25.  
  26.     private void dfs(String from, int sum, Map<String, TreeMap<String, Integer>> map) {
  27.         if (sum == 0) {
  28.             over = true;
  29.             return;
  30.         }
  31.         TreeMap<String, Integer> treeMap = map.get(from);
  32.         if(treeMap == null || treeMap.isEmpty()) return;
  33.         for (Map.Entry<String, Integer> entry : treeMap.entrySet()) {
  34.             String key = entry.getKey();
  35.             Integer value = entry.getValue();
  36.             if (value > 0) {
  37.                 value--;
  38.                 treeMap.put(key,value);
  39.                 res.add(key);
  40.                 dfs(key, sum - 1, map);
  41.                 if(over){
  42.                     return;
  43.                 }
  44.                 res.remove(res.size() - 1);
  45.                 value++;
  46.                 treeMap.put(key,value);
  47.             }
  48.         }
  49.     }
  50. }

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小蓝xlanll/article/detail/146021
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号