2020春 · 社招

2020春招面经(社招):仅记录回答得不好的问题

  1. 首先准备一份自我介绍:您新年好,我是xxx,毕业于xxx,目前就职于xxx,主要负责工作xxx,技术栈xxx,很荣幸能够获得这次面试机会。
  2. 重新梳理一下自己的项目经验和工作经验,特别记得找出一个自己最满意的项目,有的面试官会问。
  3. 准备好你想问面试官的问题:如果是技术面就问“介绍一下你们部门”(一般是一面是交叉面,问这个问题没有意义)、“介绍一下你们部门的技术栈”……
  4. 如果是HR面,不仅需要问清楚自己关心的休假、晋升、福利待遇问题,还需要准备一下“为什么你才工作了半年就想跳槽”这个问题的答案。

(一)字节跳动·上海

【一面】

一面我介绍项目经验没有露怯,问答攻防中也见招拆招、侃侃而谈,然后来到了算法问。


1.给定n位正整数a,去掉其中任意k<=n个数字后,剩下的数字按原次序排列组成一个新的正整数,对于给定的n位正整数a和正整数k,设计一个算法找出剩下数字组成的新数最小的删数方案。

我的算法真的很辣鸡,说了几种思路都是错的 - -

面试官:那我们简化一下 —— 给定一个长度为n的数字(其中每一位都是非负整数),从中去除1个数字,如何保证剩余数字是最小的?
你可以写几个数字观察一下规律。

写下几个数:1295 -> 1259521 -> 521,发现规律是尽可能使高位的数字更小,如果高位数字大于等于低位,则删除高位数字。
这种思路有种情况我没有考虑到:

  • 如果数字是完全递增的,比如1234,那么应该删除最后一位的数字。

删除k个数字和删除1个的思路是一样的,每次贪心保证剩下数字最小即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
public int reserveLeast(int a, int k) {
if (a <= 0 || k <= 0) {
return 0;
}

//将数字转为StringBuilder,方便删除
StringBuilder sb = new StringBuilder(a + "");

//贪心k次
for (int i = 0; i < k; i++) {
//使用j记录需要删除数字的位置
int j = 0;
//如果j没有到达数组底部,并且遍历部分一直是递增的,则继续往后遍历
//j < sb.length() - 1是为了排除掉1234这种完全递增的情况,遍历到底部
while(j < sb.length() - 1 && sb.charAt(j) <= sb.charAt(j + 1) ) {
j++;
}

//删除
sb.delete(j, j + 1);
}

//转为int,使用Integer.parseInt可以防止数字最高位为0
return 0 == sb.length() ? 0 : Integer.parseInt(sb.toString() );
}

【二面】

字节跳动还真是特别喜欢问算法,二面全程都是围绕着数据结构和算法来问的 - -


1.Rediszset用的什么数据结构?

当时只能说出是跳跃表,不知道ziplist和字典的存在,而且跳跃表答得还不够深入,后面补习了一下,详见《Redis基础 & 应用(秒杀系统)—— (三)Redis 对象类型 & 数据结构 —— 5.Zset

面试官:说说跳跃表的插入和查询时间复杂度。

都是O(logN)

面试官(疑惑脸):啊?查询也是O(logN)吗?

我当时愣了一下,跟面试官分析了一波,链表遍历的话是O(N),如果是skiplist从上层往下层找的话是O(logN),所以我确定是O(logN),面试官表示满意,我以为他是在诈我……
事后补习的时候回想了一下,他可能是想问我zset查询的时间复杂度,而不是skiplist的查询时间复杂度。当时我并不知道zset底层有字典和skiplist共享底层存储,所以如果是查询单个元素,通过字典可以做到O(1)

面试官:为什么要用跳跃表,而不是红黑树?

我回答的是和红黑树的层级有关。

面试官:如果是和层级有关,为什么不用哈希表?哈希表也是一层。

