KK's blog

LeetCode 248 Strobogrammatic Number III

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to count the total strobogrammatic numbers that exist in the range of low <= num <= high.

Example:

**Input: low = "50", high = "100"

**Output:** 3 

Explanation: 69, 88, and 96 are three strobogrammatic numbers.

Note: Because the range might be a large number, the lowand high numbers are represented as string.

题目大意：

求某范围的旋转数的个数。旋转数是这个数旋转180度还是一样，如0, 1, 8， 还含两位的如69， 96.

解题思路：

低频题。这是M公司的题目。这题不能用乘法原理，因为情况多变，要实实在在地找出每一个可能性。
类似于L351安卓解码种数，数字间有关系，求[m, n]范围间种数。用DFS将每一位填上合法位，此题区别是
需要它有对称性，所以DFS从中间向两边。API为f(res, low, high, map), res为当前结果字符串，map为旋转数的映射关系，
终止条件为res超过high，若在范围内，结果+1，也就是先将自己加入到结果中，然后两边加入旋转字符，进入下一轮递归，
累加到结果中。

注意: 与上题一样，和最左位不能为0除了0自己本身。

注意事项：

1. 带限制条件的填位法DFS。
2. 奇偶位。对称中心既可以是奇数位也可以是偶数位。所以DFS有空字符，单个字符0, 1, 8等4种。
3. 此题难点在验证： 三种情况，需要比较字符串，所以要比较长度
   1) 当前结果长度大于high, 长度等于high但大于high，返回0. 只有这种情况是终止条件
   2) 当前结果长度大于low, 长度等于low但大于等于low，res = 1
   3) 最左位为0，不合法如0880，但0本身除外， res = 0

Python代码：

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

def strobogrammaticInRange(self, low: str, high: str) -> int:
	stro_dict = {'0': '0', '1': '1', '8': '8', '6': '9', '9': '6'}
	res = 0
	res += self.dfs('', low, high, stro_dict)
	res += self.dfs('0', low, high, stro_dict)
	res += self.dfs('1', low, high, stro_dict)
	res += self.dfs('8', low, high, stro_dict)
	return res

def dfs(self, s, low, high, stro_dict):
	if len(s) > len(high) or (len(s) == len(high) and s > high):
		return 0
	res = 0
	if len(s) > len(low) or (len(s) == len(low) and s >= low):
		res = 1
	if len(s) > 1 and s[0] == '0': # i.e. 08
		res = 0
	for key, val in stro_dict.items():
		res += self.dfs(key + s + val, low, high, stro_dict)
	return res

注意事项：

1. 奇偶位。对称中心既可以是奇数位也可以是偶数位。
2. 最左位为0，不合法如0880，但0本身除外。

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

public int strobogrammaticInRange(String low, String high) {
	Map<String, String> map = new HashMap<>();
	map.put("6", "9");
	map.put("9", "6");
	map.put("1", "1");
	map.put("8", "8");
	map.put("0", "0");
	
	int result = 0;
	result += dfs("", low, high, map);
	result += dfs("1", low, high, map);
	result += dfs("0", low, high, map);
	result += dfs("8", low, high, map);
	return result;
}
	
public int dfs(String res, String low, String high, Map<String, String> map) {
	if(res.length() > high.length() || (res.length() == high.length() && res.compareTo(high) > 0)) 
		return 0;
	int result = 0;
	if((res.length() == low.length() && res.compareTo(low) >= 0)  || res.length() > low.length()) 
		result = 1;
	if(res.length() > 1 && res.charAt(0) == '0')
		result = 0;
	
	for (Map.Entry<String, String> entry : map.entrySet()) {
		result += dfs(entry.getKey() + res + entry.getValue(), low, high, map);
	}
	return result;
}

算法分析：

