网站怎么做网站收录,保定网站设计网站,免费咨询,中国建设人才信息网查询引言
本篇博客旨在记录一些基础算法知识的常见组合用法#xff0c;以及何时使用#xff0c;需要注意的问题等#xff0c;长期更新。
为什么要这样总结呢#xff1f;难道掌握了位运算、常用算法工具API的定义还不够吗#xff1f;
这是因为某些知识比如 、 |、 ~、 …引言
本篇博客旨在记录一些基础算法知识的常见组合用法以及何时使用需要注意的问题等长期更新。
为什么要这样总结呢难道掌握了位运算、常用算法工具API的定义还不够吗
这是因为某些知识比如 、 |、 ~、 Math.random 等这些基础知识如果只停留在知识记忆层面还是无法快速运用到算法的解题思路中去还应该有一套常见组合用法或使用规律。
这些组合用法通常并不是算法题的核心考点但却起到连接算法思想、基础知识和解题实现的枢纽作用就好比学习英语时我们的目的是连词成句但单词并不是简单的拼凑就可以连成句子而是需要中间结构——短语、常见搭配、语法、使用场景等多方面的经验知识 如上图所示光有基础知识层是不够的如果想获得算法层的能力必须要总结各种基础知识的常见组合一旦我们在遇到算法题时能够快速定位需要的算法组合搭配和小而美的算法思想最终的算法实现一定能够成功落实。
一、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 相等词频统计等具体查看《异或运算的应用》牢记以下几点异或的特性 特性10 ^ N N 特性2N ^ N 0 特性3交换律a ^ b b ^ a 特性4结合律(a ^ b) ^ c a ^ (b ^ c) 特性3 和 4总结起来就是同一批数不论使用怎样的顺序怎样的结合方式进行异或其结果始终一样。 三、Arrays.copyOf(org, len)
拷贝一个原始数组 org从0开始长度是 len。该方法通常用作测试程序生成一个对照数组。
