KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode

<div>

Implement the RandomizedSet class:

  • RandomizedSet() Initializes the RandomizedSet object.
  • bool insert(int val) Inserts an item val into the set if not present. Returns true if the item was not present, false otherwise.
  • bool remove(int val) Removes an item val from the set if present. Returns true if the item was present, false otherwise.
  • int getRandom() Returns a random element from the current set of elements (it's guaranteed that at least one element exists when this method is called). Each element must have the same probability of being returned.

You must implement the functions of the class such that each function works in average O(1) time complexity.

Example 1:

<pre>Input ["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"] [[], [1], [2], [2], [], [1], [2], []] Output [null, true, false, true, 2, true, false, 2]

Explanation RandomizedSet randomizedSet = new RandomizedSet(); randomizedSet.insert(1); // Inserts 1 to the set. Returns true as 1 was inserted successfully. randomizedSet.remove(2); // Returns false as 2 does not exist in the set. randomizedSet.insert(2); // Inserts 2 to the set, returns true. Set now contains [1,2]. randomizedSet.getRandom(); // getRandom() should return either 1 or 2 randomly. randomizedSet.remove(1); // Removes 1 from the set, returns true. Set now contains [2]. randomizedSet.insert(2); // 2 was already in the set, so return false. randomizedSet.getRandom(); // Since 2 is the only number in the set, getRandom() will always return 2. </pre>

Constraints:

  • -2<sup>31</sup> <= val <= 2<sup>31</sup> - 1
  • At most 2 * ``10<sup>5</sup> calls will be made to insert, remove, and getRandom.
  • There will be at least one element in the data structure when getRandom is called.

</div>

算法思路：

Dict + List

注意事项：

  1. 检查若删除最后一个元素发现问题，remove中删除key要放在最后，不能放中间

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
class RandomizedSet(TestCases):

    def __init__(self):
        self.nums = []
        self.key_to_index = {}

    def insert(self, val: int) -> bool:
        if val in self.key_to_index:
            return False
        self.nums.append(val)
        self.key_to_index[val] = len(self.nums) - 1
        return True

    def remove(self, val: int) -> bool:
        if val not in self.key_to_index:
            return False
        index = self.key_to_index[val]
        last_val = self.nums[len(self.nums) - 1]
        self.nums[index] = last_val
        self.key_to_index[last_val] = index
        self.key_to_index.pop(val)  # remember to put it last
        self.nums.pop()
        return True

    def getRandom(self) -> int:
        return self.nums[random.randint(0, len(self.nums) - 1)]

算法分析：

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

Posted on Edited on Disqus:

LeetCode

<div>

Given a string s containing only three types of characters: '(', ')' and '*', return true if s is valid.

The following rules define a valid string:

  • Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  • Any right parenthesis ')' must have a corresponding left parenthesis '('.
  • Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  • '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string "".

Example 1:

<pre>Input: s = "()" Output: true </pre>

Example 2:

<pre>Input: s = "(*)" Output: true </pre>

Example 3:

<pre>Input: s = "(*))" Output: true </pre>

Constraints:

  • 1 <= s.length <= 100
  • s[i] is '(', ')' or '*'.

</div>

题目大意：

求给定字符串带星号是否合法括号配对。

Stack算法思路(推荐)：

括号题优先考虑用Stack。如果不带星号，回忆合法括号题，有三种不合法情况，此题只需考虑两种，不需考虑多种括号类型 三种不合法情况： '[' (stack有余), ']' (要匹配的时候stack为空)
难点：

  1. 在于要去想多一个栈来存星号，因为星号可以作为左括号备选去match右括号。右括号在两个栈中优先配对左括号，星号可以为空。如果两个栈均为空，处理了第一种不合法情况
  2. 循环后，如果两栈有余，分4中情况讨论：
    1. 左括号栈有余星号栈空，正是第二种不合法情况
    2. 左括号栈空星号栈空，合法
    3. 左括号栈空星号栈有余，合法，星号可为空
    4. 都有余，这是难点二。星号可以作为右括号去配对左括号，前提条件是星号在左括号之后，考虑*(，这是不合法

注意事项：

  1. 如果for循环出来后，两栈不为空，要比较先后顺序
  2. for loop后，L18 - Line 19记得pop，否则死循环

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def checkValidString(self, s: str) -> bool:
	stack_left, stack_star = [], []
	for i in range(len(s)):
		if s[i] == '(':
			stack_left.append(i)
		if s[i] == '*':
			stack_star.append(i)
		if s[i] == ')':
			if stack_left:  # match ( first rather than * because * can be empty
				stack_left.pop()
			elif stack_star:
				stack_star.pop()
			else:
				return False
	while stack_left and stack_star:  # use * to match (
		if stack_left[-1] > stack_star[-1]:  # consider *(
			return False
		stack_left.pop()
		stack_star.pop()
	return len(stack_left) == 0  # stack_star can be non empty

算法分析：

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

统计算法II解题思路：

括号题另一个常用思路是用统计左右括号数。此题较难想到是用一个左括号数量范围去验证。
lo为左括号的最少合法个数，hi为左括号的最大合法个数，有范围是因为星号可以变成左右括号或空。
遇到左括号，都加1，遇到右括号，都减1，遇到星号，假设星号为右括号，所以lo减1，hi加1.
如果hi小于0，表示最大左括号数小于右括号数，不满足此法的规则一，不合法

难点在于lo设为非负。因为lo是最少且合法，合法意思是lo不是单纯地将所有星号变成右括号，而是当左括号不足时，用提高下限，将星号变成空，体现在令lo为非负。
for循环后，lo必须为0，运用了法则二，左右括号相等。

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def checkValidString(self, s: str) -> bool:
	lo = hi = 0
	for char in s:
		if char == '(':
			lo += 1
			hi += 1
		if char == '*':
			if lo > 0:  # treat * as empty space
				lo -= 1
			hi += 1
		if char == ')':
			if lo > 0:  # treat the previous * as empty space
				lo -= 1
			hi -= 1
		if hi < 0:  # the num of right parenthesis > left ones
			return False
	return lo == 0  # the num of right parenthesis should equal to left ones

算法分析：

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

DP算法III解题思路：

基本情况为s[i], s[j] 分别在(*, )* 就合法 如果用单边DP，并不能确定区间内那些合法，所以只能用区间型DP
dp[i][j] = s[i-1] == '*' and dp[i+1][j] 星号不匹配 = s[i-1] in '(*' and dp[i+1][k-1] and s[k-1] in (')*') and dp[k+1][j] 星号匹配

具体参考leetcode答案
DP基本情况比较难想出来且递归是复杂，实现易错，不推荐。不过可以多了解区间型DP的模式

算法分析：

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

Posted on Edited on Disqus:

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 and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x<sub>1</sub> - x<sub>2</sub>)<sup>2</sup> + (y<sub>1</sub> - y<sub>2</sub>)<sup>2</sup>).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

