KK's blog

LeetCode

<div>

We can shift a string by shifting each of its letters to its successive letter.

• For example, "abc" can be shifted to be "bcd".

We can keep shifting the string to form a sequence.

• For example, we can keep shifting "abc" to form the sequence: "abc" -> "bcd" -> ... -> "xyz".

Given an array of strings strings, group all strings[i] that belong to the same shifting sequence. You may return the answer in any order.

Example 1:

<pre>Input: strings = ["abc","bcd","acef","xyz","az","ba","a","z"] Output: [["acef"],["a","z"],["abc","bcd","xyz"],["az","ba"]] </pre>

Example 2:

<pre>Input: strings = ["a"] Output: [["a"]] </pre>

Constraints:

• 1 <= strings.length <= 200
• 1 <= strings[i].length <= 50
• strings[i] consists of lowercase English letters.

</div>

题目大意：

将单词按等偏移量分组

解题思路：

单词分组题，设计一个id。组内的每个单词里字母之间的差值是一致的，如abd, wxz, 差值分别为1和2，这是同一组。

解题步骤：

N/A

注意事项：

1. 求每个单词每个字母之间的差值，用下滑线连接作为id。注意差值可能为负数，所以要取mod变正
2. 单一字母单词，不存在偏移量，id为空，所以代码不需要特殊处理

Python代码：

1
2
3
4
5
6
7
8

def groupStrings(self, strings: List[str]) -> List[List[str]]:
	res = collections.defaultdict(list)
	for s in strings:
		_id = ''
		for j in range(1, len(s)):
			_id += str((ord(s[j]) - ord(s[j - 1])) % 26) + '_'
		res[_id].append(s)
	return list(res.values())

算法分析：

时间复杂度为O(nm)，空间复杂度O(1), n为单词个数, m为单词最长长度。

LeetCode

<div>

Given an m x n binary grid grid where each 1 marks the home of one friend, return the minimal total travel distance.

The total travel distance is the sum of the distances between the houses of the friends and the meeting point.

The distance is calculated using Manhattan Distance, where distance(p1, p2) = |p2.x - p1.x| + |p2.y - p1.y|.

Example 1:

<pre>Input: grid = [[1,0,0,0,1],[0,0,0,0,0],[0,0,1,0,0]] Output: 6 Explanation: Given three friends living at (0,0), (0,4), and (2,2). The point (0,2) is an ideal meeting point, as the total travel distance of 2 + 2 + 2 = 6 is minimal. So return 6. </pre>

Example 2:

<pre>Input: grid = [[1,1]] Output: 1 </pre>

Constraints:

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 200
• grid[i][j] is either 0 or 1.
• There will be at least two friends in the grid.

</div>

题目大意：

矩阵中1表示朋友的位置，求最佳见面位置，所有朋友到这个位置曼哈顿距离最短。

解题思路：

这是数学题也是非高频题。如果是一维，求最佳位置，是所有朋友位置的中点，也就是左边朋友和右边朋友的数量是一样。求距离也就是用相向双指针，求每对点的距离。
推广到二维，同理，x和y坐标是独立的。分别求距离即可。

解题步骤：

N/A

注意事项：

1. 用相向双指针，求每对点的距离

Python代码：

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

def minTotalDistance(self, grid: List[List[int]]) -> int:
	x_coordinates, y_coordinates = [], []
	for i in range(len(grid)):
		for j in range(len(grid[0])):
			if grid[i][j] == 1:
				x_coordinates.append(i)
				y_coordinates.append(j)
	x_coordinates.sort()
	y_coordinates.sort()
	res = 0
	left, right = 0, len(y_coordinates) - 1
	while left < right:
		res += y_coordinates[right] - y_coordinates[left]
		left += 1
		right -= 1

	left, right = 0, len(x_coordinates) - 1
	while left < right:
		res += x_coordinates[right] - x_coordinates[left]
		left += 1
		right -= 1
	return res

算法分析：

时间复杂度为O(nlogn)，空间复杂度O(n), n为矩阵的长边大小

LeetCode 155 Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) -- Push element x onto stack.
• pop() -- Removes the element on top of the stack.
• top() -- Get the top element.
• getMin() -- Retrieve the minimum element in the stack.

