KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<!-- raw HTML block --> <div><p>You are given two <strong>non-empty</strong> linked lists representing two non-negative integers. The digits are stored in <strong>reverse order</strong>, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.</p>

<p>You may assume the two numbers do not contain any leading zero, except the number 0 itself.</p>

<p> </p> <p><strong>Example 1:</strong></p> <img alt="" src="https://assets.leetcode.com/uploads/2020/10/02/addtwonumber1.jpg" style="width: 483px; height: 342px;"> <pre><strong>Input:</strong> l1 = [2,4,3], l2 = [5,6,4] <strong>Output:</strong> [7,0,8] <strong>Explanation:</strong> 342 + 465 = 807. </pre>

<p><strong>Example 2:</strong></p>

<pre><strong>Input:</strong> l1 = [0], l2 = [0] <strong>Output:</strong> [0] </pre>

<p><strong>Example 3:</strong></p>

<pre><strong>Input:</strong> l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] <strong>Output:</strong> [8,9,9,9,0,0,0,1] </pre>

<p> </p> <p><strong>Constraints:</strong></p>

<ul> <li>The number of nodes in each linked list is in the range <code>[1, 100]</code>.</li> <li><code>0 <= Node.val <= 9</code></li> <li>It is guaranteed that the list represents a number that does not have leading zeros.</li> </ul> </div>

题目大意：

数位链表(从最低位到最高位)相加

算法思路：

类似于merge sort

注意事项：

  1. 其中一个可能较长，所以主循环出来后还要继续循环较长的链表，类似于merge sort
  2. 所有链表遍历完后，carry可能还会是1，要加一个if语句特别处理

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def addTwoNumbers(self, l1: 'ListNode', l2: 'ListNode') -> 'ListNode':
	fake_head = ListNode(0)
	carry = 0
	it, it2, it_res = l1, l2, fake_head
	while it or it2:
		value = carry
		if it:
			value += it.val
			it = it.next
		if it2:
			value += it2.val
			it2 = it2.next
		carry = 1 if value >= 10 else 0
		value %= 10
		it_res.next = ListNode(value)
		it_res = it_res.next
	if carry == 1:
		it_res.next = ListNode(1)
	return fake_head.next

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

<pre>Input: nums = [1,2,3,4] Output: [24,12,8,6] </pre>

Example 2:

<pre>Input: nums = [-1,1,0,-3,3] Output: [0,0,9,0,0] </pre>

Constraints:

  • 2 <= nums.length <= 10<sup>5</sup>
  • -30 <= nums[i] <= 30
  • The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1)extra space complexity? (The output array does not count as extra space for space complexity analysis.)

</div>

题目大意：

求每个数对应的结果： 数组出自己外全部相乘

解题思路：

累计思想

解题步骤：

N/A

注意事项：

  1. 两轮计算，从左到右，再从右到左，用res数组作为临时计算结果。从左到右，计算res[i] = num[0] x nums[i - 1], 从右到左类似
  2. res初始值为1，因为从左到右是跳过第0个值的，而从右到左中res[i] *= product，若初始为0，结果res[i] = 0

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def productExceptSelf(self, nums: List[int]) -> List[int]:
	n = len(nums)
	res, product = [1] * n, nums[0]
	for i in range(1, n):
		res[i] = product # [1, 1]
		product *= nums[i]
	product = nums[-1] # 2
	for i in range(n - 2, -1, -1):
		res[i] *= product # [2, 1]
		product *= nums[i]
	return res

算法分析：

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

若可以用除法算法II解题思路：

按照定义用数学方法，但只要注意一个0和两个0的情况

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def productExceptSelf(self, nums: List[int]) -> List[int]:
	product, zero_count = 1, 0
	for n in nums:
		if n != 0:
			product *= n
		else:
			zero_count += 1
	if zero_count > 1:
		return [0] * len(nums)
	res = []
	for i in range(len(nums)):
		if nums[i] == 0:
			res.append(product)
		elif zero_count > 0:
			res.append(0)
		else:
			res.append(int(product / nums[i]))
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

<pre>Input: s = "1 + 1" Output: 2 </pre>

Example 2:

<pre>Input: s = " 2-1 + 2 " Output: 3 </pre>

Example 3:

<pre>Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23 </pre>

Constraints:

  • 1 <= s.length <= 3 * 10<sup>5</sup>
  • s consists of digits, '+', '-', '(', ')', and ' '.
  • s represents a valid expression.
  • '+' is not used as a unary operation (i.e., "+1" and "+(2 + 3)" is invalid).
  • '-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" is valid).
  • There will be no two consecutive operators in the input.
  • Every number and running calculation will fit in a signed 32-bit integer.

</div>

题目大意：

实现字符串加减，但有括号。

算法思路：

括号题优先考虑用Stack。这里Stack不能只存数，因为括号前可以是正负，所以将这个信息以+1或-1也压入栈（栈不能混合字符和数字）
所以用一个stack，num是一个数，res是括号内的累积结果。num在处理完每一个数都要重设，res和sign在处理完每个括号都要重设。

运用模板，代码中含五种情况：空格，运算符，数字，左右括号。左括号将res和sign入栈，右括号将res和sign出栈，计算结果存在res

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

注意事项：

  1. 括号前可以是正负，所以将这个信息以+1或-1也压入栈
  2. 左括号无论前面是正负都要入栈
  3. num在处理完每一个数都要重设，res和sign在处理完每个括号都要重设

