算法学习日志

记录每天学习的算法方便以后的复习!

排序问题

冒泡排序

对于一组数字中每两个相邻的数字,如果前面的比后面的大,则交换这两个数字;
每一趟排序完成后,都会有一个最大的数字排到正确的位置,即尾部。总共需要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:              #如果一趟中没有交换,直接停止
            return

js:

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] = temp

js:

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大。
使用递归完成排序。
image

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 left

js:

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)

堆排序

堆是一种特殊的完全二叉树,分为大根堆和小根堆两种情况。
image
堆的向下调整:当根节点的左右子树都是堆时,可以通过一次向下调整将其变成一个堆。
构造堆 ===> 挨个出数
首先建立堆,然后得到堆顶元素,即为最大元素。
去掉堆顶,将最后一个元素放到堆顶,再通过一次向下调整使堆有序。此时堆顶元素为第二大元素。
重复步骤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;
};

归并排序

image
分治法的应用,首先将待排序的数组逐层拆分成最小的单位,再通过归并的方式分别将两个有序的数组合并。

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)
image

希尔排序
计数排序
桶排序
基数排序

二叉树的遍历问题

递归法遍历前序,中序和后序:

// 树的遍历
// 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...

  1. 入门:斐波那契数列
    存在重叠的子问题(overlap sub-problem)

image

例题:每个工作所需要的时间和对应的报酬如图所示,问可以产生最大收益的工作组合:

image
思路:从工作8开始推导,对于工作8有选和不选两个选项。
如果选择工作8,那么下一项能做的工作只有工作5,则选择工作8的收益是4元加工作5的收益OPT(5)。
如果不选工作8,则收益为前7项工作的收益,即OPT(7)。进而得出递归式OPT(i)。

image

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

image

例题2 从一组数字中,挑选出不相邻且和为最大的一组数字

image

思路:如图所示,对于每个数字有两个选项,选或不选。从OPT(6)开始分析,如果选择OPT(6),则下一个可选的数字为OPT(4),结果为OPT(4)+arr[6]。如果不选OPT(6),则最优解为OPT(5),进而得出递归方程和递归出口。
image

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];
}

评论

暂无评论