KK's blog

LeetCode

Input: expression = “2-1-1”
Output: [0,2]
Explanation:
((2-1)-1) = 0
(2-(1-1)) = 2

Input: expression = “23-45”
Output: [-34,-14,-10,-10,10]
Explanation:
(2(3-(45))) = -34
((23)-(45)) = -14
((2(3-4))5) = -10
(2((3-4)5)) = -10
(((23)-4)5) = 10

题目大意：

给定一个字符串含数字和加减乘除，求所有加括号方法得到的结果

Catalan解题思路(推荐)：

求所有结果，用DFS，由于需要左右递归，双边递归，所以用Catalan法模板

解题步骤：

N/A

注意事项：

1. 终止条件返回是一个list
2. Python中用eval来计算字符串运算结果返回值为整数，所以归纳左右递归结果要用str转为字符串

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def diffWaysToCompute(self, expression: str) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.diffWaysToCompute(expression[:i])
		right_res = self.diffWaysToCompute(expression[i + 1:])
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	return res

算法分析：

时间复杂度Catalan数为O(C[n] += C[i-1]*C[n-i])，空间复杂度O(1)

记忆性搜索算法II解题思路：

大致同上，只不过加入记忆性搜索算法，但优化不算大

Python代码：

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

def diffWaysToCompute2(self, expression) -> List[int]:
	return self.dfs(expression, {})

def dfs(self, expression: str, cache) -> List[int]:
	if expression.isdigit():
		return [int(expression)] # remember to use list
	if expression in cache:
		return cache[expression]
	res = []
	for i, char in enumerate(expression):
		if char not in '+-*/':
			continue
		left_res = self.dfs(expression[:i], cache)
		right_res = self.dfs(expression[i + 1:], cache)
		res += [eval(str(_l) + char + str(_r)) for _l in left_res for _r in right_res] # remember eval and str
	cache[expression] = res
	return res

LeetCode

Input: strings = [“abc”,”bcd”,”acef”,”xyz”,”az”,”ba”,”a”,”z”]
Output: [[“acef”],[“a”,”z”],[“abc”,”bcd”,”xyz”],[“az”,”ba”]]

Input: strings = [“a”]
Output: [[“a”]]

题目大意：

将单词按等偏移量分组

解题思路：

单词分组题，设计一个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

Input: wordsDict = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1 = “coding”, word2 = “practice”
Output: 3

Input: wordsDict = [“practice”, “makes”, “perfect”, “coding”, “makes”], word1 = “makes”, word2 = “coding”
Output: 1

题目大意：

求单词列表中给定的两个单词的最短下标距离

解题思路：

同向双指针，扫一遍。贪婪法，肯定相邻，所以扫一遍

解题步骤：

N/A

注意事项：

1. 同向双指针，分别指向两单词，计算结果时必须是找到才比较

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def shortestDistance(self, wordsDict: List[str], word1: str, word2: str) -> int:
	p1 = p2 = -1
	res = float('inf')
	for i, word in enumerate(wordsDict):
		if word == word1:
			p1 = i
		if word == word2:
			p2 = i
		if p1 != -1 and p2 != -1:
			res = min(res, abs(p1 - p2))
	return res

算法分析：

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

算法思路II：

同向双指针，取出每个单词的所有下标L1, L2,双指针比较，类似于merge sort的merge

LeetCode

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:

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.

Example 2:

Input: grid = [[1,1]]
Output: 1

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.

题目大意：

矩阵中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:

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.

题目大意：

设计一个栈，支持在常数时间内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>中，额外空间复杂度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的操作