1、面试题 17.10. 主要元素 https://leetcode-cn.com/problems/find-majority-element-lcci/
考点：
class Solution:
def majorityElement(self, nums: List[int]) -> int:
eles = set(nums)
all_length = len(nums)
for ele in eles:
if nums.count(ele) >= all_length/2:
return ele
return -1
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:
return False
row = len(matrix)
col = len(matrix[0])
if row == 1 and col == 0:
return False
data = []
for i in range(row):
data.extend(matrix[i])
data = set(data)
return target in data
class Solution:
def smallestDifference(self, a: List[int], b: List[int]) -> int:
if not a or not b:
return None
a.sort()
b.sort()
len_a = len(a)
len_b = len(b)
cur_a = 0
cur_b = 0
min_abs = 2147483647 * 2
while cur_a < len_a and cur_b < len_b:
if abs(a[cur_a] - b[cur_b]) < min_abs:
min_abs = abs(a[cur_a] - b[cur_b])
if a[cur_a] > b[cur_b]:
cur_b += 1
else:
cur_a += 1
return min_abs
考点：
1、想到有一道坐公交的题，和这个类似，用一个数组表示所有年份，然后一个人一生在所有年份加1； 最后就可以直接返回 人数最多年份
class Solution:
def maxAliveYear(self, birth: List[int], death: List[int]) -> int:
years = [0] * 101
for i in range(len(birth)):
b = birth[i] - 1900
d = death[i] - 1900
for k in range(b, d + 1):
years[k] += 1
# print(years)
return years.index(max(years)) + 1900
考点:
1、逆向思维，由 字符窜 反推 数字组合
class Solution:
def getValidT9Words(self, num: str, words: List[str]) -> List[str]:
keyb = {"a":2, "b":2, "c":2, "d":3, "e":3, "f":3, "g":4, "h":4, "i":4, "j":5, "k":5, "l":5, "m":6, "n":6, "o":6, "p":7, "q":7, "r":7, "s":7, "t":8, "u":8, "v":8, "w":9, "x":9, "y":9, "z":9}
result = []
for word in words:
num_list = ""
for ch in word:
num_list += str(keyb[ch])
if num_list in num:
result.append(word)
return result
考点：
1、前缀和，相对正常前缀和，拐了个弯，按照数字是+1，字母是-1，求数组的前缀和
2、数组最后出现位置计算，先把数组求reverse().再使用index计算
3、注意，本题有个坑是，数字可能是多个数字组合的字符串，需要按下图绿色处理
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
array_len = len(array)
new_array = [0] * (array_len +1)
cur = 0
for i in range(array_len):
#数字+1， 字母-1
if array[i].startswith("1") or array[i].startswith("0") or array[i].startswith("2") or array[i].startswith("3") or array[i].startswith("4") or array[i].startswith("5") or array[i].startswith("6") or array[i].startswith("7") or array[i].startswith("8") or array[i].startswith("9"):
cur += 1
else:
cur += -1
new_array[i+1] = cur
new_array_reverse = list(new_array)
new_array_reverse.reverse()
# 值相等，表示中间结果值为0
max_len = 0
start = 0
end = 0
matched = []
for i in range(array_len):
try:
# if new_array[i] in matched:
# continue
r_value = array_len - new_array_reverse.index(new_array[i])
matched.append(new_array[i])
if r_value -i-1 > max_len:
max_len = r_value - i -1
start = i
end = r_value
except Exception as e:
continue
return array[start: end]
其实按照上面做，会出现超时，几个用例跑不完，加入如下优化进行剪枝
class Solution:
def findLongestSubarray(self, array: List[str]) -> List[str]:
array_len = len(array)
new_array = [0] * (array_len +1)
cur = 0
for i in range(array_len):
#数字+1， 字母-1
if array[i].startswith("1") or array[i].startswith("0") or array[i].startswith("2") or array[i].startswith("3") or array[i].startswith("4") or array[i].startswith("5") or array[i].startswith("6") or array[i].startswith("7") or array[i].startswith("8") or array[i].startswith("9"):
cur += 1
else:
cur += -1
new_array[i+1] = cur
new_array_reverse = list(new_array)
new_array_reverse.reverse()
# 值相等，表示中间结果值为0
max_len = 0
start = 0
end = 0
matched = []
for i in range(array_len):
try:
if new_array[i] in matched: # 同一个前缀和，前面是按照最前面和最后面计算，肯定比现在计算的长，所有不用重复计算
continue
r_value = array_len - new_array_reverse.index(new_array[i])
matched.append(new_array[i])
if r_value -i-1 > max_len:
max_len = r_value - i -1
start = i
end = r_value
except Exception as e:
continue
return array[start: end]