Example 1:

<pre>Input: points = [[1,3],[-2,2]], k = 1 Output: [[-2,2]] Explanation: The distance between (1, 3) and the origin is sqrt(10). The distance between (-2, 2) and the origin is sqrt(8). Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin. We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]]. </pre>

Example 2:

<pre>Input: points = [[3,3],[5,-1],[-2,4]], k = 2 Output: [[3,3],[-2,4]] Explanation: The answer [[-2,4],[3,3]] would also be accepted. </pre>

Constraints:

  • 1 <= k <= points.length <= 10<sup>4</sup>
  • -10<sup>4</sup> < x<sub>i</sub>, y<sub>i</sub> < 10<sup>4</sup>

</div>

算法思路：

最大堆

注意事项：

  1. 求最小距离用最大堆，距离的相反数入堆
  2. 与堆顶比较，跟模板一样仍然是大于号

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
	if not points or not points[0]:
		return 0
	heap, res = [], []
	for i in range(len(points)):
		x, y = points[i][0], points[i][1] # x=-2, y=2
		if i < k: # i=1, k=1
			heapq.heappush(heap, (-(x * x + y * y), x, y)) # -10, 1, 3
		elif -(x * x + y * y) > heap[0][0]: # -8 > -10
			heapq.heapreplace(heap, (-(x * x + y * y), x, y)) # -8, -2, -2

	while heap:
		(dis, x, y) = heapq.heappop(heap) # -8, -2, -2
		res.append([x, y])
	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