仓促之间没有想到几种数据结构的区别,我没有回答上来 - -
不用红黑树是因为红黑树遍历复杂,并且插入和删除可能会改变树结构,逻辑复杂,而skiplist会简单很多;
不用哈希表是因为哈希表元素无序,不能进行范围查找(如果答出zset底层字典和skiplist共享数据存储,大概会加分吧,可惜)


2.使用一趟扫描反转从位置mn的链表

LeetCode 92-反转链表 II,思路和反转单链表(三指针法)是一样的,不同的是需要额外引入两个指针tailcontail指针指向从链表头起的第m个结点,此结点是反转后链表的尾部;con指针指向第m个结点的前一个结点,此结点是新链表的头部。


想到思路不难,但是写出代码需要一定的熟练度:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class Solution {
public ListNode reverseBetween(ListNode head, int m, int n) {
if (head == null) {
return null;
}

//先将cur移动到第m个元素,pre移动到第m个结点的前一个结点
ListNode cur = head, prev = null;
while (m > 1) {
prev = cur;
cur = cur.next;
m--;
n--;
}

//tail指针指向从链表头起的第m个结点,此结点是反转后链表的尾部;
//con指针指向第m个结点的前一个结点,此结点是新链表的头部。
ListNode con = prev, tail = cur;

//三指针法反转[m,n]的链表:最终pre移动到了第n个元素,cur移动到了第n + 1个元素
ListNode third = null;
while (n > 0) {
third = cur.next;
cur.next = prev;
prev = cur;
cur = third;
n--;
}

//如果con为空,则pre即为新链表头,否则将pre放到con后面
if (con != null) {
con.next = prev;
} else {
head = prev;
}

//将cur放到tail的后面
tail.next = cur;

//需要返回头节点,所以不要对头结点进行后移,而是使用额外的指针进行后移
return head;
}
}

3.两个自然序的数组,找出其中的第k小元素

这个和归并排序中合并两个排序子数组的思路是一样的,通过两个指针和一个O(1)的额外存储即可做到,但是时间复杂度是O(N)

面试官:怎么优化到O(logN)

我想到好像“第k大问题”都是可以通过堆排序来进行优化的,就说可以用堆排序 - -

面试官:堆排序???(黑人问号脸.jpg)堆排序的时间复杂度是多少?

O(NlogN)…… (你说我干嘛口嗨这么一句,一顿疯狂道歉,感觉面试官对我的印象分还是大打折扣)
O(logN)的办法我第一反应就是二分查找,正好数组也是排好序的,但是想了半天没想到要怎么去二分,最后还是只写出了O(N)的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
/**
* 假设 A 和 B 的元素个数都大于 k/2,我们将 A 的第 k/2 个元素(即 A[k/2 - 1])和 B 的第 k/2个元素(即 B[k/2 - 1])进行比较:
* A[k/2 - 1] == B[k/2 - 1] 找到了第k大的元素,即A[k/2 - 1]或B[k/2 - 1]
* A[k/2 - 1] > B[k/2 - 1] B[k/2 - 1]不可能大于第k大元素,可以放心删除B数组左边一半的k/2个元素
* A[k/2 - 1] < B[k/2 - 1] A[k/2 - 1]不可能大于第k大元素,可以放心删除A数组左边一半的k/2个元素
*
* 跳出递归的条件:
* 当k = 1时,返回A[0]/B[0]中的较小值
*
*
*
**/

// 找到第k大元素
public static int findKK(int[] a, int[] b, int k) {
if(k == 0) {
return Math.min(a[0], b[0]);
}
return recursion(a, 0, a.length, b, 0, b.length, k);
}

