Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
Example 1:
Input: [23, 2, 4, 6, 7], k=6 Output: True Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2:
Input: [23, 2, 6, 4, 7], k=6 Output: True Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
Note:
- The length of the array won't exceed 10,000.
- You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
HashMap 存Sum -> index
注意各种corner cases: n可以为非正数,array有相邻2个0存在,当sum为0时要检查subarray长度
如果改变题目要求,找sum为k,也是同样类似思路
class Solution { public boolean checkSubarraySum(int[] nums, int k) { if (nums == null || nums.length < 2) return false; if (checkZeros(nums)) return true; if (k == 0) return false; Map<Integer, Integer> map = new HashMap<>(); int sum = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i]; sum %= k; if ((map.containsKey(sum) && i - map.get(sum) > 0) || (i > 0 && sum == 0)) { return true; } map.put(sum, i); } return false; } private boolean checkZeros(int[] nums) { for (int i = 1; i < nums.length; i++) { if (nums[i] == 0 && nums[i - 1] == 0) return true; } return false; } }
49. Group Anagrams
Given an array of strings, group anagrams together.
Example:
Input: ["eat", "tea", "tan", "ate", "nat", "bat"]
,
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
Note:
- All inputs will be in lowercase.
- The order of your output does not matter.
Solution #1, 把每个string都排序一下(其实也就是编码),同一个Anagram的都会有一个相同的编码
时间O(n * klog(k)), n为strs的长度,k为其中string的平均长度 空间O(n * k)
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { char[] sorted = s.toCharArray(); Arrays.sort(sorted); String st = new String(sorted); if (!map.containsKey(st)) { map.put(st, new ArrayList<>()); } map.get(st).add(s); } return new ArrayList<>(map.values()); } }
Solution #2, 换一种方法来编码,线性
O(n * k) time complexity, n是strs的changdu,k是其中string的平均长度
空间O(n * k)
class Solution { public List<List<String>> groupAnagrams(String[] strs) { Map<String, List<String>> map = new HashMap<>(); for (String s : strs) { String encoding = getEncoding(s); if (!map.containsKey(encoding)) { map.put(encoding, new ArrayList<>()); } map.get(encoding).add(s); } return new ArrayList<>(map.values()); } private String getEncoding(String s) { int[] m = new int[26]; for (int i = 0; i < s.length(); i++) { m[s.charAt(i) - 'a']++; } StringBuilder rt = new StringBuilder(); for (int i = 0; i < 26; i++) { int c = m[i] + 'a'; rt.append(c).append(","); } return rt.toString(); } }
No comments:
Post a Comment