[2019+] CS Fundamentals: Algorithms and Data structures
An engineer and explorer. Let's improve everything.
Have a fun day!
// 增加: push / unshift / splice
array.push(1)
array.unshift(1)
array.splice(增加位置, 0, 55, 66, 77)
// 删除: pop / shift / splice
array.pop()
array.shift()
array.splice(删除位置, 删除几个)# 增加: append / insert(位置, 值)
# 删除: pop(index)// 拼接 浅拷贝 类似 python [1] + [2]
concat()
// 截取
slice(startindex, endIndex(不包含))
var array = [1,2,3,4]
var slicedata = array.slice(1, 3) // [2, 3] 类似python array[1: 3]
var slicedata = array.slice(3,4) // [4]# 拼接: array1 + array2
# 截取: array[1: 4] 从位置1 到位置3 (不包含4)array.reverse()
array.sort()
array.join('&')
array.indexOf(888) // [2, 888, 1] 888是否在数组中, 返回index# 排序: sort() reverse()
# 连接: str.join(array) 例如 '&'.join(array)var topKFrequent = function(nums, k) {
if (nums.length < 1 || nums.length < k) return []
var map = new Map()
for (_d of nums) {
map.has(_d) ? map.set(_d, map.get(_d) + 1) : map.set(_d, 1)
}
var nums = [...new Set(nums)]
// 根据map里的数量, 来从大到小排序
return nums.sort((a, b) => map.get(b) - map.get(a)).slice(0, k)
};
前缀相同即可
// 两两比较
var twoMatch = function (str1, str2) {
if (!str1 || !str2) return ''
var i = 0
while (i < str1.length && i < str2.length) {
if (str1[i] !== str2[i]) break
i += 1
}
return i === 0 ? '' : str1.slice(0, i)
}
var longestCommonPrefix = function(strs) {
if (strs.length === 0) return ''
if (strs.length === 1) return strs[0]
var prev = strs[0]
for (let i = 1; i < strs.length; i++) {
prev = twoMatch(prev, strs[i])
if (prev === '') return ''
}
return prev
};// 最好的情况是O(N)，最差的时候是O(N^2)，所以平时说的O(N*logN)为其平均时间复杂度
var arr = [4, 3, 1, 5, 10, 2, 7]
function quickSort (arr) {
if (arr.length <= 1) return arr
var left = [], right = [], mid = []
var pivot_index = Math.floor(arr.length / 2)
var pivot = arr[pivot_index]
// 小于放到left, 等于放到mid, 大于放到right
for (data of arr) {
if (data < pivot) { left.push(data) }
else if (data > pivot) { right.push(data) }
else { mid.push(pivot) }
}
return quickSort(left).concat(mid).concat(quickSort(right))
}
quickSort(arr)统计一个数字在排序数组中出现的次数。
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
# 双指针
class Solution:
def search(self, nums: List[int], target: int) -> int:
if len(nums) == 0: return 0
result = 0
i = 0
while i < len(nums):
if nums[i] < target: i += 1
elif nums[i] == target:
i += 1
result += 1
else:
break
return result# 二分查找
class Solution:
def search(self, nums: List[int], target: int) -> int:
_len = len(nums)
if _len == 0: return 0
if _len == 1:
return 1 if nums[0] == target else 0
half = _len // 2
left_nums = nums[0: half]
right_nums = nums[half: ]
return self.search(left_nums, target) + self.search(right_nums, target)动态规则: 求最值问题。运筹学的最优方法。
核心问题是什么呢？求解动态规划的核心问题是穷举。
因为要求最值，肯定要把所有可行的答案穷举出来，然后在其中找最值呗
[动态规划三要素]
1. 重叠子问题
2. 最优子结构
3. 状态转移方程
明确问题 => 明确状态 => 明确选择 => 定义DP
先思考“如何穷举(所有解的可能)”，然后再追求“如何聪明地穷举”。
要求: 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
相同数为0 不同为1
eg: 001 ^ 101 (1 和 5) => 100(5)
任何数 和 0异或是本身
eg: 000 ^ 101 (0 和 5) => 101(4) => **0 ^ x = x**
相同的数 两两异或，是为0
eg: **x ^ x = 0**
# 输入: [2,2,1] 输出: 1
class Solution(object):
def singleNumber(self, nums):
"""
每个数都和0异或, 如此往复选出 只出现一次的值
[2,2,1] => [010, 010, 001]
1. 000 ^ 010 = 010
2. 010 ^ 010 = 000
3. 000 ^ 001 = 001 最后选出来为1
"""
value = 0
for num in nums:
value = value ^ num # 位运算
return value # 选出来的唯一值class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m = len(matrix)
if m == 0: return []
if m == 1: return matrix[0] # 矩阵只有一行
if m == 2: return matrix[0] + matrix[1][::-1] # 矩阵只有两行
if len(matrix[0]) == 0: return [] # 矩阵一行里没有值
if len(matrix[0]) == 1: # 矩阵一行里只有一个值
result = []
for m in matrix:
result += m
return result
up = matrix.pop(0) # 第一个
bottom = matrix.pop() # pop最后一个
left, right = [], []
for i in range(len(matrix)):
left.append(matrix[i].pop(0))
right.append(matrix[i].pop())
# [::-1] 数组逆序
return up + right + bottom[::-1] + left[::-1] + self.spiralOrder(matrix)左边子树值 < root.val
右边子树值 > root.val
通过使用【中序遍历】 left => root => right 路径判断 是否是递增的序列
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]
思路
1. forward正向 [占位1, 1, 1 * 2, 1 * 2 * 3, 1 * 2 * 3 * 4]
2. backward反向 [占位1, 5, 5 * 4, 5 * 4 * 3, 5 * 4 * 3 * 2][::-1]
3. forward[0] * backward[0], forward[1] * backward[1], .......
class Solution:
def constructArr(self, a: List[int]) -> List[int]:
if len(a) == 0: return []
if len(a) == 1: return a
if len(a) == 2: return a[::-1] # [3, 2] return [2, 3]
# [1, 2, 3, 4]
# forward = 正向推理一次 [占位1, 1, 1 * 2, 1 * 2 * 3]
# backward = 反向推理一次 [4 * 3 * 2 ,4 * 3, 4, 占位1]
# forward[0] * backward[0], forward[1] * backward[1], forward[2] * backward[2] ....
forward, backward = [1], [1]
tmp = 1
for i in range(0, len(a) - 1):
tmp *= a[i]
forward.append(tmp)
tmp = 1
for j in range(len(a) - 1, 0, -1):
tmp *= a[j]
backward.append(tmp)
backward = backward[::-1]
result = []
for i in range(len(a)): result.append(forward[i] * backward[i])
return result
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
Django
The Web framework for perfectionists with deadlines.
Laravel
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
Microsoft
Open source projects and samples from Microsoft.
Google
Google ❤️ Open Source for everyone.
Alibaba
Alibaba Open Source for everyone
D3
Data-Driven Documents codes.
Tencent
China tencent open source team.