Example:

<pre>MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2. </pre>

题目大意：

设计一个栈，支持在常数时间内push，pop，top，和取最小值。

push(x) -- 元素x压入栈 pop() -- 弹出栈顶元素 top() -- 获取栈顶元素 getMin() -- 获取栈中的最小值

解题思路：

这是考察Algorithm和data structure的经典问题。用stack即可实现push，top，pop。难点在于O(1)内实现getMin。看一个例子，
按以下顺序加入stack 5, 3, 6, 8, 2
最小值 5, 3, 3, 3, 2
可以看出来，最小值是动态变化的，所以需要动态处理，由于存储的方式与stack一致，所以可以考虑再用一个stack来存最小值。 如果不用额外stack改用Node，将make_pair(x, curMin)一起压入栈stack<Node<int,int>>中，额外空间复杂度O(n)。 见算法2。
稍改进空间复杂度，最小值只存变化的值，也就是5,3,2，当最小值变化时再存入最小栈。出栈时候，若出栈元素等于最小栈中的元素，
最小栈的元素也要出栈。

注意事项：

1. 当前最小元素可能相等。相等元素也要入最小栈，如5,3,6,3，最小栈为5,3,3。val <= self.min_stack[-1]一定要取等于。
2. 考虑栈为空时，执行pop和peek的操作。这里存在一个decision point，设计原则与stack的操作一致，也就是暴露出exception。
3. 记得写self. self.stack

Python代码：

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

class MinStack(TestCases):

    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)
        self.stack.append(val)

    def pop(self) -> None:
        val = self.stack.pop()
        if self.min_stack and val == self.min_stack[-1]:
            self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

注意事项：

1. 当前最小元素可能相等。相等元素也要入最小栈，如5,3,6,3，最小栈为5,3,3。x <= minS.peek()一定要取等于。
2. 考虑栈为空时，执行pop和peek的操作。这里存在一个decision point，设计原则与stack的操作一致，也就是暴露出exception。

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

public class MinStack {

	 /** initialize your data structure here. */
    public MinStack() {
        s = new Stack<>();
        minS = new Stack<>();
    }
    
    public void push(int x) {
        s.push(x);
        
        if(minS.isEmpty() || x <= minS.peek())
        	minS.push(x);
    }
    
    public void pop() {
        int top = s.pop();
        if(top == minS.peek())
        	minS.pop();
    }
    
    public int top() {
        return s.peek();
    }
    
    public int getMin() {
        return minS.peek();
    }
    
    Stack<Integer> s;
    Stack<Integer> minS;
}

O(1)空间算法分析(不用看)：

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

算法2也是可以通过leetcode测试的，虽然空间复杂度比上述差。 存储每个新加值对应的min，更加浪费空间

Follow-up:

如果用O(1)额外空间，怎么改进算法？

先考虑最简单的情况，用一个min来记录当前最小值，它可以满足最小值不需更新的情况，解决了问题的一半： x表示要加入的值，m表示最小值的变量，y是真正加入栈的值 x 1 5 3 m 1 1 1 y 1 5 3 可以看出无论入栈出栈，最小值均为1.

比较难的是最小值需要更新时，如下一个要加入0，最小值要更新m=0，但0不能入栈，前一个最小值1的信息就丢失了，所以要设计一个计算y方法(push)满足

1. 已知条件：含有前一个最小值的的信息。x1<m0.
2. 设计要求：y<m, 因为最小值不更新的时候y值永远大于等于m，必须区分开来，从而知道怎么pop，也就是还原入栈值（最小值）。y1<m1=x1. 解决了这个问题就解决了另一半的问题。

以下解释如何推出最小值需要更新时y的计算方式（，以及push和pop的方法：

以下例子解释Push x 1 5 3 0 6 m 1 1 1 0 0 y 1 5 3 -1 6

以下例子解释Pop x 6 0 3 5 1 m 0 0 1 1 1 y 6 -1 3 5 1 可以看出真正入栈值可以是原数或者是计算值，取决它与最小值的关系。

注意事项：

