算法学习日志
文章目录
记录每天学习的算法方便以后的复习!
排序问题
冒泡排序
对于一组数字中每两个相邻的数字,如果前面的比后面的大,则交换这两个数字;
每一趟排序完成后,都会有一个最大的数字排到正确的位置,即尾部。总共需要N-1趟完成排序。
python :
def bubble_sort(li):
for i in range(len(li)-1): #第i趟循环
exchange = False #加入标识位
for j in range(len(li)-i-1): #指针的位置
if li[j] > li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
exchange = True
if not exchange: #如果一趟中没有交换,直接停止
returnjs:
const bubbleSort = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
for (let j = 0; j < arr.length - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
let temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
return arr;
};算法复杂度:O(n2)
选择排序
每次遍历选出一个最大或最小的数归位。
python:
def select_sort(li):
for i in range(len(li)-1):
min_loc = i
for j in range(i,len(li)):
if li[j] < li[min_loc]:
min_loc = j
li[i],li[min_loc] = li[min_loc],li[i]js:
const selectSort = (arr) => {
for (let i = 0; i < arr.length - 1; i++) {
let minLoc = i;
for (let j = i; j < arr.length; j++) {
if (arr[j] < arr[minLoc]) {
minLoc = j;
}
}
let temp = arr[minLoc];
arr[minLoc] = arr[i];
arr[i] = temp;
}
return arr;
};时间复杂度:O(n2)
插入排序
每次从无序区的第一位取出一个数,在有序区中寻找正确的位置将其插入(类比抽扑克牌捋牌)。
python:
def insert_sort(li):
for i in range(1,len(li)): #摸到的牌手里的下标
temp = li[i]
j = i-1 #待比较的牌
while j >= 0 and li[j] > temp:
li[j+1] = li[j]
j -= 1
li[j+1] = tempjs:
const insertSort = (arr) => {
for (let i = 1; i < arr.length; i++) {
let temp = arr[i];
let j = i - 1;
while (j >= 0 && arr[j] > temp) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = temp;
}
return arr;
};时间复杂度:O(n2)
快速排序
取一个元素P,使元素p归位。
待排序的数组会被元素p分为两部分,p左边的元素都比p小,右边的元素都比p大。
使用递归完成排序。
python:
def quick_sort(li,left,right): #left/right:待排序部分的左/右边第一个下标
if left < right: #说明列表至少有两个元素
mid = partition(li,left,right) #mid:归位在中间的元素的下标
quick_sort(li,left,mid-1)
quick_sort(li,mid+1,right)
# 思路: 先把左边的值取出来,建立两个指针相对运动,如果右边指针的值比temp小,则填入左边的空位
#互换后左边的指针向右移动,如果左边指针的值比temp大,则填入右边的空位。
def partition(li,left,right):
temp = li[left]
while left < right:
while left < right and li[right] >= temp:
right -= 1
li[left] = li[right]
while left < right and li[left] <= temp:
left += 1
li[right] = li[left]
li[left] = temp
return leftjs:
const quickSort = (arr, left, right) => {
if (left < right) {
let mid = partition(arr, left, right);
quickSort(arr, left, mid - 1);
quickSort(arr, mid + 1, right);
}
return arr;
};
const partition = (arr, left, right) => {
let pivot = left,
index = pivot + 1;
for (let i = index; i <= right; i++) {
if (arr[i] < arr[pivot]) {
swap(arr, i, index);
index++;
}
}
swap(arr, pivot, index - 1);
return index - 1;
};
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};时间复杂度:O(nlogn) 总共logn层 每层需要n 最坏情况O(n2)
堆排序
堆是一种特殊的完全二叉树,分为大根堆和小根堆两种情况。
堆的向下调整:当根节点的左右子树都是堆时,可以通过一次向下调整将其变成一个堆。
构造堆 ===> 挨个出数
首先建立堆,然后得到堆顶元素,即为最大元素。
去掉堆顶,将最后一个元素放到堆顶,再通过一次向下调整使堆有序。此时堆顶元素为第二大元素。
重复步骤3,直到堆变空。
python:
def sift(li,low,high): #li:列表,low,堆的根节点元素的位置,high:堆的最后一个元素的位置
i = low #最开始指向根节点
j = 2*i +1 #左孩子
tmp = li[low]
while j <= high:
if j+1 <= high and li[j+1] > li[j]:
j = j+1
if li[j] > tmp:
li[i] = li[j]
i = j
j = 2*i+1
else:
li[i] = tmp
break
else:
li[i] = tmp
def heap_sort(li):
n = len(li)
for i in range((n-2)//2,-1,-1):
sift(li,i,n-1) #建堆
for i in range(n-1,-1,-1):
li[0],li[i] = li[i],li[0]
sift(li,0,i-1)js:
const swap = (arr, i, j) => {
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
};
const sift = (arr, low, high) => {
let temp = arr[low];
for (let j = 2 * low + 1; j < high; j = 2 * j + 1) {
temp = arr[low];
if (j + 1 < high && arr[j] < arr[j + 1]) {
j++;
}
if (temp < arr[j]) {
swap(arr, low, j);
low = j;
} else {
break;
}
}
};
const heapSort = (arr) => {
for (let i = Math.floor(arr.length / 2 - 1); i >= 0; i--) {
sift(arr, i, arr.length);
}
for (let i = Math.floor(arr.length - 1); i > 0; i--) {
swap(arr, 0, i);
sift(arr, 0, i);
}
return arr;
};归并排序

分治法的应用,首先将待排序的数组逐层拆分成最小的单位,再通过归并的方式分别将两个有序的数组合并。
python:
def merge(li,low,mid,high):
i = low
j = mid + 1
resArr = []
while i<= mid and j <=high:
if(li[i] <= li[j]):
resArr.append(li[i])
i += 1
else:
resArr.append(li[j])
j += 1
while i<= mid:
resArr.append(li[i])
i+=1
while j<= high:
resArr.append(li[j])
j+=1
li[low:high+1] = resArr
def merge_sort(li,low,high):
if low < high:
mid = (low + high) //2
merge_sort(li,low,mid)
merge_sort(li,mid+1,high)
merge(li,low,mid,high)js:
const mergeSort = (arr) => {
let len = arr.length;
if (len < 2) {
return arr;
}
let middle = Math.floor(len / 2),
left = arr.slice(0, middle),
right = arr.slice(middle);
return merge(mergeSort(left), mergeSort(right));
};
const merge = (left, right) => {
let result = [];
while (left.length && right.length) {
if (left[0] <= right[0]) {
result.push(left.shift());
} else {
result.push(right.shift());
}
}
while (left.length) result.push(left.shift());
while (right.length) result.push(right.shift());
return result;
};时间复杂度:O(nlogn)空间复杂度:O(n)
希尔排序
计数排序
桶排序
基数排序
二叉树的遍历问题
递归法遍历前序,中序和后序:
// 树的遍历
// 1. 树的前序,中序,后序遍历。
// 前序: 根左右 中序:左根右 后序:左右根;
const preTraversal = (root) => {
let res = [];
const traversal = (root) => {
if (root !== null) {
res.push(root.val);
traversal(root.left);
traversal(root.right);
}
};
traversal(root);
return res;
};
const inTraversal = (root) => {
let res = [];
const traversal = (root) => {
if (root !== null) {
traversal(root.left);
res.push(root.val);
traversal(root.right);
}
};
traversal(root);
return res;
};
const postTraversal = (root) => {
let res = [];
const traversal = (root) => {
if (root !== null) {
traversal(root.left);
traversal(root.right);
res.push(root.val);
}
};
traversal(root);
return res;
};//层序:
const levelOrder = (root) => {
let res = [];
const traversal = (root, depth) => {
if (root !== null) {
if (!res[depth]) {
res[depth] = [];
}
traversal(root.left, depth + 1);
res[depth].push(root.val);
traversal(root.right, depth + 1);
}
};
traversal(root, 0);
return res;
};BFS 使用队列:
const wideSeach = tree => {
let res = [];
let queue = [tree];
while(queue != 0){
let tar = queue.shift()
res.push(tar.val)
if(tar.left){
queue.push(tree.left);
}
if(tar.right){
queue.push(tree.right);
}
}
}DFS:使用栈
const deepSearch = (tree) => {
let list = [];
let stack = tree;
while (stack.length != 0) {
let target = stack.pop();
list.push(target.value);
if (target.childright) {
stack.push(target.childright);
}
if (target.childleft) {
stack.push(target.childleft);
}
}
return list;};
反转链表:
const reverseList = (head) => {
if (!head || !head.next) return head;
let next = head.next;
let reversedHead = reverseList(next);
head.next = null;
next.next = head;
return reversedHead;
};反转链表:
const reverseList = (head) => {
if (!head || !head.next) return head;
let next = head.next;
let reversedHead = reverseList(next);
head.next = null;
next.next = head;
return reversedHead;
};有效字符串:
const isValid = (str) => {
const map = {
'{': '}',
'(': ')',
'[': ']',
};
let stack = [];
if (str.length === 0) return true;
for (let i = 0; i < str.length; i++) {
if (map[str[i]]) {
stack.push(str[i]);
} else if (str[i] !== map[stack.pop()]) {
return false;
}
}
return true;
};用栈实现队列:(232)
var MyQueue = function() {
this.is = [];
this.os = [];
};
MyQueue.prototype.push = function(x) {
this.is.push(x);
};
MyQueue.prototype.pop = function() {
if(!this.os.length){
while(this.is.length){
this.os.push(this.is.pop());
}
}
return this.os.pop();
};
MyQueue.prototype.peek = function() {
if(!this.os.length){
while(this.is.length){
this.os.push(this.is.pop());
}
}
return this.os[this.os.length - 1];
};
MyQueue.prototype.empty = function() {
return !this.is.length && !this.os.length;
};
第K大的元素:(703)
class MinHeap {
constructor(k, nums) {
this.heap = [];
this.k = k;
}
add(num) {
if (this.heap.length < this.k) {
this.heap.push(num);
this.up(this.heap.length - 1);
} else if (num > this.heap[0]) {
this.heap[0] = num;
this.down(0);
}
}
up(i) {
while (i > 0) {
const parent = (i - 1) >> 1;
if (this.heap[parent] > this.heap[i]) {
[this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
i = parent;
} else {
break;
}
}
}
down(i) {
while (2 * i + 1 < this.heap.length) {
let child = 2 * i + 1;
if (child + 1 < this.heap.length && this.heap[child + 1] < this.heap[child]) {
child++;
}
if (this.heap[i] > this.heap[child]) {
[this.heap[child], this.heap[i]] = [this.heap[i], this.heap[child]];
i = child;
} else {
break;
}
}
}
}
var KthLargest = function (k, nums) {
this.heap = new MinHeap(k, nums);
for (let i = 0; i < nums.length; i++) {
this.heap.add(nums[i]);
}
};
KthLargest.prototype.add = function (val) {
this.heap.add(val);
return this.heap.heap[0];
};
有效异位词(哈希表 242)
var isAnagram = function(s, t) {
if(s.length !== t.length) {
return false
}
var hash = Array(26).fill(0)
var codeA = "a".charCodeAt()
let length = s.length
for(let i = 0; i < length; i++) {
hash[s.charCodeAt(i) - codeA]++
hash[t.charCodeAt(i) - codeA]--
}
for(let value of hash) {
if(value !== 0) {
return false
}
}
return true
};
两数之和:(1)
function twoSum(nums, target) {
const map = new Map();
for (let i = 0; i < nums.length; i++) {
const curNum = nums[i];
const targetNum = target - curNum;
const targetNumIndex = map.get(targetNum);
if (targetNumIndex !== undefined) {
return [targetNumIndex, i];
} else {
map.set(curNum, i);
}
}
}三数之和(15)
var threeSum = function(nums) {
// 最左侧值为定值,右侧所有值进行两边推进计算
let res = [];
nums.sort((a, b) => a - b);
let size = nums.length;
if (nums[0] <= 0 && nums[size - 1] >= 0) {
// 保证有正数负数
let i = 0;
while (i < size - 2) {
if (nums[i] > 0) break; // 最左侧大于0,无解
let first = i + 1;
let last = size - 1;
while (first < last) {
if (nums[i] * nums[last] > 0) break; // 三数同符号,无解
let sum = nums[i] + nums[first] + nums[last];
if (sum === 0) {
res.push([nums[i], nums[first], nums[last]]);
}
if (sum <= 0) {
// 负数过小,first右移
while (nums[first] === nums[++first]) {} // 重复值跳过
} else {
while (nums[last] === nums[--last]) {} // 重复值跳过
}
}
while (nums[i] === nums[++i]) {}
}
}
return res;
};
验证二叉搜索树:()
进行中序遍历,遍历后应该有序
var isValidBST = function(root) {
let stack = [];
let inorder = -Infinity;
while (stack.length || root !== null) {
while (root !== null) {
stack.push(root);
root = root.left;
}
root = stack.pop();
// 如果中序遍历得到的节点的值小于等于前一个 inorder,说明不是二叉搜索树
if (root.val <= inorder) {
return false;
}
inorder = root.val;
root = root.right;
}
return true;
};
动态规划基础
学习资源:https://www.bilibili.com/vide...
- 入门:斐波那契数列
存在重叠的子问题(overlap sub-problem)

例题:每个工作所需要的时间和对应的报酬如图所示,问可以产生最大收益的工作组合:
思路:从工作8开始推导,对于工作8有选和不选两个选项。
如果选择工作8,那么下一项能做的工作只有工作5,则选择工作8的收益是4元加工作5的收益OPT(5)。
如果不选工作8,则收益为前7项工作的收益,即OPT(7)。进而得出递归式OPT(i)。

对于每一个OPT,都选出两个选项中的最大值,最终推得148为最佳工作组合。

例题2 从一组数字中,挑选出不相邻且和为最大的一组数字
思路:如图所示,对于每个数字有两个选项,选或不选。从OPT(6)开始分析,如果选择OPT(6),则下一个可选的数字为OPT(4),结果为OPT(4)+arr[6]。如果不选OPT(6),则最优解为OPT(5),进而得出递归方程和递归出口。
import numpy as np
arr = [1,3,5,4,5,8,9]
def rec_opt(arr,i):
if i == 0:
return arr[0]
elif i == 1:
return max(arr[0],arr[1])
else:
A = rec_opt(arr,i-2) + arr[i]
B = rec_opt(arr,i-1)
return max(A,B)
def dp_opt(arr):
opt = np.zeros(len(arr))
opt[0] = arr[0]
opt[1] = max(arr[0],arr[1])
for i in range (2, len(arr)):
A = opt[i-2] + arr[i]
B = opt[i-1]
opt[i] = max(A,B)
return opt[len(arr)-1]爬楼梯(70)
const climbStairs = (n) => {
const dp = new Array(n + 1).fill(0);
dp[0] = 1;
dp[1] = 1;
for (let i = 2; i < dp.length; i++) {
dp[i] = dp[i - 2] + dp[i - 1];
}
return dp[n];
}

评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论