KK's blog

每天积累多一些

0%

Posted on Disqus:

LeetCode



Implement pow(x, n), which calculates x raised to the power n (i.e., x<sup>n</sup>).

Example 1:

Input: x = 2.00000, n = 10
Output: 1024.00000


Example 2:

Input: x = 2.10000, n = 3
Output: 9.26100


Example 3:

Input: x = 2.00000, n = -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25


Constraints:

-100.0 < x < 100.0 -2<sup>31</sup> <= n <= 2<sup>31</sup>-1
* -10<sup>4</sup> <= x<sup>n</sup> <= 10<sup>4</sup>

题目大意：

求幂

解题思路：

DFS

解题步骤：

N/A

注意事项：

  1. 保存dfs(x, n/2)的临时结果，避免重复计算
  2. n可以是0，负数

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def myPow(self, x: float, n: int) -> float:
	if n >= 0:
		return self.dfs(x, n)
	else:
		return self.dfs(1 / x, -n)

def dfs(self, x, n):
	if n == 0:
		return 1
	if n == 1:
		return x
	if n % 2 == 0:
		tmp = self.dfs(x, n / 2)
		return tmp * tmp
	else:
		tmp = self.dfs(x, (n - 1) / 2)
		return tmp * tmp * x

算法分析：

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

Posted on Disqus:

LeetCode



Given an array of characters chars, compress it using the following algorithm:

Begin with an empty string s. For each group of consecutive repeating characters in chars:

If the group’s length is 1, append the character to s. Otherwise, append the character followed by the group’s length.

The compressed string s should not be returned separately, but instead, be stored in the input character array chars. Note that group lengths that are 10 or longer will be split into multiple characters in chars.

After you are done modifying the input array, return the new length of the array.

You must write an algorithm that uses only constant extra space.

Example 1:

Input: chars = [“a”,”a”,”b”,”b”,”c”,”c”,”c”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”2”,”b”,”2”,”c”,”3”]
Explanation: The groups are “aa”, “bb”, and “ccc”. This compresses to “a2b2c3”.


Example 2:

Input: chars = [“a”]
Output: Return 1, and the first character of the input array should be: [“a”]
Explanation: The only group is “a”, which remains uncompressed since it’s a single character.


Example 3:

Input: chars = [“a”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”,”b”]
Output: Return 4, and the first 4 characters of the input array should be: [“a”,”b”,”1”,”2”].
Explanation: The groups are “a” and “bbbbbbbbbbbb”. This compresses to “ab12”.


Example 4:

Input: chars = [“a”,”a”,”a”,”b”,”b”,”a”,”a”]
Output: Return 6, and the first 6 characters of the input array should be: [“a”,”3”,”b”,”2”,”a”,”2”].
Explanation: The groups are “aaa”, “bb”, and “aa”. This compresses to “a3b2a2”. Note that each group is independent even if two groups have the same character.


Constraints:

1 <= chars.length <= 2000 chars[i] is a lowercase English letter, uppercase English letter, digit, or symbol.

题目大意：

相邻相同字母用数字压缩

解题思路：

N/A

解题步骤：

N/A

注意事项：

  1. 题目要求，如果是超过10，也要将这个数按多个字符populate到原数组，见populate_count的实现，用字符串处理
  2. 在循环外处理最后一部分

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def compress(self, chars: List[str]) -> int:
	res, count = 1, 1
	for i in range(1, len(chars)):
		if chars[i - 1] == chars[i]:
			count += 1
		else:
			if count > 1:
				res = self.populate_count(chars, res, count)
			count = 1
			chars[res] = chars[i]
			res += 1
	if count > 1:
		res = self.populate_count(chars, res, count)
	return res

def populate_count(self, chars, res, count):
	num_str = str(count)
	chars[res:res + len(num_str)] = [c for c in num_str]
	res += len(num_str)
	return res

算法分析：

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

Posted on Disqus:

LeetCode



You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the i<sup>th</sup> line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Example 1:



Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.


Example 2:

Input: height = [1,1]
Output: 1


Constraints:

