KK's blog

LeetCode 005 Longest Palindromic Substring

Posted on 2021-12-19 Edited on 2022-02-07 Disqus:

Given a string s, return the longest palindromic substring in s.

Example 1:

Input: s = “babad”
Output: “bab”
Explanation: “aba” is also a valid answer.

Example 2:

Input: s = “cbbd”
Output: “bb”

Constraints:

1 <= s.length <= 1000 s consist of only digits and English letters.

题目大意：

最长回文

解题思路：

遍历每个字符，以该字符为中心，往前后比较是否回文，求最长回文

解题步骤：

N/A

注意事项：

回文字符串的中心位可以为1个或2个
此题求最长回文字符串，而不是其长度
避免死循环，记得i -= 1, j += 1
Line 63 若不相等，要break，或者return[i + 1:j]和下面return一样

Python代码：

def longestPalindrome(self, s: str) -> str:
	res = ''
	for i in range(len(s)):
		tmp = self.longestPalindromeFromCenter(s, i, i)
		if len(tmp) > len(res):
			res = tmp
		if i + 1 < len(s):
			tmp = self.longestPalindromeFromCenter(s, i, i + 1)
			if len(tmp) > len(res):
				res = tmp
	return res

def longestPalindromeFromCenter(self, s, left, right):
	while left >= 0 and right <= len(s) - 1:
		if s[left] != s[right]:
			break
		left -= 1
		right += 1
	return s[left + 1:right]

算法分析：

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

LeetCode 815 Bus Routes

Posted on 2021-12-19 Edited on 2022-02-11 Disqus:

LeetCode

You are given an array routes representing bus routes where routes[i] is a bus route that the ith bus repeats forever.

For example, if routes[0] = [1, 5, 7], this means that the 0th bus travels in the sequence 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... forever.

You will start at the bus stop source (You are not on any bus initially), and you want to go to the bus stop target. You can travel between bus stops by buses only.

Return the least number of buses you must take to travel from source to target. Return -1 if it is not possible.

Example 1:

Input: routes = [[1,2,7],[3,6,7]], source = 1, target = 6
Output: 2
Explanation: The best strategy is take the first bus to the bus stop 7, then take the second bus to the bus stop 6.

Example 2:

Input: routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
Output: -1

Constraints: 1 <= routes.length <= 500.
1 <= routes[i].length <= 105 All the values of routes[i] are unique.
sum(routes[i].length) <= 105 0 <= routes[i][j] < 106
* 0 <= source, target < 106

题目大意：

求公交路线中最小换站次数

解题思路：

最值题且涉及到图，容易想到BFS。但此题难点在于不能将每个站作为一个节点，这样代码复杂且TLE。优化的做法是将路线作为节点，因为同一路线换站次数是一样的。属于一组节点作为一层的BFS。

解题步骤：

N/A

注意事项：

将整条路线作为图的节点。这些节点都位于同一层，换乘不同路线才会换到下一层，路径+1
source和target所在的路线可能是多个，所以要将target所在的所有路线放在set中
邻接表计算是用两条路线是否有交集，有交集才能换乘，才能进入下一层访问，Python用set(a) & set(b)
如果target和source相等，返回0 (相等test case)
站点不存在或者不存在任何路线，就返回-1

Python代码：

def numBusesToDestination(self, routes: List[List[int]], source: int, target: int) -> int:
	if target == source: # remember
		return 0
	graph = collections.defaultdict(list) # both set or list are fine
	queue, targets, visited, distance = collections.deque(), set(), set(), collections.defaultdict(int)
	for i in range(len(routes)):
		if source in set(routes[i]):
			queue.append(i)
			visited.add(i)
			distance[i] = 1
		if target in set(routes[i]):
			targets.add(i)
		for j in range(i + 1, len(routes)):
			if set(routes[i]) & set(routes[j]):
				graph[i].append(j)
				graph[j].append(i)

	while queue:
		node = queue.popleft()
		if node in targets:
			return distance[node]
		for neighbor in graph[node]:
			if neighbor in visited:
				continue
			queue.append(neighbor)
			visited.add(neighbor)
			distance[neighbor] = distance[node] + 1
	return -1 # remember

TLE版本用station作为节点

Python代码：

