算法中的那些骚操作

算法中的那些骚操作

  • 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

学习算法

  • 多看:书、题解、源码
  • 多写:无他, 就是写
  • 多总结:归类
  • 和工作、生活结合起来
上一篇:力扣每日一题


下一篇:CSP期末预测之最佳阈值——python版