算法红皮书第四版 读书笔记 （一） 基础 学会算法式思考

小灰灰 2023-07-13 03:51 58阅读 0赞

算法也是一种自然语言的另外一种表述

  1. public static int gcd(int p, int q) {
  3.     if (q == 0) { return p;}
  5.     int r = p % q;
  7.     return gcd(q, r);
  9. }

计算两个非负整数 p 和 q的最大公约数： 若 q 是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数 — 欧几里德算法

大多数算法都需要适当地 组织数据 ，而为了组织数据就产生了 数据结构，数据结构也是计算机科学研究的核心对象

我们的观点是数据结构是算法的副产品或是结果，因此要理解算法必须学习数据结构。

BinarySearch 二分法查找：

数组必须是有序的，被查找的键要么不存在，要么必然存在于a[lo..hi]之中

  1. public static int rank(int key, int[] a) {
  2.         int lo = 0;
  3.         int hi = a.length - 1;
  4.         while (lo <= hi) {
  5.             int mid = lo + (hi - lo) / 2;
  6.             if (key < a[mid]) {
  7.                 lo = mid - 1;
  8.             } else if (key > a[mid]) {
  9.                 lo = mid + 1;
  10.             } else {
  11.                 return mid;
  12.             }
  13.         }
  14.         return -1;
  15.     }

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70

今天看了一个面试题问int的范围：

- 2的 31次幂 至 +2的 31次幂 - 1 之间的整数（ 32 位，二进制补码）

20200310223608563.png

Java 的 整型能够表示 2的32次幂 个不同的值，用一个 32 位二进制即可表示（ 虽然现在的许多计算机有 64 位二进制，但整型仍然是 32 位 ）。与此相似，浮点型的标准规定为 64 位。

Java 还提供了其他五种原始数据类型：

64 位整数，及其算术运算符 ( long ) ；

16 位整数，及其算术运算符 ( short ) ；

16 位字符，及其算术运算符 ( char ) ；

8 位整数，及其算术运算符 ( byte ) ；

32 位单精度实数，及其算术运算符 ( float ) 。

八种基本数据类型：byte、short、int、long、float、double、boolean、char。

byte - 8位 short - 16位

int - 32位 long - 64位 ，默认0

float - 单精度、32位,default 0.0f

double - 双精度、64位,default 0.0d

char char类型是一个单一的 16 位 Unicode 字符 ,包装类Character

boolean boolean数据类型表示一位的信息，默认 false

颠倒数组元素的顺序

  1. int[] a = { 1, 1, 2, 3, 5, 8 };
  2.         int N = a.length;
  3.         for (int i = 0; i < N/2; i++) {
  4.             int tmp = a[i];
  5.             a[i] = a[N - 1 - i];
  6.             a[N - 1 - i] = tmp;
  7.         }

数组的起别名

数组名表示的是整个数组——如果我们将一个数组变量赋予另一个变量，那么两个变量将会指向同一个数组。

int[] a = new int[N];

…

a[i] = 1234;

…

int[] b = a;

…

b[i] = 5678; // a[i] 的值也会变成 5678

静态方法

静态方法被称为函数。静态方法是一组在被调用时会被顺序执行的语句

常用静态方法如下

判断一个数是否是素数：能不能被除了自身的数整除

  1. public static boolean isPrime(int N) { 
  2.     if (N < 2) return false; 
  3.     for (int i = 2; i*i <= N; i++) {
  4.         if (N % i == 0) return false;
  5.     return true; 
  6. }

计算平方根（牛顿迭代法）：

  1. public static double sqrt(double c) {
  2.         if (c < 0) return Double.NaN;
  3.         double err = 1e-15;
  4.         double t = c;
  5.         while (Math.abs(t - c / t) > err * t) t = (c / t + t) / 2.0;
  6.         return t;
  7.     }

计算直角三角形的斜边

  1. public static double hypotenuse(double a, double b) {
  2.         return Math.sqrt(a * a + b * b);
  3.     }

计算调和级数

  1. public static double H(int N) {
  2.         double sum = 0.0;
  3.         for (int i = 1; i <= N; i++) sum += 1.0 / i;
  4.         return sum;
  5.     }

方法可以产生 副作用 ：

  1. 方法的返回值可以是 void，这表示该方法没有返回值。返回值为void 的静态函数不需要明确的返回语句，方法的最后一条语句执行完毕后控制权将会返回给调用方。我们称 void 类型的静态方法会产生副作用（接受输入、产生输出、修改数组或者改变系统状态）。

递归

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4

标准输入库的静态方法的API

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 5

StdDraw

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 6

答疑相关记录

1、java的字节码：

程序的一种低级表示，可以运行在java的虚拟机。主要为了保障将程序抽象为字节码，代码可以运行在各种设备之上

2、java允许整型溢出并返回错误值的做法是错误的，难道不应该自动检查溢出吗？

这个问题一直有争议，之所以被称为原始数据类型就是因为缺乏此类检查，我们会使用int 类型表示较小的数（小于10个十进制位），而使用long表示 10亿以上的数

3、Math.abs(-2147483648) 的返回值是什么？

-2147483648，这个就是整型溢出的例子

4、如何将double 变量初始化为无穷大

可以使用java的内置常数： Double.POSITIVE_INFINITY 和 Double.NEGATIVE_INFINITY

5、使用一个变量前没有初始化，java会抛出一个编译异常

6、我的程序能够重新读取标准输入中的值吗？

不行，只有一次机会，就像不能撤销println() 一样

7、在java中，一个静态方法能够将另一个静态方法作为参数吗？

不行，因为很多语言这样做

8、sout（数组索引a）,打印的是数组的地址

9、为什么数组的起始索引是0 而不是 1

这个来源于机器语言，那是要计算一个数组元素的地址需要将数组的起始地址，加上该元素的索引，将起始索引设为1，那么会浪费数组的第一个元素的空间，要么花费额外的时间将索引减 1

10、java表达式的1/0 和 1.0/0.0 的值是什么

第一个表达式会产生一个运行时除零异常 （它会终止程序，因为这个值是未定义的）；第二个表达式的值是Infinity （无穷大）

11/12，采用截图看更真切

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 7

负数运算需要考虑溢出，和向上取整

&& 和 || 会遵从短路求值法则

发表评论

表情：
评论列表 （有 0 条评论，58人围观）

还没有评论，来说两句吧...

相关阅读