KK's blog

LeetCode 696 Count Binary Substrings

Posted on 2021-12-20 Edited on 2026-06-03 Disqus:

Give a binary string s, return the number of non-empty substrings that have the same number of 0‘s and 1‘s, and all the 0‘s and all the 1‘s in these substrings are grouped consecutively.

Substrings that occur multiple times are counted the number of times they occur.

Example 1:

Input: s = “00110011”
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1’s and 0’s: “0011”, “01”, “1100”, “10”, “0011”, and “01”.
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.

Example 2:

Input: s = “10101”
Output: 4
Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.

Constraints:

1 <= s.length <= 10<sup>5</sup> s[i] is either '0' or '1'.

题目大意：

子串中，连续0和连续1的个数中间对称，求这样的子串的个数

算法思路：

这题至少medium，一开始考虑给定一个字符串怎么判断是否满足条件，统计个数和flag变化。然后是双重循环分别以a[0..n-1]为开头的子串判断，若不满足就跳出内循环，复杂度为O(n).
既然是连续，又是只有0和1，不妨考虑统计个数。如00110011,统计0和1的个数为count=[2,2,2,2]相邻的数代表不同种类，所以去min(count[i-1], count[i])，如2, 2可以是01/10, 0011/1100两种，具体以哪个数开始取决于数组本身。统计i=[1..n-1]即所求。复杂度为O(n).

注意事项：

累计思想，按0和1累计得到累计数组，然后求相邻最小个数的和。
循环出来，处理最后一个部分。

Python代码：

def countBinarySubstrings(self, s: str) -> int:
	presum, count, res = [], 1, 0
	for i in range(1, len(s)): #
		if s[i - 1] == s[i]:
			count += 1
		else:
			presum.append(count) #[2, 2,2,2]
			count = 1
	if count > 0:
		presum.append(count)
	for i in range(1, len(presum)):
		res += min(presum[i - 1], presum[i])
	return res

算法分析：

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

LeetCode 273 Integer to English Words

Posted on 2021-12-19 Edited on 2026-06-03 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 2³¹ - 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以下，百位，千位…递归，递归的颗粒度更小，程序更简单。

注意事项：

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

Python代码：

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 ''

注意事项：

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

Java代码：

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回来。

注意事项：

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

Java代码：

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)。

LeetCode 680 Valid Palindrome II

Posted on 2021-12-19 Edited on 2026-06-04 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

注意事项：

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

Python代码：

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)

LeetCode 041 First Missing Positive

Posted on 2021-12-16 Edited on 2026-06-03 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 10⁵*-2³¹ <= nums[i] <= 2³¹ - 1`

题目大意：

找第一个缺失的正整数

解题思路：

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

解题步骤：

N/A

注意事项：

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

Python代码：

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)

LeetCode 1041 Robot Bounded In Circle

Posted on 2021-12-16 Edited on 2026-06-03 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代码：

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)