Menu Sidebar
Menu

Leetcode

Codeforces Round #725 (Div. 3)B. Friends and Candies

给一个n个数字的数组, 问最少可以取多少个数字, 使得分配给别的数字(包括自己),后让数组的值全相等. 一共n个数组, 那么全相等, 肯定就是sum % n == 0 才可能. 不然怎么分都分不出来. 然后因为要分给别的数, 所以只需要找到比sum/n大的数字, 即可., 因为反正这些大数都要分了才能变成sum/n, 是吧…..脑筋急转弯

Educational Codeforces Round 110 (Rated for Div. 2)C. Unstable String

给一个字符串, 里面有0,1和?, ?可以是1或者0, 求这个字符串的子字符串中可以变成1和0 交替出现的字符串的个数. 这题就是counting问题, 做的时候用的dp, 想了半天都有错, 后来想想, ?基本没啥用的地方, 因为0和1交替出现的字符串就两种, 一种是0101或者1010…所以如果我们强制替换奇数位上的1变成0, 0变成1, 那么如果是以上两种, 就会变成0000或者1111, 所以我们只需要用两个指针count一下每个substring是否是答案即可.

Egg Drop With 2 Eggs and N Floors

给两个鸡蛋和n层楼, 已知一个鸡蛋从x层楼掉下去不会碎,但是从x+1层就会碎 求最少多少次扔鸡蛋可以知道x是多少. 典型的dp题, 可以用一个memo存当前的状态: 首先, 如果只有一个鸡蛋, 那么测n层楼需要测n次. 这里不用binary search, 因为我们的求的是最少多少次扔鸡蛋, 而binary search不一定能找到正确的解, 最坏情况我们还是要扔n次. 转移方程中, 两个状态是:1. 扔了没有碎, x肯定在当前i floor的上边: drop(egg, floor – i), 2. 扔了碎了, x肯定在当前i floor的下边 drop(egg – 1, i – 1). 因为同样数量的move下,我们需要找的是两个解中, 最”高”的一层所以取两个状态的max. 然后和当前的所有状态中的每个状态取min.

Distribute Coins in Binary Tree

给一个二叉树, 然后给一个node的值是coin的数量, 求把这个coins分给每个node需要几步, 一步只能往下推一个node. 这题就是divide and conquer, 例题给的很明确, 如果是root有3个, 左右是0, 那么分下去需要2步(给左边一个, 给右边一个), 这题还给了一共n个node和n个coin, 所以不存在溢出的情况. 所以只需要计算left和right的和-1 就是需要的步骤.

Finding Pairs With a Certain Sum

给两个数组设计一个数据结构, 可以add一个数字到第二个数组, 还有count两个数组的数字等于total有几对儿. 这个就是第一个数组大, 第二个小, 所以先处理大的数组. 然后count的时候直接减一下即可.

Rotating the Box

各一个2d数组, 里面有石头, 空格和障碍, 求右转90度后, 石头落下, 数组的状态. 这题先转90度, 然后从下往上看到空格就往上找石头然后swap, 注意检查边界.

Older Posts

书脊

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