Day5.1 剑指 Offer 04. 二维数组中的查找

在一个 n m 的二维数组中，
每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。
请完成一个高效的函数，
输入这样的一个二维数组和一个整数，*判断数组中是否含有该整数。

方案1：利用python的内置特点：

  1. class Solution:
  2.     def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
  3.         for i in range(len(matrix)):
  4.             if target in matrix[i]:
  5.                 return True
  7.         return False


执行用时：44 ms, 在所有 Python3 提交中击败了38.40%的用户
内存消耗：18.9 MB, 在所有 Python3 提交中击败了56.15%的用户

方案2：构建左右树

时间上来说就不太好，题目的本意也不是用这样的方法image.png
这个思路牛逼，而且很快
其实从[0,0] 开始也完全没问题 — 不行 只能从方法上给的两个点来

实现一下：

  1. class Solution:
  2.     def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
  3.         # 输入为空
  4.         if len(matrix) == 0 or len(matrix[0]) == 0 :
  5.             return False
  7.         i,j = 0,len(matrix[0])-1
  9.         while(i < len(matrix) and j >= 0 ):
  10.             if matrix[i][j] == target:
  11.                 return True
  13.             if matrix[i][j] < target:
  14.                 i +=1
  15.             else:
  16.                 j -=1
  17.         # 超出索引
  18.         return False

执行用时：40 ms, 在所有 Python3 提交中击败了59.60%的用户
内存消耗：18.8 MB, 在所有 Python3 提交中击败了77.09%的用户

Day5.2 剑指 Offer 11. 旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素

这个题描述的真别扭，这个描述的害行 153. 寻找旋转排序数组中的最小值
就是给个数组，求最小值，对时间有点要求
不同的是这个数组是顺序递增的，而且被旋转了几个单位 — 利用这个特点

其实利用这个特点 — 找到某个值的左边比它的右边大，右边的值就是这个最小值
找这个值有两种方案

  • 直接遍历对比查找
  • 二分查找

看了一下二分查找 SO— COOL

  1. class Solution:
  2.     def minArray(self, numbers: List[int]) -> int:
  3.         low = 0
  4.         high = len(numbers) -1
  5.         while(low < high):
  6.             mid = low + (high -low)//2
  7.             # 仅考虑 左边即可
  8.             if numbers[mid] < numbers[high]:
  9.                 high = mid
  10.             # 仅考虑 右边即可
  11.             elif numbers[mid] > numbers[high]:
  12.                 low = mid +1 
  13.             # 中间和端点相等则 端点收一收 
  14.             else:
  15.                 high -= 1
  17.         return numbers[low]

Day5.3 剑指 Offer 50. 第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母

方案1：n方的方法

索引每一个元素后，将其在字符串中删除，然后再检查剩下的里面还有没有这个元素。。

缺点显而易见。。。极其慢

方案2：遇到仅一次就是哈希表

空间是1
时间是2n

这题只有在遍历完所有的元素才知道某个元素是否是第一次出现（最坏的情况是它在最后一个元素位置上）

问题点：哈希表是无序的。。如何辨别第一个

  • 分两步
    • 第一步建立表
    • 第二步检索表
    • 时间2n
  1. class Solution:
  2.     def firstUniqChar(self, s: str) -> str:
  3.         letter_map = {}
  4.         # 建立表
  5.         for letter in s:
  6.             if letter not in letter_map:
  7.                 letter_map[letter] = 1
  8.             else:
  9.                 letter_map[letter] +=1
  11.         # 检索表
  12.         for letter in s:
  13.             if letter_map[letter] == 1:
  14.                 return letter
  16.         return ' '

执行用时：104 ms, 在所有 Python3 提交中击败了40.24%的用户
内存消耗：15 MB, 在所有 Python3 提交中击败了84.52%的用户

2n的时间 看起来确实不太聪明。。空间害行。。

改进方案2

其实问题就在如何判断是第一个只出现一次的值
解决方案：

  • 当字母第一次出现时，把其索引作为键值存储
  • 如果第二次出现，将键值改为-1
  • 最后返回键值不为-1，且索引最小的值

总共就26个字母，就算全算上也没有多大的量，时间从2n ,变成n
[这里找到这个索引的最小值不好搞]

class Solution:
    def firstUniqChar(self, s: str) -> str:
        letter_map = {}
        # 建立表
        for index,letter in enumerate(s):
            if letter not in letter_map:
                letter_map[letter] = index
            else:
                letter_map[letter]  = -1

        # 查找字母表 -- 两处点睛之笔
        target_ = len(s)
        for  pos in letter_map.values(): # 1. 比较值 而不是键
            if pos != -1 and pos < target_:
                target_ = pos

        if target_ == len(s):
            return ' '
        else:
            return s[target_]  # 2. 利用原表的位置

空间基本没增加，还是1
时间变成了n