1. 当前最小元素可能相等。相等元素不用更新最小值，也就是新值直接入栈。
2. 以上递推式的初始条件为：第一个元素是直接加入栈且等于m，无论何种情况都不需任何计算。push时候注意当栈为空，m值为第一个元素的值。
3. 数据溢出。涉及int的加减乘除法，都要预先将其转化为long，否则会溢出。

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

public class MinStack {
     public MinStack() {
        s = new Stack<>();
    }
    
    public void push(int x) {
    	if (s.isEmpty())
    		m = x;
    	
    	long xx = (long)x;
    	if (x >= m)
    		s.push(xx);
    	else {
    		s.push(2*xx-m);
    		m = x;
    	}
    }
    
    public void pop() {
        long top = s.pop();
        if(top < m)     
        	m = 2*m - top;
    }
    
    public int top() {
        return (int)(s.peek() >= m? s.peek() : m);
    }
    
    public int getMin() { 
        return (int)m;
    }
    
    Stack<Long> s;
    long m = 0;
}

算法分析：

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

考点:

1. 先不考虑getMin，用什么数据结构实现push, pop, top
2. 暴力法可以实现getMin，怎么实现O(1)。用什么数据结构实现存储min，额外用一个stack
3. 元素可能相等
4. 考虑栈为空时，执行pop和peek的操作

LeetCode

<div>

Given an array of points where points[i] = [x<sub>i</sub>, y<sub>i</sub>] represents a point on the X-Y plane, return the maximum number of points that lie on the same straight line.

Example 1:

<pre>Input: points = [[1,1],[2,2],[3,3]] Output: 3 </pre>

Example 2:

<pre>Input: points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]] Output: 4 </pre>

Constraints:

• 1 <= points.length <= 300
• points[i].length == 2
• -10<sup>4</sup> <= x<sub>i</sub>, y<sub>i</sub> <= 10<sup>4</sup>
• All the points are unique.

</div>

题目大意：

求在同一直线上的点的最大个数

解题思路：

固定一个点，求其与其他点的斜率是否相同，记录在map中。通过同一个点，若斜率相同，肯定在同一直线上。这是几何题。

解题步骤：

N/A

注意事项：

1. 两重循环，外循环为每个点，内循环为该点和其他的点的斜率。斜率可以为无穷大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12

def maxPoints(self, points: List[List[int]]) -> int:
	res = 0
	for i in range(len(points)):
		slope_to_count = collections.defaultdict(int)
		max_p = 0
		for j in range(i + 1, len(points)):
			slope = (points[j][1] - points[i][1]) / (points[j][0] - points[i][0]) \
				if points[j][0] - points[i][0] != 0 else float('inf') # remember line is y-axis
			slope_to_count[slope] += 1
			max_p = max(max_p, slope_to_count[slope])
		res = max(res, max_p + 1)
	return res

算法分析：

时间复杂度为<code>O(n²)</code>，空间复杂度O(n)

LeetCode

<div>

Given an input string s, reverse the order of the words.

A word is defined as a sequence of non-space characters. The words in s will be separated by at least one space.

Return a string of the words in reverse order concatenated by a single space.

Note that s may contain leading or trailing spaces or multiple spaces between two words. The returned string should only have a single space separating the words. Do not include any extra spaces.

Example 1:

<pre>Input: s = "the sky is blue" Output: "blue is sky the" </pre>

Example 2:

<pre>Input: s = " hello world " Output: "world hello" Explanation: Your reversed string should not contain leading or trailing spaces. </pre>

Example 3:

<pre>Input: s = "a good example" Output: "example good a" Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string. </pre>

Constraints:

• 1 <= s.length <= 10<sup>4</sup>
• s contains English letters (upper-case and lower-case), digits, and spaces ' '.
• There is at least one word in s.

**Follow-up: **If the string data type is mutable in your language, can you solve it in-place with O(1) extra space?

</div>

题目大意：

反转字符串中的单词顺序

解题思路：

N/A

解题步骤：

N/A

注意事项：

1. word不能为空，单词之间可能含多个空格

Python代码：

1
2
3
4

def reverseWords(self, s: str) -> str:
	words = s.split(' ')
	words_without_space = [word for word in words if word]
	return ' '.join(words_without_space[::-1])

算法分析：

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