KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 007 Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-2<sup>31</sup>, 2<sup>31</sup> - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:

**Input:** x = 123
**Output:** 321

Example 2:

**Input:** x = -123
**Output:** -321

Example 3:

**Input:** x = 120
**Output:** 21

Example 4:

**Input:** x = 0
**Output:** 0

Constraints:

  • -2<sup>31</sup> <= x <= 2<sup>31</sup> - 1

题目大意：

反转整数中的数字。

数学法解题思路：

用数学方法每位取余，余数左移。另一种方法是转成字符串然后用字符串反转的方法。

与Java的区别：

  1. 不需要定义long，因为Python3所有int默认都是long
  2. 反转str一行完成，非常简洁

注意事项：

  1. 负值
  2. 溢出

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def reverse(self, x: int) -> int:
	res, is_negative = 0, False
	if x < 0:
		is_negative = True
		x = -x
	while x > 0:
		digit = x % 10
		res = res * 10 + digit
		x //= 10
	if res > pow(2, 31) - 1:
		return 0
	if is_negative:
		res = -res
	return res

字符串法解题思路：

转为字符串，然后反转。 

1
2
3
4
5
6
7
8
9
def reverse(self, x: int) -> int:
	res, is_negative = 0, False
	if x < 0:
		is_negative = True
		x = -x
	res = int(str(x)[::-1])
	if res > pow(2, 31) - 1:
		return 0
	return -res if is_negative else res

算法分析：

  1. 时间复杂度为O(n)，空间复杂度O(1)。
  2. 时间复杂度为O(n)，空间复杂度O(n)。

Posted on Edited on Disqus:

LeetCode 104 Maximum Depth of Binary Tree

Given the root of a binary tree, return its maximum depth.

A binary tree’s maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Example 1:

**Input:** root = [3,9,20,null,null,15,7]
**Output:** 3

Example 2:

**Input:** root = [1,null,2]
**Output:** 2

Example 3:

**Input:** root = []
**Output:** 0

Example 4:

**Input:** root = [0]
**Output:** 1

Constraints:

  • The number of nodes in the tree is in the range [0, 10<sup>4</sup>].
  • -100 <= Node.val <= 100

题目大意：

求二叉树高度。

解题思路：

公式dfs(root)=1+max(dfs(root.left),dfs(root.right))

Python代码：

1
2
3
4
def maxDepth(self, root: TreeNode) -> int:
	if not root:
		return 0
	return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

算法分析：

时间复杂度为O(n)，空间复杂度O(1)。

Posted on Edited on Disqus:

LeetCode 003 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

**Input:** s = "abcabcbb"
**Output:** 3
**Explanation:** The answer is "abc", with the length of 3.

Example 2:

**Input:** s = "bbbbb"
**Output:** 1
**Explanation:** The answer is "b", with the length of 1.

Example 3:

**Input:** s = "pwwkew"
**Output:** 3
**Explanation:** The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Example 4:

**Input:** s = ""
**Output:** 0

Constraints:

  • 0 <= s.length <= 5 * 10<sup>4</sup>
  • s consists of English letters, digits, symbols and spaces.

题目大意：

求最长不重复子串。

解题思路：

HashMap和滑动窗口法，利用HashMap来记录这个窗口中所有字符的下标，该窗口中所有字符都不重复。
start_idx表示窗口的左界，而i是右界。左界=上次一次出现该字符的下标和目前左界的较大值，
因为Map中的某些字符可能已经不在窗口中，我没有把它从窗口中去掉，而是用start_idx来限制。

要计算长度就要先计算start_idx，步骤：

  1. 计算start_idx
  2. 计算长度

注意事项：

  1. start_idx和前值比较，且只有当字符在map中才更新start_idx

Python代码：

1
2
3
4
5
6
7
8
9
def lengthOfLongestSubstring(self, s: str) -> int:
	start_idx, max_len = 0, 0
	char_map = {}
	for i in range(len(s)):
		if s[i] in char_map:
			start_idx = max(start_idx, char_map[s[i]] + 1)
		max_len = max(max_len, i - start_idx + 1)
		char_map[s[i]] = i
	return max_len

