Menu Sidebar
Menu

Maximize Sum Of Array After K Negations

给一个数组, 问如何翻转k(求负)个数后,数组和最大。 明显翻转最小的数是最大的。

Pairs of Songs With Total Durations Divisible by 60

给一个数组, 找到其中有多少对数的和整除60。这里上来先取模,然后就是2sum pair

Partition Array Into Three Parts With Equal Sum

求一个数组能不能分为三个小数组,并且这三个小数组的和相等。我们已知目标是三个小数组,所以数组能被3整除。然后再找到小数组目标和是多少。计算是否有三个小数组的目标和。

Binary Prefix Divisible By 5

找了半天规律,发现没意思。直接破解了。然后submit发现有overflow,看了下输入是个数组,那真是大。立刻想到取模。取模有分配律,对答案无影响

Remove Outermost Parentheses

用一个count来计算”(“和”)”的差,0就是最外边的。

Sum of Root To Leaf Binary Numbers

在树上找到binary,加起来。难点是怎么表示binary,我看答案好多用int乘来乘去,我这里选择string表示。使用Integer的parseString比较方便。而且答案易懂。

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输了。

所以只需要判断奇偶即可

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。

Distribute Candies to People

算了半天等差数列求和和取模,结果发现还不如直接实现。以后这种easy的题,千万别想多

Older Posts

书脊

这青苔碧瓦堆, 俺曾睡风流觉, 将五十年兴亡看饱.