算法中的那些骚操作

算法中的那些骚操作

• 1.直接好处是能够有写出性能更优的代码。
• 2.算法，是一种解决问题的思路和方法，有机会应用到生活和事业的其他方面。
• 3.长期来看，大脑思考能力是个人最重要的核心竞争力，而算法是为数不多的能够有效训练大脑思考能力的途径之一。

神奇的二进制

使用二进制解决过什么问题吗？

变量交换

x = x ^ y // （1）
y = x ^ y // （2）
x = x ^ y // （3）


把（1）中的 x 代入 （2）中的 x，有

y = x^y = (x^y)^y = x^(y^y) = x^0 = x


x 的值成功赋给了 y。

对于（3）,推导如下：

x = x^y = (x^y)^x = (x^x)^y = 0^y = y


最大、最小整数，掩码

一些算法题中, 会有"不能超过整数范围"的要求, 但是我们没法预知运行环境的总线长度

对于有符号整数：

//最大值：
INT_MAX = int(^uint(0) >> 1)
//最小值：
INT_MIN = ^INT_MAX


对于无符号整数：

//最大值：
INT_MAX = ^uint(0)
//最小值：
INT_MIN = 0


计算二进制中的1的个数

//核心是不停地抹去低位的1
func NumberOf1(n int) int {
res := 0
for n!=0 {
res++
n = (n - 1) & n
}
return res
}


乱序整型数组中找出没有重复的数

给你一组整型数据，这些数据中，其中有一个数只出现了一次，其他的数都出现了两次，让你来找出一个数 。

原理：

• 异或支持交换律和结合律
• 相同两数异或结果为0

func Find(arr []int) int {
var rs int
for _,v := range arr{
rs ^= v
}
return rs
}


大数据存储

案例, 双色球存储：

一注双色球格式：01,02,03,04,05,06|01(20个字符)

红区共33个号码可选, 蓝区共16个号码可选

要存储所有的组合：

C(33,6) * C(16, 1) = 1107568 * 16 = 17721088 注

存储共：17721088 * 20 = 300M

使用二进制存储：

共使用33个bit位记录33个红球和16个bit位记录16个红球, 一个整型存储就够了(64位系统), 存储可减少一半, 结合压缩, 会更低

场景：存储的数据可枚举

搞定递归

问题：容易套用平铺直叙的思维方式去推导计算机程序演进

递归的三大要素:

• 第一要素：明确你这个函数想要干什么
• 第二要素：寻找递归结束条件
• 第三要素：找出函数的等价关系式(递推公式)

例：斐波那契数:1、1、2、3、5、8、13…, 求第n项的值

//明确你这个函数想要干什么: f(n) 的功能是求第 n 项的值
func Fibonacci(n int) int {

}
//寻找递归结束条件
func Fibonacci(n int) int {
if n <= 2{
return 1
}
}
//找出函数的等价关系式(递推公式)
//根据数列规则, 一个项的值是前两项之和
f(n)=f(n-1)+f(n-2)
func Fibonacci(n int) int {
if n <= 2{
return 1
}
return Fibonacci(n-1)+Fibonacci(n-2)
}


判断链表是否有环

首先创建两个指针p1和p2，让它们同时 指向这个链表的头节点。然后开始一个大循环，在循环体中，让指针p1 每次向后移动1个节点，让指针p2每次向后移动2个节点，然后比较两个 指针指向的节点是否相同。如果相同，则可以判断出链表有环，如果不同，则继续下一次循环

追及问题：
在一个环形跑道上，两个运动员从同一地点起跑，一个运动员速度快， 另一个运动员速度慢。当两人跑了一段时间后，速度快的运动员必然会 再次追上并超过速度慢的运动员，原因很简单，因为跑道是环形的。

为什么快的指针步长是2？因为在快的追上慢的前, 必然是相差1或2步, 如果落后1, 下次一定能追上, 如果落后2, 那么下次一定是落后1, 再下一次就能追上

func hasCycle(head *ListNode) bool {
fast, slow := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}


组合计算

//输入
["a", "b", "c"]
//输出
["a", "b"]
["b", "c"]
["a", "c"]


• 1.创建有n个元素数组，数组元素的值为1表示选中，为0则没选中。
• 2.初始化，将数组前m个元素置1，表示第一个组合为前m个数。
• 3.从左到右扫描数组元素值的“10”组合，找到第一个“10”组合后将其变为“01”组合，同时将其左边的所有“1”全部移动到数组的最左端。
• 4.当某次循环没有找到“10“组合时，说明得到了最后一个组合，循环结束。

例如求5中选3的组合：

1 1 1 0 0 //1,2,3
1 1 0 1 0 //1,2,4
1 0 1 1 0 //1,3,4
0 1 1 1 0 //2,3,4
1 1 0 0 1 //1,2,5
1 0 1 0 1 //1,3,5
0 1 1 0 1 //2,3,5
1 0 0 1 1 //1,4,5
0 1 0 1 1 //2,4,5
0 0 1 1 1 //3,4,5


for {
find := false
//每次循环将第一次出现的 1 0 改为 0 1，同时将左侧的1移动到最左侧
for i := 0; i if indexs[i] == 1 && indexs[i+1] == 0 {
find = true
indexs[i], indexs[i+1] = 0, 1
if i > 1 {
moveOneToLeft(indexs[:i])
}
result = addTo(result, indexs)
break
}
}
//本次循环没有找到 1 0 ，说明已经取到了最后一种情况
if !find {
break
}
}


https://www.it610.com/article/4097023.htm

学习算法

• 多看：书、题解、源码
• 多写：无他, 就是写
• 多总结：归类
• 和工作、生活结合起来