//递归
public static int recursion(int[] a, int left1, int right1, int[] b, int left2, int right2, int k) {
//跳出递归的条件:只需要找第1小的元素
if(k == 1) {
return Math.min(a[left1], b[left2]);
}

//二分:数组长度可能不足k/2,去数组长度和k/2中的较小者
int halfA = Math.min(k / 2, right1 - left1 + 1);
int halfB = Math.min(k - halfA, right2 - left2 + 1);
//可以安全删除较小者的左边k/2(即halfA或者halfB)
if(a[left1 + halfA - 1] > b[left2 + halfB - 1]) {
//删除B的左边一半、A的右边一半
return recursion(a, left1, left1 + halfA - 1, b, left2 + halfB, right2, k - halfB);
} else {
//删除A的左边一半、B的右边一半
return recursion(a, left1 + halfA, right1, b, left2, left2 + halfB - 1, k - halfA);
}

}

4.你有什么想问的?

(1)能简单介绍一下你们部门的业务吗?

负责探索除字节跳动核心业务外的其他业务,主要内容商业机密无法透露,负责方向目前有教育、互娱等方面。

(2)如果有幸入职,我需要转语言吗?

入职后都需要转Golang,但是不要求你会Golang,如果会的话当然更锦上添花。


【三面】:可惜

原本是道送分题 —— 求二叉树的路径,用递归实现DFS遍历即可,问题是我居然没有写出来,结果变成了送命题。
我和面试官说我卡壳了,希望能换一题,面试官说没时间了 —— 大概是觉得送分题做不出来没有继续问的必要了吧。
最终还是收到了拒信。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/

class Hope{
//总路径
List<ArrayList<Integer>> result = new ArrayList<>();
//路径
List<Integer> path = new ArrayList<>();

//DFS 递归实现
public List<ArrayList<Integer>> findPath(TreeNode root, int target) {
//【递归四部曲】
//1.进入递归函数,就要说明递归结束的条件
//递归结束条件:传入了叶子节点的left/right,直接返回result
if (null == root) {
return result;
}

//2.处理当前层
//当前节点加入路径
path.add(root.val);
//路径和减去当前节点值
target -= root.val;
//如果当前节点是叶子节点,并且路径和等于target,将其加入result
if (0 == target && null == root.left && null == root.right) {
result.add(new ArrayList(path) );
}

//3.drill down,即递归到下一层
//递归处理左右子树
findPath(root.left);
findPath(root.right);

//4.如有必要,还原当前节点
//如果递归没有结束,说明当前子树不满足条件,需要剔除
path.remove(path.size() - 1);

return result;
}
}

(二)快手·杭州·广告创意方向

【一面】

问了两个DP问题,但是我死活写不出来状态转移方程,最后给我换了个简单点的题目,让我实现HashMap#get()……


1.LeetCode Medium 300 最长上升子序列

  1. 状态:dp[i]表示以nums[i]结尾的子序列中最长上升子序列长度
  2. 状态转移方程:对于每一个子序列来说,它的最长上升子序列是它的【所有子序列的最长上升子序列 + 1】中的最大值,即:dp[i] = max(dp[j] + 1) for j in [0, i)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int lengthOfLIS(int[] nums) {
if (nums.length == 0) {
return 0;
}
int[] dp = new int[nums.length];
dp[0] = 1;
int maxans = 1;
for (int i = 1; i < dp.length; i++) {
int maxval = 0;
for (int j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
maxval = Math.max(maxval, dp[j]);
}
}
dp[i] = maxval + 1;
maxans = Math.max(maxans, dp[i]);
}
return maxans;
}
}