算法分析：

时间复杂度为O(n)，空间复杂度O(n)。

Posted on Edited on Disqus:

LeetCode 138 Copy List with Random Pointer

A linked list of length n is given such that each node contains an additional random pointer, which could point to any node in the list, or null.

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Example 1:

**Input:** head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
**Output:** [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

**Input:** head = [[1,1],[2,1]]
**Output:** [[1,1],[2,1]]

Example 3:

**Input:** head = [[3,null],[3,0],[3,null]]
**Output:** [[3,null],[3,0],[3,null]]

Example 4:

**Input:** head = []
**Output:** []
**Explanation:** The given linked list is empty (null pointer), so return null.

Constraints:

  • 0 <= n <= 1000
  • -10000 <= Node.val <= 10000
  • Node.random is null or is pointing to some node in the linked list.

题目大意：

复制含next和random的链表。

解题思路（推荐）：

此法较容易实现。先复制next指针，然后利用HashMap存储旧新节点，来复制random指针。

注意事项：

  1. 复制next指针和Map中。clone题均用此法。
  2. Random指针不空才copy
  3. 加it = it.next，否则死循环
  4. 如果创建新Node用while it.next表示用它的父节点，否则某个field赋值如random用while it

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def copyRandomList(self, head: 'Node') -> 'Node':
	node_map = {}
	fake_head, fake_head_copy = Node(0), Node(0)
	fake_head.next = head
	it, it_copy = fake_head, fake_head_copy
	while it.next:
		it_copy.next = Node(it.next.val)
		node_map[it.next] = it_copy.next
		it, it_copy = it.next, it_copy.next

	it, it_copy = fake_head.next, fake_head_copy.next
	while it:
		if it.random:
			node_map[it].random = node_map[it.random]
		it, it_copy = it.next, it_copy.next
	return fake_head_copy.next

梅花间竹解题思路：

第二种方法，梅花间竹，分3部走。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def copyRandomList(self, head: 'Node') -> 'Node':
	fake_head, fake_head_copy = Node(0), Node(0)
	fake_head.next = head

	# insert
	it = fake_head.next
	while it:
		temp = it.next
		it.next = Node(it.val)
		it.next.next = temp
		it = it.next.next

	# copy random
	it = fake_head.next
	while it:
		if it.random is not None:
			it.next.random = it.random.next
		it = it.next.next

	# delete
	it, it_copy = fake_head.next, fake_head_copy
	while it:
		temp = it.next
		it.next = it.next.next
		it_copy.next = temp
		temp.next = None
		it, it_copy = it.next, it_copy.next
	return fake_head_copy.next

算法分析：

  1. 时间复杂度为O(n)，空间复杂度O(n)。
  2. 时间复杂度为O(n)，空间复杂度O(1)。

Posted on Edited on Disqus:

常用知识点

类型 函数名 作用 输入参数 返回值 例子
for range 和len结合使用相当于取某范围List下标,第三个参数为步长 N/A N/A for i in range(len(nums))前闭后开,用逗号
for in 枚举列表的每个数 N/A N/A for n in nums
for range 逆序遍历 N/A N/A for i in range(len(nums) - 1, -1, -1)前闭后开, 或用reversed(range(len(nums)))
for enumerate 枚举List的下标和数值，与range不同的是它不能指定范围和步长 N/A N/A for i, n in enumerate(nums)
Math max/min 取最大值 Num Num max_len = max(2, 3) 或min(1, 2, 3)
Math pow 求幂值 Num Num val = pow(2, 3)
Math int str转int或将float变成int String Num val = int(‘123’), val = int(2.6) -> 2
Math math.ceil/floor 求向上或下取整 Num Num import math, val = math.ceil(5/2), math.floor(5/2)
Math float(‘inf’) 无穷大值 N/A Num val = float(‘inf’) or float(‘-inf’)
Math min 求数组中的正数的最小值 N/A Num min(n for n in nums if n > 0)
Math len 求数组中的正数的个数 N/A Num len([n for n in nums if n > 0])
Math sum 求数组和 N/A Num sum(nums)
Math abs 求绝对值 Num Num abs(-1)
Math //与int 求整数值 Num Num //是比它小的整数如-2.8就是-3，只在负数是有区别。写程序用的更多是int(num / a)结果是-2，这和Java一致
String str 任意类型变成字符串 Any String str(2)
String replace 替换 String String ‘abc’.replace(‘c’, ‘d’)
String format 格式化字符串 Any String ‘{} of {}’.format(a, b)
String [] 得到某一个字符 N/A Char s[2]
String [] 得到子串(前闭后开) N/A string s = ‘abc’, s[:2] -> ‘ab’, s[2:] -> ‘c’
String len 得到字符串长度 N/A int num = len(s)
String [::-1] 反转字符串 N/A String new_str = s[::-1]
String [:-1] (DFS中)去掉最后一个字符 N/A String path = path[:-1]
String N/A 两个字符串叉乘 N/A List a_list = [s + c for s in s1 for c in s2]
String > 比较两个字符串 N/A boolean ‘111’ > ‘21’ -> False, ‘21’ == ‘21’ -> True
String find 查找返回下标 str str ‘word’.find(‘w’) 若找不到返回-1
String upper 变成全部大写 str str ‘word’.upper()
String lower 变成全部大写 str str ‘WORD’.lower()
String startswith 是否以某个字母开头 str Boolean ‘word’.startswith(‘w’)
String endswith 是否以某个字母结尾 str Boolean ‘word’.endswith(‘d’)
String strip, lstrip, rstrip 去掉空格 N/A str ‘word ‘.strip(), ‘word ‘.lstrip(), ‘word ‘.rstrip()
String split 用分隔符变成List str List ‘a,b’.split(‘,’)
String + 一个个字符加到字符串末 N/A N/A res += ‘g’
String in 查看某个字符是否属于一个字符集合里 N/A bool if char in ‘([{‘ 可以避免用list
String isalpha 是否字母 N/A bool ‘ab’.isalpha()
String isdigit 是否数字 N/A bool ‘23’.isdigit()
String ascii_lowercase a-z的所有字母 str str import string, string.ascii_lowercase
String ord 一个字母的ASCII str str ord(‘A’) = 65
String eval 计算字符串的数值，变量，函数运算结果，返回数字 str Num eval(‘5+ 6’) = 11, num = 1, eval(num + 1) = 2, eval(‘f(2)’)
String ljust 靠左右边补空格 str str line.ljust(maxWidth), line.ljust(maxWidth, ‘#’)
List [] 初始化列表 N/A N/A li = []，这是空列表，不能通过索引取值
List [] 初始化固定大小的列表 N/A N/A li = [0] * 10, [None] * 10 -> 创建一个list, * 是复制只能用于标量，若矢量是复制ref如[[]] * 10, 要用[[] for _ in range(10)]
List len 大小 N/A int num = len(li)
List append 尾部加入 Any N/A li.append(‘apple’)
List insert 头部加入 Any N/A li.insert(0, ‘apple’)
List pop 头部/某位置删除 Any N/A li.pop(0), li.pop(2)
List remove 按值删除 Any N/A li.remove(3)
List + 两个list合并 N/A N/A list1 + list2
List extend 两个list合并到第一个 Any N/A li.extend([‘apple’, ‘banana’])
List join 加入分隔符 List String ‘,’.join(li), 将字符列表变成字符串’’.join(char_list)
List sort 原地排序，如果List的元素是tuple，按第一个元素排序 List N/A li.sort(), 如果不改变原数组用list(li)先复制
List sort 按字符串长度降序排列 List N/A words.sort(key=len, reverse=True), intervals.sort(key=lambda x: x[0]), 按两个key来排序li.sort(key=lambda x: (x[0], x[1]))先顺序再逆序li.sort(key=lambda x: (x[0], -x[1]))
List sorted 非原地排序 List N/A nums[idx+1:] = sorted(nums[idx+1:])
List list 复制list List List new_list = list(old_list)
List list 扩展一倍一样的list List List new_list = nums * 2
List [] 反转list List List new_list = li[::-1]跟反转string一样，反转子列表nums[idx+1:] = nums[len(nums)-1:idx:-1]
List [-1] 返回list中最后一个元素 T int li[-1]，而不是dp[len(li)-1]广泛用于DP题
List index list中找某个元素 T int li.index(2), 找不到的话抛出异常，先要检查if 9 in li2 else -1. 字符串用find
List count list中计算某个元素值的个数 T int li.count(‘a’)
List [:] 批量替换成list中某些元素 N/A N/A nums[start:end + 1] = res
List [::-1] reverse sublist N/A N/A nums[:k] = nums[:k][::-1]先取sublist再倒转
deque deque 初始化队列 N/A N/A from collections import deque, queue = deque(), queue = deque([node])
deque append 入列 T N/A queue.append(node)
deque popleft 出列 Num T s = queue.popleft()
deque appendleft 队首入列 Num T s = queue.appendleft()较少用
deque [0] 看列首元素 N/A T queue = [], s = queue[0]
List(Heap) heapify 对list最小堆排序 List N/A from heapq import heapify, pq = [2, 3], heapify(pq) 若最大堆，则将所有值取负加入堆
List(Heap) heappush 入堆 List, T N/A from heapq import heappush, heappush(pq, 4)
List(Heap) heappop 出堆 List T from heapq import heappop, heappop(pq)
List(Heap) heapreplace 置换堆 T N/A heapq.heapreplace(pq, 4)= heappush(pq, 4) + heappop(pq)
List(Heap) [0] 看堆顶元素 N/A T pq[0]
List(Stack) append 入栈 T N/A stack = [], stack.append(node)
List(Stack) pop 出栈 N/A T stack = [], s = stack.pop()
List(Stack) [] 看栈顶元素 N/A T stack = [], s = stack[-1]
Dictionary {} 初始化字典 N/A N/A di = {}, di = {1: ‘a’, 2: ‘b’}
Dictionary {} 初始化字典带初始key N/A N/A di = collections.defaultdict(int), defaultdict(list)避免第一次赋值时需要写if语句，一定用。只有用下标di[2]才会产生key和value,其他2 in di, di.keys()都不会产生key. collections.defaultdict(lambda: [0, 0])用于value是pair, 默认返回1： collections.defaultdict(lambda: 1)
Dictionary [] 获得字典的值 T T di[key]
Dictionary [] 插入到字典 T T di[key] = 2
Dictionary items Dict的所有pairs N/A K,V for k, v in di.items()
Dictionary items Dict的所有keys N/A List for k in di.keys(), 类型不是List，若要，则list(di.keys())
Dictionary in 是否含有某个key N/A boolean if key in di
Dictionary pop 删除某个key N/A N/A di.pop(key)
Set {} 产生一个Set N/A Set b = set(), b = set([‘a’, ‘b’])
Set add set增加一个元素 T N/A b.add(‘c’)
Set remove set删除一个元素 T N/A b.remove(‘c’)
Set set List转换成Set或反之 N/A N/A s = set(l), l = list(s)
bisect bisect 二分法查找下标插入位置 Num Num 跟greater_position一样, from bisect import bisect, bisect([], 3) -> 0, bisect([2], 3) -> 1, bisect([3], 3) -> 1, bisect([4], 3) -> 0。还可以用于统计小于等于target的个数，如bisect([0, 1], 1) -> 2
bisect bisect_left 二分法查找下标插入位置 Num Num 似于greater_or_equal_position但若equal时，取第一个，但greater_or_equal_position是取最后一个. 用于LIS
bisect insort 二分法查找下标插入位置且插入 Num Num 似于greater_position，插入复杂度为O(n)
bisect bisect 二分法查找二维数组 Num Num bisect.bisect([[0, 1], [0, 2], [1, 2], [1, 3]], [1]) -> [1, 2]下标，若找[1, 2] -> [1, 3]下标
Lambda func/expr…for…in 整型数组变字符串数组 List List [str(x) for x in list]
Others return 返回tuple值 N/A N/A return a, b 不要括号
Others isinstance 判断输入是什么类型 N/A bool isinstance(stack[2], list)
Others Counter 计算List和字符串频率 List dict from collections import Counter, di = Counter(nums), di = Counter(‘apple’), graph = Counter({c: [] for word in words for c in word})
Others [] 初始化NxM矩阵为0 N/A N/A a = [[1] * M] * N不能复制矢量。[[0 for _ in range(M)] for _ in range(N)] 先col再row
Others randint 求[start, end]之间随机值 Num Num import random, random.randint(0, 1) -> 0/1
Others map, max 求矩阵最大值 [][] T max(map(max, matrix))
Others or 若0返回1 N/A N/A a or 1 -> a if a != 0, 1 if a == 0
Others or 若None返回[] N/A N/A for child in root.children or []
OrderedDict OrderedDict 类似于LinkedHashMap，dict的key的插入顺序排序 N/A N/A di = collections.OrderedDict(), di[‘a’] = 2
re search search只match一次 str str re.search(r’(\+|\-)?\d+’, ‘-23.1e2’).group() -> -23
re sub 全部用regex替代类似Java中的replaceAll str str re.sub(r’\s+’, ‘’, ‘a 6 7’) -> a67
Exception Exception 抛出异常 N/A N/A raise Exception(‘abc’)

总结：
除了deque, Stack, List的实现都是List
插入append, insert
删除pop, popleft(deque)

初始化列表：
创建一个list： li = [0] * 10, [False] * 10 而不是[False * 10], [0 * 10]这是乘法
创建一个list of list不用乘号： [[0 for _ in range(M)] for _ in range(N)], [[] for _ in range(10)]

if left_val可能为整数或None，要写成if left_val is not None，否则若left_val = 0, 会False
i += 1没有i++
if 0 < i < len(nums) 不像Java一样，Python可以连续比较范围
所有int都是long
22//5 = 4
22/5 = 4.4

def myFunc(e):
return e[‘year’]
cars.sort(reverse=True, key=myFunc)

由于Python的数字类型都是Numeric（自动识别为Integer, Float, Complex Numbers）,所以自动变成小数，不像Java是int
数据类型

True/False
and/or/not
pass什么都不做 if a: pass

&, ^异或, ~取反(~3), |, <<, >>

lo = hi = 0
swap: a, b = b, a
elif
return -res if is_negative else res
if root / if not root
if not nums 包含(None以及len(nums) == 0
Node(0)没有new
zip是将两个list的元素同步合成tuple，以短的为终结点。例如[i + j for i, j in zip(li, li2)] -> [5, 7], li = [1, 2], li2 = [4, 5, 6]
函数中更改输入list如f(list) -> list = [‘’]，不会改变原list，必须更改任意元素： list[:] = [‘’]
匿名函数和重载： ListNode.__lt__ = lambda x, y: (x.val < y.val)
Python中自定义obj可以任意定义属性，所以若要给某属性赋值如node.value，一定要match类定义里边的，不是node.val = 5。

补集：
list(set(li) - set(li2))
[n for n in self.all if n not in set(li)]
并集：
list(set(li) | set(li2))
list(set(li + li2))
交集：
list(set(li) & set(li2))
[n for n in li if n in set(li2)]

10的6次方，不能用10^6，这是异或，用1e6或pow(10, 6)
self.maxDepth

用_i来表示内部使用，dict_表示与关键字不重复

三个引号就是多行comment，#是一行comment
换行用 \

Python基础
Python命名规则
Python下划线

Free mock interview