Ricky的个人博客

/**
 * 给定一个包含非负整数的 m x n 网格 grid ，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
 *
 * 说明：每次只能向下或者向右移动一步。
 *
 * 输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
 * 输出：7
 * 解释：因为路径 1→3→1→1→1 的总和最小。
 *
 * 提示：
 *
 *     m == grid.length
 *     n == grid[i].length
 *     1 <= m, n <= 200
 *     0 <= grid[i][j] <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-path-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class MinPathSum {
    static int minPathSum(int[][] grid) {
        if (grid == null || grid.length == 0 || grid[0].length == 0) return 0;
        int n = grid.length ;
        int m = grid[0].length;
        // 动态规划
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i == 0 && j== 0) continue;
                if (i == 0) {
                    grid[0][j] += grid[0][j-1];
                    continue;
                }
                if (j == 0) {
                    grid[i][0] += grid[i-1][0];
                    continue;
                }
                if (grid[i-1][j] > grid[i][j-1]) {
                    grid[i][j] += grid[i][j-1];
                } else {
                    grid[i][j] += grid[i-1][j];
                }
            }
        }
        return grid[n-1][m-1];
    }

    public static void main(String[] args) {
        System.out.println(minPathSum(new int[][]{}));
    }
}

阅读全文 »

读书笔记-算法-第五章

发表于 2022-04-11 更新于 2024-04-08 分类于读书笔记 Disqus：

第五章字符串

Java字符串
- String是由一系列字符组成的。字符的类型是char，可能有个值。
- 不可变性。String对象是不可变的，因此可以将它们用于赋值语句、作为函数的参数或是返回值，而不用担心它们的值会发生变化
- 索引。我们最常完成的操作就是从某个字符串中提取一个特定的字符，即Java的String类的charAt()方法。我们希望charAt()方法能够在常数时间内完成，就好像字符串是保存在一个char[]数组中一样
- 长度。在Java中，String类型的length()方法实现了获取字符串的长度的操作。同样，我们也希望length()方法能够在常数时间内完成
- 子字符串。Java的substring()方法实现了提取特定的子字符串的操作。同样，我们也希望这个方法能够在常数时间内完成，Java的标准实现也做到了这一点
- 字符串的连接。在Java中通过将一个字符串追加到另一个字符串的末尾创建一个新字符串的操作是一个内置的操作（使用“+”运算符），所需的时间与结果字符串的长度成正比
  - 我们会避免将字符一个一个地追加到字符串中，因为在Java里这个过程所需的时间将会是平方级别的

阅读全文 »

读书笔记-算法-第四章

发表于 2022-04-07 更新于 2024-04-08 分类于读书笔记 Disqus：

第四章图

无向图
- 定义
  - 图是由一组顶点和一组能够将两个顶点相连的边组成的
  - 边（edge）仅仅是两个顶点（vertex）之间的连接
  - 一般使用0至V-1来表示一张含有V个顶点的图中的各个顶点
  - 我们用v-w的记法来表示连接v和w的边，w-v是这条边的另一种表示方法
- 特殊的图
  - 自环，即一条连接一个顶点和其自身的边
  - 连接同一对顶点的两条边称为平行边

阅读全文 »

读书笔记-算法-第三章

发表于 2022-04-01 更新于 2023-03-16 分类于读书笔记 Disqus：

第三章查找

符号表
- 符号表最主要的目的就是将一个键和一个值联系起来
- 能够将一个键值对插入符号表并希望在之后能够从符号表的所有键值对中按照键直接找到相对应的值
- 设计原则
  - 每个键只对应着一个值（表中不允许存在重复的键）
  - 当用例代码向表中存入的键值对和表中已有的键（及关联的值）冲突时，新的值会替代旧的值
  - 键不能为空
  - 不允许有空值
  - 删除操作
    - 延时删除
      - put(key,null)是delete(key)的一种简单的（延时型）实现
    - 即时删除
  - 基础API
  - 有序的符号表API
    - 通过实现comparabel接口带来接口的有序性
  - 最大键和最小键
    - 区别在于优先队列中可以存在重复的键但符号表中不行，而且有序符号表支持的操作更多
  - 向下取整和向上取整
    - 向下取整（floor）操作（找出小于等于该键的最大键）
    - 向上取整（ceiling）操作（找出大于等于该键的最小键）
  - 排名和选择
  - 范围查找
  - 例外情况
    - 当一个方法需要返回一个键但表中却没有合适的键可以返回时，我们约定抛出一个异常（另一种合理的方法是在这种情况下返回空）
- 成本模型
  - 统计比较的次数（等价性测试或是键的相互比较）
  - 在内循环不进行比较（极少）的情况下，我们会统计数组的访问次数
无序链表的顺序查找
- 符号表中使用的数据结构的一个简单选择是链表，每个结点存储一个键值对
  - 每次查找遍历链表，使用equals方法进行比较
  - 插入也是遍历链表，如果匹配，则进行更新，没有匹配的就插入
- 我们使用命中表示一次成功的查找，未命中表示一次失败的查找
- 注意其中的node构建方法，以及get和put方法
- 性能分析
  - 在含有N对键值的基于（无序）链表的符号表中，未命中的查找和插入操作都需要N次比较。命中的查找在最坏情况下需要N次比较。特别地，向一个空表中插入N个不同的键需要~(N^2)/2次比较
    - 查找一个已经存在的键并不需要线性级别的时间。一种度量方法是查找表中的每个键，并将总时间除以N。
    - 在查找表中的每个键的可能性都相同的情况下时，这个结果就是一次查找平均所需的比较数。我们将它称为随机命中

阅读全文 »

读书笔记-算法-第二章

发表于 2022-03-29 更新于 2023-03-16 分类于读书笔记 Disqus：

第二章排序

初级排序算法
- 排序就是将数组的主键按照某种方式排序
- 排序成本模型：我们需要计算比较和交换的数量。对于不交换元素的算法，我们会计算访问数组的次数
- java的compareTo方法必须实现一个全序关系：
  - 自反性：对于所有的v，v=v
  - 反对称性：对于所有的v<w都有w>v，且v=w时w=v
  - 传递性：对于所有的v，w和x，如果v<=w且w<=x，则v<=x
选择排序
- 基本步骤
  - 找到数组中最小的那个元素
  - 将它和数组的第一个元素交换位置
  - 在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置，如此反复
- 分析效率
  - 对于长度为N的数组，选择排序需要大约N^2/2次比较和N次交换
  - 为了找出最小的元素而扫描一遍数组并不能为下一遍扫描提供什么信息
  - 可以看到，对于长度为N的数组，交换次数固定为N次，是所有数组中，交换步数最少的
  - 简单，但效率颇低
插入排序
- 基本步骤
  - 从索引1开始，对比索引1的数字和索引0的数字，如果索引0数字比索引1数字大，则两个数字交换位置
  - 索引移到2，对比索引2和索引1所在数字，同样的，如果索引1比索引2数字大，则交换位置
  - 接下来对比索引1和索引0，以此类推
- 分析效率
  - 对于随机排列的长度为N且主键不重复的数组，平均情况下插入排序需要(N^2)/4次比较以及(N^2)/4次交换。最坏情况下需要(N^2)/2次比较和(N^2)/2次交换，最好情况下需要N-1次比较和0次交换。
  - 插入排序对于实际应用中常见的某些类型的非随机数组很有效
    - 数组中每个元素距离它的最终位置都不远
    - 一个有序的大数组接一个小数组
    - 数组中只有几个元素的位置不正确
    - 当倒置的数量很少时，插入排序很可能比本章中的其他任何算法都要快
排序算法可视化
阅读全文 »

读书笔记-人类简史

发表于 2022-03-24 更新于 2023-03-16 分类于读书笔记 Disqus：

认知革命

人类：一种没什么特别的动物

在历史的路上，有三大重要革命：
- 大约7万年前，“认知革命”（CognitiveRevolution）让历史正式启动
- 大约12000年前，“农业革命”（AgriculturalRevolution）让历史加速发展
- 而到了大约不过是500年前，“科学革命”（ScientificRevolution）可以说是让历史画下句点而另创新局
从同一个祖先演化而来的不同物种，会属于同一个“属”（genus）
- 生物学家用拉丁文为生物命名，每个名字由两个词组成，第一个词是属名，第二个词则是种名
- 例如狮子就称为“Pantheraleo”，指的是豹属（Panthera）的狮种（leo）
许多属还能再归类为同一科（family）
最早的人类是从大约250万年前的东非开始演化，祖先是一种更早的猿属“Australopithecus”（南方古猿）
- 在欧洲和西亚的人类成了“Homoneanderthalensis”，意为“来自尼安德谷（NeanderValley）的人”，一般简称为“尼安德特人”（Neanderthals）
- 在东方的亚洲，住的则是“Homoerectus”（直立人），一共存续了将近200万年，是目前所知存续最久的人类物种
- 在印度尼西亚的爪哇岛，则住着“Homosoloensis”（梭罗人，拉丁文意为“来自梭罗谷的人”）
- 人类的摇篮继续养育着许多新品种，例如“Homorudolfensis”（鲁道夫人，“来自鲁道夫湖的人”）、“Homoergaster”（匠人，“工作的人”）
- 而我们也颇为厚颜地把自己命名为“Homosapiens”（智人，“明智的人”）
人类不是线性发展的，在某一个时期同时存在多种人中，智人也是其中之一
- 大脑容量大
  - 大脑结构脆弱，不利于活动
  - 能耗很大，只占重量2%，却要消耗25%的能量
  - 令人困惑的是，在接近200万年的时间里，大脑并没有带来显著的优势，却一直偏执的在这条路上进化
- 直立行走
  - 手解放出来做更精细的事
  - 促进了神经系统的进化
  - 导致背痛，颈脖部位的酸痛
- 人类都是早产儿
  - 促使人类成为强社交生物，因为需要群体帮助照顾幼儿
- 用火
  - 一些本无法消化的食物变为主食（如小麦，水稻，马铃薯等）
  - 食物中的病菌和寄生虫被杀死
  - 咀嚼和消化时间大幅缩减
  - 缩小牙齿、减少肠的长度
    - 一种说法认为，这减少了消化时所需的能量，从而使得大脑得到发育的空间
长久以来，智人一直只是稳定位于食物链的中间位置，直到最近才有改变
- 在先前长达数百万年的时间里，人类会猎杀小动物、采集种种能得到的食物，但同时也会遭到较大型肉食动物猎杀
- 一直要到40万年前，有几种人种才开始固定追捕大型猎物，而要到10万年前智人崛起，人类才一跃而居于食物链顶端
- 人类转眼就登上顶端，不仅让生态系统猝不及防，就连人类自己也不知所措
智人如何成为唯一存活的人种
- 混种繁衍理论，即智人是和其他人种互通繁衍，从而融合为同一人种
- 替代理论，即除了智人之外的其他人种灭绝了
  - 这种理论更加政治正确，毕竟世界上的人都有同样的祖先比较不会引起种族方面的讨论
  - 然而目前，已经找到证据证明各个地区的人身上携带者不同远古人种的DNA
- 智人胜出的根本原因很可能是因为有独特的语言

阅读全文 »

读书笔记-算法-第一章

发表于 2022-03-24 更新于 2023-03-16 分类于读书笔记 Disqus：

配套网站：https://algs4.cs.princeton.edu/home/

第一章基础

无论在任何应用领域，精心设计的算法都是解决大型问题最有效的方法
我们把描述和实现算法所用到的语言特性、软件库和操作系统特性总称为基础编程模型
java程序的基本语法，同时也是多数程序语言的通用语法
- 原始数据类型：它们在计算机程序中精确地定义整数、浮点数和布尔值等。它们的定义包括取值范围和能够对相应的值进行的操作，它们能够被组合为类似于数学公式定义的表达式。
  - int 32位整数(2^31=2147483648)
    - 在java中int可表示的范围为（-2147483648——2147483647），2147483648会溢出变为-2147483648，因此Math.abs(-2147483648)=-214783648
  - double 64位双精度实数
  - 布尔型 true or false
  - string 字符串
  - long 64位整数
  - short 16位整数(2^15=32768)
  - char 16位字符
  - byte 8位整数(2^7=128)
  - float 32位单精度实数
- 语句：语句通过创建变量并对其赋值、控制运行流程或者引发副作用来进行计算。我们会使用六种语句：声明、赋值、条件、循环、调用和返回
  - java是一种强类型语言，编译器会检查类型一致性
- 数组：数组是多个同种数据类型的值的集合
- 静态方法：静态方法可以封装并重用代码，使我们可以用独立的模块开发程序
- 字符串：字符串是一连串的字符，Java内置了对它们的一些操作
- 标准输入/输出：标准输入输出是程序与外界联系的桥梁
- 数据抽象：数据抽象封装和重用代码，使我们可以定义非原始数据类型，进而支持面向对象编程
不同程序语言的运算符计算优先级会有不同，因此通常情况下用括号来进行优先级的改变
方法的性质
- 方法的参数按值传递
  - 调用方法时传递对象名也是值传递，意味着传递的是对象的别名，也就是对象的引用地址，所以在方法内修改其内容也会影响原始值
- 方法名可以重载
- 方法只能返回一个值，但是可以包含多个返回语句
- 方法可以产生副作用：在本书中，返回值是void的方法就是副作用
递归原则
- 递归总是在第一行就要包含一个包含return的条件语句
- 递归总是尝试先解决一个更小的问题
- 递归的父问题和子问题之间不应该有交集
API的目的是将调用和实现分离
重定向和管道输入
Java表达式1/0和1.0/0.0的值是什么
- 第一个表达式会产生一个运行时除以零异常（它会终止程序，因为这个值是未定义的）；第二个表达式的值是Infinity（无穷大）。
为什么数组的起始索引是0而不是1
- 这个习惯来源于机器语言，那时要计算一个数组元素的地址需要将数组的起始地址加上该元素的索引。将起始索引设为1要么会浪费数组的第一个元素的空间，要么会花费额外的时间来将索引减1
每次使用new来创建一个对象时，系统都会
- 为新的对象分配内存空间
- 调用构造函数初始化对象中的值
- 返回该对象的一个引用
为什么要区别原始数据类型和引用类型？为什么不只用引用类型
- 因为性能。Java提供了Integer、Double等和原始数据类型对应的引用类型，以供希望忽略这些类型的区别的程序员使用。原始数据类型更接近计算机硬件所支持的数据类型，因此使用它们的程序比使用引用类型的程序运行得更快
指针是什么？
- 和Java的引用一样，可以把指针看做机器地址。在许多编程语言中，指针是一种原始数据类型，程序员可以用各种方法操作它。
- 但众所周知，指针的编程非常容易出错，因此需要精心设计指针类的操作以帮助程序员避免错误。Java将这种观点发挥到了极致（许多主流编程语言的设计者也赞同这种做法）。
- 在Java中，创建引用的方法只有一种（new），且改变引用的方法也只有一种（赋值语句）。也就是说，程序员能对引用进行的操作只有创建和复制。
- 在编程语言的行话里，Java的引用被称为安全指针，因为Java能够保证每个引用都会指向某种类型的对象（而且它能找出无用的对象并将其回收）。
栈用于带括号的运算符计算

阅读全文 »

读书笔记-数据结构和算法图解

发表于 2022-03-21 更新于 2023-03-16 分类于读书笔记 Disqus：

第一章数据结构为何重要

操作的速度，并不按时间计算，而是按步数计算。理解这个观点，因为不同机器其实运行速度都会有差异，真正决定效率的是一个操作的步数。
读取是一步到位，意味着是读取数组的索引
- 计算机的内存可以看成一堆格子，内存的格子是地址连续的
- 声明数组时，是在内存中划分出一些连续的格子
- 查找任意索引，最多都是只需要1步
查找意味着从数组中寻找是否存在某个值
- 计算机需要从索引0开始寻找，即线性查找
- 查找任意内容，最多步骤为数组的索引长度N
计算机知道数组的索引开始位置和结束位置
- 插入末尾只需要一步，直接在末尾插入即可
- 开头或中间的位置，需要先移动其他元素的位置，再进行插入
- 最复杂的插入，是在数组开头插入，意味着需要将N个元素都右移，再将元素插入，即N+1步
删除任意元素都需要将右边的元素左移，以保持数组的连续性和完整性
最复杂的删除是删除开头元素，删除为1步，之后将N-1个元素左移，最终为N步
集合是一种不允许元素重复的数据结构
- 读取，查找，删除和数组的效率是一致的
- 插入的效率和数组不同
  - 需要先确定这个元素在不在集合内，因此需要先查找一遍，如前文所诉，最多需要N步
  - 确定要插入的元素不在集合内后，进行插入，和数组一样，最多需要N+1步
  - 因此集合的插入最终的复杂度为2N+1步

阅读全文 »

复习关键字

框架了解

算法

最小路径和

第五章 字符串

第四章 图

第三章 查找

第二章 排序

认知革命

人类：一种没什么特别的动物

第一章 基础

第一章 数据结构为何重要

第五章字符串

第四章图

第三章查找

第二章排序

第一章基础

第一章数据结构为何重要