LeetCode 链表专题

2020/01/17 Prolems

目录

17. 电话号码的字母组合 中等

  • 题目描述

    给定一个仅包含数字 2-9 的字符串,返回所有它能表示的字母组合。

    给出数字到字母的映射如下(与电话按键相同)。注意 1 不对应任何字母。

    Example:

    输入:”23”
    输出:[“ad”, “ae”, “af”, “bd”, “be”, “bf”, “cd”, “ce”, “cf”].

  • 解法

    dfs,把所有的对应关系放到一个 map 中。dfs 时循环这个 map 的数组。

  • 代码

      class Solution {
          Map<Character,char[]> map = new HashMap<>();
          public List<String> letterCombinations(String digits) {
              map.put('2',new char[]{'a','b','c'});
              map.put('3',new char[]{'d','e','f'});
              map.put('4',new char[]{'g','h','i'});
              map.put('5',new char[]{'j','k','l'});
              map.put('6',new char[]{'m','n','o'});
              map.put('7',new char[]{'p','q','r','s'});
              map.put('8',new char[]{'t','u','v'});
              map.put('9',new char[]{'w','x','y','z'});
              List<String> res = new LinkedList<>();
              if(digits.equals("")) return res;
              char[] cs = digits.toCharArray();
              char[] word = new char[cs.length];
              dfs(res, word, cs, 0);
              return res;
          }
          public void dfs(List<String> res, char[] word, char[] cs, int index){
              if(index == cs.length){
                  res.add(new String(word));
                  return;
              }
              char[] ss = map.get(cs[index]);
              for(int i=0;i<ss.length;i++){
                  word[index] = ss[i];
                  dfs(res,word,cs,index+1);
              }
          }
      }
    

46. 全排列 中等

  • 题目描述

    给定一个没有重复数字的序列,返回其所有可能的全排列。

    Example:

    输入: [1,2,3]
    输出:
    [
    [1,2,3],
    [1,3,2],
    [2,1,3],
    [2,3,1],
    [3,1,2],
    [3,2,1]
    ]

  • 解法

    dfs,对每两位做交换。相当于保持前 i 位不动,交换之后的每一位和 index 位。

  • 代码

      class Solution {
          public List<List<Integer>> permute(int[] nums) {
              List<List<Integer>> res = new LinkedList<>();
              if(nums.length == 0) return res;
              dfs(res, nums, 0);
              return res;
          }
          public void dfs(List<List<Integer>> res, int[] nums, int index){
              if(index == nums.length){
                  LinkedList<Integer> list = new LinkedList<>();
                  for(int num:nums){
                      list.add(num);
                  }
                  res.add(list);
                  return;
              }
              for(int i=index;i<nums.length;i++){
                  swap(nums,i,index);
                  dfs(res,nums,index+1);
                  swap(nums,i,index);
              }
          }
          public void swap(int[] list, int a, int b){
              int temp = list[a];
              list[a] = list[b];
              list[b] = temp;
          }
      }
    

47. 全排列 II 中等

  • 题目描述

    给定一个有重复数字的序列,返回其所有可能的全排列。

    Example:

    输入: [1,1,2]
    输出:
    [
    [1,1,2],
    [1,2,1],
    [2,1,1]
    ]

  • 解法

    最简单的方法是把上面的例子 list 转换成 set。

  • 代码

      class Solution {
          public List<List<Integer>> permute(int[] nums) {
              List<List<Integer>> res = new LinkedList<>();
              if(nums.length == 0) return res;
              dfs(res, nums, 0);
              return res;
          }
          public void dfs(List<List<Integer>> res, int[] nums, int index){
              if(index == nums.length){
                  LinkedList<Integer> list = new LinkedList<>();
                  for(int num:nums){
                      list.add(num);
                  }
                  res.add(list);
                  return;
              }
              for(int i=index;i<nums.length;i++){
                  swap(nums,i,index);
                  dfs(res,nums,index+1);
                  swap(nums,i,index);
              }
          }
          public void swap(int[] list, int a, int b){
              int temp = list[a];
              list[a] = list[b];
              list[b] = temp;
          }
      }
    

78. 子集 中等

  • 题目描述

    给定一组不含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

    说明:解集不能包含重复的子集。

    Example:

    输入: nums = [1,2,3]
    输出:
    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]

  • 解法

    因为是求子集,不需要交换。dfs,只不过这次不是到了数量满足才加进去,而是每有一步操作就加进去。

  • 代码

      class Solution {
          public List<List<Integer>> subsets(int[] nums) {
              List<List<Integer>> res = new LinkedList<>();
              if(nums.length==0) return res;
              LinkedList<Integer> list = new LinkedList<>();
              dfs(res,list,nums,0);
              return res;
          }
          public void dfs(List<List<Integer>> res, LinkedList<Integer> list, int[] nums, int index){
              res.add(new ArrayList<Integer>(list));
              for(int i=index;i<nums.length;i++){
                  list.add(nums[i]);
                  dfs(res,list,nums,i+1);
                  list.removeLast();
              }
          }
      }
    

