抢红包算法
原文来自于微信公众号：程序员小灰 - 漫画：如何实现抢红包算法？
对于我这种入门级水平的学渣来讲，原文对我的启发如下：
- 首先要考虑公平的问题。我就如同文中开头一样，首先想到的是直接随机，但这样子对后来的人完全不公平，这是我完全没有考虑到的。
- 虽然在看 《Java 核心技术 I》时学到过
BigDecimal() 方法 ，但完仅停留在 有印象 上，现在再次遇上该方法时已经完全搞不清。
- 我糟糕的数学啊，(；′⌒`)，基础真的烂。
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
| import java.math.BigDecimal;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class RedPackets {
public static List<Integer> divideRedPackets(Integer totalAmount, Integer totalPeopleAmount){
List<Integer> amountList = new ArrayList<>();
Integer restAmount = totalAmount;
Integer restPeopleAmount = totalPeopleAmount;
Random random = new Random();
for (int i = 0; i < totalPeopleAmount - 1; i++){
int amount = random.nextInt(restAmount / restPeopleAmount * 2 - 1) + 1;
restAmount -= amount;
restPeopleAmount--;
amountList.add(amount);
}
amountList.add(restAmount);
return amountList;
}
public static void main(String[] args){
List<Integer> amountList = divideRedPackets(10000, 20);
for (Integer amount : amountList){
System.out.println("抢到的金额：" + new BigDecimal(amount).divide(new BigDecimal(100)));
}
}
}
|
字典序算法
第一次见到字典序算法是来自于微信公众号 “程序员小灰” 的文章《什么是字典序算法》。
字典序算法从数学角度来讲其实很简单，即通过交换排列某个数来找到一个大于该数且交换后两者之差最小的数。
虽然从数学上来讲很容易，但如果要让代码来实现还是需要仔细思考一番，尤其是要理清每个步骤的含义。
具体逻辑细节可以阅读前面所给的参考文章。
下面是分部步骤和自己的理解：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
private static int findSwitchBorder(int[] numbers){
for (int i = numbers.length - 1; i > 0; i--){
if (numbers[i] > numbers[i - 1]){
return i;
}
}
return 0;
}
|
首先要找到交换的边界，即该边界上的数字要比前一位大，返回边界数字的序号。注意，如果没有找到这样的边界，这就意味着整个数组已经实现了逆序，那么返回零。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
private static int[] switchBorder(int[] numbers, int index){
int head = numbers[index - 1];
for (int i = numbers.length - 1; i > 0; i--){
if (numbers[i] > head){
numbers[index - 1] = numbers[i];
numbers[i] = head;
break;
}
}
return numbers;
}
|
首先确定逆序区域，即交换边界和交换边界后（右边）的区域。在逆序区域内找到刚刚比置换边界前一位（左边）数字大的数字，二者交换。（有点绕口…）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
private static int[] reverseOrder(int[] numbers, int index){
for (int i = index,j = numbers.length - 1; i < j; i++, j--){
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
return numbers;
}
|
现在将置换边界后（逆序区域内）的数字重新排列成顺序，即从小到大排序，这样可以满足距离原数字最近。
下面是全部代码：
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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
| import java.util.Arrays;
public class Lexicographical_Order {
private static int findSwitchBorder(int[] numbers){
for (int i = numbers.length - 1; i > 0; i--){
if (numbers[i] > numbers[i - 1]){
return i;
}
}
return 0;
}
private static int[] switchBorder(int[] numbers, int index){
int head = numbers[index - 1];
for (int i = numbers.length - 1; i > 0; i--){
if (numbers[i] > head){
numbers[index - 1] = numbers[i];
numbers[i] = head;
break;
}
}
return numbers;
}
private static int[] reverseOrder(int[] numbers, int index){
for (int i = index,j = numbers.length - 1; i < j; i++, j--){
int temp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = temp;
}
return numbers;
}
private static void printNumbers(int[] numbers){
for (int i: numbers){
System.out.print(i);
}
System.out.println();
}
public static int[] findNearestNum(int[] numbers){
int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
int index = findSwitchBorder(numbersCopy);
if (index == 0){
return null;
}
switchBorder(numbersCopy, index);
reverseOrder(numbersCopy, index);
return numbersCopy;
}
public static void main(String[] args){
int[] numbers = {1, 2, 3, 5, 4};
numbers = findNearestNum(numbers);
printNumbers(numbers);
}
}
|
这里要注意主方法中的 Arrays.copyOf() 方法，原文中注释说 “拷贝入参，避免直接修改入参”。而我一开始写的是 int[] num = numbers ，虽然也可以跑通，但这里肯定存在问题。这还是说明了我基础仍然薄弱，对于 Java 的参数传递还是需要多学习。