1.练习题

1.1.两数之和 (opens new window)

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

class Solution:

  # # 方法一 借助hashmap
  def twoSum(self, nums: List[int], target: int) -> List[int]:
      
      hashdict= dict()

      for i in range(len(nums)):

          temp = target - nums[i]

          if temp in hashdict:
              return [i, hashdict.get(temp)]
          hashdict[nums[i]]= i

  # 暴力解法
  # def twoSum(self, nums: List[int], target: int) -> List[int]:

  #     for i in range(len(nums)):
  #         for j in range(i+1, len(nums)):
  #             if nums[i] + nums[j] == target:
  #                 return i, j
  

// Make sure to add code blocks to your code group

1.2. LRU 缓存 (opens new window)

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类： LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

笔记

hashmap + 双端队列

hashmap 中按照对应的key存储节点信息，在节保存key和value

class LinkedNode:
  
  def __init__(self, key=None, value=None, prev=None, nex=None):
      self.key = key
      self.value = value
      self.prev = prev
      self.nex = nex


class LRUCache:

  def __init__(self, capacity: int):
      self.capacity= capacity
      self.lru = dict()
      #  初始化两个节点作为首尾节点，并连接起来
      self.head = LinkedNode()
      self.tail = LinkedNode()
      self.head.nex = self.tail
      self.tail.prev = self.head

  def get(self, key: int) -> int:
      if key in self.lru:
          node = self.lru.get(key)

          self.node_to_tail(node)
          return node.value
      else: 
          return -1

  def put(self, key: int, value: int) -> None:

      if key in self.lru:  # to linkednode tail
          node = self.lru.get(key)
          node.value = value
          self.node_to_tail(node)
          return

      if len(self.lru) == self.capacity:
          
          # remove head
          node = self.head.nex
          del self.lru[node.key]
          print(self.head.nex.value, self.head.nex.value)
          self.remove_head_node(node)

      node = LinkedNode(key=key, value=value)
      self.lru[key] = node
      self.add_tail_node(node)
  def remove_head_node(self, node):
      """
      去除某个节点
      """
      # 开始移除
      
      node_prev = node.prev
      node_nex = node.nex
      node_prev.nex = node_nex
      node_nex.prev = node_prev


  def add_tail_node(self, node):
      """
      添加至末尾，此时需要保持尾节点不变
      """
      self.tail.prev.nex = node
      node.prev = self.tail.prev
      node.nex = self.tail
      self.tail.prev = node


  def node_to_tail(self, node):
      """
      将任意节点移动到尾部
      """
      self.remove_head_node(node)
      self.add_tail_node(node)

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

// Make sure to add code blocks to your code group

1.3. 最长连续序列 (opens new window)

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

笔记

借助hashmap

class Solution:
  """
  借助hashmap来实现
  """
  def longestConsecutive(self, nums: List[int]) -> int:

      if not nums:
          return 0
      max_len = 0
      nums_set = set(nums)
      
      for num in nums_set:
          pre_num = num -1

          
          if pre_num not in nums_set:
              temp_len = 1
              cur = num

              while cur+ 1 in nums_set:
                  cur +=1
                  temp_len += 1
              max_len = max(temp_len, max_len)
          
      return max_len
      

::: noite

动态规划解法

:::

class Solution:
  def longestConsecutive(self, nums: List[int]) -> int:
      res = 0
      hash_dict = dict()
      for num in nums:
          if num not in hash_dict:
              left = hash_dict.get(num-1, 0)
              right = hash_dict.get(num+1, 0)
              cur_lenght = left + right +1
              res = max(cur_lenght, res)
              hash_dict[num] = cur_lenght
              hash_dict[num-left]= cur_lenght
              hash_dict[num+right] = cur_lenght
      return res

// Make sure to add code blocks to your code group

1.4. 矩阵置零 (opens new window)

给定一个 *m* x *n* 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 (opens new window) 算法**。**

class Solution:
  def setZeroes(self, matrix: List[List[int]]) -> None:
      """
      Do not return anything, modify matrix in-place instead.
      """

      need_zero_raw = set()
      need_zero_col = set()
      for i in range(len(matrix)):
          for j in range(len(matrix[0])):
              if matrix[i][j] == 0:
                  need_zero_raw.add(i)
                  need_zero_col.add(j)
      
      for row in need_zero_raw:
          for j in range(len(matrix[0])):
              matrix[row][j] = 0

      for col in need_zero_col:
          for i in range(len(matrix)):
              matrix[i][col] = 0

