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

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

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

>     public static int gcd(int p, int q) {
>     
>         if (q == 0) { return p;}
>     
>         int r = p % q;
>     
>         return gcd(q, r);
>     
>     }
> 
> 计算两个非负整数 p 和 q的最大公约数： 若 q 是0，则最大公约数为p。否则，将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数  -- 欧几里德算法

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

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

BinarySearch 二分法查找：

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

public static int rank(int key, int[] a) {
            int lo = 0;
            int hi = a.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (key < a[mid]) {
                    lo = mid - 1;
                } else if (key > a[mid]) {
                    lo = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }

![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***

***颠倒数组元素的顺序***

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

***数组的起别名***

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

> int\[\] a = new int\[N\]; 
> 
> ... 
> 
> a\[i\] = 1234; 
> 
> ... 
> 
> **int\[\] b = a;** 
> 
> ... 
> 
> b\[i\] = 5678; // a\[i\]  的值也会变成  5678
> 
>

***静态方法***

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

常用静态方法如下

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

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

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

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

计算直角三角形的斜边

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

计算调和级数

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

方法可以产生 ***副作用*** ：

>   
> 
>     方法的返回值可以是 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][]

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

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200311221441794.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[20200310223608563.png]: https://img-blog.csdnimg.cn/20200310223608563.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200310235012829.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200310235258360.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200310235345840.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200311000200481.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200311000658468.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200311220710793.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200311233640495.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM1Mjc1MjMz,size_16,color_FFFFFF,t_70