算法设计中的基础常用代码

柔情只为你懂 2022-10-22 07:47 133阅读 0赞

# 引言 #

本篇博客旨在记录一些基础算法知识的**常见组合用法**，以及**何时使用**，**需要注意的问题**等，长期更新。

为什么要这样总结呢？难道掌握了位运算、常用算法工具API的定义还不够吗？

这是因为某些知识比如 &、 |、 ~、 Math.random 等这些基础知识如果只停留在**知识记忆层面**还是无法快速运用到算法的解题思路中去，还应该有一套常见**组合用法或使用规律**。

这些组合用法通常并不是算法题的核心考点，但却起到连接**算法思想**、**基础知识**和**解题实现**的枢纽作用，就好比学习英语时，我们的目的是连词成句，但单词并不是简单的拼凑就可以连成句子，而是需要中间结构——**短语、常见搭配、语法、使用场景等多方面的经验知识**：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

如上图所示，光有基础知识层是不够的，如果想获得算法层的能力，必须要总结各种基础知识的常见组合，一旦我们在遇到算法题时，能够快速定位需要的算法组合搭配和小而美的算法思想，最终的算法实现一定能够成功落实。

# 一、Math.random()的应用 #

random()方法可以返回 \[0, 1)之间的随机数。

围绕这个核心方法，推广到以下一些常用场景，注意，以下范围都是**左右闭区间**，如果是右开区间，需要考虑清楚是否要 +1：

> 1、**得到 \[0, range\] 范围内的一个int数？**
> 
> (int) (Math.random() \* ( range + 1))
> 
> 2、**得到 \[1, range\] 范围内的一个int数？**
> 
> (int) (Math.random() \* range) + 1
> 
> 3、**万能公式**：min和max都是正整数，返回 \[min, max\] 范围内的一个 int数？
> 
> (int) (Math.random() \* (max - min + 1)) + min
> 
> 4、**max 是一个正整数，返回\[-max, max\]范围内的一个int数？**
> 
> (int) (Math.random() \* (max + 1)) - (int) (Math.random() \* (max + 1))

# 二、位运算的应用 #

## &1 和 &0 ##

在位运算中，**&1用来保留原数，&0用来清除原数。**例如，5（二进制：101），如何将其二进制位放入int\[\] 数组？或依次取得每个bit位上的值？

对于一个int型整数来说，其二进制长度是32bit，因此可以初始化一个空的int\[32\]数组，然后循环数组下标 i，然后逐位&1：

public static int[] getBits(int num) {
            int[] bits = new int[32];
            for (int i = 0; i < bits.length; i++) {
                bits[i] = (num >> i) & 1;
            }
            return bits;
        }

这样，移位后再&1就可以得到 i 位置上的二进制数。

有时候需要将多个数**按位累加**，bits\[i\] += (num >> i) & 1。这通常在**词频统计**的时候非常有用。

又比如，如何取某整数**二进制位最右1**？例如，12，二进制1100，取最右1，即100。方法是 num & ((~num) + 1)，另外 (~num) + 1 也等于 -num。

public static int getMostRightOne(int num) {
            return num & ((~num) + 1);
        }

## |1  ##

在位运算中，**|1通常用来设值，|0通常用来保留原数**。

比如，**按位设值**，假如我们知道了某个数二进制位有值条件，那么就可以使用 |1的方法，将1逐位放入：

int num = 0;
    for(int i = 0; i < 32; i++) {
        if (该位有值的case) {
            num |= (1 << i);
        }
    }
    return num;

## ^ 异或运算 ##

异或运算可以很好的规避某些额外空间消耗的问题，例如两数调换（注意，对于数组两数调换，切记不可将相同位置调换，a\[i\]、a\[j\] 调换的话，一定不能让 i 和 j 相等！），词频统计等，具体查看《[异或运算的应用][Link 1]》，牢记以下几点异或的特性：

> 特性1：0 ^ N = N
> 
> 特性2：N ^ N = 0
> 
> 特性3（交换律）：a ^ b = b ^ a
> 
> 特性4（结合律）：(a ^ b) ^ c = a ^ (b ^ c)
> 
> 特性3 和 4总结起来，就是同一批数，不论使用怎样的顺序，怎样的结合方式进行异或，其结果始终一样。

# 三、Arrays.copyOf(org, len) #

拷贝一个原始数组 org，从0开始，长度是 len。该方法通常用作测试程序，生成一个对照数组。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221022/490ea1b7065046acb7693502ad01599e.png
[Link 1]: https://morty.blog.csdn.net/article/details/115265221