ITPub博客

首页 > 应用开发 > Python > leetcode算法数据结构题解---数据结构

leetcode算法数据结构题解---数据结构

原创 Python 作者:ckxllf 时间:2021-03-03 16:09:57 0 删除 编辑

  05 替换空格

  解题思路:

  字符串是不可变类型,本题中需要替换字符串中的某个字符,可以使用replace方法直接替换;以下是遍历字符串的方式进行求解的,逐个判断字符串中的字符是否为空,若为空,将新字符串添加相应字符串;否则添加原来字符。该方法的时间复杂度为o(n)

  代码:

  class Solution:

  def replaceSpace(self, s: str) -> str:

  # return s.replace(' ', '%20')

  tmp = ''

  for i in range(len(s)):

  tmp += '%20' if s[i] == ' ' else s[i]

  return tmp

  class Solution {

  public String replaceSpace(String s) {

  StringBuilder res = new StringBuilder(); // 可变的字符串对象,没有线程安全

  for(Character c : s.toCharArray()){ // for写法,字符串转字符列表

  if(c == ' '){res.append("%20");} // 双引号

  else{res.append(c);}

  }

  return res.toString();

  }

  }

  在Java和python3中,string都是不可变类型,需要增加新变量来得到最后的结果。而C++是可变类型,通过s.resize()可以改变字符串长度,按照空格数改变字符串长度,然后从后往前寻找空格,往相应地方添加题目中要求的字符。

  class Solution {

  public:

  string replaceSpace(string s) {

  // 首先先确定空格的数量,然后更改字符串的长度,用两个指针从后往前遍历,如果遇到空格,从后往前将20%写上

  int len = s.size();

  int count = 0;

  for(char c : s){

  if(c == ' '){ // C++中单字符用单引号

  count++;

  }

  }

  s.resize(len + count * 2);

  for(int i=len-1,j=s.size()-1;i

  if(s[i] == ' '){

  s[j] = '0';

  s[j-1] = '2';

  s[j-2] = '%';

  j -= 2;

  }else{

  s[j] = s[i];

  }

  }

  return s;

  }

  };

  06 从尾到头打印链表

  我的思路就是逐个读取链表节点的value得到一个list,然后逆序输出list即可,时间复杂度和空间复杂度都是o(n)

  class Solution:

  def reversePrint(self, head: ListNode) -> List[int]:

  result = []

  # 正序读取O(n)

  while head is not None: # 可以简写为:while head:

  result.append(head.val)

  head = head.next

  # list逆序输出,下标操作

  return [result[len(result)-i-1] for i in range(len(result))]

  # python中list逆序可以直接通过切片实现

  # return result[::-1]

  解题方法:

  递归回溯法:

  若head不是空,那么逐个遍历链表,直到head为空时,再依次回溯回去。在python的代码中,我认为self.reversePrint()本身就是一个递归的机制,表示求某条链表的逆序。

  return self.reversePrint(head.next) + [head.val] if head else []

  辅助栈法:

  由于本题是单链表,需要逆序输出值,考虑到栈先进后出的原则,考虑用栈来解决此题。以上我的思路就是这种方法,在python中,使用list就足够。在Java中,需要使用LinkedList stack = new LinkedList()定义一个栈,然后stack.removeLast()出栈存储值。

  09 用两个栈实现队列

  首先,明确队列和栈的工作方式。队列是“先进先出”,栈是“先进后出”。本题需要完成两个功能,分别是添加和删除,即往队尾添加新元素,删除队首的元素。如果用一个栈来完成队列的操作,添加元素时,直接添加即可;删除元素时,弹出最后一个值(栈底元素)就需要逐个弹出所有元素。那么可以用一个栈完成添加操作,另一个栈逆序存储列表顺序,完成删除操作。在python中,可以直接用list作为栈。

  class CQueue:

  def __init__(self):

  # 初始化队列,即两个空栈

  self.A, self.B = [], []

  def appendTail(self, value: int) -> None:

  # 添加队尾元素

  self.A.append(value)

  def deleteHead(self) -> int:

  # 删除队首元素,并弹出该值

  if self.B: return self.B.pop()

  # 队列为空

  if not self.A: return -1

  # 将A逆序存储到B中

  while self.A:

  self.B.append(self.A.pop())

  return self.B.pop()

  # Your CQueue object will be instantiated and called as such:

  # obj = CQueue()

  # obj.appendTail(value)

  # param_2 = obj.deleteHead()

  此处注意一个点:判断列表是否为空时,直接if list,若True表示不空,Flase表示空。is not None表示对象不存在。

  20 表示数值的字符串

  请实现一个函数用来判断字符串是否表示数值(包括整数和小数)。例如,字符串"+100"、“5e2”、"-123"、“3.1416”、"-1E-16"、“0123"都表示数值,但"12e”、“1a3.14”、“1.2.3”、"±5"及"12e+5.4"都不是。

  暴力破解,逻辑判断,if-else堆砌:(没有得到最终答案,仍然考虑不全面)主要考虑小数点左右,e左右两侧的合格与否,判断两侧字符串是否为整数,存在给定字符中字符顺序导致的各种问题。

  class Solution:

  def __init__(self):

  self.mark = None

  def isNum(self, s):

  try:

  int(s) # 直接转为float就可以判断是否为数值型字符串了

  return True

  except ValueError:

  return False

  def split(self, s, c):

  pos = s.find(c)

  return s[:pos], s[pos + 1:]

  def isNumber(self, s: str) -> bool:

  sym = ['+', '-', '.', 'e', 'E']

  num = [repr(i) for i in range(10)]

  s = s.strip(' ')

  if self.isNum(s): return True # 若本身就是整数

  if s == '': return False

  # 保证字符在合法范围

  for c in s:

  # print(c)

  if c not in sym + num:

  return False

  for c in s:

  # 寻找小数点的位置,如果有一侧为整数暂时标记成True(方便1.,.2这种的)

  if c == '.':

  if s.count(c) <= 1:

  left, right = self.split(s, c)

  if right != '' and right[0] in ['+', '-']:

  return False # 小数点右侧不能有符号

  if (self.isNum(left) and right == '') or (self.isNum(right) and left == ''):

  return True # 1. .2

  elif self.isNum(left) and self.isNum(right):

  return True # 1.2

  else: return False

  # 寻找e的位置,再判断是否有小数点,然后判断完成直接return

  if c in ['e', 'E']:

  left, right = self.split(s, c)

  if (self.isNum(left) or (self.isNum(self.split(left, '.')[0]) or self.isNum(self.split(left, '.')[1]))) and self.isNum(right): # 左侧是整数/小数,右侧是整数

  self.mark = True

  # print('e', self.mark)

  else: self.mark = False

  return self.mark

  else: self.mark = False

  return self.mark

  haha = Solution()

  test = ['1.+2', '.-4', '9.-', '+++', '. 1', 'ee', ' ', '..', '12E', '1a3.12', '1.2.3', '+-1', '.', 'e', '1.0e', '.0e',

  '1e1.2', '1.2e3.4', # 都是False

  '1.0', ' .2', '1. ', '+5.4e3', '1.1e2', '0.e2', '123', '+12', '-12', '-1E-16', '5e2', '+.8'] # 都是True

  for i in test:

  print(i, haha.isNumber(i))

  官方解题方法::看着有一个好高级的名字,其实还是考虑各种情况!

  本题使用有限状态自动机。根据字符类型和合法数值的特点,先定义状态,再画出状态转移图,最后编写代码即可。空格[ ]、数字[0-9]、正负号[+, -] 、小数点[.]、幂符号[e, E]。

  状态定义:

  按照字符串从左到右的顺序,定义以下 9 种状态。

  开始的空格:字符串左右两侧的空格,内部空格按照其他字符处理,直接判为False

  幂符号前的正负号:幂符号左右都可以有正负号;幂符号后不能是小数;前后都不能为空

  小数点前的数字:小数点前后只能一处为空,另一处需要数字,小数点后不可有符号,小数点前可以正负号

  小数点、小数点后的数字

  当小数点前为空格时,小数点、小数点后的数字

  幂符号

  幂符号后的正负号

  幂符号后的数字

  结尾的空格

  结束状态:

  合法的结束状态有 2, 3, 7, 8

  补课

  24.翻转列表,输出新列表的头节点

  方法一:迭代双指针

  遍历单链表,修改next指针(时间复杂度为O(N),空间复杂度为O(1))

  # Definition for singly-linked list.

  # class ListNode:

  # def __init__(self, x):

  # self.val = x

  # self.next = None

  class Solution:

  def reverseList(self, head: ListNode) -> ListNode:

  cur, pre = head, None # 标记当前节点,前一节点

  while cur: # 若当前节点存在,执行循环体

  tmp = cur.next # 暂存下一节点

  cur.next = pre # 修改当前节点的方向为前一节点

  pre = cur # 修改当前按节点为前一节点,为下一次循环做准备

  cur = tmp # 将下一节点作为下一次的当前节点

  return pre

  方法二:递归回溯法

  考虑使用递归法遍历链表,当越过尾节点后终止递归,在回溯时修改各节点的 next 引用指向。(时间复杂度、空间复杂度均为O(N))。递归就是将一部分重复的操作提取出来,函数内部调用自身的方式进行简单的循环,设置递归出口以及返回值即可。以下操作,就是逐步遍历整条单链表,直到找到最后一个节点,然后用res标记反链的头节点(在找到最后一个节点,发现cur为None的时候,res获得了返回值pre,此时的pre为最后一个节点,之后res一直没有改变),然后依次改变前面几对节点的连接方向。

  class Solution:

  def reverseList(self, head: ListNode) -> ListNode:

  def reverse(cur, pre): # 交换两个节点的方向

  if not cur: return pre # 递归出口

  res = reverse(cur.next, cur) # 递归

  cur.next = pre # 执行操作

  return res

  return reverse(head, None)

  30 包含 min 函数的栈

  包含 min 函数的栈:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

  在python中,list就可以当作是一个栈,并且list本身就包含pop,push,min方法。如果自己实现这个程序,寻找最小值可能最容易想到的就是遍历比较,这样需要消耗的时间复杂度为O(N)。那么,题目的难点就在于min的复杂度压缩。我们可以设置一个最小值辅助栈来实现,在压栈出栈的过程中,就按照大小顺序将元素压入另一个栈中。解析:易出错的点在于压栈的时候,需要将小于等于当前最小值的元素都压入B栈,否则一旦pop出去,就会出错

  class MinStack:

  def __init__(self):

  """

  initialize your data structure here.

  """

  self.A, self.B = [],[]

  def push(self, x: int) -> None:

  self.A.append(x) # x压栈

  if not self.B or x <= self.B[-1]: # 若x小于B中的最小值,那么压入B;否则不压

  self.B.append(x)

  def pop(self) -> None:

  if self.A.pop() == self.B[-1]:

  self.B.pop()

  def top(self) -> int:

  return self.A[-1]

  def min(self) -> int:

  return self.B[-1]

  # Your MinStack object will be instantiated and called as such:

  # obj = MinStack()

  # obj.push(x)

  # obj.pop()

  # param_3 = obj.top()

  # param_4 = obj.min()

  35. 复杂链表的复制

  在复杂链表中,每个节点除了有一个next指针指向下一个节点,还有一个random指针指向链表中的任意节点或者null。

  

  复制分为两类,分别是浅复制和深复制。浅复制为复制头节点;深复制为复制所有节点和连接关系,修改复制链表时原链表不受影响,二者完全独立。在python中可使用的方法:copy.deepcopy(head)。解析1;解析2

  将含有多个指针的链表看作有向图来处理,通过DFS和BFS两种方式递归解决。

  35.1 DFS:通过递归拷贝所有next节点和random节点,用字典存储

  class Solution:

  def copyRandomList(self, head: 'Node') -> 'Node':

  # return copy.deepcopy(head) import cop

  def dfs(head):

  if not head: return None

  if head in visited:

  return visited[head]

  newNode = Node(head.val, None, None) # 定义一个新节点

  visited[head] = newNode

  newNode.next = dfs(head.next)

  newNode.random = dfs(head.random)

  return newNode

  visited = {}

  return dfs(head)

  执行过程:先不看newNode.random=dfs(head.random)这一句

  递归:dfs(7) -> 7 -> dfs(13) -> 13 -> dfs(11) -> 11 -> dfs(10) -> 10 -> dfs(1) -> 1 -> dfs(None)【递归的过程创造了7 13 11 10 1五个独立的节点,然后创建了5对原链表节点和新节点的映射】

  回溯:dfs(None)得到返回值None,因此newNode(1).next = None -> 执行return newNode,因此newNode(10).next = 1 -> 依次进行,得到了7->13->11->10->1->None

  最后分析random的递归回溯过程,此处newNode.random的值是通过if head in visited:return visited[head]获得返回值的,在next遍历的过程中,在字典中存储了所有的节点对{7:7, 13:13, 11:11, 10:10, 1: 1},即得到dfs(1)=1,dfs(10)=10,…

  35.2 哈希表方式

  深度拷贝单链表:顺着next遍历这条链表,用当前节点的值创建新节点,建立“源节点”和“新节点”之间的映射关系,然后按照源节点的连接方式对新节点进行连接即可。(标记新节点的前驱节点pre的next为新节点,然后当前节点后移,前驱节点更新为新节点。)

  class Solution:

  def copyRandomList(self, head: 'Node') -> 'Node':

  if not head:return

  # 形成{原:新}映射,dict[原节点] = 新节点

  cur = head # 对链表处理时,一定要将head存起来

  visited = {}

  while cur:

  visited[cur] = Node(cur.val)

  cur = cur.next

  # 新节点的连边直接等于原节点的边,dict.get(key)的方式等同于dict[key],有捕捉异常的作用

  cur = head

  while cur:

  visited[cur].next = visited.get(cur.next) # 新节点.next = 映射关系(原节点.next)

  visited[cur].random = visited.get(cur.random)

  cur = cur.next

  return visited[head]

  35.3 拼接+拆分

  逐个生成新节点,并修改原节点的next,使得新节点逐个跟随在原节点之后,之间用next连接。

  然后按照原节点的random方式对新节点进行random连接。

  最后将新节点构成的链表和原节点的拆开。

  class Solution:

  def copyRandomList(self, head: 'Node') -> 'Node':

  if not head: return

  cur = head

  # 1. 复制各节点,并构建拼接链表

  while cur:

  tmp = Node(cur.val)

  tmp.next = cur.next

  cur.next = tmp

  cur = tmp.next

  # 2. 构建各新节点的 random 指向

  cur = head

  while cur:

  if cur.random:

  cur.next.random = cur.random.next

  cur = cur.next.next

  # 3. 拆分两链表

  cur = res = head.next

  pre = head

  while cur.next:

  pre.next = pre.next.next

  cur.next = cur.next.next

  pre = pre.next

  cur = cur.next

  pre.next = None # 单独处理原链表尾节点

  return res # 返回新链表头节点

  58 II. 左旋转字符串

  给定一个字符串和一个整数,然后该整数将字符串分割成两部分,然后左右两部分交换位置拼接,该过程切片就可以实现。

  return s[n:]+s[:n]

  如果不用切片该怎么做呢?还是用list,直接遍历两次字符串,先将后半部分填入list,然后再将前半部分填入,最后join在一起。

  res = []

  for i in range(n, len(s)):

  res.append(s[i])

  for i in range(n):

  res.append(s[i])

  return ''.join(res)

  # 用余数简化代码 大连做人流哪里好

  for i in range(n, n+len(s)): # 如abcde,n=2,i的范围在2,3,4,5,6,对5取余结果:2,3,4,0,1

  res.append(s[i % len(s)])

  总结:要求不让借用list和join方法如何处理:直接将list换成字符串类型的,将list.append换成加号即可不用join。本题涉及到的知识点就是Java和python中的字符串为不可变对象,要对字符串进行操作,必须重新定义一个新字符串或者list。

  用切片方式最快,无冗余操作,效率最高。

  列表(Python) 和 StringBuilder(Java) 都是可变对象,每轮遍历拼接字符时,只是向列表尾部添加一个新的字符元素。最终拼接转化为字符串时,系统 仅申请一次内存 。

  在 Python 和 Java 中,字符串是 “不可变对象” 。因此,每轮遍历拼接字符时,都需要新建一个字符串;因此,系统 需申请 NN 次内存 ,数据量较大时效率低下。

  C++中字符串是可变类型,实现方式是将左字符串逆序,右字符串逆序,然后整个逆序,以下分别是调用库函数和自己实现reverse操作:

  class Solution {

  public:

  string reverseLeftWords(string s, int n) {

  reverse(s.begin(), s.begin() + n);

  reverse(s.begin() + n, s.end());

  reverse(s.begin(), s.end());

  return s;

  }

  };

  class Solution {

  public:

  string reverseLeftWords(string s, int n) {

  reverseString(s, 0, n - 1);

  reverseString(s, n, s.size() - 1);

  reverseString(s, 0, s.size() - 1);

  return s;

  }

  private:

  void reverseString(string& s, int i, int j) {

  while(i < j) swap(s[i++], s[j--]);

  }

  };

  59 I. 滑动窗口的最大值

  简单题目一定会有所限制,像本题第一反应如下,用list切片作为窗口,可以得到n-k+1个窗口,每个窗口中寻找max,需要O(k)的时间复杂度。总体时间复杂度为O(n-k+1)k:

  class Solution:

  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

  def max(lst): # 求list的max

  max_num = lst[0]

  for i in range(len(lst)):

  max_num = lst[i] if lst[i] > max_num else max_num

  return max_num

  # list,遍历,切片,max

  res = []

  if len(nums) == 0:return res

  for i in range(len(nums)-k+1):

  res.append(max(nums[i:i+k]))

  return res

  因此重点就是如何降低时间复杂度!借鉴30题 包含min函数的栈,用o(1)的方式得到min。一般窗口对应的数据结构为双端队列,本题用单端队列即可。Python 通过zip(range(), range())可实现滑动窗口的左右边界i, j 同时遍历。

  复杂度分析:图解查看此处

  时间复杂度O(n):其中n为数组 nums长度;线性遍历nums占用 O(n) ;每个元素最多仅入队和出队一次,因此单调队列 deque 占用 O(2n)。

  空间复杂度O(k): 双端队列 deque 中最多同时存储 k个元素(即窗口大小)。

  class Solution:

  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

  deque = collections.deque()

  res, n = [], len(nums)

  for i, j in zip(range(1 - k, n + 1 - k), range(n)):

  # 删除 deque 中对应的 nums[i-1]

  if i > 0 and deque[0] == nums[i - 1]:

  deque.popleft()

  # 保持 deque 递减

  while deque and deque[-1] < nums[j]:

  deque.pop()

  deque.append(nums[j])

  # 记录窗口最大值

  if i >= 0:

  res.append(deque[0])

  return res

  此处用到了python中的collections库,学习点这里

  59 II. 队列的最大值

  **题目要求:**请定义一个队列并实现函数 max_value 得到队列里的最大值,要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空,pop_front 和 max_value 需要返回 -1。

  67. 把字符串转换成整数

  **题目要求:**将字符串中的数字转换成整数输出。

  丢弃无用的开头空格字符

  当第一个非空格字符为正负号时,寻找紧挨着的连续数字,得到最后的带符号整数;若首个非空格字符是数字时,那就得到连续的整数(其后包含一些其他字符的干扰项,就无视啦)

  任何不能转换成整数的条件下,返回0

  如果超出整数范围,那么输出+/- int_max

  20 59 67 三道题理解收尾;其余题目回顾复习


来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/69945560/viewspace-2760920/,如需转载,请注明出处,否则将追究法律责任。

请登录后发表评论 登录
全部评论

注册时间:2019-08-16

  • 博文量
    198
  • 访问量
    174379