专栏首页米虫的家算法学习记录

算法学习记录

一、介绍

1、常见的数据结构

「队列」「栈」这两种数据结构既可以使⽤链表也可以使⽤数组实现。⽤数组实现,就要处理扩容缩容的问题;⽤链表实现,没有这个问题,但需要更多的内存空间存储节点指针。 「图」的两种表⽰⽅法,邻接表就是链表,邻接矩阵就是⼆维数组。邻接矩阵判断连通性迅速,并可以进⾏矩阵运算解决⼀些问题,但是如果图⽐较稀疏的话很耗费空间。邻接表⽐较节省空间,但是很多操作的效率上肯定⽐不过邻接矩阵。 「散列表」就是通过散列函数把键映射到⼀个⼤数组⾥。⽽且对于解决散列冲突的⽅法,拉链法需要链表特性,操作简单,但需要额外的空间存储指针;线性探查法就需要数组特性,以便连续寻址,不需要指针的存储空间,但操作稍微复杂些。 「树」,⽤数组实现就是「堆」,因为「堆」是⼀个完全⼆叉树,⽤数组存储不需要节点指针,操作也⽐较简单;⽤链表实现就是很常⻅的那种「树」,因为不⼀定是完全⼆叉树,所以不适合⽤数组存储。为此,在这种链表「树」结构之上,⼜衍⽣出各种巧妙的设计,⽐如⼆叉搜索树、AVL树、红⿊树、区间树、B 树等等,以应对不同的问题。

2、常见的算法框架

数组遍历框架,典型的线性迭代结构:

java

 void traverse(int[] arr) {
     for (int i = 0; i < arr.length; i++) {
// 迭代访问 arr[i]
      }
 }

链表遍历框架,兼具迭代和递归结构:

java

/* 基本的单链表节点 */
class ListNode {
    int val;
    ListNode next;
}

void traverse(ListNode head) {
     for (ListNode p = head; p != null; p = p.next) {
		// 迭代访问 p.val
     }
 }

void traverse(ListNode head) {
	// 递归访问 head.val
     traverse(head.next)
 }

⼆叉树遍历框架,典型的⾮线性递归遍历结构:

java

/* 基本的⼆叉树节点 */
class TreeNode {
    int val;
    TreeNode left, right;
}

 void traverse(TreeNode root) {
        traverse(root.left)
        traverse(root.right)
 }

二、动态规划

1、斐波那契数列的算法优化

java

// 斐波那契数列(备忘录)
private static int fib3(int N) {
    if (N < 0) return 0;
    int[] meno = new int[N + 1];
    return helper(meno, N);
}

private static int helper(int[] meno, int n) {

    if (n == 1 || n == 2) return 1;
    if (meno[n] != 0) return meno[n];

    meno[n] = helper(meno, n - 1) + helper(meno, n - 2);
    return meno[n];
}


// 斐波那契数列(dp表)
private static int fib(int N) {

    int[] dp = new int[N + 1];
    dp[1] = dp[2] = 1;

    for (int i = 3; i <= N; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[N];
}

//斐波那契数列(空间复杂度降为1)
private static int fib2(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    int prev = 1, curr = 1;
    for (int i = 3; i <= n; i++) {

        int sum = prev + curr;
        prev = curr;
        curr = sum;
    }
    return curr;
}

三、回溯算法

纯暴力穷举算法,复杂度很高

回溯算法的框架:

java

result = []
def backtrack(路径, 选择列表):
if 满⾜结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择

1、全排列算法

java

/**
 *
 * 全排列代码
 * @author MiChong
 * @date 2020-11-04 08:35
 */
public class QuanPaiLie {
    //路径集合
    private static List<List<Integer>> res = new LinkedList<>();

    public static void main(String[] args) {
        // 结果:[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]
        int[] nums = {1, 2, 3};
        List<List<Integer>> res = permute(nums);
        System.out.println(res.toString());
    }
    private static List<List<Integer>> permute(int[] nums) {
        LinkedList<Integer> track = new LinkedList<>();
        backtrack(nums, track);
        return res;
    }

    /**
     *  路径:记录在 track 中
     *  选择列表:nums 中不存在于 track 的那些元素
     *  结束条件:nums 中的元素全都在 track 中出现
     * 
     * @param nums 需要排列的数组
     * @param track 存放的路径
     */
    private static void backtrack(int[] nums, LinkedList<Integer> track) {

        // 到底了,跳出此方法
        if (track.size() == nums.length) {
            res.add(new LinkedList(track));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            // 排除不合法的选择
            if (track.contains(nums[i]))
                continue;

            //做选择
            track.add(nums[i]);

            // 进入下一层决策树
            backtrack(nums, track);

            // 取消选择
            track.removeLast();
        }
    }
}

四、BFS算法

图的搜索算法分为BDF(广度优先搜索)和(深度优先搜索)

BFS框架

java

// 计算从起点 start 到终点 target 的最近距离
int BFS(Node start, Node target) {
    Queue<Node> q; // 核⼼数据结构
    Set<Node> visited; // 避免⾛回头路
    q.offer(start); // 将起点加⼊队列
    visited.add(start);
    int step = 0; // 记录扩散的步数
    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点:这⾥判断是否到达终点 */
            if (cur is target)
            return step;
            /* 将 cur 的相邻节点加⼊队列 */
            for (Node x : cur.adj())
                if (x not in visited) {
                q.offer(x);
                visited.add(x);
            }
        }
        /* 划重点:更新步数在这⾥ */
        step++;
    }
}

