Day 7 | 7/4

[tech-cow]

今日任务 (Two Pointers)

• 用Easy试水。
• 搜集资源，看视频/总结

刷题

Leetcode

• 344 Reverse String
• 283 Move Zeroes
• 167 Two Sum II - Input array is sorted
• 125 Valid Palindrome
• 345 Reverse Vowels of a String

[tech-cow]

Leetcode

344. Reverse String

类型：斗鸡眼
Time Complexity O(n)
Space Complexity O(n)

虽然说可以直接秒....: return s[::-1]
Two Pointers比较好理解，最左和最右不同换即可。

class Solution:
    def reverseString(self, s):
        arr = list(s)
        l , r = 0 , len(s) - 1
        while l < r :
            arr[l], arr[r] = arr[r], arr[l]
            l += 1
            r -= 1
        return ''.join(arr)

283. Move Zeroes

类型：龟兔赛跑
Time Complexity O(n)
Space Complexity O(1)

同一方向的Two Pointers，快的指针每次遇到一个不为0的数，就和幔的指针进行交换。

class Solution:
    def moveZeroes(self, nums):
        slow, fast = 0 , 0 
        while fast <= len(nums) - 1:
            if nums[fast] is not 0:
                nums[slow], nums[fast] = nums[fast], nums[slow]
                slow += 1
            fast += 1

167. Two Sum II - Input array is sorted

类型：斗鸡眼
Time Complexity O(n)
Space Complexity O(1)

这题还可以用二分，以下是Two Pointers答案

class Solution:
    def twoSum(self, nums, target):
        l , r = 0 , len(nums) - 1
        while l < r:
            s = nums[l] + nums[r]
            if s == target:
                return(l+1, r+1)
            if s < target:
                l += 1
            else:
                r -= 1

不行，还是强迫性的练一下二分吧：

Binary Search O(nlogn)

class Solution:
    def twoSum(self, nums, target):
        for i , num in enumerate(nums):
            l , r = i + 1, len(nums) - 1
            temp = target - nums[i]
            while l <= r:
                mid = l + (r-l)//2
                if nums[mid] == temp:
                    return [i+1, mid+1]
                if nums[mid] < temp:
                    l = mid + 1
                else:
                    r = mid - 1

125. Valid Palindrome

类型：斗鸡眼
Time Complexity O(n)
Space Complexity O(1)

isalnum() 用来去掉一些障碍物，然后缩进双指针

class Solution:
    def isPalindrome(self, s):
        l, r = 0, len(s) - 1
        while l < r:
            if not s[l].isalnum():
                l += 1
            elif not s[r].isalnum():
                r -= 1
            else:
                if s[l].lower() != s[r].lower():
                    return False
                else:
                    l += 1
                    r -= 1
        return True

345. Reverse Vowels of a String

类型：斗鸡眼
Time Complexity O(n)
Space Complexity O(1)

这题第一次做的时候没有把大写考虑进去，其他和楼上基本上一样。

class Solution:
    def reverseVowels(self, s):
        dic = set(list("aeiouAEIOU"))        
        arr = list(s)
        l , r = 0, len(s) - 1
        while l < r:
            if arr[l] not in dic:
                l += 1
            elif arr[r] not in dic:
                r -= 1
            else:
                arr[l] , arr[r] = arr[r], arr[l]
                l += 1
                r -= 1
        return ''.join(arr)