Google 高频随机题

4xi 发表于 2021-8-11 10:23
我说的就是follow up的思路，既然比的是行是否相同，那么问题简化为如何生成一行， 把生成一行抽象成为生 ...

我觉得我收到你的启发可以先generate 一个list代表所有可能的candidates的数, 既所有可能的1到15的5次方之间的数减去有重复存在的数, 再从这个里面去随机, 并且使用list + hashmap的方法

kikiisme0201 发表于 2021-8-11 09:49
这样子生成的数会存在两个位置上的数字相同? 比如 可能出现 1,1,1,1,1  = 31 的情况? 如果你说的这个思路 ...

当然是需要换算的。一次生成一行 ，那个是逻辑上抽象嘛。 1，1，1，1，1 就代表1，16，31，46，61

4xi 发表于 2021-8-11 19:13
当然是需要换算的。一次生成一行 ，那个是逻辑上抽象嘛。 1，1，1，1，1 就代表1，16，31，46，61

可能我没表达清楚, 我的意思是 这个题目要求的是这五个数字不相同不是吗, 那如果那找你直接的解法会出现31这个数字,那么会有5个相同的数字. 我的理解是得要去除掉这些数字. 如果我理解错了还麻烦你纠正我

kikiisme0201 发表于 2021-8-11 09:51
我觉得我收到你的启发可以先generate 一个list代表所有可能的candidates的数, 既所有可能的1到15的5次方 ...

当然可以这么做，generate这个list，然后shuffle，从前往后挨个取就是了，每个都是随机不一样的。这个值域空间是可以的 也就15^5, 但是值域空间大了就不可行了。

非followup 我自己联系的部分在这里, 关于followup 还请给位多给一些思路

1. from random import randint
   
2. def random_row(l, r, col_num):
   
3.     pools = [num for num in range(l, r+1)]
   
4.     res = []
   
5.     for i in range(col_num):
   
6.         selected_idx = randint(0, len(pools)-1)
   
7.         res.append(pools[selected_idx])
   
8.         pools[selected_idx], pools[-1] =  pools[-1], pools[selected_idx]
   
9.         pools.pop()
   
10.     return res
    
11.         
    
12. def bingo_board():
    
13.     num_cand_each_row, col_num, row_num = 15, 5, 5
    
14.     res = []
    
15.     for i in range(row_num):
    
16.         start, end = i*15+1, (i+1)*15
    
17.         res.append(random_row(start, end, col_num))
    
18.     return res

复制代码

follow-up 的练习

1. from itertools import permutations as perm
   
2. from random import randint
   
3. def random_select(p):
   
4.     idx = randint(0, len(p)-1)
   
5.     res = p[idx]
   
6.     p[idx], p[-1] = p[-1], p[idx]
   
7.     p.pop()
   
8.     return res
   
9.    
   
10. def bingo_board_followup(N):
    
11.     # when it requires each row to be different
    
12.     perms = [list(perm([i for i in range(1+i*15, 16+i*15)], 5)) for i in range(5)]
    
13.    
    
14.     res = []
    
15.     for i in range(N):
    
16.         for p in perms:
    
17.             res.append(random_select(p))
    
18.     return res

复制代码

用 1到 15^5中的数字表示bingoBoard的row是好方法

1988deandean 发表于 2021-8-23 03:23
用 1到 15^5中的数字表示bingoBoard的row是好方法

我觉得用15^5代表row是个很好的办法, 如果和naive hashmap rejection对比,可以节约空间, 但这本质上还是一种rejection. 是否使用hashmap去reject这depends需要的board 数目多不多, 因为数量大了的话collision很多需要, 产生一个新的board很难, 总共有15*14*13*12*11个board, 那么如果你要用这个方法产生所有的board几乎是不可行的, 考虑到collision的情况.

同时我觉得那位层主忽略了一个点,也可能是我没看懂, 就是当你产生一个随机数‘0001 0001 0001 0001 0001’ 其实这个得判断这个数字是不能用的, 因为这会产生5个一样的数在一个row, 而这是不符合要求的.

我实现了那位层主的代码, 发现在数字小时, 这个代码很快, 但数字大了就很慢了因为有collision

1. def unique_number(num):
   
2.     b_num = bin(num)[2:]
   
3.     b_num = '0'*(20-len(b_num))+b_num
   
4.     num_set = set([b_num[i*4:i*4+4] for i in range(5)])
   
5.     if len(num_set) < 5 or '0000' in num_set:
   
6.         return False
   
7.     return True
   
8. def bitmask_to_row(num, start):
   
9.     b_num = bin(num)[2:]
   
10.     b_num = '0'*(20-len(b_num)) + b_num
    
11.    
    
12.     return [int(b_num[i*4:i*4+4],2) + start for i in range(5)]
    
13.         
    
14. def bingo_board_followup(N):
    
15.     # when it requires each row to be different
    
16.     # 16**5
    
17.     row_used = [set() for _ in range(5)]
    
18.     res = []
    
19.     for _ in range(N):
    
20.         for row_idx in range(5):
    
21.             while True:
    
22.                 rand_num = randint(2**16, 16**5)
    
23.                 if rand_num not in row_used[row_idx] and unique_number(rand_num):
    
24.                     row_used[row_idx].add(rand_num)
    
25.                     res.append(bitmask_to_row(rand_num, 15*row_idx))
    
26.                     break
    
27.     return res
    
28.                     
    
29.    
    
30. bingo_board_followup(100000)

复制代码

4xi 发表于 2021-8-11 19:17
当然可以这么做，generate这个list，然后shuffle，从前往后挨个取就是了，每个都是随机不一样的。这个值 ...

您好! 我之前想表达的是有一个情况我没理解, 就是当你产生一个随机数‘0001 0001 0001 0001 0001’ 其实这个得判断这个数字是不能用的, 因为这会产生5个一样的数在一个row, 而这是不符合要求的.
然后我代码实现在下面了, unique_number 这个函数就是判断上面这个情况, 可能能把我想说的解释得更清楚? 另外rejection的话还是会有collision的问题, 在N>100000时这不是一个好方法(在我看来), 我之前的解法在时间上会更好, 但是空间上会更差

1. def unique_number(num):
   
2.     b_num = bin(num)[2:]
   
3.     b_num = '0'*(20-len(b_num))+b_num
   
4.     num_set = set([b_num[i*4:i*4+4] for i in range(5)])
   
5.     if len(num_set) < 5 or '0000' in num_set:
   
6.         return False
   
7.     return True
   
8. def bitmask_to_row(num, start):
   
9.     b_num = bin(num)[2:]
   
10.     b_num = '0'*(20-len(b_num)) + b_num
    
11.    
    
12.     return [int(b_num[i*4:i*4+4],2) + start for i in range(5)]
    
13.         
    
14. def bingo_board_followup(N):
    
15.     # when it requires each row to be different
    
16.     # 16**5
    
17.     row_used = [set() for _ in range(5)]
    
18.     res = []
    
19.     for _ in range(N):
    
20.         for row_idx in range(5):
    
21.             while True:
    
22.                 rand_num = randint(2**16, 16**5)
    
23.                 if rand_num not in row_used[row_idx] and unique_number(rand_num):
    
24.                     row_used[row_idx].add(rand_num)
    
25.                     res.append(bitmask_to_row(rand_num, 15*row_idx))
    
26.                     break
    
27.     return res
    
28.                     
    
29.    
    
30. bingo_board_followup(100000)

复制代码