KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.

If the fractional part is repeating, enclose the repeating part in parentheses.

If multiple answers are possible, return any of them.

It is guaranteed that the length of the answer string is less than 10<sup>4</sup> for all the given inputs.

Example 1:

Input: numerator = 1, denominator = 2
Output: “0.5”


Example 2:

Input: numerator = 2, denominator = 1
Output: “2”


Example 3:

Input: numerator = 4, denominator = 333
Output: “0.(012)”


Constraints:

-2<sup>31</sup> <= numerator, denominator <= 2<sup>31</sup> - 1 denominator != 0

题目大意：

N/A

解题思路：

小学定理为若余数重复则前重复对应的结果到目前位置的前一位为循环体

解题步骤：

N/A

注意事项：

  1. 小学定理为若余数重复则前重复对应的结果到目前位置的前一位为循环体，并不是digit一样，而是余数。类似于L003 Longest Substring Without Repeating Characters，记录余数到商下标。循环中顺序很重要，与长除法一致(上图)。分子为remainder，查看remainder是否重复，若否，加入到map，乘以10，求商和新余数，进入下一轮迭代。
  2. 输入均为负数或其一为负数的情况，计算结果符号，分子分母分别转成正数
  3. 分子大于分母或分子小于分母的情况都归结为用分子除以分母，加入到结果，若有余数，再加小数点

