leetcode hot100_part25

2024/4/23

56.合并区间

略

189.轮转数组

使用额外数组

        遍历老数组，每个位置的元素放到新数组的位置（取余）。

环状替换

        这个思路也想到了但是没想出来。

        也就是连续跳，从i位置跳到它应该在(取余后)的位置x，再从x位置开始跳，这么一直进行下去直到再次跳回 i 位置。但是只是这一次并不能覆盖所有的元素。

        继续从i+1位置重复上述步骤，直到跳回i+1位置。

        如果要得到这个过程重复的次数，就要知道每一趟遍历多少个元素，设为x。暂时不知道咋算可以先设置变量count，每遍历一个+1，直到count == length。x一定是小于k的。

        一趟走过的路长s，一定是数组长度和k的整数倍，由于是第一次回到i位置，所以s为nums.length和k的最小公倍数，那么 x = s/k。最后算出来重复次数为n 和 k的最大公约数即gcd(n,k)。gcd怎么求？

翻转

        先整体，再前k个，再剩下length - k 个。翻转三次。

        翻转的思路就是交换首尾直至中间位置。

        

238.除自身以外数组的乘积

空间复杂度O(n)

        和第一印象一样，既然不让用除法，那么就找 i 位置前面的数和后面的数的乘积，设置两个等长数组，前缀和后缀数组，长度为nums.length，前缀数组表示从0到位置i所有元素的乘积（包含位置i），后缀数组表示从最后一个数到位置i的乘积。计算位置i的结果用相邻位置的前后缀相乘。

        官方解法里前后缀数组表示的是 i 位置之前元素累乘（0~ i-1 ）和最后一个元素到i+1位置的累乘，不包括 i 位置。

空间复杂度O(1)

        总体的思路还是一样的，就是先让前缀乘积数组充当结果数组，然后再从数组尾部遍历，乘上该位置的后缀积，只是后缀积是用一个变量迭代的。