KK's blog

LeetCode 003 Longest Substring Without Repeating Characters

Given a string s, find the length of the longest substring without repeating characters.

Example 1:

<pre>Input: s = "abcabcbb" Output: 3 Explanation: The answer is "abc", with the length of 3. </pre>

Example 2:

<pre>Input: s = "bbbbb" Output: 1 Explanation: The answer is "b", with the length of 1. </pre>

Example 3:

<pre>Input: s = "pwwkew" Output: 3 Explanation: The answer is "wke", with the length of 3. Notice that the answer must be a substring, "pwke" is a subsequence and not a substring. </pre>

Example 4:

<pre>Input: s = "" Output: 0 </pre>

Constraints:

• 0 <= s.length <= 5 * 10<sup>4</sup>
• s consists of English letters, digits, symbols and spaces.

题目大意：

求最长不重复子串。

解题思路：

HashMap和滑动窗口法，利用HashMap来记录这个窗口中所有字符的下标，该窗口中所有字符都不重复。
start_idx表示窗口的左界，而i是右界。左界=上次一次出现该字符的下标和目前左界的较大值，
因为Map中的某些字符可能已经不在窗口中，我没有把它从窗口中去掉，而是用start_idx来限制。

要计算长度就要先计算start_idx，步骤：

1. 计算start_idx
2. 计算长度

注意事项：

1. start_idx和前值比较，且只有当字符在map中才更新start_idx

Python代码：

1
2
3
4
5
6
7
8
9

def lengthOfLongestSubstring(self, s: str) -> int:
	start_idx, max_len = 0, 0
	char_map = {}
	for i in range(len(s)):
		if s[i] in char_map:
			start_idx = max(start_idx, char_map[s[i]] + 1)
		max_len = max(max_len, i - start_idx + 1)
		char_map[s[i]] = i
	return max_len

算法分析：

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

LeetCode

<div>

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:

<pre>Input: nums = [-1,0,1,2,-1,-4] Output: [[-1,-1,2],[-1,0,1]] </pre>

Example 2:

<pre>Input: nums = [] Output: [] </pre>

Example 3:

<pre>Input: nums = [0] Output: [] </pre>

Constraints:

• 0 <= nums.length <= 3000
• -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>

</div>

算法思路：

N/A

注意事项：

1. 先排序
2. 结果要去重，用i, j, k指针比较前一个元素，若相等指针移动跳过，k是比较后一个元素
3. 注意指针移动，等于target两指针都要移动，若与前一元素相等，相应指针移一位，要避免死循环

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 threeSum(self, nums: List[int]) -> List[List[int]]:
	nums.sort()
	res = []
	for i in range(len(nums)):
		if i > 0 and nums[i] == nums[i - 1]:
			continue
		sub_res = self.two_sum(nums, i + 1, -nums[i])
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, start, target):
	j, k, res = start, len(nums) - 1, []
	while j < k:
		if (j > start and nums[j] == nums[j - 1]) or nums[j] + nums[k] < target:
			j += 1
		elif (k < len(nums) - 1 and nums[k] == nums[k + 1]) or nums[j] + nums[k] > target:
			k -= 1
		elif nums[j] + nums[k] == target:
			res.append([nums[j], nums[k]])
			j += 1
			k -= 1
	return res

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

public List<List<Integer>> threeSum2(int[] nums) {
	List<List<Integer>> re = new ArrayList<>();
	if(nums == null || nums.length == 0)
		return re;
	Arrays.sort(nums);
	for(int i = 0; i < nums.length - 2; i++) {
		if(i > 0 && nums[i] == nums[i-1])
			continue;
		twoPointers(nums, i + 1, nums.length - 1, -nums[i], re);
	}
	return re;
}

void twoPointers(int[] nums, int left, int right, int target, List<List<Integer>> re) {
	int leftOri = left, rightOri = right;
	while(left < right) {
		if(left > leftOri && nums[left] == nums[left-1]) {
			left++;
			continue;
		}
		if(right < rightOri && nums[right] == nums[right + 1]) {
			right--;
			continue;
		}
		
		if(nums[left] + nums[right] == target) 
			re.add(Arrays.asList(-target, nums[left++], nums[right--]));
		else if(nums[left] + nums[right] < target)
			left++;
		else 
			right--;
	}
}

算法分析：

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

LeetCode

<div>

Given a string path, which is an absolute path (starting with a slash '/') to a file or directory in a Unix-style file system, convert it to the simplified canonical path.

In a Unix-style file system, a period '.' refers to the current directory, a double period '..' refers to the directory up a level, and any multiple consecutive slashes (i.e. '//') are treated as a single slash '/'. For this problem, any other format of periods such as '...' are treated as file/directory names.

The canonical path should have the following format:

• The path starts with a single slash '/'.
• Any two directories are separated by a single slash '/'.
• The path does not end with a trailing '/'.
• The path only contains the directories on the path from the root directory to the target file or directory (i.e., no period '.' or double period '..')

Return the simplified canonical path.

Example 1:

<pre>Input: path = "/home/" Output: "/home" Explanation: Note that there is no trailing slash after the last directory name. </pre>