二叉树的最小深度

题目地址:https://leetcode-cn.com/problems/minimum-depth-of-binary-tree/

java

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() { }
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public int minDepth(TreeNode root) {

    if (root == null) return 0;
    Queue<TreeNode> q = new LinkedList<>();
    q.offer(root);

    int depth = 1;

    while (!q.isEmpty()) {
        int sz = q.size();

        for (int i = 0; i < sz; i++) {
            TreeNode cur = q.poll();

            if (cur.left == null && cur.right == null) return depth;
            if (cur.left != null) q.offer(cur.left);
            if (cur.right != null) q.offer(cur.right);
        }
        depth++;
    }
    return depth;
}

DFS的时间复杂度比BFS高,但是DFS的空间复杂度比BFS低。 DFS在最坏的情况下空间复杂度为O(logN),而BFS最坏情况下的空间复杂度为O(N)。

五、二分搜索

零、⼆分查找框架

java

int binarySearch(int[] nums, int target) {
        int left = 0, right = ...;
        while (...){
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
			...
            } else if (nums[mid] < target) {
                left = ...
            } else if (nums[mid] > target) {
                right = ...
            }
        }
        return ...;
}

二分查找

题目地址: https://leetcode-cn.com/problems/binary-search/

java

public static int binarySearch(int[] nums, int target) {
    int left = 0;
    int right = nums.length - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) return mid;

        else if (nums[mid] < target) left = mid + 1;

        else if (nums[mid] > target) right = mid - 1;

    }

    return -1;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • JVM学习记录-垃圾回收算法

    纪莫
  • Markdown语法学习记录

    鉴于每次写博客,写文章的时候,总是要重复去查询Markdown的相关语法,这种闹心的感觉我再也不要了。

    格子Lin
  • 算法学习笔记

    这是一个算法题目合集,题目是我从网络和书籍之中整理而来,部分题目已经做了思路整理。问题分类包括:

    芋道源码
  • 算法学习笔记(二):贪心算法

    free赖权华
  • 算法学习笔记-二分法

    leetcode875爱吃香蕉的珂珂https://leetcode-cn.com/problems/koko-eating-bananas/

    买唯送忧
  • Berlekamp-Massey算法学习笔记

    很久之前就听说过这个算法,当时六校联考的时候Day1T1是一道很有意思的递推,神仙zzx不会做于是就拿BM算法艹出了递推式Orzzzzzzzzzzx

    attack
  • 算法学习笔记-回溯

    买唯送忧
  • 算法笔记学习-链表

    灵活使用递归。构造递归条件,使用递归可以巧妙的解题。不过需要注意有些题目不能使用递归,因为递归深度太深会导致超时和栈溢出。

    买唯送忧
  • 算法学习笔记-栈(stack)

    这题跟上面的题目是一模一样的,最少添加就是有多少括号没有对象,,没有对象的括号都会留在栈中,有的都会出栈,所以就是求栈的大小;

    买唯送忧
  • 算法学习笔记-无题

    买唯送忧
  • kubernetes学习记录(0)——学习记录阅读顺序

    目前很多内容都是基于无安全认证的集群,会尝试在安全认证后的集群进行操作,成功后会更新博客。已实现 1.阅读Centos7.2学习记录(1)——静态IP配置 使用...

    胡了了
  • 【译】算法的记录

    为了找到目标元素,每次可以通过减少搜索区域的一半来查找。二分查找算法是针对有序的数组进行,否则毫无意义。

    嘉明
  • 【译】算法的记录

    为了找到目标元素,每次可以通过减少搜索区域的一半来查找。二分查找算法是针对有序的数组进行,否则毫无意义。

    嘉明
  • Docker学习记录

    刺_猬
  • Oracle学习记录

           oracle学习过程中记录的一些知识点,包括sqlplus一些命令、角色、DML、DCL、DDL、数据字典、表空间、函数。 1. sys 超级管...

    高爽
  • Git 学习记录

    版本控制系统有两类:集中式与分布式。 分布式版本系统的代表是 Git,而集中式版本系统的代表是 SVN(Subversion)。

    caoqi95
  • Spark2.0学习记录

    小勇DW3
  • git学习记录

    注释:用-r参数删除目录, git rm --cached a.txt 删除的是本地仓库中的文件,且本地工作区的文件会保留且不再与远程仓库发生跟踪关系,如果本地...

    K同学啊
  • GN学习记录

    近期准备学习WebRTC源码,发现WebRTC构建使用的是GN,花了些时间进行学习,这里做下笔记。

    tyrionchen

扫码关注云+社区

领取腾讯云代金券