leetcode 刷题记录

leetcode27 移除元素

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums) == 0:
            return 0
        
        l = 0
        r = len(nums) -1
        while l < r:
            # 找左边等于val的元素
            while(l<r and nums[l]!=val):
                l += 1
            # 找右边不等于val的元素
            while (l<r and nums[r] == val):
                r -= 1
            # 将右边不等于val的元素覆盖左边等于val的元素
            nums[l], nums[r] =nums[r], nums[l]

            print(nums)
            if nums[l] == val:
                return l
            else:
                return l+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        if nums is None or len(nums) == 0:
            return 0
        
        fast = slow = 0

        while fast < len(nums):
            if nums[fast] != val:
                nums[slow] = nums[fast]
                slow += 1
            
            # 当fast指针遇到要删除的元素时停止赋值
            # slow指针停止移动，fast指针继续前进

            fast += 1
        
        return slow
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

leetcode977 有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回 每个数字的平方 组成的新数组，要求也按 非递减顺序 排序。

示例 1： 输入：nums = [-4,-1,0,3,10] 输出：[0,1,9,16,100] 解释：平方后，数组变为 [16,1,0,9,100]，排序后，数组变为 [0,1,9,16,100]

示例 2： 输入：nums = [-7,-3,2,3,11] 输出：[4,9,9,49,121]

解题思路：
数组其实是有序的， 只不过负数平方之后可能成为最大数了。

那么数组平方的最大值就在数组的两端，不是最左边就是最右边，不可能是中间。

此时可以考虑双指针法了，i指向起始位置，j指向终止位置。

定义一个新数组result，和A数组一样的大小，让k指向result数组终止位置。

两边数字比较，指针往中间开始移动。

如果A[i] * A[i] < A[j] * A[j] 那么result[k–] = A[j] * A[j]; 。

如果A[i] * A[i] >= A[j] * A[j] 那么result[k–] = A[i] * A[i]; 。

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        i, j, k =0, n-1, n-1
        ans = [-1] * n
        while i <= j:
            lm = nums[i] ** 2
            rm = nums[j] ** 2
            if lm > rm:
                ans[k] = lm
                i += 1
            else: 
                ans[k] = rm 
                j -= 1
            k -= 1
        return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16