Menu Sidebar
Menu

Leetcode

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都是答案的选项.

Newer Posts
Older Posts

书脊

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

April 2025
M T W T F S S
 123456
78910111213
14151617181920
21222324252627
282930