KK's blog

每天积累多一些

0%

Posted on Edited on Disqus:

LeetCode



You are given a 0-indexed array of positive integers w where w[i] describes the weight of the i<sup>th</sup> index.

You need to implement the function pickIndex(), which randomly picks an index in the range [0, w.length - 1] (inclusive) and returns it. The probability of picking an index i is w[i] / sum(w).

For example, if w = [1, 3], the probability of picking index 0 is 1 / (1 + 3) = 0.25 (i.e., 25%), and the probability of picking index 1 is 3 / (1 + 3) = 0.75 (i.e., 75%).

Example 1:

Input
[“Solution”,”pickIndex”]
[[[1]],[]]
Output
[null,0]

Explanation
Solution solution = new Solution([1]);
solution.pickIndex(); // return 0. The only option is to return 0 since there is only one element in w.


Example 2:

Input
[“Solution”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”,”pickIndex”]
[[[1,3]],[],[],[],[],[]]
Output
[null,1,1,1,1,0]

Explanation
Solution solution = new Solution([1, 3]);
solution.pickIndex(); // return 1. It is returning the second element (index = 1) that has a probability of 3/4.
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 1
solution.pickIndex(); // return 0. It is returning the first element (index = 0) that has a probability of 1/4.

Since this is a randomization problem, multiple answers are allowed.
All of the following outputs can be considered correct:
[null,1,1,1,1,0]
[null,1,1,1,1,1]
[null,1,1,1,0,0]
[null,1,1,1,0,1]
[null,1,0,1,0,0]
……
and so on.


Constraints: 1 <= w.length <= 10<sup>4</sup>
1 <= w[i] <= 10<sup>5</sup> pickIndex will be called at most 10<sup>4</sup> times.

题目大意：

根据数组每个元素的weight来决定其出现的概率： weight/sum of weight

解题思路：

模拟运算过程，先求和，然后根据上述公式分配概率： 如[1, 3], 小于0.25属于第一个元素，大于属于后一个元素，我们不用小数，还原回整数
所以数值小于1属于第一个元素，大于1小于4属于后一个，想到用presum，然后在presum搜索某个value，就想到二分法。

解题步骤：

N/A

注意事项：

  1. random.randint前闭后闭

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution(TestCases):

    def __init__(self, w: List[int]):
        self.presum = []
        sum = 0
        for n in w:
            sum += n
            self.presum.append(sum)

    def pickIndex(self) -> int:
        rand_value = random.randint(0, self.presum[-1] - 1)
        return bisect.bisect(self.presum, rand_value)

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: strs = [“flower”,”flow”,”flight”]
Output: “fl”


Example 2:

Input: strs = [“dog”,”racecar”,”car”]
Output: “”
Explanation: There is no common prefix among the input strings.


Constraints:

1 <= strs.length <= 200 0 <= strs[i].length <= 200
* strs[i] consists of only lower-case English letters.

题目大意：

字符串列表的最长前缀

算法思路：

N/A

注意事项：

  1. 求最小值len初始值用最大值而不是0
  2. char = strs[0][i]而不是char = strs[i]

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
def longestCommonPrefix(self, strs: List[str]) -> str:
	min_len, res = sys.maxsize, ''
	for s in strs:
		min_len = min(min_len, len(s))
	for i in range(min_len):
		char = strs[0][i]
		same_char = True
		for j in range(1, len(strs)):
			if char != strs[j][i]:
				same_char = False
				break
		if not same_char:
			break
		res += char
	return res

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: [“((()))”,”(()())”,”(())()”,”()(())”,”()()()”]


Example 2:

Input: n = 1
Output: [“()”]


Constraints:

* 1 <= n <= 8

题目大意：

产生n对括号的所有可能

算法思路：

DFS填位法，运用括号定律1： 左括号数 >= 右括号数，也就是左括号剩余数 < 右括号剩余数