Line 26 - 27与Line 16 - 17一致

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 fractionToDecimal(self, numerator: int, denominator: int) -> str:
	res, remainder_to_pos = '', collections.defaultdict(int)
	is_negative, remainder = 1, 0
	if numerator / denominator < 0:
		is_negative = -1
	numerator = abs(numerator)
	denominator = abs(denominator)
	'''
	if numerator < denominator:
		res = '0.'
		remainder = numerator
	else:
		res = str(numerator // denominator)
		remainder = numerator % denominator
	'''
	res = str(numerator // denominator)
	remainder = numerator % denominator
	if remainder > 0:
		res += '.'
	while remainder > 0:
		if remainder in remainder_to_pos:
			res = res[:remainder_to_pos[remainder]] + '(' + res[remainder_to_pos[remainder]:] + ')'
			break
		remainder_to_pos[remainder] = len(res)  # remember
		remainder *= 10 # remember not numerator * 10 // denominator
		res += str(remainder // denominator)
		remainder %= denominator
	return res if is_negative == 1 else '-' + res

算法分析：

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

Posted on Edited on Disqus:

LeetCode 2074 Reverse Nodes in Even Length Groups



You are given the head of a linked list.

The nodes in the linked list are sequentially assigned to non-empty groups whose lengths form the sequence of the natural numbers (1, 2, 3, 4, ...). The length of a group is the number of nodes assigned to it. In other words,

The 1<sup>st</sup> node is assigned to the first group. The 2<sup>nd</sup> and the 3<sup>rd</sup> nodes are assigned to the second group.
The 4<sup>th</sup>, 5<sup>th</sup>, and 6<sup>th</sup> nodes are assigned to the third group, and so on.

Note that the length of the last group may be less than or equal to 1 + the length of the second to last group.

Reverse the nodes in each group with an even length, and return the head of the modified linked list.

Example 1:



Input: head = [5,2,6,3,9,1,7,3,8,4]
Output: [5,6,2,3,9,1,4,8,3,7]
Explanation:
- The length of the first group is 1, which is odd, hence no reversal occurrs.
- The length of the second group is 2, which is even, hence the nodes are reversed.
- The length of the third group is 3, which is odd, hence no reversal occurrs.
- The length of the last group is 4, which is even, hence the nodes are reversed.


Example 2:



Input: head = [1,1,0,6]
Output: [1,0,1,6]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the second group is 2. The nodes are reversed.
- The length of the last group is 1. No reversal occurrs.


Example 3:



Input: head = [2,1]
Output: [2,1]
Explanation:
- The length of the first group is 1. No reversal occurrs.
- The length of the last group is 1. No reversal occurrs.


Example 4:

Input: head = [8]
Output: [8]
Explanation: There is only one group whose length is 1. No reversal occurrs.


Constraints: The number of nodes in the list is in the range [1, 10<sup>5</sup>].
* 0 <= Node.val <= 10<sup>5</sup>

题目大意：

把链表分成1,2,3..n大小的组。若该组大小为偶数，反转链表。

解题思路：

一开始考虑分奇偶组来处理，但忽略了最后一组也可能为偶数。用stack来，先做统计，若为偶数，就出栈且反转。
后来为了程序更加简洁，就独立一个函数出来按组处理。而每组用迭代将后续节点一个个加到上一组末节点和首节点之间。

解题步骤：

  1. 按组处理
  2. 每组先统计个数，如果为偶数，反转链表

start(group n) -> end(group n+1, head of group n+1 will become new tail after reversed) -> …
不断将end直接后面的节点加到start直接后面
start(group n) -> NodeA （新状态） -> … -> end(group n+1) -> NodeA （前状态） -> …

注意事项：

  1. 若最后一组不满为偶数，也要逆转。
  2. 反转链表时，个数为这组大小减一，因为该组的首节点不用反转。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def reverseEvenLengthGroups(self, head: Optional[ListNode]) -> Optional[ListNode]:
	group, cur = 2, head
	while cur.next:
		cur = self.process_one_group(cur, group)
		group += 1
	return head

def process_one_group(self, tail_of_last: ListNode, n: int) -> ListNode:
	cur, count = tail_of_last, 0
	while cur.next and count < n:
		cur = cur.next
		count += 1
	if count % 2 == 0:
		start, end = tail_of_last, tail_of_last.next
		for i in range(count - 1):
			# delete the node
			moved_node, end.next = end.next, end.next.next
			# insert the moved_node
			start.next, moved_node.next = moved_node, start.next
	cur = tail_of_last
	for i in range(count):
		cur = cur.next
	return cur

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.

Implement the ZigzagIterator class:

ZigzagIterator(List<int> v1, List<int> v2) initializes the object with the two vectors v1 and v2. boolean hasNext() returns true if the iterator still has elements, and false otherwise.
int next() returns the current element of the iterator and moves the iterator to the next element.

Example 1:

Input: v1 = [1,2], v2 = [3,4,5,6]
Output: [1,3,2,4,5,6]
Explanation: By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,3,2,4,5,6].


Example 2:

Input: v1 = [1], v2 = []
Output: [1]


Example 3:

Input: v1 = [], v2 = [1]
Output: [1]


Constraints: 0 <= v1.length, v2.length <= 1000
1 <= v1.length + v2.length <= 2000 -2<sup>31</sup> <= v1[i], v2[i] <= 2<sup>31</sup> - 1

Follow up: What if you are given k vectors? How well can your code be extended to such cases?

Clarification for the follow-up question:

The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”.

Follow-up Example:

Input: v1 = [1,2,3], v2 = [4,5,6,7], v3 = [8,9]
Output: [1,4,8,2,5,9,3,6,7]


题目大意：

求两数组轮替取值的Iterator

解题思路：

将数组和数组下标分别存于新数组中。用一个list_index来记录要取哪个数组

解题步骤：

N/A

注意事项：

  1. 用Iterator模板，hasNext也是找到下一个元素为止，由于只有两个数组，所以不用循环。取值是一个二维数组val = self.input[self.list_index][self.index[self.list_index]]
  2. next中取值后指针要后移。

Python代码：

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

    def __init__(self, v1: List[int], v2: List[int]):
        self.input = [v1, v2]
        self.index = [0, 0]
        self.list_index = 0

    def next(self) -> int:
        if self.hasNext():
            val = self.input[self.list_index][self.index[self.list_index]]
            self.index[self.list_index] += 1
            self.list_index = (self.list_index + 1) % 2
            return val
        return None

    def hasNext(self) -> bool:
        if self.index[self.list_index] < len(self.input[self.list_index]):
            return True
        self.list_index = (self.list_index + 1) % 2
        return self.index[self.list_index] < len(self.input[self.list_index])

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.

The test cases are generated so that the answer can fit in a 32-bit integer.

Example 1:

Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.


Example 2:

Input: nums = [9], target = 3
Output: 0


Constraints:

1 <= nums.length <= 200 1 <= nums[i] <= 1000
All the elements of nums are unique. 1 <= target <= 1000

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

题目大意：

求所有可能组合的和等于target。元素可以复用且顺序在组合中可以任意。

LeetCode 377 Combination Sum IV 题目基本一样，唯一区别是结果元素有序，属于排列
LeetCode 518 Coin Change 2 题目基本一样，唯一区别是结果元素无序，属于组合

解题思路：

这题似组合又似排列，是组合的结果再全排列。求种数另一种的方法是DP. dp[n]为target=n所有的所有组合种数。属于数值->个数型DP
递归公式

1
dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]

