【力扣hot100】day4

39.组合总和【中】

39. 组合总和

方法一：回溯

//执行用时: 1 ms
//内存消耗: 41.9 MB
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates); //排序
        backTracing(candidates, target, 0, 0);
        return result;
    }

    public void backTracing(int[] candidates, int target, int sum, int index) {
        if(sum == target) {
            result.add(new ArrayList<>(path));
            return ;
        }
        for(int i = index; i < candidates.length; i++) {
            if (sum + candidates[i] > target) break;//这一步差一些就忽略了！！！
            path.add(candidates[i]);
            backTracing(candidates, target, sum + candidates[i], i);
            path.remove(path.size() - 1);
        }
    }
}
           

42.接雨水【难】

42. 接雨水

46.全排列【中】

46. 全排列

方法一：回溯

//执行用时: 1 ms
//内存消耗: 41.8 MB
class Solution {
    List<List<Integer>> result = new ArrayList<>();
    List<Integer> path = new ArrayList<>();
    public List<List<Integer>> permute(int[] nums) {
        backTracing(nums, 0);
        return result;
    }

    public void backTracing(int[] nums, int len) {
        if(path.size() == nums.length) {
            result.add(new ArrayList<>(path));
            return ;
        }
        for(int i = 0; i < nums.length; i++) {
            if(path.contains(nums[i])) continue ; //这一步挺重要的！！！
            path.add(nums[i]);
            backTracing(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}
           

48.旋转图像【中】

48. 旋转图像

49.字母异位词分组【中】

49. 字母异位词分组

方法一：哈希表

//执行用时: 6 ms
//内存消耗: 44.3 MB
class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
       //判断是否为空字符串数组
        if(strs == null || strs.length == 0){
            return new ArrayList();
        }
        //1.创建一个哈希表
        Map<String,List> map = new HashMap<String, List>();
        for (String s: strs) {
            //将字符串转化为字符数组
            char[] chars = s.toCharArray();
            //对字符数组按照字母顺序排序
            Arrays.sort(chars);
            //将排序后的字符串作为哈希表中的key值
            String key = String.valueOf(chars);
            //2.判读哈希表中是否有该key值
            if (!map.containsKey(key)){
                //若不存在，则为新的异位词语，在map中创建新的键值对
                map.put(key,new ArrayList());
            }
            //3.将该字符串放在对应key的list中
            map.get(key).add(s);
        }
        //返回map中所有键值对象构成的list
        return new ArrayList(map.values());
    }
}