言和和和

题目一 12345678910111213141516171819202122232425262728293031package class068;// 不同的子序列// 给你两个字符串s和t ，统计并返回在s的子序列中t出现的个数// 答案对 1000000007 取模// 测试链接 : https://leetcode.cn/problems/distinct-subsequences/public class Code01_DistinctSubsequences { // 已经展示太多次从递归到动态规划了 // 直接写动态规划吧 public static int numDistinct1(String str, String target) { char[] s = str.toCharArray(); char[] t = target.toCharArray(); int n = s.length; int m = t.length; // dp[i][j] : // s[前缀长度为i]的所有子序列中，有多少个子序列等于t[前缀长度为...

递归到二维动态规划 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112题目一package class067;// 最小路径和// 给定一个包含非负整数的 m x n 网格 grid// 请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。// 说明：每次只能向下或者向右移动一步。// 测试链接 : https://leetcode.cn/problems/minimum-path-sum/public class Code01_MinimumPathSum { // 暴力递归 public static int minPathSum1(int[][] grid...

bfs的特点是逐层扩散，从源头点到目标点扩散了几层，最短路就是多少bfs可以使用的特征是 任意两个节点之间的相互距离相同(无向图)bfs开始时，可以是单源也可以是多个源头bfs频繁使用队列，形式可以是单点弹出或者整层弹出bfs进行时，进入队列的节点要标记状态，防止同一个节点重复进出队列bfs进行时，可能会包含剪纸策略的设计bfs难点在于节点如何找到路，路的展开，剪枝设计 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576// 地图分析// 你现在手里有一份大小为 n x n 的 网格 grid// 上面的每个 单元格 都用 0 和 1 标记好了其中 0 代表海洋，1 代表陆地。// 请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的// 并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。// 我们这里说的距离是「曼哈顿...

动态规划：用空间代替重复计算任何动态规划问题都一定对应着一个有重复调用行为的递归所以动态规划的题目都一定可以从递归入手，逐渐实现动态规划的方法。 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100package class066;import java.util.Arrays;// 最低票价// 在一个火车旅行很受欢迎的国度，你提前一年计划了一些火车旅行// 在接下来的一年里，你要旅行的日子将以一个名为 days 的数组给出// 每一项是一个从 1 到 365 的整数// 火车票有 三种不同的销售方式// 一张 为期1天 的通行证售价为 costs[0] 美元// 一张 为期7天 的通行证售价为 costs[1] 美元// 一张 为期30天 的通行证售...

主存储器用来存放数据的叫做存储体里面还有MAR和MDRMAR：存储地址寄存器MDR：存储数据寄存器 存储体，数据在存储体内按地址存储一整个存储体被分成一个一个的存储单元，每个存储单元存储了一串二进制代码。存储字：就是每个存储单元中二进制代码的组合存储字长：存储单元中二进制代码的位数存储元：即存储二进制的电子元件（电容），每个存储元1bit MAR的位数反映了存储单元的个数MDR位数=存储字长 ex：MAR4位 代表总共有2^4个存储单元MDR16位 代表每个存储单元可以存放16bit，1个字（word）=16bit易混淆：1个字节（Byte）=8bit1个字有可能是16bit 也有可能是8bit 也有可能是32bit 或者64bit具体看计算机硬件1B = 1个字节 运算器的基本组成：算数运算（加减乘除）逻辑运算（与或非） ACC：累加器，用于存放操作数或者运算结果MQ：乘商寄存器，在乘，除运算时，用于存放操作数或者运算结果。X：通用的操作数寄存器，用于存放操作数ALU：算数逻辑单元，通过内部复杂的电路实现算数运算，逻辑运算。 控制器的基本...

A*算法源点到目标点

