贪心算法
理论基础
什么是贪心？
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
说实话贪心算法并没有固定的套路。
所以唯一的难点就是如何通过局部最优，推出整体最优。
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
这个四步其实过于理论化了，我们平时在做贪心类的题目 很难去按照这四步去思考，真是有点“鸡肋”。
做题的时候，只要想清楚 局部最优 是什么，如果推导出全局最优，其实就够了
1. 分发饼干
455
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
1
2
3
4
5
6
| 输入: g = [1,2,3], s = [1,1]
输出: 1
解释:
你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。
虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。
所以你应该输出1。
|
这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。
可以尝试使用贪心策略，先将饼干数组和小孩数组排序。
然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
var findContentChildren = function(g, s) {
g.sort((a,b)=>a-b)
s.sort((a,b)=>a-b)
let index=s.length-1
let result=0
for(let i=g.length-1;i>=0;i--){
if(index>=0&&s[index]>=g[i]){
index--
result++
}
}
return result
};
|
算法
1、数组的快慢指针
2、递归和尾递归
3、 回溯算法
回溯法 采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，
回溯法的模板代码 比如：力扣46题全排列
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| var permute = function(nums) {
const res=[], path=[]
const used=[]
backtracking(nums,nums.length,used)
return res
function backtracking(n, k, used){
if(path.length===k){
return res.push(Array.from(path))
}
for(let i=0;i<k;i++){
if(used[i]) continue
path.push(n[i])
used[i]=true
backtracking(n,k,used)
path.pop()
used[i]=false
}
}
};
|
4、动态规划
我们先来了解一下动态规划的几个步骤
1，确定状态
2，找到转移公式
f(i,j)=f(i−1,j)+f(i,j−1)
3，确定初始条件以及边界条件
4，计算结果。
5、数字翻转
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| 示例 1：
输入：x = 121
输出：true
示例 2：
输入：x = -121
输出：false
解释：从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3：
输入：x = 10
输出：false
解释：从右向左读, 为 01 。因此它不是一个回文数。
来源：力扣（LeetCode）
链接：https:
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
var isPalindrome = function(x) {
if(x<0||(x%10==0&&x!=0)){
return false
}
let remeber=0
while(x>remeber){
remeber=remeber*10+x%10
x=Math.floor(x/10)
}
return x==Math.floor(remeber/10)||x==remeber
};
|
对于数字翻转 可用变为字符串，然后前后指针一一对比。这里采用%10,/10的方法 实现了翻转，Math.floor() 向下取整，Math.ceil()向上取整
6、二叉树
dfs深度优先遍历。
1
2
3
4
5
6
7
8
9
10
|
var maxDepth = function(root) {
if(!root){
return 0
}
return 1+Math.max(maxDepth(root.left),maxDepth(root.right))
};
|
bfs广度优先遍历
队列先进先出，符合一层一层遍历的逻辑
力扣102题
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
var levelOrder = function(root) {
let queue=[]
let res=[]
if(!root){
return res
}
queue.push(root)
while(queue.length){
let length=queue.length
let curNode=[]
while(length--){
let node=queue.shift()
curNode.push(node.val)
node.left && queue.push(node.left)
node.right && queue.push(node.right)
}
res.push(curNode)
}
return res
};
|
7. 二维数组的创建
1
2
3
|
let result = Array.from(new Array(n), () => new Array(n).fill(0))
let arr=new Array(n).fill(0).map(() => new Array(n).fill(0))
|
8. 异或运算
1、任何数和自己做异或运算，结果为 0，即 a⊕a=0。
2、任何数和 0 做异或运算，结果还是自己，即 a⊕0=a。
3、异或运算中，满足交换律和结合律，也就是 a⊕b⊕a=b⊕a⊕a=b⊕(a⊕a)=b⊕0=b
1
2
| Operator: x ^= y
Meaning: x = x ^ y
|
按位异或赋值 (^=)
9. 字符串转数字
https://www.jb51.net/article/261613.htm
JavaScript中将字符串转换为数字的七种方法总结
10. 隐式转换
11. sort快速排序
时间复杂度为nlogn
二维数组的排序比如力扣347题
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
1
2
3
4
5
6
7
8
9
10
11
12
|
var topKFrequent = function(nums, k) {
const map=new Map()
for(let item of nums){
map.set(item,(map.get(item)||0)+1)
}
return [...map].sort((a,b)=>b[1]-a[1]).map(item=>item[0]).slice(0,k)
};
|