34
35
36
37
38
39
40
public int[][] kClosest(int[][] points, int K) {
	PriorityQueue<Point> maxHeap = new PriorityQueue<Point>(K,
			new Comparator<Point>() {
				@Override
				public int compare(Point o1, Point o2) {
					return distance(o2, o1); // descending
				}
			}
	);
	
	for(int i = 0; i < points.length; i++) {
		Point p = new Point(points[i][0], points[i][1]);
		if(maxHeap.size() < K)
			maxHeap.offer(p);
		else if(distance(p, maxHeap.peek()) < 0) {
			maxHeap.poll();
			maxHeap.offer(p);
		}
	}
	int[][] res = new int[K][2];
	int j = 0;
	while(!maxHeap.isEmpty()) {
		Point p = maxHeap.poll();
		res[j][0] = p.x;
		res[j][1] = p.y;
		j++;
	}
	return res;
}

int distance(Point o1, Point o2) {
	return (o1.x * o1.x + o1.y * o1.y) - (o2.x * o2.x + o2.y * o2.y);
}

class Point {
	 int x;
	 int y;
	 Point() { x = 0; y = 0; }
	 Point(int a, int b) { x = a; y = b; }
}

算法分析：

时间复杂度为O(nlogk)，空间复杂度O(k)

Posted on Edited on Disqus:

LeetCode 054 Spiral Matrix

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.

For example,
Given the following matrix:

<pre>[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ] </pre>

You should return [1,2,3,6,9,8,7,4,5].

题目大意：

给定一个mxn的矩阵（m行 n列），以螺旋状返回矩阵中的所有元素。

解题思路：

打印方法主要是以下两种：第一种四边对称打印，实现起来边际情况很多，不推荐。因为要不断向内遍历，所以对称打印不合适。第二种方法是每条边比上一条少一个，
用四个指针，top, bottom, left, right来记录四个边界，每打印完一条边该边界向内扩展。注意有些回路不是完整比如[1,2]或上面例子中5就不是完整回路，此情况，
注意判断top和bottom以及left和right关系即可。四指针法可以进一步升级到两指针法甚至一个指针法，其实都是大同小异。

注意事项：

  1. 注意不是所有矩阵都有完整回路。所以后两个for循环要加if语句
  2. 右边和左边，遍历矩阵用matrix[i][right]，而不是matrix[right][i]
  3. Python中从后往前遍历要注意始点-1，range(right, left - 1, -1):

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
	if not matrix or not matrix[0]:
		return []
	res = []
	top, bottom, left, right = 0, len(matrix) - 1, 0, len(matrix[0]) - 1
	while top <= bottom and left <= right:
		for i in range(left, right + 1):
			res.append(matrix[top][i])
		top += 1
		for i in range(top, bottom + 1):
			res.append(matrix[i][right])  # remember [i[[right] not [right][i]
		right -= 1
		if top <= bottom:
			for i in range(right, left - 1, -1):
				res.append(matrix[bottom][i])
			bottom -= 1
		if left <= right:
			for i in range(bottom, top - 1, -1):
				res.append(matrix[i][left])
			left += 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
