Day 8 | 7/5

[tech-cow]

今日任务 (Two Pointers)

• 盲目冲撞第二天，明天开始看总结和其他资源。

刷题

Leetcode

• 844 Backspace String Compare
• 88 Merge Sorted Array
• 26 Remove Duplicates from Sorted Array
• 141 Linked List Cycle

[tech-cow]

Leetcode

844. Backspace String Compare

解法: Stack

Time Complexity O(m + n)
Space Complexity O(m + n)

刚开始试着思考这题的Two Pointers算法，没有思路，却发现这个题的性质特别符合Stack，就用Stack先解决了。当char is not '#'的时候要缩减，这和Stack的pop一个性质。

class Solution:
    def backspaceCompare(self, S, T):
        l1 = self.stack(S, [])
        l2 = self.stack(T, [])
        return l1 == l2
        
    
    def stack(self, S, stack):
        for char in S:
            if char is not "#":
                stack.append(char)
            else:
                if not stack:
                    continue
                stack.pop()
        return stack

解法: Two Pointers

类型：从右往左Index
Time Complexity O(n)
Space Complexity O(1)

解题思路：
对两个字符串从右往左遍历，用子方程getChar() 从两个字符串分别取值，如取值不等则返回False，相等就继续迭代，知道迭代技术返回True

子方程getChar()的取值规则：

While循环退出条件：下标出界或者返回值不为空。

Case 1: 当值等于#, count增值
Case 2: 如果count == 0 说明这个值没有被#给抵消，返回
Case 3: 如果count != 0 切这个值不为#，这个值要被#抵消掉
三个Case运行完后，记得锁紧下标r

class Solution(object):
    def backspaceCompare(self, S1, S2):
        r1 = len(S1) - 1 
        r2 = len (S2) - 1
        
        while r1 >= 0 or r2 >= 0:
            char1 = char2 = ""
            if r1 >= 0:
                char1, r1 = self.getChar(S1, r1)
            if r2 >= 0:
                char2, r2 = self.getChar(S2, r2)
            if char1 != char2:
                return False
        return True
        
    
    def getChar(self, s , r):
        char, count = '', 0
        while r >= 0 and not char:
            if s[r] == '#':
                count += 1
            elif count == 0:
                char = s[r]
            else:
                count -= 1
            r -= 1
        return char, r

88. Merge Sorted Array

类型: 从左往右，双数组普通遍历
Time Complexity O(m + n)
Space Complexity O(1)

Naive Attempt, 以下代码有BUG

class Solution:
    def merge(self, nums1, m, nums2, n):
        r1, r2, end = m-1, n-1, m+n-1
        while r1 >= 0 or r2 >= 0:
            if nums1[r1] >= nums2[r2]:
                nums1[end] = nums1[r1]
                r1 -= 1
            else:
                nums1[end] = nums2[r2]
                r2 -= 1
            end -= 1

第一次写的时候，没有考虑到当r2缩减为-1的时候，nums2[r2] = nums2[-1] = nums2数组的最后一位value, 如果nums2[-1]的值大于nums1[0]，就会覆盖掉nums1[0]的值，具体看下图：

所以为了解决这个问题，将while loop的判定条件从原来的
while r1 >= 0 or r2 >= 0
变成
while r1 >= 0 and r2 >= 0

然后再对r1 = -1的Edge单独处理，得到以下Accepted Solution：

class Solution:
    def merge(self, nums1, m, nums2, n):
        r1, r2, end = m-1, n-1, m+n-1
        while r1 >= 0 and r2 >= 0:
            if nums1[r1] >= nums2[r2]:
                nums1[end] = nums1[r1]
                r1 -= 1
            else:
                nums1[end] = nums2[r2]
                r2 -= 1
            end -= 1
        if r1 < 0:
            nums1[:r2+1] = nums2[:r2+1]

26. Remove Duplicates from Sorted Array

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

slow的下标代表着Unique值的下标，fast用来遍历并且寻找下一个Unique的值，找到以后赋值给nums[slow+1]
slow+1这个下标代表的是下一个Unique的值，当nums[fast] != nums[slow]成立以后，自然符合这个要求。

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

141. Linked List Cycle

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

龟兔赛跑的经典题

class Solution(object):
    def hasCycle(self, head):
        fast = slow = head
        while fast and fast.next:
            fast = fast.next.next 
            slow = slow.next
            if slow is fast:
                return True
        return False