Loading...
墨滴

YoungMan

2021/06/01  阅读:63  主题:全栈蓝

算法

ch1

递归分析

直接给出结论
直接给出结论

三柱汉诺塔

先把A柱的n-1移到B柱
先把A柱的n-1移到B柱
A柱剩下的一个移到C柱
A柱剩下的一个移到C柱
B柱移回A柱,递归
B柱移回A柱,递归
 public void hanota(List<Integer> A, List<Integer> B, List<Integer> C) {
                //汉诺塔是典型的递归问题
                if(A.size()==0){
                    return;//递归终点
                }

                while(A.size()!=1){
                    B.add(A.remove(A.size()-1));
                }//对应上图图1
                C.add(A.remove(0));//对应上图2
                while(B.size()!=0){
                    A.add(B.remove(B.size()-1));
                }
                hanota(A,B,C);//对应上图3
    }//复杂度:2^n-1

四柱汉诺塔

四柱很简单,利用三柱计算
四柱很简单,利用三柱计算

利用 for 循环挑出一个 K 值使得结果最优即可。

//非存储化写法
public int hanota4 (int n)
    
{
        int tmp =0, res = Integer.MAX_VALUE;
        if (1 == n) return 1;//终止条件
        for (int i = 1; i < n; i++){
            tmp = 2*hanota4(n - i) + (1 << i) - 1;//相当于三柱汉诺塔的复杂度2^n-1
            if (tmp < res) res = tmp;
        }
        return res;
    }
public int  hanota4_mem (int n)
    
{
        int tmp =0, m = Integer.MAX_VALUE;
        int[] mem = new int[n];//用备忘录记录中间结果
        men[0] = 1;//初始条件
        for (int i = 1; i < n; i++)
        {
            for (int j = 1; j < i + 1; j++)
            {
                tmp = 2*mem[i - j] + (1 << j) - 1;
                if (tmp < m)
                    m = tmp;
            }
            mem[i] = m;
            m = Integer.MAX_VALUE;
        }
        return mem[n - 1];
    }
四柱汉诺塔的结论
四柱汉诺塔的结论

扔鸡蛋

扔鸡蛋问题很难!是谷歌经典面试题

动态规划需要明确 base case -> 明确「状态」-> 明确「选择」 -> 定义 dp 数组/函数的含义。

这里只介绍最简单的方法 状态转移方程

K 个鸡蛋,N 层楼,max 是最坏情况,min 是最少次树,也就是算最坏情况下的最好次数。

状态:层数和鸡蛋数。

选择:碎或者没碎

# 当前状态为 K 个鸡蛋,面对 N 层楼
# 返回这个状态下的最优结果
def dp(K, N):
    for 1 <= i <= N:
        # 最坏情况下的最少扔鸡蛋次数
        res = min(res,
                  max(
                        dp(K - 1, i - 1), # 碎
                        dp(K, N - i)      # 没碎
                     ) + 1 # 在第 i 楼扔了一次
                 )
    return res

最长上升子序列

经典动态规划,不解释

public int lengthOfLIS(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    for (int i = 0; i < n; i++) {
        int max = 1;
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                max = Math.max(max, dp[j] + 1);
            }
        }
        dp[i] = max;
    }
    return Arrays.stream(dp).max().orElse(0);
}

0-1 背包

状态转移方程
状态转移方程
空间优化的状态转移方程
空间优化的状态转移方程

贪婪策略

作业调度:选择完成时间最早的

最佳股票交易:只要涨了就买

ch2

卡特兰数

计数问题
计数问题
圆与弦问题
圆与弦问题
中序遍历个数
中序遍历个数
出栈问题
出栈问题

Dijkstra

关于DIjkstra的算法详解
关于DIjkstra的算法详解

Kruskal 算法

Kruskal算法
Kruskal算法

P 和 NP

N和NP
N和NP

ch3

网络流-Ford-Fulkerson 算法

FF算法
FF算法

排队

下面代码写的很简单

 /**
     * 解题思路:先排序再插入
     * 1.排序规则:按照先H高度降序,K个数升序排序
     * 2.遍历排序后的数组,根据K插入到K的位置上
     *
     * 核心思想:高个子先站好位,矮个子插入到K位置上,前面肯定有K个高个子,矮个子再插到前面也满足K的要求
     *
     */

    public int[][] reconstructQueue(int[][] people) {
        // [7,0], [7,1], [6,1], [5,0], [5,2], [4,4]
        // 再一个一个插入。
        // [7,0]
        // [7,0], [7,1]
        // [7,0], [6,1], [7,1]
        // [5,0], [7,0], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [7,1]
        // [5,0], [7,0], [5,2], [6,1], [4,4], [7,1]
        Arrays.sort(people, (o1, o2) -> o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]);

        LinkedList<int[]> list = new LinkedList<>();
        for (int[] i : people) {
            list.add(i[1], i);
        }

        return list.toArray(new int[list.size()][2]);
    }
————————————————
版权声明:本文为CSDN博主「manDD_HH」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:https://blog.csdn.net/manDD_HH/article/details/109728341

二部图

用最大流解决二部图匹配
用最大流解决二部图匹配

二部图匹配[1]

调度问题

调度问题
调度问题

线性规划

最大流问题可以转化为线性规划问题(具体如何转化?没看懂)

ch4

随机化算法的特点

对随机化算法的介绍
对随机化算法的介绍

Karger 算法

Karger
Karger

洗牌算法

洗牌算法介绍

Nginx 负载均衡算法

遗传算法

10 分钟搞定遗传算法

模拟退火算法

模拟退火算法

ch5

流算法

流算法适用于一些极端情况下,例如没有足够空间或时间来处理数据

存储空间:Θ(1)或O(log(n)), 更新时间:Θ(1)或O(log(n))

求中位数

同时构建最大堆和最小堆,分别用来保存较小的数,和较大的数,再根据堆的大小决定中位值

租雪橇

租还是买?这一问题也称为雪橇租借问题,人们需要决定租雪橇还是买雪橇

加权多数算法

加权多数算法维护一个权重集合,给每个专家分 配一个权重

用这些权重对专家的预测进行加权投票,得出某 一天的预测结果

在一天结束后,算法对在这一天犯了错误的专家减少权重

怎么做:令wi,t表示第t天专家i的权重,令li,t表示专家i在第t天的“损失”;如果专家出错,li,t为1,否则为0

FFT(快速傅里叶)

TODO

Reference

[1]

关于二部图匹配的一些知识: https://zhuanlan.zhihu.com/p/89972891

YoungMan

2021/06/01  阅读:63  主题:全栈蓝

作者介绍

YoungMan