public void spiral2(int[][] a){
	int rowTop = 0, rowBottom = a.length-1, colLeft = 0, colRight = a[0].length-1;
	
	while(rowTop<=rowBottom && colLeft<=colRight){
		//topRow
		for(int i=colLeft;i<=colRight;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=rowBottom;i++)
			System.out.print(a[i][colRight]+" ");
		colRight--;
		if(rowTop<=rowBottom){
			for(int i=colRight;i>=colLeft;i--)
				System.out.print(a[rowBottom][i]+" ");
			rowBottom--;
		}
		if(colLeft<=colRight){
			for(int i=rowBottom;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public void spiral3(int[][] a){
	int rowTop = 0, colLeft = 0;
	
	while(rowTop<=a.length-rowTop-1 && colLeft<=a[0].length-colLeft-1){
		//topRow
		for(int i=colLeft;i<=a[0].length-colLeft-1;i++)
			System.out.print(a[rowTop][i]+" ");
		rowTop++;
		//rightCol
		for(int i=rowTop;i<=a.length-rowTop;i++)
			System.out.print(a[i][a[0].length-colLeft-1]+" ");
		//colRight--;
		if(rowTop<=a.length-rowTop){
			for(int i=a[0].length-colLeft-2;i>=colLeft;i--)
				System.out.print(a[a.length-rowTop][i]+" ");
		}
		if(colLeft<=a[0].length-colLeft-2){
			for(int i=a.length-rowTop-1;i>=rowTop;i--)
				System.out.print(a[i][colLeft]+" ");
			colLeft++;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public void spiral4(int[][] a){
	int num = Math.min(a.length, a[0].length);
	for(int st=0;st<(num+1)/2;st++){
		//complete edge(top)
		for(int i=st;i<a[0].length-st;i++)
			System.out.print(a[st][i]+" ");
		//complete edge-top (right)
		for(int i=st+1;i<a.length-st;i++)
			System.out.print(a[i][a[0].length-1-st]+" ");
		if(a[0].length-2-st>st)
			for(int i=a[0].length-2-st;i>=st;i--)
				System.out.print(a[a.length-st-1][i]+" ");
		if(a.length-2-st>st+1)
			for(int i=a.length-2-st;i>=st+1;i--)
				System.out.print(a[i][st]+" ");
	}
}

算法分析：

时间复杂度为<code>O(mn)</code>，空间复杂度<code>O(1)</code>。

Posted on Edited on Disqus:

LeetCode 121 Best Time to Buy and Sell Stock

Say you have an array for which the i<sup>th</sup> element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

<pre>Input: [7, 1, 5, 3, 6, 4] Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) </pre>

Example 2:

<pre>Input: [7, 6, 4, 3, 1] Output: 0

In this case, no transaction is done, i.e. max profit = 0. </pre>

题目大意：

如果你只能进行一次交易（比如购买或者销售一个股票），设计一个算法来获取最大利润。

解题思路：

利润=当前价格-买入价，利润作为第一个变量求其最大值。由于买入价越低，利润可能会越大，所以第二个变量就要不断更新买入价
（最小值）。本题核心思路就是维护两个变量：最低价，利润。为什么不用最高价而选择利润呢？因为最低价和最高价没有顺序，最高价
必须在最低价后面，这样的利润才可实现，但如果是最低价和利润，就能确保这个顺序了，因为利润一定是在最低价后，否则这个利
润为负，不能为最大值。另一种稍麻烦的方法是凡是min更新，最高价就reset为0，大原则就是保持顺序。

注意事项：

  1. 数组为空

Python代码：

1
2
3
4
5
6
7
def maxProfit(self, prices: List[int]) -> int:
	min_buy_idx, max_profit = 0, 0
	for i in range(len(prices)):
		max_profit = max(max_profit, prices[i] - prices[min_buy_idx])
		if prices[i] < prices[min_buy_idx]:
			min_buy_idx = i
	return max_profit

Java代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int maxProfit(int[] prices) {
	if(prices.length==0)
		return 0;
	int min = prices[0];
	int curProfit = 0;
	for(int i=1;i<prices.length;i++){
		int todayProfit = prices[i]-min;
		if(todayProfit>curProfit)
			curProfit = todayProfit;
		if(min>prices[i])
			min = prices[i];
	}
	return curProfit;
}

算法分析：

时间复杂度为O(n)，n为字符串长度，空间复杂度O(1)。

相关题目：

LeetCode 121 Best Time to Buy and Sell Stock
LeetCode 122 Best Time to Buy and Sell Stock II LeetCode 309 Best Time to Buy and Sell Stock with Cooldown LeetCode 123 Best Time to Buy and Sell Stock III

Free mock interview