n == height.length 2 <= n <= 10<sup>5</sup>
* 0 <= height[i] <= 10<sup>4</sup>

题目大意：

求两板之间的最大水量

解题思路：

贪婪法，求面积，然后移动矮的那条边

解题步骤：

N/A

注意事项：

  1. 贪婪法，求面积，然后移动矮的那条边

Python代码：

1
2
3
4
5
6
7
8
9
10
def maxArea(self, height: List[int]) -> int:
	res = 0
	i, j = 0, len(height) - 1
	while i < j:
		res = max(res, min(height[i], height[j]) * (j - i))
		if height[i] < height[j]:
			i += 1
		else:
			j -= 1
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



There are n buildings in a line. You are given an integer array heights of size n that represents the heights of the buildings in the line.

The ocean is to the right of the buildings. A building has an ocean view if the building can see the ocean without obstructions. Formally, a building has an ocean view if all the buildings to its right have a smaller height.

Return a list of indices (0-indexed) of buildings that have an ocean view, sorted in increasing order.

Example 1:

Input: heights = [4,2,3,1]
Output: [0,2,3]
Explanation: Building 1 (0-indexed) does not have an ocean view because building 2 is taller.


Example 2:

Input: heights = [4,3,2,1]
Output: [0,1,2,3]
Explanation: All the buildings have an ocean view.


Example 3:

Input: heights = [1,3,2,4]
Output: [3]
Explanation: Only building 3 has an ocean view.


Constraints:

1 <= heights.length <= 10<sup>5</sup> 1 <= heights[i] <= 10<sup>9</sup>

题目大意：

大海在右边，求看到大海的大厦的下标

解题思路：

数组元素之间大小关系且保持顺序，用stack

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
def findBuildings(self, heights: List[int]) -> List[int]:
	stack = []
	for i in range(len(heights)):
		while stack and heights[i] >= heights[stack[-1]]:
			stack.pop()
		stack.append(i) # 4 3 1
	return stack

算法分析：

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

算法II解题思路(推荐)：

数组元素之间大小关系且保持顺序，用stack

解题步骤：

类似于Leetcode 42的trapping rain water，看不到大海表示在低位。此题只求单边，从右往左扫描一次。

注意事项：

Python代码：

1
2
3
4
5
6
7
def findBuildings2(self, heights: List[int]) -> List[int]:
	right_max, res = 0, []
	for i in reversed(range(len(heights))):
		if heights[i] > right_max:
			res.append(i)
		right_max = max(right_max, heights[i])
	return res[::-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of strings words and a width maxWidth, format the text such that each line has exactly maxWidth characters and is fully (left and right) justified.

You should pack your words in a greedy approach; that is, pack as many words as you can in each line. Pad extra spaces ' ' when necessary so that each line has exactly maxWidth characters.

Extra spaces between words should be distributed as evenly as possible. If the number of spaces on a line does not divide evenly between words, the empty slots on the left will be assigned more spaces than the slots on the right.

For the last line of text, it should be left-justified and no extra space is inserted between words.

Note:

A word is defined as a character sequence consisting of non-space characters only. Each word’s length is guaranteed to be greater than 0 and not exceed maxWidth.
The input array words contains at least one word.

Example 1:

Input: words = [“This”, “is”, “an”, “example”, “of”, “text”, “justification.”], maxWidth = 16
Output:
[
   “This    is    an”,
   “example  of text”,
   “justification.  “
]


Example 2:

Input: words = [“What”,”must”,”be”,”acknowledgment”,”shall”,”be”], maxWidth = 16
Output:
[
  “What   must   be”,
  “acknowledgment  “,
  “shall be        “
]
Explanation: Note that the last line is “shall be    “ instead of “shall     be”, because the last line must be left-justified instead of fully-justified.
Note that the second line is also left-justified becase it contains only one word.


Example 3:

Input: words = [“Science”,”is”,”what”,”we”,”understand”,”well”,”enough”,”to”,”explain”,”to”,”a”,”computer.”,”Art”,”is”,”everything”,”else”,”we”,”do”], maxWidth = 20
Output:
[
  “Science  is  what we”,
  “understand      well”,
  “enough to explain to”,
  “a  computer.  Art is”,
  “everything  else  we”,
  “do                  “
]


Constraints: 1 <= words.length <= 300
1 <= words[i].length <= 20 words[i] consists of only English letters and symbols.
1 <= maxWidth <= 100 words[i].length <= maxWidth

题目大意：

加入尽量均等的空格使得单词组成的每行左右对齐

Round Robin加入space解题思路(推荐)：

法二是先将一个space加入到预结果，再计算extra spaces，计算比较复杂。此法与maxWidth比较时，用1个space，而最后不区分正常space和extra space，将space按round robin方法加入，不用考虑法二复杂的计算公式。

注意事项：

  1. 关键变量两个word_list, cur_len. 用目前结果cur_len + 空格个数 + 准加入单词长度与maxWidth比较。1个单词和2个单词以上的空格情况都照顾到了。
  2. i % (len(word_list) - 1)若长度为1时候，不能对0取余，所以此情况要变成1， 加入or 1。word_list中的单词加入空格
  3. 最后一行用ljust向左对齐，右边补齐空格

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
	res = []
	word_list, cur_len = [], 0
	for word in words:
		if cur_len + len(word_list) + len(word) > maxWidth:
			for i in range(maxWidth - cur_len):
				word_list[i % (len(word_list) - 1 or 1)] += ' '
			res.append(''.join(word_list))
			word_list, cur_len = [], 0
		word_list.append(word)
		cur_len += len(word)
	return res + [' '.join(word_list).ljust(maxWidth)]

算法分析：

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

计算extra space算法II解题思路：

用公式计算空格数和位置：

1
extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1)

