Intersection of Multiple Arrays
给几个数组, 求所有数字重复的, 并且排序.
给几个数组, 求所有数字重复的, 并且排序.
上课问题, 拓扑排序, 但是这题可以在同一时间连续上课, 然后求最优. 因为可以并行上课, 所以是一道dp问题, dp[i]= max(max(dp[i],dp[i]+time[i]), dp[j]) j is the neighbor of i.
给一个数组, 找最小排序大小的子数组可让数组排序. 这题是双指针, 从左侧找最大值, 然后可以知道最大值右边的数字都是应该被sort的,因为如果是已经排序的数组, 最大值应该在最右侧. 同理, 我们再弄一个指针从右往左走. 然后去两个指针之差
定义了一些操作, 求复原perm数组的操作次数. 暴力解…也没有什么简化方法.
定义一个happy string, 求第k个字典序的happy string是什么. 暴力解, 好像没有什么简化方法.
给一个字符串s和一个字符串part, 删除所有part在s中的字符. 这题就暴力做即可.
给一个string, 里面是0和1, 给一个操作, 可以flip所有在i后的字符, 求最少flip几次. 这题通过观察, 可以发现如果从左往右考虑, 从0到1的flip和从1到0的flip, 其实都不会影响左边已经flip过的字符, 故操作次数只与当前的字符是不是和前一个字符相同有关.
给一个board, 里面的’X’代表船的位置, 船和船之间隔着至少一个’.’, 问有几艘船 这题就dfs一下即可. 搜过的mark成’Y’
给一个数组, 有多少组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都是答案的选项.