KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode 273 Integer to English Words

Convert a non-negative integer to its english words representation. Given input is guaranteed to be less than 231 - 1.

Example 1:

**Input:** 123
**Output:** "One Hundred Twenty Three"

Example 2:

**Input:** 12345
**Output:** "Twelve Thousand Three Hundred Forty Five"

Example 3:

**Input:** 1234567
**Output:** "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven"

Example 4:

**Input:** 1234567891
**Output:** "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One"

题目大意：

这是将非负整数转化为其英文单词表示。给定输入确保小于 2 ^ 31 - 1

解题思路(推荐)：

第二种方法是按千位递归的。下面的方法是按20以下，100以下，百位，千位…递归，递归的颗粒度更小，程序更简单。

注意事项：

  1. 在入口方法中，若num为0，则返回Zero，要单独列出。
  2. 在递归中，num为0要单独列出，因为0表示此位不存在，可以记在dict中或返回空字符串。
  3. strip来去掉空格。

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
NUM_DICT = {
    0: '',
    1: 'One',
    2: 'Two',
    3: 'Three',
    4: 'Four',
    5: 'Five',
    6: 'Six',
    7: 'Seven',
    8: 'Eight',
    9: 'Nine',
    10: 'Ten',
    11: 'Eleven',
    12: 'Twelve',
    13: 'Thirteen',
    14: 'Fourteen',
    15: 'Fifteen',
    16: 'Sixteen',
    17: 'Seventeen',
    18: 'Eighteen',
    19: 'Nineteen',
    20: 'Twenty',
    30: 'Thirty',
    40: 'Forty',
    50: 'Fifty',
    60: 'Sixty',
    70: 'Seventy',
    80: 'Eighty',
    90: 'Ninety',
}
class Solution(TestCases):

    def numberToWords(self, num: int) -> str:
        if num == 0:
            return 'Zero'
        return self.dfs(num)

    def dfs(self, num: int) -> str:
        if num < 20:
            return NUM_DICT[num]
        elif num < 100:
            return (NUM_DICT[num // 10 * 10] + ' ' + self.dfs(num % 10)).strip()
        elif num < 1000:
            return (NUM_DICT[num // 100] + ' Hundred ' + self.dfs(num % 100)).strip()
        elif num < 1000000:
            return (self.dfs(num // 1000) + ' Thousand ' + self.dfs(num % 1000)).strip()
        elif num < 1000000000:
            return (self.dfs(num // 1000000) + ' Million ' + self.dfs(num % 1000000)).strip()
        elif num < 1000000000000:
            return (self.dfs(num // 1000000000) + ' Billion ' + self.dfs(num % 1000000000)).strip()
        return ''

注意事项：

  1. 空格总加在新数前面，只需要加在有返回值的时候，也就是tens和lows中，其他如numberToWordsR(number/1000)
    可能返回空值，此时不在前面加空格。
  2. 在递归中，num为0要单独列出，因为0表示此位不存在，也就是无返回值。
  3. 在入口方法中，若num为0，则返回Zero，要单独列出。

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public String numberToWords(int number) {
	if (number == 0)
		return "Zero";
	
	return numberToWordsR(number).trim();
}

public String numberToWordsR(int number) {
	if(number == 0) {
		return "";
	} else if (number < 20) {
		return " " + lows[number];
	} else if (number < 100) {
		return " " + tens[number / 10] + numberToWordsR(number % 10);
	} else if (number < 1000) {
		return " " + lows[number / 100] + " Hundred" + numberToWordsR(number % 100);
	} else if (number < 1000000) {
		return numberToWordsR(number / 1000) + " Thousand" + numberToWordsR(number % 1000);
	} else if (number < 1000000000) {
		return numberToWordsR(number / 1000000) + " Million" + numberToWordsR(number % 1000000);
	} else {
		return numberToWordsR(number / 1000000000) + " Billion" + numberToWordsR(number % 1000000000);
	}
}

算法II每三位解题思路：

这是logical and maintainable的经典题。按照英语的习惯，每三位是一组，所以实现的时候，也是按千为分组，有一个方法去处理一千
内的数。一千以内也分为三种情况，20以内，几十，其他。20以内和几十都是特殊情况的单词，所以可以放入数组或HashMap，数组比较
好，因为可以直接用索引读出。大于一千的数，可以用递归来做，从人的习惯，从低位到高位，每三位加一个逗号分隔。所以同样，算法
也是从低位开始，若千位内的数大于0，加入Thousand, Million等，每三位调用千位方法，再递归。
group的引入作为递归的层次来决定Thousand还是Million。
由于从低位递归，所以倒着做，要reverse地加入到结果，最终结果再reverse回来。

注意事项：

  1. 空格总加在新数前面，也就是append前先加空格
  2. 低3位大于0才加Thousand, Million等词，也就是低三位在1-999之间，若为0如1 million。

Java代码：

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
public String[] lows = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", 
   "Eleven", "Twelve","Thirteen", "Fourteen","Fifteen","Sixteen","Seventeen","Eighteen", "Nineteen"};

public String[] tens = {"", "", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};

public String numberToWords(int number) {
	if(number == 0) {
		return "Zero";	
	}

	StringBuilder result = new StringBuilder();

	translateThreeR(number, result, 0);
	return result.reverse().toString().trim();
}

public void translateThreeR(int number, StringBuilder result, int group) {
	int lower = number % 1000;
	int thousands = number / 1000;     

	if (group == 1 && lower > 0)
		result.append(reverse(" Thousand"));
	else if (group==2 && lower > 0)
		result.append(reverse(" Million"));
	else if (group==3 && lower > 0)
		result.append(reverse(" Billion"));
	
	if(lower>0)
		result.append(reverse(translateThree(lower)));
	
	if(thousands >= 1) {
		translateThreeR(thousands, result, ++group);
	}

}

public String translateThree(int number) {
	StringBuilder result = new StringBuilder();
	if(number > 99) {
		result.append(" "+lows[number / 100]);
		result.append(" Hundred");
		number = number % 100;
	}

	if(number > 19) {
		result.append(" ");
		result.append(tens[number/10]);
		number = number % 10;
	}

	// Remainder is under 20
	result.append(" "+lows[number]);
	return " "+result.toString().trim();
}

public String reverse(String s) {
	return (new StringBuilder()).append(s).reverse().toString();
}

算法分析：

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

Follow-up：

integer, minus, decimals, internationlization(localization)。

Posted on Edited on Disqus:

LeetCode



Given a string s, return true if the s can be palindrome after deleting at most one character from it.

Example 1:

Input: s = “aba”
Output: true


Example 2:

Input: s = “abca”
Output: true
Explanation: You could delete the character ‘c’.


Example 3:

Input: s = “abc”
Output: false


Constraints:

1 <= s.length <= 10<sup>5</sup> s consists of lowercase English letters.

题目大意：

删除一个字符变成回文字符串

解题思路：

暴力法是O(n^2)，要优化到O(n)且这是关于元素之间的关系，考虑用Two pointers。 这题更类似于DP，假设左部分和右部分已经是回文，现在比较a[i]和a[j]，两种可能，这是只有一步的DP。

解题步骤：

N/A

注意事项：

  1. 当发现不相等的字符，不能简单认为s[i + 1] == s[j]就觉得应该删除左边字符，因为可能是刚好相等，如bddbd，第一个b和倒数第二个b相等，如果删除第一个b，就会得到False，所以应该删除左边字符和删除右边字符同时都要试

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def validPalindrome(self, s: str) -> bool:
	i, j = 0, len(s) - 1
	while i < j:
		if s[i] != s[j]:
			if self.is_palindrome(s[i + 1:j + 1]) or self.is_palindrome(s[i:j]):
				return True
			else:
				return False
		i += 1
		j -= 1
	return True
	
def is_palindrome(self, s):
	return s == s[::-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an unsorted integer array nums, return the smallest missing positive integer.

You must implement an algorithm that runs in O(n) time and uses constant extra space.

Example 1:

Input: nums = [1,2,0]
Output: 3


Example 2:

Input: nums = [3,4,-1,1]
Output: 2


Example 3:

Input: nums = [7,8,9,11,12]
Output: 1


Constraints:

`1 <= nums.length <= 5 105*-231 <= nums[i] <= 231 - 1`

题目大意：

找第一个缺失的正整数

解题思路：

类似于quick sort里面的partition，满足某些条件才移动指针

解题步骤：

N/A

注意事项：

  1. 第一个正确元素为1，所以预期数组为[1, 2, 3…]，从1开始并不是从0开始。
  2. 交换元素的条件：需要交换nums[i] != i + 1, 可以交换[1 <= nums[i] <= len(nums)], 不会死循环(nums[nums[i] - 1] != nums[i])
  3. 若满足条件，无限交换，直到不满足条件。不满足条件才移动遍历指针i
  4. 交换两元素涉及内嵌数组，所以不能用comment上的。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def firstMissingPositive(self, nums: List[int]) -> int:
	i = 0
	while i < len(nums):
		if nums[i] != i + 1 and 1 <= nums[i] <= len(nums) and nums[nums[i] - 1] != nums[i]:
			# nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
			self.swap(nums, i, nums[i] - 1)
		else:
			i += 1
	j = 1
	while j <= len(nums):
		if j != nums[j - 1]:
			break
		j += 1
	return j

def swap(self, nums, i, j):
	nums[i], nums[j] = nums[j], nums[i]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



On an infinite plane, a robot initially stands at (0, 0) and faces north. The robot can receive one of three instructions:

"G": go straight 1 unit; "L": turn 90 degrees to the left;
"R": turn 90 degrees to the right.

The robot performs the instructions given in order, and repeats them forever.

Return true if and only if there exists a circle in the plane such that the robot never leaves the circle.

Example 1:

Input: instructions = “GGLLGG”
Output: true
Explanation: The robot moves from (0,0) to (0,2), turns 180 degrees, and then returns to (0,0).
When repeating these instructions, the robot remains in the circle of radius 2 centered at the origin.


Example 2:

Input: instructions = “GG”
Output: false
Explanation: The robot moves north indefinitely.


Example 3:

Input: instructions = “GL”
Output: true
Explanation: The robot moves from (0, 0) -> (0, 1) -> (-1, 1) -> (-1, 0) -> (0, 0) -> …


Constraints: 1 <= instructions.length <= 100
* instructions[i] is 'G', 'L' or, 'R'.

题目大意：

循环按模式走是否回到原点

解题思路：

数学题，很难证明。定理是，只要按照给定模式走完，若回到原点或最后方向不是向北，都能回到原点

解题步骤：

N/A

注意事项：

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def isRobotBounded(self, instructions: str) -> bool:
	DIRECTION_CONVERT_LEFT = {
		(0, 1): (-1, 0),
		(-1, 0): (0, -1),
		(0, -1): (1, 0),
		(1, 0): (0, 1),
	}
	DIRECTION_CONVERT_RIGHT = {
		(0, 1): (1, 0),
		(1, 0): (0, -1),
		(0, -1): (-1, 0),
		(-1, 0): (0, 1),
	}
	path, direction, position = instructions, (0, 1), (0, 0)
	for char in path:
		if char == 'L':
			direction = DIRECTION_CONVERT_LEFT[direction]
		elif char == 'R':
			direction = DIRECTION_CONVERT_RIGHT[direction]
		else:
			position = (position[0] + direction[0], position[1] + direction[1])
	return True if position == (0, 0) or direction != (0, 1) else False

算法分析：

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

Posted on Edited on Disqus:

LeetCode 239 Sliding Window Maximum



You are given an array of integers nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example 1:

Input: nums = [1,3,-1,-3,5,3,6,7], k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position                Max
—————               —–
[1  3  -1] -3  5  3  6  7       3
 1 [3  -1  -3] 5  3  6  7       3
 1  3 [-1  -3  5] 3  6  7       5
 1  3  -1 [-3  5  3] 6  7       5
 1  3  -1  -3 [5  3  6] 7       6
 1  3  -1  -3  5 [3  6  7]      7


Example 2:

Input: nums = [1], k = 1
Output: [1]


Constraints:

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

算法思路：

LL(queue) + 递减栈
难点是什么时候输出结果，并不是出栈时候，而是每轮遍历时，就可以计算当轮的最大值，也就是当前的队首。此题也可以用heap，实现几乎一样，但时间复杂度是nlogn

注意事项：

  1. 每轮遍历时，计算当轮的最大值就是当前的队首，用queue[0]而不是queue[-1]
  2. 注意程序顺序，先递减栈模板，在计算结果，最后移出越界元素。如例子[876], i = 2, 窗口大小满足了，计算结果为8,8在下一轮会越界，所以移除。
  3. 结果数小于数组大小，注意line 7的条件

Python代码：

1
2
3
4
5
6
7
8
9
10
11
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
	queue, res = deque(), []
	for i in range(len(nums)):
		while queue and nums[i] > nums[queue[-1]]:
			queue.pop()
		queue.append(i)
		if i >= k - 1:
			res.append(nums[queue[0]])#attn queue[0] not -1
		if i - queue[0] + 1 >= k: #attn queue[0] not -1
			queue.popleft()
return res

算法分析：

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

Free mock interview