2.LeetCode Medium 1143 最长公共子序列

  1. 定义状态:不要让思维僵化,状态不一定是一个一维数组,对于本题,很明显一维数组不足以存储状态,所以我们需要定义一个二维数组。dp[i][j]表示text1长度为itext2长度为j时,两者的最长公共子序列。
  2. 边界条件:dp[0][0] = 0,由于Java类加载时自动为变量赋初值的特性,我们可以不显式地写这一行。
  3. 推导状态转移方程:①如果text1[i] == text2[j],那么最长公共子序列则为当前字符长度(即1)加上当前字符之前的最长公共子序列,即dp[i][j] = dp[i - 1][j - 1] + 1;;②如果text1[i] != text2[j],那么最长公共子序列则为text1text2去除一个字符后的最长公共子序列中的较大者。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int longestCommonSubsequence(String text1, String text2) {
int m = text1.length(), n = text2.length();
int[][] dp = new int[m + 1][n + 1]; //暗含dp[0][0]=0
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
if (text1.charAt(i - 1) == text2.charAt(j - 1) ) {
dp[i][j] = dp[i - 1][j - 1] + 1;
}else{
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}

【二面】

所以说面试真的会有所谓相性一说,我和二面的面试官感觉就八字不合,聊不到一块,感觉自己被怼得挺惨的,不过还是给我过了 - -
他的问题实在不具有代表性,我都有点不想总结……


1.中台和平台的区别

中台是应用而不是技术,中台和业务息息相关。


2.二维数组中,每一行从左到右递增,每一列从上到下递增,判断数组中是否含有某个整数。

在排序数组中查找让我想到了二分查找,但是我只能写出一个维度的二分,所以我在另一个维度用了遍历,最后结果自然是O(NlogN)……
而实际上由于该二维数组的特殊性,我们可以实现O(N)的算法 —— 从右上角开始判断:

  • = target:右上角元素即需要查找的元素;
  • < target:由于每一行从左到右排序,该元素左边元素都比target小,所以可以剔除整个行;
  • > target:由于每一列从上到下排序,该元素下边元素都比target大,所以可以剔除整个列;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public boolean search(int[][] array, int target) {
int rows = array.length; //行数
int cols = array[0].length; //列数

if (null == array || 0 == rows || 0 == cols) {
return false;
}

//如果target比最小值小,或者比最大值大,直接返回false
if (array[0][0] > target || array[rows - 1][cols - 1] < target) {
return false;
}

int row = 0;
//从右上角开始遍历
for (int col = cols - 1; col >= 0 && row < rows; ) {
if (array[row][col] == target) {
return true;
}else if (array[row][col] > target) {
col--; //剔除整个列
}else{
row++; //剔除整个行
}
}

return false;
}

3.LeetCode Medium 287 寻找重复数

我原本给出的思路是类似missing number的位运算,后来发现这个题目还会存在元素重复不止一次的情况,比如2 2 2 2


解法1:二分查找 O(NlogN)
  • 数组本身不是有序的,但是数组元素[1,n]是有序的,我们可以对它进行二分。

  • 抽屉原理:如果子数组中小于等于mid的元素个数超过了mid个,则[left,mid]中一定存在重复元素。

    举个栗子你就很容易想明白:如果数组中<= 4的元素个数超过了4个,是不是说明[1,4]中间一定有至少一个元素不止一个?

  • 二分查找mid时间复杂度O(logN),对于每个mid需要遍历一次数组计数,时间复杂度O(N),所以最终时间复杂度为O(NlogN)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int findDuplicate(int[] nums) {
int len = nums.length; //n + 1

//从[1,n]开始二分
int left = 1;
int right = len - 1;

while(left < right) {
//left + (right - left)/2要更优化,可以防止越界
//位运算:>>>1 相当于/2
int mid = left + ((right - left) >>> 1);

//遍历数组并计数,记录<=mid的数有多少个
int cnt = 0;
for (int num : nums) {
if (num <= mid) {
cnt++;
}
}

//如果子数组中小于等于mid的元素个数超过了mid个,则[left,mid]中一定存在重复元素
if (cnt > mid) {
right = mid;
}else{
left = mid + 1;
}
}

return left;
}

解法2:快慢指针(判断链表环入口)

这个方法很有技巧性,让我想几天都想不出来 - -

  • 首先将数组下标和数组元素的关系看作一个i -> nums[i]的指针关系,所有元素就组成了一个单链表,数组中存在重复元素就是单链表存在环,找到环入口就找到了重复元素。

  • 首先判断是否存在环:通过快慢指针,快指针每次走两步(quick = nums[nums[quick]]),慢指针每次走一步(slow = nums[slow]),快慢指针相遇就是存在环。
  • 找到环入口:双指针同步前进,一个从起点开始,一个从交点开始,双指针相遇即为环入口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public int findDuplicate(int[] nums) {
int slow = nums[0];
int quick = nums[0];
//首先判断是否存在环,这一步并不能找到环的入口
//找到快慢指针在环内的交点,注意指针的交点并不是环的入口
do {
//慢指针每次走一步
slow = nums[slow];
//快指针每次走两步
quick = nums[nums[quick]];
} while (slow != quick);

//双指针:一个从头开始,一个从交点开始,指针相遇处即为环入口
int ptr1 = nums[0];
int ptr2 = slow;
while (ptr1 != ptr2) {
ptr1 = nums[ptr1];
ptr2 = nums[ptr2];
}

return ptr1;
}
}

