每日Leetcode—算法（5）

35. 搜索插入位置

示例 1:

输入: [1,3,5,6], 5，输出: 2
输入: [1,3,5,6], 2，输出: 1
输入: [1,3,5,6], 7，输出: 4

算法一：

def searchInsert(self, nums: List[int], target: int) -> int:
    if nums[0]>target:
        return 0
    if nums[len(nums)-1]<target:
        return len(nums)-1
    for i in range(len(nums)):
        if target == nums[i]:
            return i
        if nums[i]<target and target<nums[i+1]:
            return i+1

算法二：

lo = 0
hi = len(nums)-1
while lo<hi:
    mid = lo + (hi - lo)//2
    if nums[mid] < target:
        lo = mid + 1
    elif nums[mid] > target:
        hi = mid
    else:
        return mid
return lo

分析：该方法用了二分查找，时间复杂度为O（logN）

38.报数

1. 1
   

2. 11
   

3. 21
   

4. 1211
   

5. 111221
   

例如第一项为1，第二项有一个1，故写做11；第二项有两个1，故写做21......以此类推。

示例：

输入: 4，输出: "1211"

算法：

def countAndSay(self, n: int) -> str:
    if n == 1:
        return '1'
    if n == 2:
        return '2'
    pre = '11'
    for i in range(3,n+1):      #循环到n，实现第n次报数
        cou = 1
        res = ''
        for j in range(1,len(pre)):     #对上一次报数循环查看并报数
            if pre[j-1] == pre[j]: 
                cou+=1                #如果相等计数变量加一
            else:
                res+=str(cou)+pre[j-1]        #不相等将计数、数字添加到结果里
                cou = 1             #计数变量还原为1
        res += str(cou)+pre[j]         #将最后一个数添加到结果里
        pre = res         #结果赋值给pre，并进行循环。
    return pre