剑指 Offer 05. 替换空格

三种方法，replace函数

class Solution:
    def replaceSpace(self, s: str) -> str:
        return '%20'.join(s.split(' '))

class Solution:
    def replaceSpace(self, s: str) -> str:
        res = []
        for c in s:
            if c == ' ': 
                res.append("%20")
            else: 
                res.append(c)
        return "".join(res)

class Solution:
    def replaceSpace(self, s: str) -> str:
        # s.replace(' ',"%20") #没有赋值给s
        s = s.replace(' ',"%20")
        return s

剑指 Offer 58 - II. 左旋转字符串

字符串拼接

class Solution:
    def reverseLeftWords(self, s: str, n: int) -> str:
        seq = len(s)
        shift = n % seq #注意是移动数 除以 句子长度
        pre = s[ :shift]
        back = s[shift:]
        return back + pre

剑指 Offer 03. 数组中重复的数字

集合、字典的应用

class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        rep = {}
        for x in nums:
            if x not in rep:
                rep[x] = 1
            else:
                return x
                
class Solution:
    def findRepeatNumber(self, nums: [int]) -> int:
        dic = set()
        for num in nums:
            if num in dic: return num
            dic.add(num)
        return -1

剑指 Offer 53 - I. 在排序数组中查找数字 I

因为是排好序了，自然会想到二分搜索。
二分搜索其实重点是循环结束后，下标left和right代表的含义：
while left<=right: 所以最后一步可能是left

如果目标值大于mid，则left需往右走，（1）left+1 = right 或者 （2）left+1 > right。（1）情况会继续下一次循环。（2）代表left + 1一定大于目标值。

如果目标值小于mid，则right需往左走，（1）right-1 = left 或者 （2）right-1 < left。（1）情况会继续下一次循环。（2）代表right - 1一定小于目标值。

如果left==righ，如果目标值不等于mid， 也属于上面两种（2）的情况。
理解了这个规律，才好明白题解：
如果不存在目标值
最后的left一定大于目标值
最后的right一定小于目标值

class Solution:
    def search(self, nums: [int], target: int) -> int:
        # 搜索右边界 right
        i, j = 0, len(nums) - 1
        while i <= j:
            m = (i + j) // 2
            if nums[m] <= target: i = m + 1 # 因为目标值多个
            else: j = m - 1 
            # 目的是让i右移，就算找到target，i的前一个为target
        right = i
        # 若数组中无 target ，则提前返回
        if j >= 0 and nums[j] != target: return 0
        # 搜索左边界 left
        i = 0
        while i <= j:
            m = (i + j) // 2
            if nums[m] < target: i = m + 1 # 因为目标值多个
            else: j = m - 1  
            # 目的是让j左移，就算找到target，j的后一个为target
        left = j
        return right - left - 1

我的就只搜索目标值，在移动

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left, right = 0, len(nums)-1
        lens = right
        index = -1
        while left<=right: # 需要等号
            mid = int((left + right) / 2)
            if  nums[mid] == target:
                index = mid
                break
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        if index == -1:
            return 0
        count = 1
        l = r = index
        while l>0:
            if nums[l-1] == target:
                count += 1 
                l -= 1
            else:
                break
        while r < lens:
            if nums[r+1] == target:
                count += 1 
                r += 1
            else:
                break
        return count

剑指 Offer 53 - II. 0～n-1中缺失的数字

所以我还是不熟悉二分搜索的判断条件和left、right如何移动，返回的是left还是right。

class Solution:
    def missingNumber(self, nums: List[int]) -> int:
        left, right = 0, len(nums)-1
        # 死循环
        # while left < right:
        #     mid = (left + right) // 2
        #     if mid != nums[mid]:
        #         right = mid
        #     else:
        #         left = mid
        # return left
        while left <= right:
            mid = (left + right) // 2
            if mid != nums[mid]:
                right = mid - 1
            else:
                left = mid + 1
        return left