【三面】

面试很顺利,目前已经进入谈薪阶段啦~


LeetCode Medium 162 寻找峰值

O(N)的方法很容易想到,双向查找比单向查找快也容易想到,但是最佳的方法是O(logN)的二分查找。

  • 根据题意,数组中一定会存在峰值,并且相邻元素一定不相等,所以我们可以知道:从峰值往左一定是递减,从峰值往右一定是递增
  • 每次进行二分查找 —— 如果中点元素比它右边的元素小,那么它一定是在峰值左边,可以舍弃[left,mid]这部分的数据;如果中点元素比它右边的元素大,那么它一定是在峰值右边,可以舍弃(mid,right]这部分的数据。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
public int findPeakElement(int[] nums) {
int l = 0, r = nums.length - 1;
//二分查找
while (l < r) {
// int mid = (l + r) / 2; 优化:
int mid = l + ((r - l) >>> 1);
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}

(三)字节跳动·北京

【一面】

问了很多MySQL主从同步延迟时,Redis缓存脏数据的问题。


LeetCode Medium 678 有效的括号字符串

  1. 我用的是栈来解决,最后判断的时候没有考虑空栈pop()会报NPE,被面试官提醒了:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class Solution {
public boolean checkValidString(String s) {
Stack<Integer> stack1 = new Stack(); //存储(
Stack<Integer> stack2 = new Stack(); //存储*
//遍历字符串
for(int i = 0; i < s.length(); i++) {
if(s.charAt(i) == '(' ) {
stack1.push(i);
}else if(s.charAt(i) == '*') {
stack2.push(i);
}else{
//如果是),先和(匹配,然后再和*匹配
if(!stack1.isEmpty() ) {
stack1.pop();
}else if(!stack2.isEmpty() ){
stack2.pop();
}else{
return false;
}
}

}
//匹配完所有)后,最后判断两个栈顶
//如果没有(了,那么直接返回true,否则要将(和*再次进行匹配
while(!stack1.isEmpty() ){
//判空,否则抛出NPE
if(stack2.isEmpty() ) {
return false;
}
//*(是不合法的情况,所以(不能在*前面
if(stack1.pop() > stack2.pop() ){
return false;
}
}
return true;
}
}
  1. 后来看题解的时候发现个特别骚的操作:如果从左往右遍历,( + *数量 < )数量;从右往左遍历,* + )数量 < (数量,则返回false,否则返回true
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public boolean checkValidString(String s) {
int l = 0, r = 0;
for(int i = 0; i < s.length(); i++) {
//left to right: ( * < )
if(s.charAt(i) == ')' ) {
l++;
if(i + 1 - l < l) return false;
}
//right to left: * ) < (
if(s.charAt(s.length() - 1 - i) == '(' ) {
r++;
if(i + 1 - r < r) return false;
}
}
return true;
}
}

【二面】

问了很多计算机网络方面的知识:详见http://www.dragonbaby308.com/tcp-ip/

找出下两条SQL的性能差异:

1
2
3
4
5
6
7
uid nickname mobile email pwd

primary key uid
key idx_acc (mobile, email)

