Menu Sidebar
Menu

Number of Students Unable to Eat Lunch

给两个数组, 一个数组是学生, 一个数组是三明治, 问轮转学生数组后, 有多少学生没有三明治吃

这个是个模拟题, 模拟一下即可.

Determine if String Halves Are Alike

给一个string, 问二分后, 是不是包含相同数目的元音字符.

Non-decreasing Array

给一个数组, 求能不能只改变一个元素, 使得数组变成非递减数组.

主要是很多corner cases. 考虑到了就可以

Poj 3270 Cow Sorting

给一个数组,求通过两两交换后排序这个数组, 交换有代价, 代价是交换的两个元素之和, 求排序的最小代价.

这个题我第一眼看是dp的问题, 但是很难考虑边界的元素交换, 而且很容易超时. 后来看了看答案, 原来是群论的置换群问题, 后来补了补. 发现也不是置换群, 只是单纯的置换中的轮换的概念, 关键是从哪个角度看待问题的本质(排序).

首先看置换群的概念在这里的应用, 拿例题举例:

由例子可以得知, 上面的例子最好的解法是: 取最小的数字作为媒介与其他数字做交换, 得到的成本是最小的.

然而这并不是唯一的最优解, 考虑一下的例子:

这个例子中, 可以把一个数组写成两个三阶置换, 那么对与[1,3,2],交换最小的成本并不是1与其他两个数的交换, 而是把0(全数组中最小的数字)先和1(当前数组最小数字)交换, 然后再次交换.这个最优解我没有想到

下面是如何计算最优解一:

最优解二:

答案在两个最优解中选最小的成本.

最后还有个技巧, 就是如何找到一个数组的index在排序后的对应index, 这里要用counting sort, 在counting sort中取count和的时候, 可以找到index的位置.

Make Sum Divisible by P

给一个数组nums和一个p, 求删去最小的子数组后的数字和可以整除p.

let s = sum of nums, r = s mod p -> r = (s + p) mod p

因为我们知道presum可以用两个指针表示其中间隔的和. let (i, j) = indexs in presum where 0 <=i <= j <= presum.length.

since r = (s + p) mod p, then r = (pre[j] – pre[i] + p) mod p

因为我们知道2sum中, 两个index可以用O(n)的space换取O(n^2) -> O(n)的时间.

since r = (pre[j] – pre[i] + p) mod p, then pre[i] =(pre[j] – r + p) % p;

所以我们用map存pre[i]即可

Maximum Height by Stacking Cuboids

给一些砖块的长宽高, 可以旋转, 问怎么摆放可以有最高的高度, 求高度.

这个题虽然可以旋转, 但是其实因为限制: 必须完全小于长宽高的砖块才能放到另一个砖块上边. 所以没有旋转没有任何意义. 通过排序, 找到最长的, 然后再通过排序找到最大的. 即可做dp.

设dp[i]是包含砖块i作为可用砖块的最佳规划方案. 那么dp[i] = max{dp[j], where j < i and (i,j) meet requirements} 这个是bottom-up.

Partitioning Into Minimum Number Of Deci-Binary Numbers

定义了一个数组叫deci-binary, 是decimal, 并且有没有leading zeros的1和0组成, 问这个数字的和组成n.

这个题主要是读懂题, 问的其实只是怎么组成n, 因为只有1和0, 那么看n的最大的digit的大小即可.

Count of Matches in Tournament

给一个由n个team组成的比赛, 如果n是偶数, 则进行n/2个比赛, 如果n是奇数则进行(n – 1)/2 +1个比赛,问一共要有多少比赛才能决定胜者.

Sum of Absolute Differences in a Sorted Array

给一个排序好的数组, 求里面某个数字的与其他数字的绝对值之和.

这个题通过观察就可以看出来是前序和+后序和, 但是因为前序和后序是从两侧算的, 所以要通过减法使得从数字当前坐标开始计算.

Newer Posts
Older Posts

书脊

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