90. 子集2 中等

  • 题目描述

    给定一个可能包含重复元素的整数数组 nums,返回该数组所有可能的子集(幂集)。

    说明:解集不能包含重复的子集。

    Example:

    输入: nums = [1,2,3]
    输出:
    [
    [3],
    [1],
    [2],
    [1,2,3],
    [1,3],
    [2,3],
    [1,2],
    []
    ]

  • 解法

    dfs 的时候要查看一下这个数是否和上一个数相等,相等就跳过这个数。

  • 代码

      class Solution {
          public List<List<Integer>> subsetsWithDup(int[] nums) {
              List<List<Integer>> res = new LinkedList<>();
              if(nums.length==0) return res;
              LinkedList<Integer> list = new LinkedList<>();
              Arrays.sort(nums);
              dfs(res,list,nums,0);
              return res;
          }
          public void dfs(List<List<Integer>> res, LinkedList<Integer> list, int[] nums, int index){
              res.add(new LinkedList<Integer>(list));
              for(int i=index;i<nums.length;i++){
                  if(i>index && nums[i]==nums[i-1]){
                      continue;
                  }
                  list.add(nums[i]);
                  dfs(res, list, nums, i+1);
                  list.removeLast();
              }
          }
      }
    

39. 组合总和 中等

  • 题目描述

    给定一个无重复元素的数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

    candidates 中的数字可以无限制重复被选取。

    说明:

    所有数字(包括 target)都是正整数。

    解集不能包含重复的组合。 

    Example:

    输入: candidates = [2,3,5], target = 8,
    所求解集为:
    [
      [2,2,2,2],
      [2,3,3],
      [3,5]
    ]

  • 解法

    与之前区别是可以有重复数字。所以是在 dfs 时对应的序号不 +1。

  • 代码

      class Solution {
          public List<List<Integer>> combinationSum(int[] candidates, int target) {
              List<List<Integer>> res = new LinkedList<>();
              if(candidates.length==0) return res;
              dfs(res,new LinkedList<Integer>(),candidates,target,0);
              return res;
          }
          public void dfs(List<List<Integer>> res, LinkedList<Integer> list, int[] candidates, int target, int index){
              if(target<0) return;
              if(target==0){
                  res.add(new LinkedList<>(list));
                  return;
              }
              for(int i=index;i<candidates.length;i++){
                  list.add(candidates[i]);
                  dfs(res,list,candidates,target-candidates[i],i);
                  list.removeLast();
              }
          }
      }
    

40. 组合总和 II 中等

  • 题目描述

    给定一个数组 candidates 和一个目标数 target ,找出 candidates 中所有可以使数字和为 target 的组合。

    candidates 中的每个数字在每个组合中只能使用一次。

    说明:

    所有数字(包括目标数)都是正整数。

    解集不能包含重复的组合。 

    Example:

    输入: candidates = [10,1,2,7,6,1,5], target = 8,
    所求解集为:
    [
    [1, 7],
    [1, 2, 5],
    [2, 6],
    [1, 1, 6]
    ]

  • 解法

    重复数字不能重复使用。所以是在 dfs 时对应的序号 +1。同时由于不能重复,所以对应重复数需要跳过,也就是如果这一次数字等于上一个且不是第一轮循环(i>index)数就跳过。

  • 代码

      class Solution {
          public List<List<Integer>> combinationSum2(int[] candidates, int target) {
              List<List<Integer>> res = new LinkedList<>();
              if(candidates.length==0) return res;
              Arrays.sort(candidates);
              dfs(res,new LinkedList<>(),candidates,0,target);
              return res;
          }
          public void dfs(List<List<Integer>> res, LinkedList<Integer> list, int[] candidates, int index, int target){
              if(target<0) return;
              if(target==0){
                  res.add(new ArrayList<Integer>(list));
                  return;
              }
              for(int i=index;i<candidates.length;i++){
                  if(i>index&&candidates[i]==candidates[i-1]) continue;
                  list.add(candidates[i]);
                  dfs(res,list,candidates,i+1,target-candidates[i]);
                  list.removeLast();
              }
          }
      }
    

