华子员工爆料：17级以下，晚上基本都在熬工时等夜宵，17级以上开会讨论方案。。
老鬼约 4 分钟嗯，这样的工作节奏对我们程序员来说，真是太“熟悉”了。
说实话，职场上，尤其是在大公司，很多时候看似拼的是能力，实际上拼的更多是谁能熬得住。
能力是基础，但要想在大公司站稳脚跟，夜以继日地拼命工作、把工时“熬”出来，似乎成了某种“潜规则”。
你以为那些高等级的同事在开会讨论创新方案，光鲜亮丽，其实他们也只不过是从解决临时问题、推新版本里脱颖而出罢了。
不过，话说回来，这种“熬”的方式，真的值得提倡吗？这也让我反思：我们到底是在“拼能力”还是在“拼熬夜”呢？🤔
算法题：按权重随机选择
嗨，大家好，今天我们来聊一个有意思的技术问题：按权重随机选择。
那么问题来了，怎么用代码实现这个“按权重随机选择”的功能呢？今天我就通过一个简单的 Java 示例，给大家带来一次代码解读。
首先，问题的关键在于如何根据权重来生成一个合理的概率分布。假设我们有一些物品，每个物品都有一个不同的权重，权重越大的物品被选择的概率就越高。直接生成一个随机数是没用的，因为我们需要让这些物品被选中的概率与它们的权重成正比。
为了简化，假设我们有一个物品列表，每个物品的权重已经给定了，比如：
class Item {
String name;
int weight; public Item(String name, int weight) {
this.name = name;
this.weight = weight;
}
}
接下来，我们来实现按权重随机选择的功能。最直接的思路是利用权重的累计和一个随机数来进行选择。
步骤 1: 计算权重的累计和
我们首先需要计算出所有物品权重的总和。然后根据每个物品的权重在这个总和中的比例来确定它的选择概率。
import java.util.*;public class WeightedRandom {
private List<Item> items;
private int totalWeight;
public WeightedRandom(List<Item> items) {
this.items = items;
this.totalWeight = 0;
for (Item item : items) {
totalWeight += item.weight;
}
}
public Item getRandomItem() {
Random random = new Random();
int randomValue = random.nextInt(totalWeight) + 1; // 生成 1 到 totalWeight 之间的随机数
int accumulatedWeight = 0;
for (Item item : items) {
accumulatedWeight += item.weight;
if (randomValue <= accumulatedWeight) {
return item; // 如果随机数落在这个物品的权重范围内，则返回这个物品
}
}
return null; // 逻辑上不应该到这里，避免返回空
}
public static void main(String[] args) {
List<Item> items = Arrays.asList(
new Item("Item1", 1),
new Item("Item2", 4),
new Item("Item3", 2)
);
WeightedRandom weightedRandom = new WeightedRandom(items);
// 模拟随机选择
for (int i = 0; i < 10; i++) {
Item selectedItem = weightedRandom.getRandomItem();
System.out.println("Selected Item: " + selectedItem.name);
}
}
}
代码解析：
计算总权重：首先遍历所有的物品，计算出权重总和。这个总和是我们后面计算随机数的基础。 生成随机数：我们使用 Random类生成一个 1 到总权重范围内的随机数。这个随机数决定了我们选择哪个物品。选择物品：我们通过遍历物品列表，累加每个物品的权重，直到累加的权重大于或等于随机数。此时，当前物品就是我们选择的物品。
步骤 2: 运行结果
假设我们的物品列表是：
Item1 权重为 1 Item2 权重为 4 Item3 权重为 2
那么它们的选择概率分别是：
Item1 的概率为 1/7 Item2 的概率为 4/7 Item3 的概率为 2/7
你会发现，运行这段代码时，Item2 被选择的几率明显比其他两个大，这是因为它的权重大呀！🎉
注意事项：
这个方法的时间复杂度是 O(n)，其中 n 是物品的数量。因为我们每次选择物品都要遍历一遍列表。 这种方法适用于物品数量不特别大的场景。如果你有几百万个物品，或者频繁进行选择，可能会需要优化。一个常见的优化方式是使用前缀和来减少每次选择的时间复杂度。
优化（前缀和法）：
如果物品数量非常大，我们可以在初始化时计算一个前缀和数组，用这个数组来快速定位一个随机数应该落在哪个物品上。具体来说，就是维护一个数组 prefixSums，它的第 i 个元素表示前 i 个物品的权重总和，然后通过二分查找来找到随机数对应的物品。
不过考虑到这个问题比较复杂，在这里就不展开了。感兴趣的小伙伴可以自己去查资料，或者等我下次给大家分享如何用前缀和加速选择过程！
-END-
以上，就是今天的分享了，看完文章记得右下角给何老师点赞，也欢迎在评论区写下你的留言。