算法学习记录

MiChong

发布于 2020-11-17 10:50:44

3940

发布于 2020-11-17 10:50:44

一、介绍

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

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2020-11-04，如有侵权请联系 cloudcommunity@tencent.com 删除

java