6.14号刷题

第一题 358. Rearrange String k Distance Apart

题目描述

给定一个string和距离k。重新排列string中的所有character，使得它们至少相隔k。

算法

首先使用HashMap存储所有的字符串和他们出现的频率，之后按照出现频率从高到底排列map中元素。之后利用贪婪搜索，依次将频率从高到低的字符插入空的String中

public class Solution {
    public String rearrangeString(String s, int k) {
        Map<Character, Integer> charStore = new HashMap<>();
        for (char c : s.toCharArray()) charStore.put(c, charStore.getOrDefault(c, 0) + 1);
        Queue<Map.Entry<Character, Integer>> maxHeap = new PriorityQueue<>(new Comparator<Map.Entry<Character, Integer>>() {
            @Override
            public int compare(Map.Entry<Character, Integer> o1, Map.Entry<Character, Integer> o2) {
                return o2.getValue() - o1.getValue();
            }
        });
        Queue<Map.Entry<Character, Integer>> waitQueue = new LinkedList<>();
        maxHeap.addAll(charStore.entrySet());
        StringBuilder res = new StringBuilder();
        while (!maxHeap.isEmpty()) {
            Map.Entry<Character, Integer> cur = maxHeap.poll();
            res.append(cur.getKey());
            cur.setValue(cur.getValue() - 1);
            waitQueue.offer(cur);
            
            if (waitQueue.size() < k) {
                continue;
            }
            
            Map.Entry<Character, Integer> front = waitQueue.poll();
            if (front.getValue() > 0) maxHeap.offer(front);
        }
        return res.length() == s.length() ? res.toString() : "";        
    }
}

学到的东西

一个HashMap可以用Map.Entry进行遍历。Map.entry entry = map.entrySet()。然后可以用iteratory的方式进行遍历

第二题 565. Array Nesting

题目描述

索引从0开始的数组A包含N个不同的数字。每个数字范围[0, N - 1]

定义集合S[K] 对于 0 <= K < N：

S[K] = { A[K], A[A[K]], A[A[A[K]]], … }

对于每一个K，S[K]是有限的，不包含重复。

编写函数返回最大的S[K]的大小。

注意：

N是整数，范围[1, 20000]
A中的元素各不相同
A是整数，范围[0, N - 1]

算法

题目可以转换为找到数组A中最长的那个圈，因此，当我们找到一个圈的时候，将圈中数字全部置为-1，表示已经找过了。

public class Solution {
    public int arrayNesting(int[] nums) {
        int max = 0;
        for (int i = 0; i < nums.length; i++) {
            int length = 0;
            int cur = i;
            while (nums[cur] >= 0) {
                length++;
                int temp = cur;
                cur = nums[cur];
                nums[temp] = -1;
            }
            max = Math.max(max, length);
        }
        return max;        
    }
}

第三题 39. Combination Sum

题目描述

给定一个Array和一个target，求Array中有多少组合的sum的和可以满足target的值。

注意：可以包含重复的值

算法

回溯：注意开始和终止的条件

public class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(res, curRes, candidates, target, 0);
        return res;
    }
    public void backtrack(List<List<Integer>> res, List<Integer> curRes, int[] candidates, int remain, int start) {
        if (remain < 0) return;
        else if (remain == 0) res.add(new ArrayList<>(curRes));
        else {
            for (int i = start; i < candidates.length; i++) {
                curRes.add(candidates[i]);
                backtrack(res, curRes, candidates, remain - candidates[i], i);
                curRes.remove(curRes.size() - 1);
            }
        }
    }
}

第四题 40. Combination Sum II

题目描述

这一次不同的地方在于Array中的数字只能使用一次(注意可能包含相同的数字)

算法

题目难点在于最后结果的list中不能包含重复的，但是Array中会有重复的数字，利用if (i > start && nums[i] == num[i-1])来判断是否是第一次进入循环，且跳过重复的可能性

public class Solution {
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(res, curRes, candidates, target, 0);
        return res;
    }
    public void backtrack (List<List<Integer>> res, List<Integer> curRes, int[] nums, int remain, int start) {
        if (remain < 0) return;
        else if (remain == 0) res.add(new ArrayList<>(curRes));
        else {
            for (int i = start; i < nums.length; i++) {
                if (i > start && nums[i] == nums[i - 1]) continue;  //What beautiful algorithm
                curRes.add(nums[i]);
                backtrack(res, curRes, nums, remain - nums[i], i + 1);
                curRes.remove(curRes.size() - 1);
            }
        }
    }
}

第五题 216. Combination Sum III

题目描述

寻找所有满足k个数之和等于n的组合，只允许使用数字1-9，并且每一种组合中的数字应该是唯一的。

确保组合中的数字以递增顺序排列。

测试样例见题目描述。

算法

与之前的方法相似，只是在判断回溯条件的时候，稍微有所不同