Dijkstra 算法概述Dijkstra 算法的核心思想是一种贪心策略。它从一个起始节点开始，逐步向外扩展，每次都选择离起点最近且未被访问过的节点，并用该节点来更新其所有邻居节点到起点的最短距离。 这个过程可以形象地理解为，从起点向四周铺设一条条路径，每次都优先铺设最短的那条，直到所有可达的节点都被铺设完毕。 算法步骤1.dist[i]表示从源点到i的最短距离，visited[i]表示i节点是否从小根堆弹出过2.准备好小根堆，小根堆存放记录：(x点，x到源点距离)，小根堆根据距离组织3.令dist[源点]=0，(源点，0)进入小根堆4.从小根堆弹出(u,源点到u的距离) a.如果visited[u]==true ,不做任何处理，重复步骤4 b.如果visited[u]==false,令为true，u也算弹出过了 然后考察u的每一条边，假设某边去v，边权w 1)如果visited[v]==false 并且dist[u]+w <dist[v] 令dist[v] = d...

早期冯诺依曼机的结构第一次提出了存储程序的概念:这个东西很重要，是指将指令以二进制的形式事先输入计算机的主存储器，然后按其在主存储器的首地址执行程序的第一条指令，以后就按照程序的规定顺序执行其他指令，直到程序执行结束。我们可以把我们想要计算机执行的一系列指令 一口气的告诉它，程序员就不需要一条一条的进行手工连接了 输入设备：把信息转换成计算器能够识别的形式 先流向运算器存储器：存放数据和程序运算器：进行算术运算和逻辑运算控制器：存储器到控制器有一条数据线，就是控制器从存储器中读取一条指令，解析之后，指挥运算器所以这些数据线和控制线就可以分清了输入-运算器-存储器-输出都是数据线存储-控制又一条 其他的都是控制线 控制器-输入输出运算存储在计算机系统中，软件和硬件在逻辑上是等效的。 冯诺依曼计算机的特点：1.计算机由五大部件组成2.指令和数据以同等地位存于存储器，可按地址寻访3.指令和数据都用二进制表示4.指令由操作码和地址码组成5.存储程序6.以运算器为中心(因为数据的传送必须经过运算器来完成) 现代计算机的结构以存储器为中心 运算器和控制器通常是集成到一个芯片上的 即cp...

最小生成树:在 无向带权图 中选择一些边，在保证连通性的情况下，边的总权值最小最小生成树可能不只一棵，只要保证边的总权值最小，就是正确的最小生成树。如果无向带权图有n个点，那么最小生成树一定有n-1条边 Kruskal算法(最常用)1 把所有的边，根据权值从小到大排序，从权值小的边开始考虑2 如果连接当前的边不会形成环，就选择3 如果连接当前的边会形成环，就不选4 考察完所有的边，就得到最小生成树 用并查集来判断会不会形成环 P3366 【模板】最小生成树题目描述如题，给出一个无向图，求出最小生成树，如果该图不连通，则输出 orz。 输入格式第一行包含两个整数 $N,M$，表示该图共有 $N$ 个结点和 $M$ 条无向边。 接下来 $M$ 行每行包含三个整数 $X_i,Y_i,Z_i$，表示有一条长度为 $Z_i$ 的无向边连接结点 $X_i,Y_i$。 输出格式如果该图连通，则输出一个整数表示最小生成树的各边的长度之和。如果该图不连通则输出 orz。 输入输出样例 #1输入 #11234564 51 2 21 3 21 4 32 3 43 4 3 输出 #117 说明&#x...

1.一开始元素拥有自己的集合，在自己的集合里只有这个元素自己2.find(i):查找i所在集合的代表元素，代表元素来代表i所在的集合3.boolean isSameSet(a,b):判断a,b在不在一个集合里4.void union(a,b):a所在集合所有元素和b所在集合所有元素 合并成一个集合5.各种操作单次调用的均摊时间复杂度O(1) find一直往上找 一直找到不能再往上的优化一 union小的去挂大的优化二 扁平化(路径压缩)比如说 2-3 3-4 4-5find(2)的时候 在找父节点的过程中 我们把沿途的都给直接挂到5那越调用速度越快，挺好 father 和 size的改变只有代表节点的size信息有用 也就是最上方的节点对吧father指向父节点 import java.io.*; public class Main { // n 和 m 为题目给定的总数和操作数 static int n, m; // father[i] 存储 i 的父节点 static int[] father; // size[i] 存...