三十二岁, 我过了世界上最长的生日
三十二岁, 我坐在北京飞芝加哥的航班上, 度过这个长达30多小时的七月七日.
命运的转轮已经开始转动, 你方唱罢我登场, 是时候了
Maximize Sum Of Array After K Negations
给一个数组， 问如何翻转k（求负）个数后，数组和最大。 明显翻转最小的数是最大的。
|
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 |
class Solution { public int largestSumAfterKNegations(int[] A, int K) { for(int i = 0 ; i < K; i++) { int index = findMin(A); A[index] = -A[index]; // always flip min value } int sum = 0; for(int a : A) { sum += a; } return sum; } private int findMin(int[] A) { // return the min index of array int min = Integer.MAX_VALUE; int min_index = -1; for(int i = 0 ; i < A.length; i++) { if(A[i] < min) { min_index = i; min = A[i]; } } return min_index; } } |
Pairs of Songs With Total Durations Divisible by 60
给一个数组， 找到其中有多少对数的和整除60。这里上来先取模，然后就是2sum pair
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
public int numPairsDivisibleBy60(int[] time) { for(int i = 0 ; i < time.length; i++) { time[i] %= 60; } int count = 0; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i < time.length; i++) { int key = (60 - time[i]) % 60; count += map.getOrDefault(key, 0); map.put(time[i], map.getOrDefault(time[i], 0)+1); } return count; } |
Partition Array Into Three Parts With Equal Sum
求一个数组能不能分为三个小数组，并且这三个小数组的和相等。我们已知目标是三个小数组，所以数组能被3整除。然后再找到小数组目标和是多少。计算是否有三个小数组的目标和。
|
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 boolean canThreePartsEqualSum(int[] A) { int sum = 0; for(int a : A) { sum += a ; // calculate sum } if(sum % 3 != 0) { return false; // divide by 3 ? } sum /= 3; // get the sum goal int count = 0; // count how many sum we have int tmp = 0; for(int a : A) { tmp += a; if(tmp == sum){ // if we find one count++; tmp = 0; } if(count == 3) // if there 3 return true; } return false; } } |
Binary Prefix Divisible By 5
找了半天规律，发现没意思。直接破解了。然后submit发现有overflow，看了下输入是个数组，那真是大。立刻想到取模。取模有分配律，对答案无影响
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public List<Boolean> prefixesDivBy5(int[] A) { List<Boolean> res = new ArrayList<>(); long n = 0; for(int i : A){ n = n*2 + i; //convert int[] A to binary n %= 5;// mod distribution law if(n == 0) res.add(true); else res.add(false); } return res; } } |
Remove Outermost Parentheses
用一个count来计算”(“和”)”的差，0就是最外边的。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { public String removeOuterParentheses(String S) { int count = 0; // count the diff between "(" and ")" StringBuffer res = new StringBuffer(); StringBuffer tmp = new StringBuffer(); for(int i = 0 ; i < S.length(); i++) { if(S.charAt(i) == '(') count++; else if(S.charAt(i) == ')') count--; tmp.append(S.charAt(i)); if(count == 0){ // if it is outter tmp.deleteCharAt(0); // remove first tmp.deleteCharAt(tmp.length()-1);//remove last res.append(tmp); tmp.setLength(0); //reset tmp } } return res.toString(); } } |
Sum of Root To Leaf Binary Numbers
在树上找到binary，加起来。难点是怎么表示binary，我看答案好多用int乘来乘去，我这里选择string表示。使用Integer的parseString比较方便。而且答案易懂。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
class Solution { int sum = 0; public int sumRootToLeaf(TreeNode root) { solve(root,""); return sum; } private void solve(TreeNode root, String s) { if(root.left == null && root.right == null) { sum += toInt(s+root.val); } if(root.left != null) solve(root.left, s+root.val); if(root.right != null) solve(root.right, s+root.val); } private int toInt(String s) { return Integer.parseInt(s,2); } } |
Divisor Game
注意的是N % k == 0， 所以如果是偶数，那么Alice取个1就赢了。奇数就是Bob取个1，Alice取个1，然后就不能去了，因为k的取值范围是0 < k < N。因为可以取1，所以最后结束肯定是取不了数了才结束。比如5的话，Alice只能选1. 因为5不能整除2，3，4任何一个数，然后Bob对着4可以选2，但是他不选，他选1，这样4-1=3，Aice要面对3，他只能选1，然后Bob面对2选1，剩下1. Alice输了。
所以只需要判断奇偶即可
|
1 2 3 4 5 |
class Solution { public boolean divisorGame(int N) { return N % 2 == 0; } } |
Two City Scheduling
这题可有点绕，开始直接想的就是动态规划，然后琢磨了一下，觉得easy应该有greedy的做法，于是想到比较两个人去A和B之间的差的abs，即B[1]-A[1]（去B点cost的差）和B[0]-A[0]（去A点的cost的差），然后排序，再求和。
最后翻了翻答案， 看到以下解法，真是更巧妙。
举例[[10,20],[30,200],[400,50],[30,20]]，因为只有A，B两个点，所以我们假设所有人都去一个点B，那么就是 20 + 200 + 50 + 20. 然后我们数组的两个数相减，得出如果去A，那么哪些人优先去？[20-10], [200-30], [50-400],[20-30] -> [10], [170], [-350], [-10], 然后排序，[170], [10], [-10], [-350]. 这个数组序列是按照最应该去A的人。最后是最巧妙的一点， 我们因为已知n个人要去A，所以只需取前两个，[170], [10].，
然后是我们如何加到最开始的数组？ 首先，我们把[170], [10] 还原成 [200-30], [20-10], 然后我们用20 + 200 + 50 + 20 – (200-30) – (20 – 10).就可以消去B并且加回A。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 |
class Solution { public int twoCitySchedCost(int[][] costs) { int sum = 0; for(int[] c : costs) sum += c[1]; Arrays.sort(costs,new Comparator<int[]>(){ public int compare(int[] o1, int[] o2){ return (o2[1]-o2[0]) - (o1[1]-o1[0]); }}); for(int i = 0; i < costs.length / 2; i++) sum -= (costs[i][1] - costs[i][0]); return sum; } } |
Distribute Candies to People
算了半天等差数列求和和取模，结果发现还不如直接实现。以后这种easy的题，千万别想多
|
1 2 3 4 5 6 7 8 9 10 11 12 13 |
class Solution { public int[] distributeCandies(int candies, int num_people) { int[] res = new int[num_people]; int i = 0; // index int j = 1; // count while(candies > 0) { res[i] += Math.min(j, candies); // find rest of candies candies -= j++; // minus first, then ++ i = ++i%num_people; // ++ first then mod } return res; } } |