Example 2:

<pre>Input: path = "/../" Output: "/" Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go. </pre>

Example 3:

<pre>Input: path = "/home//foo/" Output: "/home/foo" Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one. </pre>

Constraints:

• 1 <= path.length <= 3000
• path consists of English letters, digits, period '.', slash '/' or '_'.
• path is a valid absolute Unix path.

</div>

题目大意：

简化路径，遇.表示当前目录不做事，遇..表示到上一个目录

解题思路：

路径类似于括号题，利用括号题模板

解题步骤：

N/A

注意事项：

1. edge case /../ 表示若stack为空，就不pop。if stack不能加到elif token == '..'中
2. 遇到..返回到上层目录

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

def simplifyPath(self, path: str) -> str:
	path += '/'
	token, stack = '', []
	for c in path:
		if c == '/':
			if token == '.':
				pass
			elif token == '..':
				if stack: # remember
					stack.pop()
			elif token:
				stack.append(token)
			token = ''
		else:
			token += c
	return '/' + '/'.join(stack)

算法分析：

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

LeetCode

<div>

You are given a list of songs where the i^th song has a duration of time[i] seconds.

Return the number of pairs of songs for which their total duration in seconds is divisible by 60. Formally, we want the number of indices i, j such that i < j with (time[i] + time[j]) % 60 == 0.

Example 1:

<pre>Input: time = [30,20,150,100,40] Output: 3 Explanation: Three pairs have a total duration divisible by 60: (time[0] = 30, time[2] = 150): total duration 180 (time[1] = 20, time[3] = 100): total duration 120 (time[1] = 20, time[4] = 40): total duration 60 </pre>

Example 2:

<pre>Input: time = [60,60,60] Output: 3 Explanation: All three pairs have a total duration of 120, which is divisible by 60. </pre>

Constraints:

• 1 <= time.length <= 6 * 10<sup>4</sup>
• 1 <= time[i] <= 500

</div>

题目大意：

求数组中两数和能被60整除

解题思路：

两数和的关系第一时间想到two sum。但由于target是60的倍数，并不固定，所以先用公式求所有数的mod，(time[i] + time[j]) % 60 = time[i] % 60 + time[j] % 60, 这样target就是60了
第二个难点是此题求个数并不是像two sum一样求可行性，所以value to index改成value to count

解题步骤：

N/A

注意事项：

1. 对所有数对60求mod，map存value到count
2. 如果输入是60，取模后为0， 求(60 - time_mod[i])要对60取模，否则60不在map中，因为60 - time_mod[i] = 60.

Python代码：

1
2
3
4
5
6
7
8
9
10

# (time[i] + time[j]) % 60 = time[i] % 60 + time[j] % 60
def numPairsDivisibleBy60(self, time: List[int]) -> int:
	time_mod = [t % 60 for t in time] # [30,30]
	val_to_count = collections.defaultdict(int)
	res = 0
	for i in range(len(time_mod)):
		if (60 - time_mod[i]) % 60 in val_to_count:
		   res += val_to_count[(60 - time_mod[i]) % 60]
		val_to_count[time_mod[i]] += 1 # 30:1
	return res

算法分析：

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

LeetCode

<div>

Suppose you have n integers labeled 1 through n. A permutation of those n integers perm (1-indexed) is considered a beautiful arrangement if for every i (1 <= i <= n), either of the following is true:

• perm[i] is divisible by i.
• i is divisible by perm[i].

Given an integer n, return the number of the beautiful arrangements that you can construct.

Example 1:

<pre>Input: n = 2 Output: 2 Explanation: The first beautiful arrangement is [1,2]: - perm[1] = 1 is divisible by i = 1 - perm[2] = 2 is divisible by i = 2 The second beautiful arrangement is [2,1]: - perm[1] = 2 is divisible by i = 1 - i = 2 is divisible by perm[2] = 1 </pre>

Example 2:

<pre>Input: n = 1 Output: 1 </pre>

Constraints:

• 1 <= n <= 15

</div>

题目大意：

求数组中所有排列中下标（从1开始）和数值能整除（下标整除数值或反之）的个数

解题思路：

一开始考虑用DP，因为求个数且类似于L368 Largest Divisible Subset，但问题与子问题的具体排位有关，所以DP不可行。考虑用Stack，但数组顺序可变。
只能用暴力法，也就是DFS中排列求解

解题步骤：

N/A

注意事项：

1. 用排列模板，但此题不涉及具体数组。用set来记录访问过的数值而不是下标，start来记录模拟结果path中的位置

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

def countArrangement(self, n: int) -> int:
	return self.permute(n, 1, set())

def permute(self, n, start, visited): # 2, 1, [F,F,F]
	if start == n + 1: # remember n + 1
		#print(path)
		return 1
	res = 0 # 1
	for i in range(1, n + 1): # [1,3)
		if i in visited:
			continue
		if i % start == 0 or start % i == 0:
			visited.add(i)
			#path.append(i)
			res += self.permute(n, start + 1, visited) # 2, 2, [FFT]
			#path.pop()
			visited.remove(i)
	return res

算法分析：

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