// Make sure to add code blocks to your code group

笔记

一种改进方法是用矩阵得第一行和第一列来记录需要置为0得行列，如果某行得第一个元素为0则改行置为0，同理设置列

注意这样会改变行列得值，所以要提前判断第一行和第一列是否为0就可以了

1.5. O(1) 时间插入、删除和获取随机元素 (opens new window)

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象 bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。 bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。 int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。 你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

class RandomizedSet:

  # def __init__(self):
  #     self.data = set()

  # def insert(self, val: int) -> bool:
  #     if val not in self.data:
  #         self.data.add(val)
  #         return True
  #     else:
  #         return False

  # def remove(self, val: int) -> bool:
  #     if val in self.data:
  #         self.data.remove(val)
  #         return True
  #     else:
  #         return False

  # def getRandom(self) -> int:
  #     # 此方法list（）时间复杂度是O(n)
  #     return random.choice(list(self.data))
  def __init__(self):
      self.data = dict()
      self.end_index = -1
      self.nums = list()

  def insert(self, val: int) -> bool:
      if val not in self.data:
          self.end_index += 1
          self.data[val]= self.end_index
          self.nums.append(val)
          return True
      else:
          return False

  def remove(self, val: int) -> bool:
      if val in self.data:
          index = self.data.get(val)
          end_num = self.nums[self.end_index]

          # 不能执行删除， 需要执行交换，将最后一个元素换到index 位置，然后删除最后一个元素
          # 将end_index    -1
          self.nums[index] = end_num
          self.data[end_num] = index
          self.nums.pop()
          del self.data[val]
          self.end_index -= 1
          return True
      else:
          return False
  def getRandom(self) -> int:
      return random.choice(self.nums)
# Your RandomizedSet object will be instantiated and called as such:
# obj = RandomizedSet()
# param_1 = obj.insert(val)
# param_2 = obj.remove(val)
# param_3 = obj.getRandom()

// Make sure to add code blocks to your code group

1.6. 字母异位词分组 (opens new window)

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的字母得到的一个新单词，所有源单词中的字母通常恰好只用一次。

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/group-anagrams 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
  def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
      """
      使用hashmap
      """
      hashmap = collections.defaultdict(list)
      for str_ in strs:
          key= sorted(str_)
          key = "".join(key)
          hashmap[key].append(str_)
      return [val for _,val in hashmap.items()]

// Make sure to add code blocks to your code group

1.7. 猜数字游戏 (opens new window)

你在和朋友一起玩 猜数字（Bulls and Cows）游戏，该游戏规则如下：

写出一个秘密数字，并请朋友猜这个数字是多少。朋友每猜测一次，你就会给他一个包含下述信息的提示：

猜测数字中有多少位属于数字和确切位置都猜对了（称为 "Bulls"，公牛）， 有多少位属于数字猜对了但是位置不对（称为 "Cows"，奶牛）。也就是说，这次猜测中有多少位非公牛数字可以通过重新排列转换成公牛数字。 给你一个秘密数字 secret 和朋友猜测的数字 guess ，请你返回对朋友这次猜测的提示。

提示的格式为 "xAyB" ，x 是公牛个数， y 是奶牛个数，A 表示公牛，B 表示奶牛。

请注意秘密数字和朋友猜测的数字都可能含有重复数字。

class Solution:
  def getHint(self, secret: str, guess: str) -> str:
      a = b = 0

      secret_dict = collections.defaultdict(int)
      guess_dict = collections.defaultdict(int)
      for s, g in zip(secret, guess):
          # 公牛
          if s == g:
              a += 1

          else:
              secret_dict[s] += 1
              guess_dict[g] += 1
      # 统计母牛得个数
      for g in guess_dict:
          temp_num = min(guess_dict.get(g) , secret_dict.get(g,0))
          b += temp_num
          
      return "{a}A{b}B".format(a=a, b=b)

// Make sure to add code blocks to your code group

标题测试