解题步骤：

N/A

注意事项：

  1. dp[i + nums[j]] += dp[i] 而不是dp[i] + 1
  2. dp[0] = 1表示数值为0，可以不用任何数就能获得，所以是1种
  3. 先排序，否则如[3, 1, 2, 4]，返回dp[1] = 0, 但应该是dp[1] = 1

Python代码：

1
2
3
4
5
6
7
8
9
10
11
# dp[n + num[i]] = dp[n], n = [1, tgt], i = [0, len(nums) - 1]
def combinationSum4(self, nums: List[int], target: int) -> int:
	nums.sort() # remember
	dp = [0] * (target + 1)
	dp[0] = 1
	for i in range(len(dp)):
		for j in range(len(nums)):
			if i + nums[j] > target:
				break
			dp[i + nums[j]] += dp[i] # remember no +1
	return dp[-1]

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.

Example 1:

Input: s = “aaabb”, k = 3
Output: 3
Explanation: The longest substring is “aaa”, as ‘a’ is repeated 3 times.


Example 2:

Input: s = “ababbc”, k = 2
Output: 5
Explanation: The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.


Constraints:

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

题目大意：

求最长每种字符至少k个的子串

解题思路：

类似于L003 Longest Substring Without Repeating Characters用双指针法，难点是每种字符，用26字母存储法解决。
前面的sliding window题都要求字符种数是固定的，否则不单调，例如本题。如aabbcc, i=1, “aa”,满足题目条件，但向右移就不满足条件，但事实再移一位就满足条件
若修改为n=2, 也就是收缩条件为字符窗口必须有两种字符，若出现3个就shrink直到只有两个字符，而这个窗口忽略了每个字符都要出现k个的条件。
举例aabb, i=3, res=4. i=4, aabbc, 出现3种字符，shrink到bbc, 再扩展到bbcc.

此题关键在于将收缩条件：每个字符出现k次转化成字符种数=n再计算k

解题步骤：

N/A

注意事项：

  1. 按多少种不同字符来做sliding window。有1-26种。
  2. 子函数求给定种数下的最长子串，所以满足条件在外循环不在内循环，还需进一步统计每种字符是否符合k个。内循环为不满足条件的情况len(char_to_count) == n + 1
  3. char_to_count记录每种字符个数, valid_count是子串[left, i]之间满足题意中个数大于等于k的种数。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def longestSubstring(self, s: str, k: int) -> int:
	res = 0
	for i in range(1, 27):
		res = max(res, self.longest_substring(s, k, i))
	return res

def longest_substring(self, s, k, n) -> int:
	left, char_to_count = 0, collections.defaultdict(int)
	res = 0
	for i in range(len(s)):
		char_to_count[ord(s[i]) - ord('a')] += 1
		while len(char_to_count) == n + 1:
			char_to_count[ord(s[left]) - ord('a')] -= 1 # use left not i
			if char_to_count[ord(s[left]) - ord('a')] == 0:
				char_to_count.pop(ord(s[left]) - ord('a'))
			left += 1
		valid_count = len([_ for _ in char_to_count.values() if _ >= k])
		if len(char_to_count) == valid_count:
			res = max(res, i - left + 1)
	return res

算法分析：

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

Free mock interview