Menu Sidebar
Menu

Interview Question

Parallel Courses III

上课问题, 拓扑排序, 但是这题可以在同一时间连续上课, 然后求最优. 因为可以并行上课, 所以是一道dp问题, dp[i]= max(max(dp[i],dp[i]+time[i]), dp[j]) j is the neighbor of i.

Shortest Unsorted Continuous Subarray

给一个数组, 找最小排序大小的子数组可让数组排序. 这题是双指针, 从左侧找最大值, 然后可以知道最大值右边的数字都是应该被sort的,因为如果是已经排序的数组, 最大值应该在最右侧. 同理, 我们再弄一个指针从右往左走. 然后去两个指针之差

Minimum Suffix Flips

给一个string, 里面是0和1, 给一个操作, 可以flip所有在i后的字符, 求最少flip几次. 这题通过观察, 可以发现如果从左往右考虑, 从0到1的flip和从1到0的flip, 其实都不会影响左边已经flip过的字符, 故操作次数只与当前的字符是不是和前一个字符相同有关.

Count Triplets That Can Form Two Arrays of Equal XOR

给一个数组, 有多少组triple(i,j,k), 可以让0<= i < j<k <=n中[i,j),[j,k]的xor相等. 这题挺有意思, 直接做就是O(N^3), 是可以过的. 然后考虑优化到O(N^2), 因为xor是半加符号, 所以可以想到是用presum的方法. 首先建立pre xor数组, 但是怎么用这个数组, 可以考虑一下, xor相等的意思是值为0, 所以如果有一个区间[i,k]中的xor为0, 那么这个区间里的所有j都是答案的选项.

Older Posts

书脊

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

May 2022
M T W T F S S
 1
2345678
9101112131415
16171819202122
23242526272829
3031