面试算法学习

前言

为了应对腾讯的笔试，简单学习一些算法来应对吧，也是好久没有写代码了，一些基本的代码如何用都忘了，简单复习一下

算法题

洗牌算法

对52张牌洗牌，要求尽量洗乱，而且原牌不能在原位置上重复

洗牌算法是常见的随机问题：将1-52张扑克牌重新洗牌。

Fisher–Yates随机置乱算法也被称做高纳德置乱算法，通俗说就是生成一个有限集合的随机排列。Fisher-Yates随机置乱算法是无偏的，所以每个排列都是等可能的，当前使用的Fisher-Yates随机置乱算法是相当有效的，需要的时间正比于要随机置乱的数，不需要额为的存储空间开销。

1
2
3
4
5
6
7
8
9
10
11
12
13
import random
def shuffle(buf):
    length = len(buf)
    print(length)
    for i in range(length):
        number = random.randint(i,51);
        buf[i],buf[number] = buf[number],buf[i]
buf=[]
for i in range(1,53):
    buf.append(str(i))
print(buf)
shuffle(buf)
print(buf)

高纳德置乱算法的步骤如下：

  1. 遍历数组，从最后一个元素开始，依次向前。
  2. 对于当前遍历到的元素，随机生成一个位于它之前（包括它自己）的位置，将该元素与随机选取的位置上的元素交换。

这个算法的核心思想是，每一次迭代中，当前元素的位置是随机选择的，保证了每个元素被选取的概率都是相等的，因此在数组中的每个位置都有相等的概率被选中，从而实现了均匀随机地排列数组元素的目的。

函数学习

  • 生成随机数的函数为random.randint(start,end)
  • 使用当前时间戳作为随机数种子 random.seed(time.time())
  • 对一个列表数组进行插入用append()，将整数转换为对应的ascii码用str(),案例buf.append(str(i))

找出重复数字

数组a[N]，存放了数字1至N-1，其中某个数字重复一次。写一个函数，找出被重复的数字。时间复杂度必须为O(N), 空间复杂度不能是O[N]

这道题的时间复杂度要求o（N），一般我的思路就是先排序再遍历，计算a[i]与a[i+1]是否相等，相等就return。