Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity and use only constant extra space.
Example 1:
Input: nums = [2,2,1] Output: 1
Example 2:
Input: nums = [4,1,2,1,2] Output: 4
Example 3:
Input: nums = [1] Output: 1
Constraints:
`1 <= nums.length <= 3 104*-3 104 <= nums[i] <= 3 104` * Each element in the array appears twice except for one element which appears only once.
题目大意：
数列中，所有数都出现两次除了一个数，求这一个数
异或解题思路(推荐)：
Easy题
解题步骤：
N/A
注意事项：
Python代码：
1 2 3 4 5
defsingleNumber(self, nums: List[int]) -> int: res = 0 for n in nums: res ^= n return res
算法分析：
时间复杂度为O(n)，空间复杂度O(1)
HashMap算法II解题思路：
记录频数，最直观解法
Python代码：
1 2 3
defsingleNumber2(self, nums: List[int]) -> int: num_to_count = collections.Counter(nums) return [n for n, count in num_to_count.items() if count == 1][0]
Given an input string (s) and a pattern (p), implement regular expression matching with support for '.' and '*'.
'.' Matches any single character.
'*' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
Note:
s could be empty and contains only lowercase letters a-z.
p could be empty and contains only lowercase letters a-z, and characters like . or *.
Example 1:
**Input:**
s = "aa"
p = "a"
**Output:** false
**Explanation:** "a" does not match the entire string "aa".
Example 2:
**Input:**
s = "aa"
p = "a*"
**Output:** true
**Explanation:** '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".
Example 3:
**Input:**
s = "ab"
p = ".*"
**Output:** true
**Explanation:** ".*" means "zero or more (*) of any character (.)".
Example 4:
**Input:**
s = "aab"
p = "c*a*b"
**Output:** true
**Explanation:** c can be repeated 0 times, a can be repeated 1 time. Therefore, it matches "aab".
Example 5:
**Input:**
s = "mississippi"
p = "mis*is*p*."
**Output:** false
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!
deftrap(self, height: List[int]) -> int: stack = [] sum = 0 for i inrange(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) returnsum
m == matrix.lengthn == matrix[0].length 1 <= m, n <= 200-2<sup>31</sup> <= matrix[i][j] <= 2<sup>31</sup> - 1
Follow up:
A straightforward solution using O(mn) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution. * Could you devise a constant space solution?
defsetZeroes(self, matrix: List[List[int]]) -> None: # calculate is_zero_row_zero = Trueiflen([0for n in matrix[0] if n == 0]) > 0elseFalse is_zero_col_zero = Trueiflen([0for i inrange(len(matrix)) if matrix[i][0] == 0]) > 0elseFalse for i inrange(1, len(matrix)): for j inrange(1, len(matrix[0])): if matrix[i][j] == 0: matrix[i][0], matrix[0][j] = 0, 0 # Set for i inrange(1, len(matrix)): # remember to start with 1 if matrix[i][0] == 0: for j inrange(1, len(matrix[0])): matrix[i][j] = 0 for j inrange(1, len(matrix[0])): # remember to start with 1 if matrix[0][j] == 0: for i inrange(1, len(matrix)): matrix[i][j] = 0 if is_zero_row_zero: for j inrange(len(matrix[0])): matrix[0][j] = 0 if is_zero_col_zero: for i inrange(len(matrix)): matrix[i][0] = 0
