仔细观察，开始撸了一个冗长的hashmap，仔细观察后其实HashSet就可以解决。
public class Solution {
public int distributeCandies(int[] candies) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int c : candies){
map.put(c, map.getOrDefault(c,0)+1);
}
int target = candies.length/2;
for(Integer key : map.keySet()){
if(map.get(key)>1){
target-=map.get(key)-1;
}
if(target<=0){
return map.size();
}
}
return map.size()-target;
}
}
public class Solution {
public int distributeCandies(int[] candies) {
Set<Integer> kinds = new HashSet<>();
for (int candy : candies) kinds.add(candy);
return kinds.size() >= candies.length / 2 ? candies.length / 2 : kinds.size();
}
}
开始还以为是个DP，因为只care两个数字同时不care顺序，所以hashmap存就可以。
public class Solution {
public int findLHS(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int n : nums)
map.put(n, map.getOrDefault(n,0)+1);
int ans = 0;
for(Integer key : map.keySet()){
if(map.containsKey(key+1)){
ans = Math.max(ans, map.get(key)+map.get(key+1));
}
}
return ans;
}
}
public class Solution {
public List<Integer> killProcess(List<Integer> pid, List<Integer> ppid, int kill) {
HashMap<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
for(int i=0;i<pid.size();i++){
int p = pid.get(i); int pp = ppid.get(i);
if(!map.containsKey(pp)) map.put(pp, new ArrayList<Integer>());
map.get(pp).add(p);
}
List<Integer> ans = new ArrayList<Integer>();
remove(ans, map, kill);
return ans;
}
public void remove(List<Integer> ans, HashMap<Integer, ArrayList<Integer>> map, int kill){
ans.add(kill);
if(!map.containsKey(kill)) return;
for(int k : map.get(kill)){
remove(ans, map, k);
}
}
}
很好的一道考设计和hashmap的题，首先要和面试官交流scalability 和每个API调用的frequency。字符串truancate后直接自然字符串比较就可以。
public class LogSystem {
HashMap<String, ArrayList<Integer>> map;
HashMap<String, Integer> time;
public LogSystem() {
map = new HashMap<String, ArrayList<Integer>>();
time = new HashMap<String, Integer>();
time.put("Year", 4);
time.put("Month", 7);
time.put("Day", 10);
time.put("Hour", 13);
time.put("Minute", 16);
time.put("Second", 19);
}
public void put(int id, String timestamp) {
if(!map.containsKey(timestamp)) map.put(timestamp, new ArrayList<Integer>());
map.get(timestamp).add(id);
}
public List<Integer> retrieve(String s, String e, String gra) {
String start = s.substring(0,time.get(gra));
String end = e.substring(0,time.get(gra));
List<Integer> ans = new ArrayList<Integer>();
for(String tt : map.keySet()){
String t = tt.substring(0,time.get(gra));
// System.out.println(start);
// System.out.println(end);
// System.out.println(t);
// System.out.println(t.compareTo(start));
// System.out.println(t.compareTo(end));
if(t.compareTo(start)>=0 &&t.compareTo(end)<=0)
ans.addAll(map.get(tt));
}
return ans;
}
}
两种解法，hashmap O(n)复杂度，two pointers O(nlogn).
自己写的one pass hashmap，统计每个数字出现的次数，只考虑非重复pair，当nums[i]已经存在hashmap里，只有k=0的情况才考虑，剩下的情况直接continue。count只自增1. map主要是服务于k＝0的时候。当k＝0并且nums[i] 只出现1次的时候，count+1；当k!=0, 搜索nums[i]+/-k, count++.
public class Solution {
public int findPairs(int[] nums, int k) {
if(k<0) return 0;
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int count = 0;
for(int i=0;i<nums.length;i++){
if(map.containsKey(nums[i])) {
if(k==0&&map.get(nums[i])==1) count++;
map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
continue;
}
if(map.containsKey(nums[i]-k))
count++;
if(map.containsKey(nums[i]+k))
count++;
map.put(nums[i], map.getOrDefault(nums[i], 0)+1);
}
return count;
}
}
我的做法在逻辑上略显繁琐。论坛里的解法更简单。1st pass统计num count，2nd pass 统计合理的pair
public class Solution {
public int findPairs(int[] nums, int k) {
if (nums == null || nums.length == 0 || k < 0) return 0;
Map<Integer, Integer> map = new HashMap<>();
int count = 0;
for (int i : nums) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (k == 0) {
//count how many elements in the array that appear more than twice.
if (entry.getValue() >= 2) {
count++;
}
} else {
if (map.containsKey(entry.getKey() + k)) {
count++;
}
}
}
return count;
}
}
Two Pointers
public class Solution {
public int findPairs(int[] nums, int k) {
Arrays.sort(nums);
int start = 0, end = 1, result = 0;
while (start < nums.length && end < nums.length) {
if (start == end || nums[start] + k > nums[end]) {
end++;
} else if (nums[start] + k < nums[end]) {
start++;
} else {
start++;
result++;
// start
// |
// [1, 1, ...., 8, 8]
// |
// end
while (start < nums.length && nums[start] == nums[start - 1]) start++;
end = Math.max(end + 1, start + 1);
}
}
return result;
}
}
非常巧妙的问题，因为这里是考虑k的倍数的问题，k可以是正，负，0中的某个数。
所以在建hashmap的时候，考虑到是要k的倍数的特性，我们可以用sum%k来建作key，val记录当前位置。
通过查询sum%k, 就可以知道是否可以形成k的倍数。
所以不能用nums[i]来建k，在k!=0的时候，用nums[i]%k来建立, k==0用其本身。
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); map.put(0, -1);
int sum = 0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
if(k!=0) sum%=k;
if(map.containsKey(sum) && i-map.get(sum)>=2) return true;
else if(!map.containsKey(sum)) map.put(sum, i);
}
return false;
}
}
两个string，char一对一match。比如（“banana”和“cololo”），follow up：如果有一个String[]对一个String，同样的match判断，要求输出所有match的string。(G)
naive的解法是对每一个"banana"和“cololo”进行匹配。当词多字典大的时候，这个时候建立HashMap<String, ArrayList<String>>, key是每个词形成的signature，比如banana是1,2,3,2,3,2.
两种方式，如果每个node有唯一的编号，可以用union find，对每个array中的pointer找到其root。第二种方式可以对每个connected component建立一个hashset，进行查找。具体space上的trade off需要讨论。