解题步骤：

N/A

注意事项：

0.1 题目要求： 若空格有多余，尽量分到前面；若某一行只有一个单词，左对齐右补空格；最后一行无论多少个单词都是左对齐右补空格
0.2 用buffer记录这一行的单词，count记录单词和空格的长度，若count + 当前单词长度大于maxWidth就处理

  1. 公式：extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1)
    有多余空格就分配到单词间隔个数中len(buffer) - 1，而不是单词个数. 商为多余的空格个数，余数为从第几位开始，减一个空格。如x x x x，idx = 1，表示平分后仍多出一个空格，所以分配到第0个到第1个单词之间，也就是[:idx + 1]中，而剩余的buffer[idx + 1:]比上述少一个空格。它们之间的连接用较少空格数
  2. 公式中若余数为0， 表示全部平均分配，这时要取extra_space_num + 1，所以令idx = len(buffer) - 1。 extra_space_num + 1里面的1是原本就应该有一个空格，所以此情况并没有额外多空格。
  3. 公式中len(buffer) - 1可能为0，所以要特别处理，对应到题目要求的第二点
  4. 最后一行是buffer的内容，出来for循环后，向右加空格，对应到题目要求的第三点，代码与第二点要求类似

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
def fullJustify(self, words: List[str], maxWidth: int) -> List[str]:
	# words.append(' ' * maxWidth)
	buffer, count, res = [], 0, []
	for word in words:
		new_length = len(word) if len(buffer) == 0 else 1 + len(word)
		if count + new_length <= maxWidth:
			buffer.append(word)
			count += new_length
		else:
			num_space_left = maxWidth - count # 3
			if len(buffer) > 1:
				extra_space_num, idx = math.ceil(num_space_left / (len(buffer) - 1)), num_space_left % (len(buffer) - 1) # 3, 0
				if idx == 0:
					idx = len(buffer) - 1
				tmp = (' ' * (extra_space_num + 1)).join(buffer[:idx + 1]) + (' ' * extra_space_num) #
				tmp += (' ' * extra_space_num).join(buffer[idx + 1:])
				res.append(tmp.strip())
			else:
				tmp = buffer[0] + (' ' * (maxWidth - len(buffer[0])))
				res.append(tmp)
			buffer = [word]
			count = len(word)

	if buffer:
		res.append(' '.join(buffer))
		res[-1] += (' ' * (maxWidth - len(res[-1])))
	return res

算法分析：

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

Free mock interview