216. 组合总和 III 中等

  • 题目描述

    找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数,并且每种组合中不存在重复的数字。

    说明:

    • 所有数字都是正整数。
    • 解集不能包含重复的组合。

    Example:

    输入: k = 3, n = 9
    输出: [[1,2,6], [1,3,5], [2,3,4]]

  • 解法

    循环是从 1 到 9。剪枝条件有两个,一个是 target<0,一个是加到的时候 k 的数量不是 0.

  • 代码

      class Solution {
          public List<List<Integer>> combinationSum3(int k, int n) {
              List<List<Integer>> res = new LinkedList<>();
              dfs(res,new LinkedList<Integer>(),1,n,k);
              return res;
          }
          public void dfs(List<List<Integer>> res, LinkedList<Integer> list,int index,int target,int rest){
              if(target<0) return;
              if(rest==0){
                  if(target==0){
                      res.add(new LinkedList<Integer>(list));
                  }
                  return;
              }
              for(int i=index;i<=9;i++){
                  list.add(i);
                  dfs(res,list,i+1,target-i,rest-1);
                  list.removeLast();
              }
          }
      }
    

22. 括号生成 中等

  • 题目描述

    给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。

    例如,给出 n = 3,生成结果为:

    Example:

    [
    “((()))”,
    “(()())”,
    “(())()”,
    “()(())”,
    “()()()”
    ]

  • 解法

    回溯法,当左括号数量少于 n 数量时,需要追加左括号回溯。

    当右括号数量少于左括号数量时,需要追加左括号回溯。

  • 代码

      class Solution {
          public List<List<Integer>> combinationSum3(int k, int n) {
              List<List<Integer>> res = new LinkedList<>();
              dfs(res,new LinkedList<Integer>(),1,n,k);
              return res;
          }
          public void dfs(List<List<Integer>> res, LinkedList<Integer> list,int index,int target,int rest){
              if(target<0) return;
              if(rest==0){
                  if(target==0){
                      res.add(new LinkedList<Integer>(list));
                  }
                  return;
              }
              for(int i=index;i<=9;i++){
                  list.add(i);
                  dfs(res,list,i+1,target-i,rest-1);
                  list.removeLast();
              }
          }
      }
    

473. 火柴拼正方形 中等

  • 题目描述

    还记得童话《卖火柴的小女孩》吗?现在,你知道小女孩有多少根火柴,请找出一种能使用所有火柴拼成一个正方形的方法。不能折断火柴,可以把火柴连接起来,并且每根火柴都要用到。

    输入为小女孩拥有火柴的数目,每根火柴用其长度表示。输出即为是否能用所有的火柴拼成正方形。

    Example:

    输入: [1,1,2,2,2] 输出: true

    解释: 能拼成一个边长为2的正方形,每边两根火柴。

  • 解法

    回溯法,先求出正方形的边长。

    之后可以回溯法,如果任意一边长度超过边长,可以剪枝。如果有任意一边长度为 0,剪枝。只有当所有边都等于边长才返回 true。

  • 代码

      class Solution {
          boolean res = false;
          public boolean makesquare(int[] nums) {
              int sum = 0;
              for(int num:nums){
                  sum+=num;
              }
              if(sum%4!=0) return false;
              backtrack(nums,0,0,0,0,0,sum/4);
              return res;
          }
          public void backtrack(int[] nums, int index, int top,int down,int left,int right,int side){
              if(top>side||down>side||left>side||right>side) return;
              if(index == nums.length){
                  if(top==0||down==0||left==0||right==0) return;
                  if(top!=down||top!=right||top!=left) return;
                  res = true;
                  return;
              }
              int length = nums[index];
              if(res == false)
              backtrack(nums,index+1,top+length,down,left,right,side);
              if(res == false)
              backtrack(nums,index+1,top,down+length,left,right,side);
              if(res == false)
              backtrack(nums,index+1,top,down,left+length,right,side);
              if(res == false)
              backtrack(nums,index+1,top,down,left,right+length,side);
          }
      }
    

93. 复原IP地址 中等

  • 题目描述

    给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。

    Example:

    输入: “25525511135”
    输出: [“255.255.11.135”, “255.255.111.35”]

  • 解法

    回溯法,从字符串截取,有效的数字可以继续 dfs 下去,到 4 位时添加。

  • 代码

      class Solution {
          public List<String> restoreIpAddresses(String s) {
              List<String> res = new ArrayList<String>();
              if (s.length() < 4 || s.length() > 12)
                  return res;
              dfs(res, "", 0, s);
              return res;
          }
          public void dfs(List<String> list, String temp, int count,String s){
              if(s.length()>(4-count)*3) return;
              if(count==4){
                  if(s.equals("")){
                      list.add(temp.substring(0,temp.length()-1));
                  }
                  return;
              }
              for(int i=1;i<=Math.min(3,s.length());i++){
                  String cur = s.substring(0,i);
                  if(isValid(cur)){
                      dfs(list,temp+cur+".",count+1,s.substring(i));
                  }
              }
          }
          public boolean isValid(String s) {
              // 前导0,如果第一个字符是0,只能一个为0
              if (s.charAt(0) == '0')
                  return s.equals("0");
              int num = Integer.parseInt(s);
              return 0 < num && num < 256;
          }
      }
    

Search

    Table of Contents