五大常用算法思想
- 分治
- 分解问题（把一个大问题分解成小问题）
- 解决问题（解决每一个问题）
- 合并问题（把子问题答案合并）
- 动态规划
- 贪心
- 回溯
- 分支界定
LRU(【查找快】【插入快】【删除快】【有顺序之分】)
map
- 根据创建顺序排序
- 可以直接调用 size 方法
- 能够根据迭代器直接删除第一个节点
```javascript
// map
/**
- @param {number} capacity */ var LRUCache = function(capacity) { this.size = capacity; this.map = new Map() };
/**
- @param {number} key
- @return {number}
*/
LRUCache.prototype.get = function(key) {
if(this.map.has(key)){
} else {const value = this.map.get(key);this.map.delete(key);this.map.set(key, value)return value;
} };return -1
/**
- @param {number} key
- @param {number} value
@return {void} */ LRUCache.prototype.put = function(key, value) { if(this.map.has(key)){
const value = this.map.get(key); this.map.delete(key);}
this.map.set(key, value)
if(this.map.size > this.size){
this.map.delete(this.map.keys().next().value)} };
/**
- Your LRUCache object will be instantiated and called as such:
- var obj = new LRUCache(capacity)
- var param_1 = obj.get(key)
- obj.put(key,value)
*/
```
链表（处理新老关系）+哈希（查询在不在）
- 底层应该用链表，按照数据的新旧程度来排列，旧的在左边，新的在右边，新来一个加到尾部（你可以想象自己从左往右画一条链表），删除是删头,除了这两个操作，还有就是把一个数据从中间拿出来放尾巴上（这个数组就很难做到）
- 这里还有一个需求，就是要知道这个数据有没有存在于链表中，如果不在链表中，加到尾巴即可，如果已经在链表中，就只要更细数据的位置,如何查找这个数据在不在呢，这就用哈希表。
- 考虑删除操作，要把当前节点的前一个节点的指针的改变，获取它前一个节点，方便的数据结构就是 双向链表
使用双链表+HashMap
二分法
最坏时间复杂度 O(logn)
最优时间复杂度 O(1)
平均时间复杂度 O(logn)
空间复杂度 O(1)
给定一个数组 arr，目标值 T，查找 T 在 a 中的位置 ```javascript // 递归 function binary_search(arrs, T){ let left = 0; let right = arrs.length - 1; let ans = -1 function search(left, right){ if(left > right){ return -1 }
let m = parseInt( (left + right) / 2 )
if(T === arrs[m]){ ans = m; return } else if(T > arrs[m]){ search(m + 1, right); } else if(T < arrs[m]){ search(left, m - 1); } }
search(left, right); return ans; }
binary_search([1, 2, 3], 1)
// 非递归 function binary_search(arrs, T){ let left = 0; let right = arrs.length - 1; while(left <= right){ let m = parseInt((left + right)/2); if(T === arrs[m]){ return m } else if(T > arrs[m]){ left = m + 1 } else if(T < arrs[m]){ right = m - 1 } } return -1 }
<a name="Iv4rl"></a>
# 排序
**算法分类**<br />十种常见排序算法可以分为两大类：
- **比较类排序**：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此也称为非线性时间比较类排序。
- **非比较类排序**：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。
<a name="agJFN"></a>
## 选择排序（暴力解法）
最暴力的解法就是先找出数组中的最小值，放在第一位，然后再找到第二小的元素，放在第二位... <br />算法的时间复杂度一律都是O(N)， 基本上可以说是最差的了
移动元素最少
```javascript
function sort(arrs){
let i = 0;
let j = 0;
while( j <= arrs.length - 1){
i = j
let minIndex = i;
while( i <= arrs.length - 1){
if(arrs[i] < arrs[minIndex]){
minIndex = i
}
i++
}
console.log('minIndex', minIndex)
const temp = arrs[minIndex];
arrs[minIndex] = arrs[j];
arrs[j] = temp;
j++
}
return arrs
}
冒泡排序
从第一个元素开始，把当前元素和下一个索引元素进行比较。如果当前元素大，那么就交换位置，重复操作直到比较到最后一个元素
最优时间复杂度： O(n)
平均/最坏时间复杂度：O(N)
空间复杂度： O(1)
function sort(arrs){
if(arrs.length === 0){
return 0
}
let i = 0;
let j = arrs.length - 1;
while( j > 0 ){
i = 0
while(i < arrs.length - 1){
if(arrs[i] > arrs[i + 1]){
let temp;
temp = arrs[i + 1];
arrs[i + 1] = arrs[i];
arrs[i] = temp;
}
i++
}
j--
}
return arrs
}
插入排序
原理：第一个元素默认是已排序元素，取出下一个元素和当前元素比较，如果当前元素大就交换位置。那么此时第一个元素就是当前的最小数，所以下次取出操作从第三个元素开始，向前对比，重复之前的操作。
最优时间复杂度： O(n)
平均/最坏时间复杂度：O(N)
空间复杂度： O(1)
- 数组中每个元素距离它的最终位置都不远
- 一个有序的大数组接一个小数组
- 数组中只有几个元素的位置不正确
```javascript
var arr=[5,7,2,9,3,8,4,7,1];
// 每次选择最左边的数作为基数
function quickSort(arr){
// 定义左指针
var left = 0;
// 定义右指针
var right = arr.length-1;
//开启每一轮的排序
while(left < right){
// 寻找右边比arr[0]小的数的下标
while(arr[right] >= arr[0] && left < right){
} // 寻找左边比arr[0]大的数的下标 while(arr[left] <= arr[0] && left < right){right = right - 1;
} //当左边指针与右边指针相遇后，交换arr[0]与当前两个指针所在的元素 if (right == left) {left++;
} // 当左指针小于右指针的位置，交换两个指针当前位置的元素 let tem = arr[right]; arr[right] = arr[left]; arr[left] = tem; } //递归实现 return quickSort(arr.slice(0,left)).concat(arr.slice(left,right+1)).concat(quickSort(arr.slice(right+1))); } //对数组进行排序 console.log(quickSort(arr));let mid = arr[right]; arr[right] = arr[0]; arr[0] = mid; break;
<a name="MEHmC"></a>
##
<a name="hQynG"></a>
## 希尔排序
<a name="a1BTN"></a>
## 快速排序
- 1．先从数列中取出一个数作为基准数。
- 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3．再对左右区间重复第二步，直到各区间只有一个数。
<a name="dau49"></a>
# 数组
- 优点：构建比较简单，能够在 O(1) 的时间里根据数组的下标（index) 查询某个元素
- 缺点：
- 构建时必须分配一段连续的空间
- 查询某个元素是否存在时需要遍历整个数组，耗费 O(n) 的时间
- 删除某个元素时，同样需要耗费 O(n) 的时间
<a name="vpScl"></a>
## [左旋转字符串](https://leetcode-cn.com/problems/zuo-xuan-zhuan-zi-fu-chuan-lcof/)
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
**输入:** s = "abcdefg", k = 2<br />**输出: **"cdefgab"
```javascript
// 原地(不申请额外空间) 局部反转+整体反转
// reverse 是数组的方法！
var reverse = function( str ){
return str.split('').reverse().join('');
};
var reverseLeftWords = function(s, n) {
return reverse(reverse(s.slice(0, n)) + reverse(s.slice(n)))
}
// 字符串切片
var reverseLeftWords = function(s, n) {
const _str = s
const str1 = s.slice(0, n);
const str2 = _str.slice(n);
return str2 + str1;
}
// 列表遍历拼接
var reverseLeftWords = function(s, n) {
let str1 = '',
str2 = '';
for(let i = 0; i < s.length; i++){
if(i < n){
str1 += s.charAt(i)
} else {
str2 += s.charAt(i)
}
}
return str2 + str1;
}
// 列表遍历拼接
// 先转换为数组
// 分为两个数组
// 数组合并
var reverseLeftWords = function(s, n) {
const arr = s.split('');
const arr1 = [];
const arr2 = [];
for(let i = 0; i < arr.length; i++ ){
if(i < n){
arr1.push(arr[i])
}else{
arr2.push(arr[i])
}
}
return arr2.concat(arr1).join('');
};
字符串翻转
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串”I am a student. “，则输出”student. a am I”。
输入: “the sky is blue“
输出: “blue is sky the“
var reverseWords = function(s) {
return s.trim().split(' ').filter( item => item !== '').reverse().join(' ')
};
// 双指针
var reverseWords = function(s) {
let _s = s.trim();
let right = _s.length - 1;
let res = [];
let isEnd = false;
for(let left = _s.length - 1; left >= 0; left--){
if(s[left].charAt() === ' '){
res.push(s.slice(left + 1, right + 1))
isEnd = true
}
if(isEnd && _s[left].charAt() !== ' '){
right = left;
isEnd = false;
}
}
for(let i = 0; i < _s.length; i++){
if(_s[i].charAt() === ' '){
res.push(_s.slice(0, i))
break;
}
}
return res.join(' ')
}
var reverseWords = function(s) {
s=s.trim()
res=[]
let i = j = s.length-1
while(i >= 0){
while( i >= 0 & s[i] != ' '){ i-=1 }
res.push(s.slice(i + 1,j + 1))
while(s[i] == ' '){ i -= 1}
j = i
}
return res.join(' ')
};
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词（只包含小写字母）
// 哈希表
var isAnagram = function(s, t) {
let arrs = Array(26).fill(0);
for(let i = 0; i < s.length; i++){
arrs[s[i].charCodeAt() - 'a'.charCodeAt()]++
}
for(let j = 0; j < t.length; j++){
arrs[t[j].charCodeAt() - 'a'.charCodeAt()]--
}
for(let k = 0; k < arrs.length; k++){
if(arrs[k] !== 0){
return false;
}
}
return true;
};
// 对字母重新排序
var isAnagram = function(s, t) {
return s.split('').sort().join() === t.split('').sort().join()
}
链表
单链表：链表的每个元素实际上是一个单独的对象，而所有的对象都是通过每个元素中的引用字段链接在一起的
双向链表：与单链表不同的是，双链表的每个节点中都含有两个引用字段
- 优点：
- 灵活地分配内存空间
- 能在 O(1) 时间内删除或者添加元素
- 缺点：查询元素需要 O(n) 时间
利用快慢指针（prev curr next）
- 链表的翻转、
- 寻找倒数第 k 个元素、
- 寻找链表中中间位置的元素
- 判断链表是否有环
构建一个新的链表头要返回新的链表头
- 两个排序链表、进行整合排序
- 将链表的奇偶数按原定顺序分离、生成前半部分为奇数、后半部分为偶数的链表
合并有序链表
function mergeTwoLists( l1 , l2 ) {
// write code here
if(l1 === null) return l2;
if(l2 === null) return l1;
if(l1.val < l2.val){
l1.next = mergeTwoLists(l1.next, l2);
return l1;
} else {
l2.next = mergeTwoLists(l1, l2.next);
return l2;
}
}
function mergeTwoLists( l1 , l2 ) {
// write code here
let hair=new ListNode(0);
let l=hair;
while(l1&&l2){
if(l1.val<=l2.val){
l.next=l1;
l=l.next;
l1=l1.next;
}else{
l.next=l2;
l=l.next;
l2=l2.next;
}
}
while(l1){
l.next=l1;
l=l.next;
l1=l1.next;
}
while(l2){
l.next=l2;
l=l.next;
l2=l2.next;
}
return hair.next;
}
链表的翻转
function ListNode(val) {
this.val = val;
this.next = null;
}
function LinkedList(){
this.find = find // 查找
this.insert = insert // 插入
this.remove = remove // 删除元素
this.findPrev = findPrev // 查找前一个元素
}
function find(value) {
let cur = this.head;
while(cur.val !== value){
cur = cur.next
}
return cur;
}
function insert(newEle, value){
let node = new ListNode(newEle);
let curr = this.find(value);
node.next = curr.next;
curr.next = node;
}
// 从链表中删除节点时，我们先要找个待删除节点的前一个节点，找到后，我们修改它的 next 属性，使其不在指向待删除的节点，而是待删除节点的下一个节点。那么，我们就得需要定义一个 findPrevious 方法遍历链表，检查每一个节点的下一个节点是否存储待删除的数据。如果找到，返回该节点，这样就可以修改它的 next 属性了。 findPrevious 的实现如下：
function findPrev(value){
let curr = this.head;
while( !(curr.next == null) && curr.next.val !== value ){
curr = curr.next
}
return curr;
}
function remove(value){
let removeItem = this.find(value);
let removePrevItem = this.findPrev(value);
if(removePrevItem.next !== null){
removePrevItem.next = removePrevItem.next.next;
}
}
var reverseList = function(head) {
let cur = null;
let pre = head;
while(pre){
let temp = pre.next
// 翻转
pre.next = cur;
// 同时向前移动
cur = pre
pre = temp;
}
return cur
};
删除链表的节点
// 双指针
var deleteNode = function(head, val) {
if( head.val === val){
return head.next
}
let curr = head;
let prev = curr.next;
while(prev.val !== val){
// prev curr 都向前移动
let tempNode = prev;
prev = prev.next;
curr = tempNode;
}
curr.next = curr.next.next;
return head;
};
k 个一组翻转链表（25）
给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k是一个正整数，如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序
// 使用一个栈存放 k 个元素，满了就出栈
var reverseKGroup = function(head, k) {
let arrs = [];
let curr = head;
let ans;
if(arrs.length < k){
arrs.push(curr)
curr = curr.next;
}
if(arrs.length === k){
}
};
判断链表中是否有环
给定一个链表，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
如果链表中存在环，则返回 true 。 否则，返回 false 。
1. 用 JSON.stringify() 如果报错说明有循环引用
2. 快慢指针
3. 哈希表
var hasCycle = (head) => {
let map = new Map();
while(head){
if(map.has(head)) return true;
map.set(head);
head = head.next
}
return false
}
var hasCycle = (head) => {
let fastP = head;
let slowP = head;
while(fastP){
if(fastP.next == null) return false
slowP = slowP.next;
fastP = fastP.next.next;
if(slowP == fastP) return true
}
return false
}
栈
后进先出
利用一个单链表实现栈的数据结构
当你只关心最近一次的操作，并且在操作完成之后要查找上一次的操作。
两个栈模拟一个队列
var stack1 = [];
var stack2 = [];
function push(node)
{
// write code here
stack1.push(node);
}
function pop()
{
// write code here
if(stack2.length) return stack2.pop();
while(stack1.length){
let temp = stack1.pop();
stack2.push(temp);
}
return stack2.pop()
}
有效括号（20）
给定一个只包括 ( ) { } [] 的字符串，判断字符串是否有效，有效字符串需要满足:
- 左括号必须用同类型的右括号闭合
- 左括号必须用争取的顺序闭合
- 空字符串可被认为是有效字符串
每日温度（739）
根据每日气温列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数，如果之后都不会升高，请在该位置用 0 代替。
队列
先进先出（双链表，尾指针允许在队尾查看和添加指针，头指针查看和删除数据）
需要按照一定的顺序处理数据并且数据在不断地变化
双端队列
- 队列的头和尾两端能在 O(1) 的时间内进行数据查看、添加和删除
二叉树
分别按照二叉树先序，中序和后序打印所有的节点。
function threeOrders( root ) {
if(!root){
return [];
}
// write code here
let res = [];
res[0] = [];
res[1] = [];
res[2] = []
// 先序
const def1 = (root) => {
if(!root) return;
res[0].push(root.val);
def1(root.left);
def1(root.right);
}
// 中序
const def2 = (root) => {
if(!root) return;
def2(root.left);
res[1].push(root.val);
def2(root.right);
}
// 后序
const def3 = (root) => {
if(!root) return;
def3(root.left);
def3(root.right);
res[2].push(root.val);
}
def1(root);
def2(root);
def3(root);
return res;
}
二叉树的层序遍历
function levelOrder( root ) {
// write code here
return dfs(root, 0, []);
}
function dfs(root, step, res){
if(!root) return [];
if(!res[step]) res[step] = [];
res[step].push(root.val);
dfs(root.left, step + 1, res);
dfs(root.right, step + 1, res);
return res
}
若有收获，就点个赞吧
0 人点赞