def numBusesToDestination2(self, routes: List[List[int]], source: int, target: int) -> int:
	if target == source: # remember
		return 0
	graph, station_to_route = collections.defaultdict(list), collections.defaultdict(set)
	for j in range(len(routes)):
		r = routes[j] + [routes[j][0]]
		for i in range(1, len(r)):
			# graph[r[i - 1]].append(r[i])
			station_to_route[r[i]].add(j)

	queue = collections.deque()
	visited = set()
	bus_num = collections.defaultdict(int)  # remember collections.defaultdict(lambda: 1)
	for j in station_to_route[source]:
		for i in routes[j]:
			if i in visited:
				continue
			queue.append(i)
			visited.add(i)
			bus_num[i] = 1

	while queue:
		node = queue.popleft()
		if node == target:
			return bus_num[node]
		for j in station_to_route[node]:
			for i in routes[j]:
				if i in visited:
					continue
				queue.append(i)
				visited.add(i)
				bus_num[i] = bus_num[node] + 1
	return -1 # remember

算法分析：

时间复杂度为O(n²)，空间复杂度O(n²), n = num of routes

LeetCode 809 Expressive Words

Posted on 2021-12-18 Edited on 2022-01-30 Disqus:

LeetCode

Sometimes people repeat letters to represent extra feeling. For example:

"hello" -> "heeellooo" "hi" -> "hiiii"

In these strings like "heeellooo", we have groups of adjacent letters that are all the same: "h", "eee", "ll", "ooo".

You are given a string s and an array of query strings words. A query word is stretchy if it can be made to be equal to s by any number of applications of the following extension operation: choose a group consisting of characters c, and add some number of characters c to the group so that the size of the group is three or more.

For example, starting with "hello", we could do an extension on the group "o" to get "hellooo", but we cannot get "helloo" since the group "oo" has a size less than three. Also, we could do another extension like "ll" -> "lllll" to get "helllllooo". If s = "helllllooo", then the query word "hello" would be stretchy because of these two extension operations: query = "hello" -> "hellooo" -> "helllllooo" = s.

Return the number of query strings that are stretchy.

Example 1:

Input: s = “heeellooo”, words = [“hello”, “hi”, “helo”]
Output: 1
Explanation:
We can extend “e” and “o” in the word “hello” to get “heeellooo”.
We can’t extend “helo” to get “heeellooo” because the group “ll” is not size 3 or more.

Example 2:

Input: s = “zzzzzyyyyy”, words = [“zzyy”,”zy”,”zyy”]
Output: 3

Constraints: 1 <= s.length, words.length <= 100
1 <= words[i].length <= 100 s and words[i] consist of lowercase letters.

题目大意：

Cisco常考题
定义了一种富于表现力的单词，就是说某个字母可以重复三次或以上，叫stretchy
找给定的单词列表中的单词可以成为stretchy单词的个数

解题思路：

统计每个字符的个数，然后比较对应每个字符个数

解题步骤：

N/A

注意事项：

Line 13的条件，若个数不等，word的字符个数大于stretchy的字符个数(word不能删除字符)，或者stretchy的个数小于3，就不满足

Python代码：

def expressiveWords(self, s: str, words: List[str]) -> int:
	res = 0
	s_count = self.get_consecutive_count(s)
	for word in words:
		char_count = self.get_consecutive_count(word)
		if len(char_count) != len(s_count):
			continue
		for i in range(len(s_count)):
			char_s, count_s = s_count[i]
			char_w, count_w = char_count[i]
			if char_w != char_s:
				break
			if count_s != count_w and (count_w > count_s or count_s < 3): # remember
				break
			if i == len(s_count) - 1:
				res += 1
	return res

def get_consecutive_count(self, s):
	s += ' '
	s_count, count = [], 1
	for i in range(1, len(s)):
		if s[i] != s[i - 1]:
			s_count.append((s[i - 1], count))
			count = 0
		count += 1
	return s_count

算法分析：

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

LeetCode 829 Consecutive Numbers Sum

Posted on 2021-12-16 Disqus:

LeetCode

Given an integer n, return the number of ways you can write n as the sum of consecutive positive integers.

Example 1:

Input: n = 5
Output: 2
Explanation: 5 = 2 + 3

Example 2:

Input: n = 9
Output: 3
Explanation: 9 = 4 + 5 = 2 + 3 + 4

Example 3:

Input: n = 15
Output: 4
Explanation: 15 = 8 + 7 = 4 + 5 + 6 = 1 + 2 + 3 + 4 + 5

Constraints:

* 1 <= n <= 109

题目大意：

求连续整数的和等于N的个数

解题思路：

只有Fintech考，数学题。思路见注释

解题步骤：

N/A

注意事项：

Python代码：

# x, x+1, ... , x+k-1
# (x + x+k-1) * k / 2 = 2x+k-1) = n, x = [n - k(k-1)/2]/k
def consecutiveNumbersSum(self, n: int) -> int:
	res = 1
	for i in range(2, int(math.sqrt(2 * n) + 1)):
		if (n - i * (i - 1) / 2) % i == 0:
			res += 1
	return res

算法分析：

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

LeetCode 041 First Missing Positive

Posted on 2021-12-16 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)