【LeetCode】【Two Pointers】squares of a sorted array

2024-03-30 23:28:21

题目：

给定一个以非降序排序的整数A数组，返回每个数字的平方的数组，也以非降序排序。

Example 1:

Input: [-4,-1,0,3,10]
Output: [0,1,9,16,100]

Example 2:

Input: [-7,-3,2,3,11]
Output: [4,9,9,49,121]

Note:

1 <= A.length <= 10000
-10000 <= A[i] <= 10000
A is sorted in non-decreasing order.

【解法】

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        answer = collections.deque()
        l, r = 0, len(A) - 1
        while l <= r:
            left, right = abs(A[l]), abs(A[r])
            if left > right:
                answer.appendleft(left * left)
                l += 1
            else:
                answer.appendleft(right * right)
                r -= 1
        return list(answer)

Runtime: 248 ms, faster than 49.87% of Python3 online submissions for Squares of a Sorted Array. Memory Usage: 15.7 MB, less than 51.20% of Python3 online submissions for Squares of a Sorted Array.

为什么不能这样？

class Solution:
    def sortedSquares(self, A: List[int]) -> List[int]:
        B = [0]*len(A)
        for i in range(0,len(A)):
            B[i] = A[i]*A[i]
        return B.sort()

双指针

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。

换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

解决双指针问题三种常用思想：左右指针：需要两个指针，一个指向开头，一个指向末尾，然后向中间遍历，直到满足条件或者两个指针相遇。适用于有序数组，也就是说档题目给定有序数组时，第一时间想到用左右指针解题。伪代码大致如下：

def function(self,list=A):
    left = 0
    right = len(A) - 1
    
    #遍历数组
    while left <= right: #一般循环结束的条件是判断两指针是否相遇
        left += 1
        #条件判断和处理
        
        right -= 1
    return answer

以LeetCode 881救生艇问题为例

由于本题只要求计算出最小船数，所以原数组是否被改变，和元素索引位置都不考虑在内，所以可以先对于给定数组进行排序，再从数组两侧向中间遍历。所以解题思路如下：

对给定数组进行升序排序
初始化左右指针
每次都用一个”最重的“和一个”最轻的“进行配对，如果二人重量小于Limit，则此时的”最轻的“上船，即（left++）。不管”最轻的“是否上船，”最重的“都要上船，即（right--）并且所需船数量加一，即（num++）

代码如下：

var numRescueBoats = function(people, limit) {
people.sort((a, b) => (a - b));
var num = 0
let left = 0
let right = people.length - 1
while (left <= right) {
    if ((people[left] + people[right]) <= limit) {
      left++
    }
    right--
    num++
}
return num
};

　　
快慢指针：需要两个指针，开始都指向开头，根据条件不同，快指针走得快，慢指针走的慢（如快指针每次走两步，慢指针每次走一步），直到满足条件或者快指针走到结尾。

以LeetCode 141.环形链表为例,，判断给定链表中是否存在环，可以定义快慢两个指针，快指针每次增长一个，而慢指针每次增长两个，最后两个指针指向节点的值相等，则说明有环。就好像一个环形跑道上有一快一慢两个运动员赛跑，如果时间足够长，跑地快的运动员一定会赶上慢的运动员。

解题代码如下：

后序指针：常规指针操作是从前向后便利，对于合并和替换类型题，防止之前的数据被覆盖，双指针需从后向前便利以LeetCode 88 Merge sorted array为例，题目要求：给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1中，使得 num1 成为一个有序数组。你可以假设 nums1有足够的空间（空间大小大于或等于m + n）来保存 nums2 中的元素。在 nums1 和 nums2 中初始化的元素的数量分别是 m 和 n。
题目分析：算法思想是：由于合并后A数组的大小必定是m+n，所以从最后面开始往前赋值，先比较A和B中最后一个元素的大小，把较大的那个插入到m+n-1的位置上，再依次向前推。如果A中所有的元素都比B小，那么前m个还是A原来的内容，没有改变。如果A中的数组比B大的，当A循环完了，B中还有元素没加入A，直接用个循环把B中所有的元素覆盖到A剩下的位置。
题目解答：
记忆口诀：左右指针中间夹，快慢指针走到头，后序指针往回走
————————————————

原文链接：https://blog.csdn.net/pushup8/java/article/details/85071735
原文链接：https://blog.csdn.net/pushup8/java/article/details/85071735 参考：https://hk029.gitbooks.io/leetbook/twopoint.html

码农公寓

相关文章