给一个国际象棋的板子, 问某个个子的颜色.
|
1 2 3 4 5 6 7 |
class Solution { public boolean squareIsWhite(String c) { boolean res = (c.charAt(0) - 'a') % 2 == 0 ? false : true ; res = (c.charAt(1) - '1') % 2 == 0 ? res : !res; return res; } } |
给一个log是<user, min>, 定义UAM是一个user对应唯一的min的个数, 给一个k, 求[1,k]min中独立user的个数.
这题就是读懂题….
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public int[] findingUsersActiveMinutes(int[][] logs, int k) { int[] res = new int[k]; Map<Integer, Set<Integer>> map = new HashMap<>();// <user id, unique min> for(int[] l : logs) { if(map.containsKey(l[0])){ Set<Integer> set = map.get(l[0]); set.add(l[1]); map.put(l[0], set); }else{ Set<Integer> set = new HashSet<>(); set.add(l[1]); map.put(l[0], set); } } for(Map.Entry<Integer, Set<Integer>> e : map.entrySet()){ res[e.getValue().size() - 1]++; } return res; } } |
给一个sentence, 里面没有前置和后置空格, 求前k个words的sentence.
|
1 2 3 4 5 6 7 8 9 10 |
class Solution { public String truncateSentence(String s, int k) { String[] strs = s.split(" "); StringBuilder sb = new StringBuilder(); for(int i = 0 ; i < k && i < strs.length ; i ++) { sb.append(strs[i]+" "); } return sb.toString().trim(); } } |
设计一个验证器, 要有添加, 更新和查看有多少未过期token的功能.
这题直接做吧…优化就是加了个删除过期token的…
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 |
class AuthenticationManager { Map<String, Integer> m = new HashMap<>(); int ttl; public AuthenticationManager(int timeToLive) { ttl = timeToLive; } public void generate(String tokenId, int currentTime) { m.put(tokenId, currentTime + ttl); } public void renew(String tokenId, int currentTime) { if(!m.containsKey(tokenId) || m.get(tokenId) <= currentTime) return; m.remove(tokenId); generate(tokenId, currentTime); } public int countUnexpiredTokens(int currentTime) { int res = 0; Set<String> set = new HashSet<>(); for(Map.Entry<String, Integer> e : m.entrySet()){ if(e.getValue() > currentTime){ res++; }else{ set.add(e.getKey()); } } for(String s : set){ m.remove(s); //remove all expired token } return res; } } /** * Your AuthenticationManager object will be instantiated and called as such: * AuthenticationManager obj = new AuthenticationManager(timeToLive); * obj.generate(tokenId,currentTime); * obj.renew(tokenId,currentTime); * int param_3 = obj.countUnexpiredTokens(currentTime); */ |
给一个string, 找第二大的数字.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public int secondHighest(String s) { Set<Integer> set = new HashSet<>(); for(char c : s.toCharArray()){ if('0' <= c && c <= '9'){ set.add(c - '0'); } } boolean largest = false; for(int i = 9; i >= 0; i--){ if(set.contains(i)){ if(!largest) largest = true; else{ return i; } } } return -1; } } |
给一个数组, 求其中的最大和的递增子数组的和是多少.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
class Solution { public int maxAscendingSum(int[] nums) { int prev = Integer.MIN_VALUE; int res = 0; int tmp = 0; for(int i = 0; i < nums.length; i++){ if(prev < nums[i]){ tmp += nums[i]; }else{ tmp = nums[i]; } prev = nums[i]; res = Math.max(res, tmp); } return res; } } |
给一个数n, 求一个数组大小为2n的数组, 里面的数字有[1,n],每个数字两个, 并且每个数之间的间隔是这个数字本身的数组有几个.
这个是组合数学问题的一个经典题, dfs直接做即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public void findLangfordPairing(int[] arr, int n) { if (n == 0) { res++;//res is the numbers; return; } for (int i=0;i<arr.length-n-1;i++) { if(arr[i] == 0 && arr[i+n+1] == 0) { // valid arr[i] = n; arr[i+n+1] = n; findLangford(arr, n-1); arr[i] = 0; arr[i+n+1] = 0; //reset the array } } } |
给一个Employee类, 里面有一个数组的子类的id和一个importance数字, 求他自己和他下面所有的id的importance的和
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 |
/* // Definition for Employee. class Employee { public int id; public int importance; public List<Integer> subordinates; }; */ class Solution { public int getImportance(List<Employee> employees, int id) { Map<Integer, List<Integer>> map = new HashMap<>(); Map<Integer, Integer> im = new HashMap<>(); Employee c = null; for(Employee e : employees){ if(e.id == id) c = e; if(map.containsKey(e.id)){ map.get(e.id).addAll(e.subordinates); }else{ map.put(e.id, e.subordinates); } im.put(e.id, im.getOrDefault(e.id, e.importance)); } int res = 0; res += sumUp(c.id, map, im); return res; } private int sumUp(int id, Map<Integer, List<Integer>> map, Map<Integer, Integer> im) { int sum = im.get(id); for(int s : map.get(id)){ sum += sumUp(s, map,im); } return sum; } } |
给一个数组, 返回每个数与其后边最近的比他大的数的差.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
class Solution { public int[] finalPrices(int[] prices) { int n = prices.length; int[] res = new int[n]; for(int i = n - 1; i >= 0; i--) { res[i] = prices[i]; for(int j = i + 1; j < n; j++) { if(prices[j] <= res[i]){ res[i] -= prices[j]; break; } } } return res; } } |
给一个2d数组, 里面是[id, score], 求每个id的top 5 score的average, 并且还要按照id排序.
因为要排序, 所以先排序, 然后只加top5即可.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Solution { public int[][] highFive(int[][] items) { Arrays.sort(items, (a,b) -> (a[0] == b[0] ? b[1] - a[1] : a[0] - b[0])); List<int[]> list = new ArrayList<>(); int i = 0; while(i < items.length){ int cur = items[i][0]; int sum = 0; for(int j = 0; j < 5; i++,j++){ sum += items[i][1]; } list.add(new int[]{cur, sum / 5}); while(i < items.length && cur == items[i][0]){ i++; } } int[][] res = new int[list.size()][2]; for(int k = 0; k < list.size(); k++){ res[k][0] = list.get(k)[0]; res[k][1] = list.get(k)[1]; } return res; } } |