1 (num & (~num + 1)) 获取num 第一个二进制位为1的数
12
1100 2**3 + 2**2 + .. => 12
print( 12 & (~12 + 1))
# 0100 2**2 4
2 l + ((r - l) >> 1) 获取 left , right 中的中位数
l = 1
r = 11
origin = ""
for i in range(l, r + 1):
origin += str(i)
print(origin)
# 1 2 3 4 5 6 7 8 9 10 11
print(l + ((r - l) >> 1))
3 (1 << n) -1 获取 2的N次方 - 1 (2 ** n - 1)
4 int 32位 n （n >> 31）
负数 得到 1
正数 得到 0
数组中出现次数超过一半的数字
# 1 字典映射
from collections import defaultdict
count_dict = defaultdict(int)
l = [1, 0, 1, 3, 5, 1, 4, 1, 1, 1]
def find_max_len(l):
for item in l:
count_dict[item] += 1
if count_dict[item] * 2 > len(l):
return item
print(find_max_len(l))
# 2 摩尔投票
def moor_select(nums):
count = 0
majority = 0
# 摩尔投票法
for num in nums:
if count == 0:
majority = num
count += 1 if num == majority else -1
return majority
100 以内的质数
prime_number = []
for i in range(2, 101):
is_prime = True
for j in range(2, i):
if i % j == 0:
is_prime = False
break
if is_prime:
prime_number.append(i)
print(prime_number)
数组中有一个数出现次数为奇数次， 其他均为偶数次， 求出这个数 (两个数为奇数次， 求出这两个数)
l1 = [1, 1, 2, 3, 3, 4, 5, 5, 4]
l2 = [1, 1, 2, 3, 3, 4, 5, 5, 4, 9]
class Solution:
def __init__(self, array):
self.array = array
def solution_one_odd(self):
result = 0
# 0 与 任何数 亦或都等于这个数本身
for number in self.array:
# 出现偶数次的数亦或之后都是 0，最后剩下的数就是出现奇数次数的数
result ^= number
return result
@staticmethod
def _get_first_bin(number):
return number & (~number + 1)
def solution_two_odd(self):
tmp_result = 0
for number in self.array:
tmp_result ^= number
a = 0
b = 0
mask = self._get_first_bin(tmp_result)
# 找到 tmp_result 中第一次为1的位数值
for number in self.array:
# 区分 该 位是否为1
if self._get_first_bin(number) == mask:
a ^= number
else:
b ^= number
return a, b
s = Solution(array=l1)
print(s.solution_one_odd())
s = Solution(array=l2)
print(s.solution_two_odd())
无重复字符的最长子串
def find_max_length(s):
start = 0
max_len = 0
tmp_dic = {}
for index, string in enumerate(s):
if string in tmp_dic and tmp_dic[string] >= start:
start = tmp_dic[string] + 1
tmp_dic[string] = index
max_len = max(max_len, index - start + 1)
return max_len
print(find_max_length("pwwkew3215789"))
通过 2个 5/6 升水壶 从池塘得到3升水
# 装满情况下
# 5 ==> 6
# 5 ==> 6
# 5 得到 4
# 6 清空
# 5 ==> 6
# 6 得到 4
# 5 ==> 6
# 5 剩下 3
第二高的薪水 (mysql)
Employee 表：
+-------------+------+
| Column Name | Type |
+-------------+------+
| id | int |
| salary | int |
+-------------+------+
id 是这个表的主键。
表的每一行包含员工的工资信息
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/second-highest-salary
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
select (select distinct salary from Employee order by salary desc limit 1,1 ) as SecondHighestSalary
-- SELECT DISTINCT salary FROM employee ORDER BY salary DESC LIMIT N, 1
-- 第N高的薪水
select max(salary) as SecondHighestSalary from
Employee
where salary < (select max(salary) from Employee)
两数之和
# 1 O(N) O(N)
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
hash_map = {}
for index, num in enumerate(nums):
if hash_map.get(target - num) is not None:
return index, hash_map.get(target - num)
hash_map[num] = index
# 2
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
number_length = len(nums)
for left, tmp_num in enumerate(nums):
right = number_length - 1
while right > left:
if nums[right] == target - tmp_num:
return left, right
right -= 1
# 3
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for left, tmp_num in enumerate(nums):
for right, tmp_num_ in enumerate(nums):
if tmp_num + tmp_num_ == target and left != right:
return left, right
单向链表翻转
# Definition for singly-linked list.
class ListNode(object):
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution(object):
def reverse_node(self, head):
current_node, pre_node = head, None
while current_node:
tmp = current_node.next
current_node.next = pre_node
pre_node = current_node
current_node = tmp
return pre_node
def reverse_node_(self, head):
if not head or not head.next:
return head
res = self.reverse_node_(head.next)
head.next.next = head
head.next = None
return res
图 Graph
图：
顶点： 顶点又称为节点，是图的基础部分，我们可以给它一个名字叫“键”。
边： 边是图的另一个基础部分，两个顶点通过一条边相连，表示它们之间存在的关系，边既可以是单向的也可以是双向的
权重： 边可以带权重，表示从一个顶点到另一个顶点的成本
路径: 路径是由边连接的顶点组成的序列
环： 有向图中的一条起点和终点为同一顶点的路径，没有环的图叫无环图，没有环的有向图叫有向无环图（DAG）
图的表示
邻接表法：对于每个图中的点，将它的邻居放到一个链表里
邻接矩阵：对于 n 个点，构造一个 n * n 的矩阵，如果有从点 i 到点 j 的边，就将矩阵的位置 matrix[i][j] 置为 1.
图的遍历
BFS: Breadth First Search，广度优先搜索
DFS: Depdth First Search，深度优先搜索
# 图的广度优先遍历
from queue import Queue
GRAPH = {
'A': ['B', 'F'],
'B': ['C', 'I', 'G'],
'C': ['B', 'I', 'D'],
'D': ['C', 'I', 'G', 'H', 'E'],
'E': ['D', 'H', 'F'],
'F': ['A', 'G', 'E'],
'G': ['B', 'F', 'H', 'D'],
'H': ['G', 'D', 'E'],
'I': ['B', 'C', 'D'],
}
q = Queue()
unique_set = set()
#
def bfs(graph, start):
q.put(start)
while not q.empty():
current = q.get()
if current not in unique_set:
unique_set.add(current)
print(current)
for next in graph[current]:
q.put(next)
bfs(GRAPH, 'A')
# A
# B
# F
# C
# I
# G
# E
# D
# H
#
def dfs(graph, start):
if start not in unique_set:
print(start)
unique_set.add(start)
for next in graph[start]:
if next not in unique_set:
dfs(graph, next)
dfs(GRAPH, 'A')
#
# A
# B
# C
# I
# D
# G
# F
# E
# H
####
