LeetCode-算法-双指针-第2天

977. 有序数组的平方

给你一个按非递减顺序排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
请你设计时间复杂度为 O(n) 的算法解决本问题
具体题目链接

Python（参考leetcode答案）

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        length=len(nums)
        left,right,povit,newnums=0,length-1,length-1,[0]*length
        while left<=right:
            if -nums[left]<nums[right]:
                newnums[povit]=nums[right]**2
                right-=1
            else:
                newnums[povit]=nums[left]**2
                left+=1
            povit-=1
        return newnums

思路：通过初始化新列表newnums来记录平方结果，序列是非递减顺序的，但不排除出现负数可能，例如[-2,-1,1],其中-2的平方就会大于1的平方。在此采用双指针，left从0出发，right从len(nums)-1出发，每次判断nums[left]的平方与nums[right]的平方（在本示例中是采用的-nums[left]<nums[right]来进行判断，原因：当存在负数时，-nums[left]为正，若不大于nums[right]，则平方也不会大于，反之同理。），povit倒序记录，因此每次取大。最终返回newnums。

GO（参考leetcode答案）

func sortedSquares(nums []int) []int {
    negative:=-1
    for i,j:=range nums{//寻找最后一个负数的下标
        if j<0{
            negative=i
        }else{
            break
        }
    }
    length:=len(nums)
    newnums:=make([]int,0,length)
    for left,right:=negative,negative+1;left>=0 || right<length;{
        if left<0{//所有负数已被使用完
            newnums=append(newnums,nums[right]*nums[right])
            right++
        }else if right==length{//所有非负数已被使用完
            newnums=append(newnums,nums[left]*nums[left])
            left--
        }else if -nums[left]<nums[right]{//普通情况下，先记录小的平方。
            newnums=append(newnums,nums[left]*nums[left])
            left--
        }else{
            newnums=append(newnums,nums[right]*nums[right])
            right++
        }
    }
    return newnums
}

思路：本方法通过寻找数组中最后一个负数的下标，来将一个数组分为负数数组和非负数数组，下标left取遍历负数数组、right取遍历非负数数组，负数数组从右向左的平方越来越大，非负数数组从左向右平方越来越大，因此每次选出小值，来添加到newnums中。最后返回newnums

189. 旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？
具体题目链接

思考

原本自己的思维是环状替换，例如[1,2,3,4,5,6,7]，k=3，则最后应该是[5,6,7,1,2,3,4],替换顺序是从下标为0开始，则依次是1->4->7->3->6->2->5。思想总是好的，但未能考虑到小环的情况[1,2,3,4,5,6],k=2,则会出现1->3->5->1,会有没遍历到的，虽然加if能解决，但又不得不考虑数组长度lenght=9,k=6时，转两圈成小环的，当然官网也给了相应方法，但感觉太过麻烦。
于是便被官网所提供的一个超级好方法所吸引。思路如下

nums = "----->-->"; k =3
result = "-->----->";
reverse "----->-->" we can get "<--<-----"
reverse "<--" we can get "--><-----"
reverse "<-----" we can get "-->----->"
this visualization help me figure it out :)

超级棒对不对，首先先把数组整体翻转，之后在将挪位到前面的数组部分翻转，挪位到后面的在翻转，即可。

Python（参考leetcode答案）

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        k%=len(nums)
        nums[:]=reversed(nums)
        nums[:k]=reversed(nums[:k])
        nums[k:]=reversed(nums[k:])

思路：python内置reversed翻转，但空间复杂度未知。

class Solution:
    def rotate(self, nums: List[int], k: int) -> None:
        length=len(nums)
        k%=length
        self.reverse(nums,0,length)
        self.reverse(nums,0,k)
        self.reverse(nums,k,length)

    def reverse(self,nums,index,end):
        end-=1#构造[index,end),使其符合python规律。
        while index<end:
            nums[index],nums[end]=nums[end],nums[index]
            index+=1
            end-=1

思路：自行构建reverse函数，通过提供数组、开始和结束下标。

GO（参考python答案）

func rotate(nums []int, k int)  {
    k%=len(nums)
    reversed(nums[:])
    reversed(nums[:k])
    reversed(nums[k:])
}
func reversed(nums []int){
    for i,length:=0,len(nums);i<length/2;i++{
        nums[i],nums[length-1-i]=nums[length-1-i],nums[i]
    }
}

思路：和python一样的reversed函数便不写了，这里因为GO语言切片传递的也是指针形式，因此只需要传递数组即可。剩余通过函数内判断。