KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given an integer array nums, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.

A subarray is a contiguous part of an array.

Example 1:

Input: nums = [-2,1,-3,4,-1,2,1,-5,4]
Output: 6
Explanation: [4,-1,2,1] has the largest sum = 6.


Example 2:

Input: nums = [1]
Output: 1


Example 3:

Input: nums = [5,4,-1,7,8]
Output: 23


Constraints:

1 <= nums.length <= 10<sup>5</sup> -10<sup>4</sup> <= nums[i] <= 10<sup>4</sup>

Follow up: If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.

题目大意：

最大子数组和

算法思路：

dp[i] = max(dp[i-1] + nums[i], nums[i])

注意事项：

  1. 引入全局最大的res，因为递归式是以末位为结尾的最大和

Python代码：

1
2
3
4
5
6
7
8
9
10
# dp[i] = max(dp[i-1] + nums[i], nums[i])
def maxSubArray(self, nums: List[int]) -> int:
	sum, res = -sys.maxsize, -sys.maxsize
	for num in nums:
		if sum > 0:
			sum += num
		else:
			sum = num
		res = max(sum, res)
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode

Given a string s containing an out-of-order English representation of digits 0-9, return the digits in ascending order. Example 1:

Input: s = “owoztneoer”
Output: “012”


Example 2:

Input: s = “fviefuro”
Output: “45”


Constraints: 1 <= s.length <= 10<sup>5</sup> s[i] is one of the characters ["e","g","f","i","h","o","n","s","r","u","t","w","v","x","z"]. s is *guaranteed to be valid.

题目大意：

数字用英语单词表示如12 -> onetwo, 但打乱顺序otwone. 求如何获得原数字

算法思路：

统计每个字母的个数，根据个数来决定数字
规律见代码： 有些字母但唯一的，如two，w可以知道数字含2
但有些字母是多个数字的和如s，six和seven都含有s，减去用上述的six的个数就知道seven的个数

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
def originalDigits(self, s: str) -> str:
	char_to_num = {
		'z': '0',
		'w': '2',
		'u': '4',
		'x': '6',
		'g': '8',
		'o': '1',  # decided by previous keys
		'h': '3',  # decided by previous keys
		'f': '5',  # decided by previous keys
		's': '7',  # decided by previous keys
		'i': '9',  # decided by previous keys
	}
	res = []
	char_to_freq = collections.defaultdict(int)
	for char in s:
		char_to_freq[char] += 1
	char_to_freq['o'] -= char_to_freq['z'] + char_to_freq['w'] + char_to_freq['u']
	char_to_freq['h'] -= char_to_freq['g']
	char_to_freq['f'] -= char_to_freq['u']
	char_to_freq['s'] -= char_to_freq['x']
	char_to_freq['i'] -= char_to_freq['x'] + char_to_freq['g'] + char_to_freq['f']
	for char, num in char_to_num.items():
		if char in char_to_freq and char_to_freq[char] > 0:
			for _ in range(char_to_freq[char]):
				res.append(num)
	res.sort()
	return ''.join(res)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of strings strs, group the anagrams together. You can return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

Example 1:

Input: strs = [“eat”,”tea”,”tan”,”ate”,”nat”,”bat”]
Output: [[“bat”],[“nat”,”tan”],[“ate”,”eat”,”tea”]]


Example 2:

Input: strs = [“”]
Output: [[“”]]


Example 3:

Input: strs = [“a”]
Output: [[“a”]]


Constraints:

1 <= strs.length <= 10<sup>4</sup> 0 <= strs[i].length <= 100
* strs[i] consists of lowercase English letters.

题目大意：

对同字母不同序单词分组

算法思路：

N/A

注意事项：

  1. list(id_to_words.values())要转成list

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
	id_to_words = collections.defaultdict(list)
	for word in strs:
		id_to_words[self.get_id(word)].append(word)
	return list(id_to_words.values())  # remember to convert it to list

def get_id(self, word):
	char_to_freq = collections.Counter(word)
	res = ''
	for c in string.ascii_lowercase:
		if c in char_to_freq:
			res += c + str(char_to_freq[c])
	return res

算法分析：

时间复杂度为O(nm)，空间复杂度O(n+m). n是单词个数，m是单词长度

Posted on Edited on Disqus:

LeetCode



There are n gas stations along a circular route, where the amount of gas at the i<sup>th</sup> station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i<sup>th</sup> station to its next (i + 1)<sup>th</sup> station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.


Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can’t start at station 0 or 1, as there is not enough gas to travel to the next station.
Let’s start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can’t travel around the circuit once no matter where you start.


Constraints:

gas.length == n cost.length == n
1 <= n <= 10<sup>5</sup> 0 <= gas[i], cost[i] <= 10<sup>4</sup>

题目大意：

N/A

算法思路：

只要总gas >= 总cost，就总有一个点满足gas-cost为非负

注意事项：

  1. 先判断不合法的情况sum(gas) < sum(cost)

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
	if sum(gas) < sum(cost):
		return -1
	sum_gas, sum_cost, pos = 0, 0, 0
	for i in range(len(gas)):
		sum_gas += gas[i]
		sum_cost += cost[i]
		if sum_gas < sum_cost:
			pos = i + 1
			sum_gas = 0
			sum_cost = 0
	return pos

算法分析：

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

Posted on Edited on Disqus:

LeetCode



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:

Input: s = “1 + 1”
Output: 2


Example 2:

Input: s = “ 2-1 + 2 “
Output: 3


Example 3:

Input: s = “(1+(4+5+2)-3)+(6+8)”
Output: 23


Constraints:

`1 <= s.length <= 3 105*sconsists of digits,‘+’,‘-‘,‘(‘,‘)’, and‘ ‘. *srepresents 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.

题目大意：

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

算法思路：

括号题优先考虑用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)

Free mock interview