KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.

  • For example, for arr = [2,3,4], the median is 3.
  • For example, for arr = [2,3], the median is (2 + 3) / 2 = 2.5.

Implement the MedianFinder class:

  • MedianFinder() initializes the MedianFinder object.
  • void addNum(int num) adds the integer num from the data stream to the data structure.
  • double findMedian() returns the median of all elements so far. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Example 1:

<pre>Input ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] Output [null, null, null, 1.5, null, 2.0]

Explanation MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0 </pre>

Constraints:

  • -10<sup>5</sup> <= num <= 10<sup>5</sup>
  • There will be at least one element in the data structure before calling findMedian.
  • At most 5 * 10<sup>4</sup> calls will be made to addNum and findMedian.

Follow up:

  • If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
  • If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

</div>

题目大意：

求动态中位数

算法思路：

用max_heap, min_heap, 保证min_heap个数永远等于max_heap或多一个。插入元素先进max_heap, 再heappop将堆顶元素加入min_heap, 若此时比max_heap多2个，就再heappop加入到max_heap.

注意事项：

  1. 中位数有1-2个
  2. Python中的max_heap用负数实现，入堆出堆都要取反

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class MedianFinder(TestCases):

    def __init__(self):
        self.max_heap = []
        self.min_heap = []

    def addNum(self, num: int) -> None:
        heapq.heappush(self.max_heap, -num)
        max_value = -heapq.heappop(self.max_heap)
        heapq.heappush(self.min_heap, max_value)
        if len(self.min_heap) - len(self.max_heap) >= 2:
            min_value = heapq.heappop(self.min_heap)
            heapq.heappush(self.max_heap, -min_value)

    def findMedian(self) -> float:
        if len(self.max_heap) == len(self.min_heap):
            return (-self.max_heap[0] + self.min_heap[0]) / 2
        else:
            return self.min_heap[0]

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

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:

<pre>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". </pre>

Example 2:

<pre>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. </pre>

Example 3:

<pre>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".</pre>

Example 4:

<pre>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. </pre>

Constraints:

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

</div>

题目大意：

相邻相同字母用数字压缩

解题思路：

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 Edited on Disqus:

LeetCode

<div>

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:

<pre>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. </pre>

Example 2:

<pre>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. </pre>

Constraints:

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

</div>

题目大意：

子串中，连续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).

注意事项：

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

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
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)

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 2<sup>31</sup> - 1.

Example 1:

<pre>Input: 123 Output: "One Hundred Twenty Three" </pre>

Example 2:

<pre>Input: 12345 Output: "Twelve Thousand Three Hundred Forty Five"</pre>

Example 3:

<pre>Input: 1234567 Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven" </pre>

Example 4:

<pre>Input: 1234567891 Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven Thousand Eight Hundred Ninety One" </pre>

题目大意：

这是将非负整数转化为其英文单词表示。给定输入确保小于 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

<div>

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

Example 1:

<pre>Input: s = "aba" Output: true </pre>

Example 2:

<pre>Input: s = "abca" Output: true Explanation: You could delete the character 'c'. </pre>

Example 3:

<pre>Input: s = "abc" Output: false </pre>

Constraints:

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

</div>

题目大意：

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

解题思路：

暴力法是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)

Free mock interview