public class combinationSumIII216 {
    public List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        backtrack(res, curRes, nums, n, 0, k);
        return res;
    }
    public void backtrack(List<List<Integer>> res, List<Integer> curRes, int[] nums, int remain, int start, int k) {
        if (remain < 0 || curRes.size() > k) return;
        else if (remain == 0 && curRes.size() == k) res.add(new ArrayList<>(curRes));
        else {
            for (int i = start; i < nums.length; i++) {
                curRes.add(nums[i]);
                backtrack(res, curRes, nums, remain - nums[i], i + 1, k);
                curRes.remove(curRes.size() - 1);
            }
        }
    }
}

第六题 78. Subsets

题目描述

给定一个数组(不含重复)，求这个数组包含的所有子集

算法

还是利用回溯的方法进行求解

public class subsets78 {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        res.add(curRes);
        backtrack(res, curRes, nums, 0);
        return res;
    }
    public void backtrack(List<List<Integer>> res, List<Integer> curRes, int[] nums, int start) {
        for (int i = start; i < nums.length; i++) {
            curRes.add(nums[i]);
            res.add(new ArrayList<>(curRes));
            backtrack(res, curRes, nums, i + 1);
            curRes.remove(curRes.size() - 1);
        }
    }
}

第七题 90. Subsets II

题目描述

给定一个数组(含重复)，求这个数组包含的所有子集

算法

利用if (i > start && nums[i] == num[i-1])来判断是否是第一次进入循环，且跳过重复的可能性

public class subsetsWithDup90 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        List<Integer> curRes = new ArrayList<>();
        res.add(curRes);
        Arrays.sort(nums);
        backtrack(res, curRes, nums, 0);
        return res;
    }
    public void backtrack(List<List<Integer>> res, List<Integer> curRes, int[] nums, int start) {
        for (int i = start; i < nums.length; i++) {
            if (i > start && nums[i] == nums[i-1]) continue;
            curRes.add(nums[i]);
            res.add(new ArrayList<>(curRes));
            backtrack(res, curRes, nums, i + 1);
            curRes.remove(curRes.size() - 1);
        }
    }
}

第八题 560. Subarray Sum Equals K

题目描述

给定整数数组nums和整数k，寻找和等于k的连续子数组的个数。

注意：

数组长度为[1, 20000]
数组元素范围[-1000, 1000]，整数k范围[-1e7, 1e7]

算法

这题其实应该算在动态规划中。我们的目标是找出sum[i, j] 等于k，可以转化为求sum[0, j] - sum[0, i - 1] = k的问题。因此我们利用HashMap记录下所有的sum值，如果曾经出现了sum[0,j] - k的值包含在内，说明中间有一段的sum是等于k的，计数加1

public class Solution {
    public int subarraySum(int[] nums, int k) {
        if (nums.length == 0) return 0;
        Map<Integer, Integer> preSum = new HashMap<>();
        preSum.put(0, 1);
        int sum = 0, total = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (preSum.containsKey(sum - k)) {
                total += preSum.get(sum - k);
            }
            preSum.put(sum, preSum.getOrDefault(sum, 0) + 1);
        }
        return total;
    }
}

第九题 533. Lonely Pixel II

题目描述

给定一个包含字符’W’（白色）和’B’（黑色）的像素矩阵picture，以及一个整数N。

求所有同行同列恰好有N个’B’像素，并且这N行必须完全相同。

注意：

二维数组的宽度和高度在范围[1,500]之间。

算法

这道题方法很巧妙，由于要求N行完全相同，因此可以用Map记录下相同的行，然后再对每列的黑点个数进行统计。如果相同的行数不等于N，或此行此列的黑点个数不等于N都可以被排除。

public class Solution {
    public int findBlackPixel(char[][] picture, int N) {
        int n = picture.length, m = picture[0].length;
        if (n <= 0 || m <= 0) return 0;
        //Row ; Frequency
        Map<String, Integer> map = new HashMap<>();
        int[] colCount = new int[m];
        for (int i = 0; i < n; i++) {
            StringBuilder rowString = new StringBuilder();
            int rowCount = 0;
            for (int j = 0; j < m; j++) {
                rowString.append(picture[i][j]);
                if (picture[i][j] == 'B') {
                    colCount[j]++;
                    rowCount++;
                }
            }
            if (rowCount == N) map.put(rowString.toString(), map.getOrDefault(rowString.toString(), 0) + 1);
        }
        int result = 0;
        for (Map.Entry<String, Integer> entry: map.entrySet()) {
            String row = entry.getKey();
            int num = entry.getValue();
            if (num == N) {
                for (int j = 0; j < m; j++) {
                    if (colCount[j] == N && row.charAt(j) == 'B') {
                        result += N;
                    }
                }
            }
        }
        return result;
    }
}