Python代码：

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
29
30
31
32
33
# 1-(2+3)+(4+5)
# 1+2+3
def calculate(self, s: str) -> int:
	res, num, stack, sign = 0, 0, [], 1
	s += '+'
	for char in s:
		if char == ' ':
			continue
		if char.isdigit():
			num = num * 10 + int(char)
		if char == '+':
			res += sign * num
			sign = 1
			num = 0
		if char == '-':
			res += sign * num
			sign = -1
			num = 0
		if char == '(':
			stack.append(res) # [-4+]
			stack.append(sign) #
			sign = 1
			res = 0
		if char == ')':
			res += sign * num # 9
			prev_sign = stack.pop() # +
			tmp = stack.pop() # -4
			res = tmp + prev_sign * res # -4 +9
			# sign = 1 next one will be +-, so num = 0 and sign doesn't matter
			num = 0
		# else:
		 #   res += char
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Implement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.

You may assume that the given expression is always valid. All intermediate results will be in the range of [-2<sup>31</sup>, 2<sup>31</sup> - 1].

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Example 1:

<pre>Input: s = "1+1" Output: 2 </pre>

Example 2:

<pre>Input: s = "6-4/2" Output: 4 </pre>

Example 3:

<pre>Input: s = "2*(5+5*2)/3+(6/2+8)" Output: 21 </pre>

Constraints:

  • 1 <= s <= 10<sup>4</sup>
  • s consists of digits, '+', '-', '*', '/', '(', and ')'.
  • s is a valid expression.

</div>

题目大意：

实现字符串加减乘除且有括号。

解题思路：

类似于Leetcode 227求加减乘除，这里多了括号，括号内含加减乘除，所以每对括号是一轮DFS。遇到左括号，就进入递归，遇到右括号就返回递归值

LeetCode 224 Basic Calculator 括号加减法, 同一层括号内求和遇括号入栈
LeetCode 227 Basic Calculator II 加减乘除, 和的每一项入栈，方便出栈计乘除
LeetCode 772 Basic Calculator III 加减乘除括号, L227的递归版

解题步骤：

N/A

注意事项：

  1. 不同于L227, 类似于填位法将i作为DFS参数传入，返回括号内的值以及i。i放入while循环， i += 1要加入到空格情况和循环最后
  2. 最后位加入加号要移除DFS中，放入主函数
  3. 注意处理括号情况的顺序，左括号在空格后，右括号在最后

Python代码：

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
29
30
31
32
33
def calculate(self, s: str) -> int:
	s += '+'
	return self.dfs(s, 0)

def dfs(self, s, i):
	res, num, stack, op = 0, 0, [], '+'
	while i < len(s):
		char = s[i]
		if char == ' ':
			i += 1
			continue
		if char == '(':
			num, i = self.dfs(s, i + 1)
		elif char.isdigit():
			num = num * 10 + int(char)
		elif op == '-':
			stack.append(-num)
		elif op == '+':
			stack.append(num) # [4+2*1]
		elif op == '*':
			prev = stack.pop()
			stack.append(prev * num)
		elif op == '/':
			prev = stack.pop()
			stack.append(int(prev / num))  # remember
		if char in '+-*/':
			num = 0
			op = char

		if char == ')':
			return sum(stack), i
		i += 1
	return sum(stack)

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given an m x n matrix mat, return an array of all the elements of the array in a diagonal order.

Example 1:

<pre>Input: mat = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,4,7,5,3,6,8,9] </pre>

Example 2:

<pre>Input: mat = [[1,2],[3,4]] Output: [1,2,3,4] </pre>

Constraints:

  • m == mat.length
  • n == mat[i].length
  • 1 <= m, n <= 10<sup>4</sup>
  • 1 <= m * n <= 10<sup>4</sup>
  • -10<sup>5</sup> <= mat[i][j] <= 10<sup>5</sup>

</div>

题目大意：

按类对角线梅花间竹地遍历每个元素，输出最后结果

找规律解题思路：

边界条件很难找，而且每一层的结束点也和矩阵的长度或宽度有关。先找规律，可以看出 

1
每层的所有元素下标和相等
正常从左到右从上到下遍历矩阵，用一个dict来每层的每一个数，可以看出这些数的顺序都是按题目要求的，只不过是正序或逆序，所以最后按照奇偶决定是否正序或逆序加入到结果

解题步骤：

  1. 从左到右从上到下遍历矩阵，dict[i + j]来加入每层的每一个数
  2. dict的key的范围容易得知，按照奇偶决定是否正序或逆序加入到结果

注意事项：

  1. dict[i + j]来加入每层的每一个数
  2. dict的key的最大值为len(mat) + len(mat[0]) - 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
	groups = collections.defaultdict(list)
	for i in range(len(mat)):
		for j in range(len(mat[0])):
			groups[i + j].append(mat[i][j])
	res = []
	for i in range(len(mat) + len(mat[0]) - 1):
		if i % 2 == 1:
			res.extend(groups[i])
		else:
			res.extend(groups[i][::-1])
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(nm)

按题意II解题思路：

Python代码：

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
29
30
31
32
def print_diagnals(matrix):
    if not matrix or not matrix[0]:
        return []
    res = []
    is_reversed = True
    # all diagnal starting from top row
    for col in range(len(matrix[0])):
        diag_row, diag_col = 0, col
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    # diagnal start rightmost columns
    for row in range(1, len(matrix)):
        diag_row, diag_col = row, len(matrix[0]) - 1
        one_print = []
        while diag_row < len(matrix) and diag_col >= 0:
            one_print.append(matrix[diag_row][diag_col])
            diag_row += 1
            diag_col -= 1
        if is_reversed:
            res.extend(one_print[::-1])
        else:
            res.extend(one_print)
        is_reversed = not is_reversed
    return res

算法分析：

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

Free mock interview