根据自己对算法和数据结构的理解写出的思路和代码，如有错误欢迎指出。
一 排序
快排
快排的思想是从一堆数中随便选一个数作为pivot，遍历把所有比pivot小的移到左边，把比pivot大的移到右边。然后对生成的左右两个区间重复上述过程，直到区间大小缩小为1。
思路：
- 选取数组末尾的数作为pivot
- 将数组的值和pivot进行比较：
a. 当前值比pivot大，但索引是位于pivot的的左边，进行交换
b. 当前值比pivot小，但索引是位于pivot的的右边，进行交换 - 递归调用对左边子区间进行处理
- 递归调用对右边子区间进行处理
- 递归出口是区间内只有一个元素
function sort(arr, startIndex, endIndex) {
// 递归出口，区间内只有一个元素的情况
if (startIndex >= endIndex) {
return
}
// 把最左侧作为pivot
let pivot = endIndex
for(let i = startIndex; i < endIndex; i++) {
// 当前值比pivot大，但索引是位于pivot的的左边，进行交换
if (arr[i] > arr[pivot] && i < pivot) {
swap(arr, i, pivot)
}
// 当前值比pivot小，但索引是位于pivot的的右边，进行交换
if (arr[i] < arr[pivot] && i > pivot) {
swap(arr, i, pivot)
}
}
console.log(JSON.stringify(arr), pivot)
// 递归调用对左边子区间进行处理
sort(arr, startIndex, pivot-1)
// 递归调用对右边子区间进行处理
sort(arr, pivot+1, endIndex)
}
// 数据交换和索引交换，有副作用
function swap(arr, i, pivot) {
let temp = arr[pivot]
arr[pivot] = arr[i]
arr[i] = temp
pivot = i
}
// 测试数据
const arr = [1, 5, 7, 4, 3, 6, 10, 11, 12, 20, 19, 18, 17, 9, 40, 21, 32, 8]
// 进行搜索
sort(arr, 0, arr.length-1)
console.log(arr)
归并排序
二 动态规划问题
动态规划的定义：
dynamic programming is a method for solving a complex problem by breaking it down into a collection of simpler subproblems.
爬楼梯
有一个有n个台阶的楼顶，小明一次只能爬一个或者两个台阶，爬到楼顶有多少种可能？
思路：
由于一次只能爬1个或两个台阶，爬到第n个台阶有两个可能，从n-1阶爬1个台阶，或者是从n-2阶爬2个台阶，假设爬到第n个台阶的可能记为f(n)，那么爬到n-1个台阶的可记为f(n-1)，爬到n-2个台阶为f(n-2)，其实不用考虑f(n-1)和f(n-2)是否有重复的路径，即使重复了也没关系，最后到第n阶台阶是两种不同的选择，就会让所有的选择都不相同。(这里有点绕，理解了这一点，解决类似的问题就很容易了)，这样就能得出下面的等式
f(n)=f(n-1)+f(n-2)
这里只给出动态规划的代码
求 f(n)=f(n-1)+f(n-2)，可以分解成 f(n-1)=f(n-2)+f(n-3)、f(n-2)=f(n-3)+f(n-4)...、f(3)=f(2)+f(1)
可以自底往上求解，f(1)、f(2)可以很容易得到，从而可以求出f(3)，根据f(2)和f(3)可以求出f(4)，可以对这一过程进行循环最终得到f(n)
function f(n){
let arr = new Array(n)
for (let i = 0; i < n; i++) {
if (i === 0) {
arr[0] = 1
} else if (i === 1) {
arr[1] = 2
} else {
arr[i] = arr[i-1] + arr[i-2]
}
}
console.log(arr)
return arr[n-1]
}
console.log(f(10))
数组最大子序和
棋盘路径
三 链表
链表的反转
四 二叉树
二叉树的前、中、后序遍历
这里的前、中、后是指遍历中间节点的顺序，若是中、左、右的顺序遍历则是前序，若是在左、中、右的顺序遍历则是中序，若是左右中的顺序遍历则是后序
前序
二叉搜索树查找
五 字符串相关
哈希查重
找出字符串中第一个只出现一次的字符 输入描述：输入一个非空字符串
输出描述：输出第一个只出现一次的字符，如果不存在输出-1
示例1
输入：asdfasdfo
输出：o
有两种解题思路：
- 可以采用双重循环，遍历每一个字符累加它出现的次数，遇到次数为1的情况则返回该字符。
function find(str) {
for(let i = 0; i < str.length; i++) {
let times = 0
for(let j = 0; j < str.length; j++) {
if (str[i] === str[j]) {
times++
}
}
if(times === 1){
return str[i]
}
}
return -1
}
console.log(find('asdfasdfo'))
由于采用了双重循环算法的时间复杂度是O(n²)
- 采用哈希，时间复杂度可以达到O(n)，跟字符串查重相关的题目可以优先考虑哈希
function find(str) {
let hashObject = {}
for(let i = 0; i < str.length; i++) {
if (hashObject[str[i]]) {
hashObject[str[i]] +=1
} else {
hashObject[str[i]] = 1
}
}
for(let i = 0; i < str.length; i++) {
if (hashObject[str[i]] === 1) {
return str[i]
}
}
return -1
}
console.log(find('asdfasdfo'))
参考:
https://www.zhihu.com/question/23995189
https://blog.csdn.net/a911711054/article/details/72869324
https://101.zoo.team/dong-tai-gui-hua/dong-tai-gui-hua-part-1-zui-da-zi-xu-he-pa-lou-ti-he-mai-mai-gu-piao-de-zui-jia-shi-ji