注意事项：

  1. 复杂度的计算

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
def generateParenthesis(self, n: int) -> List[str]:
	res = []
	self.dfs(n, n, '', res)
	return res

def dfs(self, left_paren_left, right_paren_left, path, res):
	if left_paren_left == 0 and right_paren_left == 0:
		res.append(path)
		return
	if left_paren_left > 0:
		path += '('
		self.dfs(left_paren_left - 1, right_paren_left, path, res)
		path = path[:-1]
	if right_paren_left > 0 and left_paren_left < right_paren_left:
		path += ')'
		self.dfs(left_paren_left, right_paren_left - 1, path, res)
		path = path[:-1]

算法分析：

n个括号，有2n位，时间复杂度为Catalan数O[C(n,2n)/n+1]，空间复杂度O(n)

Posted on Edited on Disqus:

LeetCode



Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

Example 1:

Input: s = “()”
Output: true


Example 2:

Input: s = “()[]{}”
Output: true


Example 3:

Input: s = “(]”
Output: false


Example 4:

Input: s = “([)]”
Output: false


Example 5:

Input: s = “{[]}”
Output: true


Constraints:

1 <= s.length <= 10<sup>4</sup> s consists of parentheses only '()[]{}'.

题目大意：

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

算法思路：

括号题优先考虑用Stack

注意事项：

  1. 三种不合法情况： ‘[‘ (stack有余), ‘]’ (要匹配的时候stack为空), ‘{]’ (不匹配)

第二遍

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def isValid(self, s: str) -> bool:
	stack = []
	paren_dict = {')': '(', '}':'{', ']':'['}
	for i in range(len(s)):
		if s[i] in '([{':
			stack.append(s[i])
		elif not stack:
			return False
		elif stack[-1] != paren_dict[s[i]]:
			return False
		else:
			stack.pop()
	return False if stack else True

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
PARENTHESES_DICT = {'(': ')', '[': ']', '{': '}'}
class Solution:
    def isValid(self, s: str) -> bool:
        if not s:
            return False
        stack = []
        for char in s:
            if char in '([{':
                stack.append(char)
            else:
                if not stack:
                    return False
                left = stack.pop()
                if PARENTHESES_DICT[left] != char:
                    return False
        return True if not stack else False

算法分析：

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

Posted on Edited on Disqus:

LeetCode



Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]


Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]


Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]


Example 4:

Input: nums = [1]
Output: [1]


Constraints:

1 <= nums.length <= 100 0 <= nums[i] <= 100

题目大意：

下一个全排列数

解题思路：

N/A

解题步骤：

  1. 找到从后往前升序的第一个非升序数，如135864的5
  2. 找到从后往前比步骤1中大的数，调换，如6，变成136854
  3. 后边部分按升序排列或者做reverse(更高效)

注意事项：

  1. Python语法问题： reverse子列表，跟倒序遍历数组一样，要指明前后边界，前面边界值更大

Python代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 135864 -> 136854 -> 136458
# 1355864 -> 1356458
# 99
def nextPermutation(self, nums: List[int]) -> None:
	to_be_swapped_index, greater_index = -1, -1
	for i in range(len(nums) - 2, -1, -1):
		if nums[i] < nums[i + 1]: # 5 < 8
			to_be_swapped_index = i # 2
			break
	if to_be_swapped_index == -1:
		nums.sort()
		return nums
	for i in range(len(nums) - 1, to_be_swapped_index, -1): #
		if nums[to_be_swapped_index] < nums[i]: # 5 < 6
			greater_index = i # 4
			break # 136854
	nums[to_be_swapped_index], nums[greater_index] = nums[greater_index], nums[to_be_swapped_index]
	# nums[to_be_swapped_index + 1:] = sorted(nums[to_be_swapped_index + 1:]) # 136458
	nums[to_be_swapped_index + 1:] = nums[:to_be_swapped_index:-1]
	return nums

算法分析：

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

Free mock interview