算法中的那些骚操作
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了算法中的那些骚操作，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含3854字，纯文字阅读大概需要6分钟。
内容图文
算法中的那些骚操作
- 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 < n-1; 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
学习算法
- 多看：书、题解、源码
- 多写：无他, 就是写
- 多总结：归类
- 和工作、生活结合起来
内容总结
以上是互联网集市为您收集整理的算法中的那些骚操作全部内容，希望文章能够帮你解决算法中的那些骚操作所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。