时间复杂度为O(# of results)，空间复杂度O(lengh(high))。

LeetCode 540 Single Element in a Sorted Array

Given a sorted array consisting of only integers where every element appears twice except for one element which appears once. Find this single element that appears only once.

Example 1:

**Input:** [1,1,2,3,3,4,4,8,8]
**Output:** 2

Example 2:

**Input:** [3,3,7,7,10,11,11]
**Output:** 10

Note: Your solution should run in O(log n) time and O(1) space.

题目大意：

一个有序数组中，每个数字都出现了两次，只有一个数字出现了一次，求出现一次的数字。

解题思路：

这是A公司Problem solving的题目。类似于L136。此题数组有序且要求O(logn)时间，所以考虑用二分法。由于没有输入tgt，有点似
算法文档中用二分法求峰值，就是比较相邻两个数做二分法。考虑一个结论，若数组为偶数个数，就一定不存在只出现一次的元素。
所以必须考虑奇偶位，若下标mid为偶数，其后一位与其相等，就一定在右半边搜索left=mid+2(不会是mid和mid+1)，如第二个
例子，因为mid左边个数为偶数，利用结论可知不会在左边。同理与后一位不等，搜左边right=mid(可能为mid)。注意边界。
若mid为奇数，mid前面有奇数个，mid包括自己的后面有偶数个，所以mid和mid+1上的数相等，就应在左半搜，所以与偶数位的
情况正好相反，但是边界不同，产生了4个if语句。
法二：改进一下，若mid为奇数位，就mid–归结为偶数位的情况，这样if变成两个。

注意事项：

1. 类似于Leetcode 033，四种情况，前两种中的第二种全包第一种。
2. for循环后，答案一定在start和end其中一个。end前面有偶数个与start不同就肯定在start上。

Python代码：

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

def singleNonDuplicate(self, nums: List[int]) -> int:
	start, end = 0, len(nums) - 1
	while start + 1 < end:
		mid = start + (end - start) //2
		if mid % 2 == 1 and mid >= 1 and nums[mid - 1] == nums[mid]:
			start = mid
		elif mid % 2 == 1:
			end = mid
		elif mid % 2 == 0 and mid >= 1 and nums[mid - 1] != nums[mid]:
			start = mid
		else:
			end = mid
	if end % 2 == 1 and nums[start] != nums[end]:
		return nums[start] # remember
	else:
		return nums[end]

注意事项：

1. 边界也就是mid的赋值，写出例子来理解。

Java代码：

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

public int singleNonDuplicate(int[] nums) {
	int N = nums.length;
	int left = 0, right = N - 1;
	while (left < right) {
		int mid = (right - left) / 2 + left;
		boolean isEven = true;
		if (mid % 2 == 1) isEven = false;
		if ((isEven && nums[mid] != nums[mid + 1]) )
			right = mid;
		else if (isEven && nums[mid] == nums[mid + 1])
			left = mid + 2;
		else if (!isEven && nums[mid] == nums[mid + 1])
			right = mid-1;
		else
			left = mid + 1;
	}
	return nums[left];
}

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

public int singleNonDuplicate2(int[] nums) {
	  int N = nums.length;
	  int left = 0, right = N - 1;
	  while (left < right) {
		  int mid = (right - left) / 2 + left;
		  if (mid % 2 == 1) mid--;
		  if (nums[mid] != nums[mid + 1])
			  right = mid;
		  else
			  left = mid + 2;
	  }
	  return nums[left];
}

算法分析：

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

Follow-up:

首先问L316 Given a non-empty array of integers, every element appears twice except for one. Find that single one.
XOR解法，不用实现。
Follow up问题是L260 Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.
分三步。若只有一个数出现1次，只要把所有数异或^即可(相同数异或=0)。如果有两个此数，异或结果是这两数不同的位。只要选为1且最低位(或任意为1的位)lowBit=a-(a&(a-1))。再扫所有数，根据它们在lowBit上=0和=1分组异或num1, num2，最后分组异或后它们为所求

LeetCode 042 Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

Example:

**Input:** [0,1,0,2,1,0,1,3,2,1,2,1]
**Output:** 6

题目大意：

给出 n 个非负整数，代表一张X轴上每个区域宽度为 1 的海拔图, 计算这个海拔图最多能接住多少（面积）雨水。

解题思路：

画图解题。
比较直观的方法是找低谷，只有低谷才可以藏水。用一个递减栈来存所有呈递减趋势的下标，而当上升时就计算藏水量。

从图可以看出，栈中有最高的，3,2,1，最矮的已经出栈了。蓝色的bar准备入栈。计算水量是水平计算的。具体而言，
右边界是确定的，左边界以及高度都是由此bar相邻的在栈中的bar确定的。如1的水量由bar2的高度和位置确定。
同理bar2的水量由bar3确定。实质上，是求出栈的元素之间的水量，既然是之间，最后一个出栈就要特殊处理，需要准入栈
元素来确定。特殊之处是计算栈中最后一个将要被新bar踢出栈的bar3时，并没有相邻的bar作参考，
导致它需要用新bar作为参考，所以它不能在while中处理，需要特别处理，主要因为它是最后一个，属于edge case。

解题步骤：

1. 遍历数组
2. 若比上一个高度递增，出栈直至栈中下标对应高度大于当前高度（保持递减栈）。每次出栈，用上一轮的高度作为底部计算高度差
   乘以下标距离即为横向藏水增量，更新底部进入下一次出栈。
3. 出栈完成后，根据新bar计算最后一个bar的水量，用当前高度计算藏水增量。
4. 加入下标到栈中

公式：

1

水量 = 准入栈下标与相邻栈(栈顶)的下标i - stack[-1] - 1 乘以 (相邻栈高度 - 刚出栈高度)

注意事项：

1. [公式]水量 = 准入栈下标与相邻栈(栈顶)的下标i - stack[-1] - 1 乘以 (相邻栈高度 - 刚出栈高度)
   水量的宽度并不是用刚出栈的下标，因为如上图，2-3之间可能实际上不相邻（有些高度已出栈），若用当前栈的下标会忽略了2-3之间的水量。
2. 最后一个出栈的宽度计算要还有相邻栈(栈顶)i - stack[-1] - 1才计算也就是栈不为空if stack。
3. 最后一个出栈的高度公式要改成相邻栈高度 -> 准入栈高度。

Python代码：

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

def trap(self, height: List[int]) -> int:
	stack = []
	sum = 0
	for i in range(len(height)):
		j = -1
		while stack and height[i] > height[stack[-1]]:
			j = stack.pop()
			if stack and height[i] > height[stack[-1]]:
				sum += (height[stack[-1]] - height[j]) * (i - stack[-1] - 1) # stack[-1] is the neighboring index
		if stack and j > 0:
			sum += (height[i] - height[j]) * (i - stack[-1] - 1)
		stack.append(i)
	return sum

算法分析：

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

算法II解题思路(推荐)：

算法I主要从面考虑，现在我们从点来考虑。下标4的水量取决于向左最大值（下标0）和向右最大值（下标12）中的较小值。
问题转化为求每个点的向左向右最大值。数组从左到右扫描，把当前最大值存入leftHeight中，这是向左最大值。

同理，数组从又到左扫描，得到向右最大值。对每个点取向左向右最大值的较小者，从而计算水量。此法实现起来简单很多。

Python代码：

1
2
3
4
5
6
7
8
9
10
11

def trap(self, height: List[int]) -> int:
	max_height = max(height)
	max_index = height.index(max_height)
	sum, left_max, right_max = 0, 0, 0
	for i in range(max_index):
		sum += max(0, left_max - height[i])
		left_max = max(left_max, height[i])
	for i in range(len(height) - 1, max_index, -1):
		sum += max(0, right_max - height[i])
		right_max = max(right_max, height[i])
	return sum

算法分析：

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

题目大意：

生成唯一ID如用户ID，订单ID。

解题思路：

基本思路是将所有网站映射到一个整数。
三大核心需求：

1. 全局唯一(unique)
2. 按照时间粗略有序(sortable by time)。按时间查询是普遍的请求，如得到最新的1000个用户。
3. 尽可能短。省空间，查询要更有效率。

UUID：

UUID是一类算法的统称，具体有不同的实现。UUID的有点是每台机器可以独立产生ID，理论上保证
不会重复，所以天然是分布式的，缺点是生成的ID太长，不仅占用内存，而且索引查询效率低。
4个字节表示的Unix timestamp,
3个字节表示的机器的ID
2个字节表示的进程ID
3个字节表示的计数器

多机器分别自增：

假设用8台MySQL服务器协同工作，第一台MySQL初始值是1，每次自增8，第二台MySQL初始值是2，
每次自增8，依次类推。前面用一个 round-robin load balancer 挡着，每来一个请求，由
round-robin balancer 随机地将请求发给8台MySQL中的任意一个，然后返回一个ID。
load balance可以确保请求平均分配到不同的机器，所以粗略有序，缺点是加机器要re-hash这些Id
且顺序不够稳定。

Twitter Snowflake：

原理与UUID基本一样。也是时间戳+机器id+自增序号。时间戳保证有序。

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。

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的操作