语句1:select * from users where mobile = 'xxx'
语句2select uid from users where mobile = 'xxx'
  1. 首先必须明确一点,MySQL索引是否使用只和where后的条件有关,所以语句1和语句2都会使用索引idx_acc
  2. 语句1查找了除主键(uid)、索引项(mobile/email)之外的其他字段,所以不满足覆盖索引的条件,需要进行回表,性能较差;
  3. 语句2满足覆盖索引的条件,不需要回表,性能较高

【三面】:你杀了我吧

依稀记得是之前“剑指offer”做过的题,问题是我当年偷了懒,直接用的Math.random()实现,想的是不会考 - -
面试44分钟结束了,估计是又凉了。


LeetCode Medium 236 二叉树的最近公共祖先

递归DFS

  1. 退出递归的条件:找到了需要查找的节点 / 递归到了叶子节点
  2. 处理当前层 && drill down:判断当前节点左、右子树是否存在需要查找的节点 —— 如果左子树中不存在,那么右孩子就是最近公共祖先;如果右子树中不存在,那么左孩子就是最近公共祖先;如果左右子树中都存在,那么当前节点就是最近公共祖先
  3. 不需要回溯
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//1.退出递归的条件:
//①当前节点为空,无结果
if (root == null) {
return null;
}
//②当前节点为要查找的两个节点中的一个,那么当前节点即为最小公共祖先
if (root == p || root == q) {
return root;
}

//2.处理当前层 && 3.drill down
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
//当前节点左子树没有找到p和q,那么右孩子就是最小公共祖先
if (left == null) {
return right;
}
//当前节点右子树没有找到p和q,那么左孩子就是最小公共祖先
if (right == null) {
return left;
}
//当前节点左子树和右子树都找到了p和q,那么当前节点就是最小公共祖先
return root;
}
}

LeetCode Medium 470Rand7()实现Rand10()

Rand10()中,1-56-10出现的概率各占50%,那么只需要随机生成1-5,并有50%的概率为其+5,得到的即是Rand10()

  1. Rand7()实现Rand5(),只需要在Rand7()获得6/7时再次调用,直到随机数在1-5中即可;
  2. 50%的概率:Rand7()中,出现1-3和出现4-6的概率分别为50%,如果得到7就再次调用,直到随机数在1-6中即可。

    但是!这种方法只适合偶数,如果题目改成用Rand5()生成Rand7()就不行了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
int rand5;
do{
rand5 = rand7();
}while(rand5 > 5);

int half;
do{
half = rand7();
}while(half == 7);

return (half <= 3) ? rand5 : rand5 + 5;

}
}

Rand5()实现Rand7()

两种错误的思路:

  1. Rand5() + Rand2():由于Rand5()Rand2()最小都是11 + 1 > 1,所以这样相加不可能获得1
  2. Rand5() + Rand5()%3Rand5()%3获得0/1/2的概率是不相等的。

正确的思路:

  1. 通过Rand5()生成1-25之间的随机数:Rand5() + (Rand5() - 1) * 5

    通过RandX()实现RandX^2()RandX() + (RandX() - 1) * X

  2. 1-21映射为1-7,如果随机数为22-25则再次随机:x % 7 + 1

代码:

1
2
3
4
5
6
7
8
9
10
public int rand7() {
//用rand5()随机出1-25
//1-21映射到rand7(),22-25随机掉
int rand25;
do{
rand25 = rand5() + (rand5() - 1) * 5;
}
while(rand25 > 21);
return rand25 % 7 + 1;
}
-------------本文结束感谢您的阅读-------------

本文标题:2020春 · 社招

文章作者:DragonBaby308

发布时间:2020年02月04日 - 20:02

最后更新:2020年03月01日 - 20:00

原始链接:http://www.dragonbaby308.com/2020spring/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

急事可以使用右下角的DaoVoice,我绑定了微信会立即回复,否则还是推荐Valine留言喔( ఠൠఠ )ノ
0%