文章目录
- 1. 最小+1次数使得列表中的数字互异（Hash）
- 2. 数组排序，使得交换的次数最少
- 3. 按优先级排序（分奇偶）
- 4. 投骰子求期望（求期望）
1. 最小+1次数使得列表中的数字互异（Hash）
给定字符串 A，A 是由逗号分割的数字串，A可以解析成整数数组 B。每次操作可以选择任意 B[i]，并将其递增 1。返回使 B 中的每个值都是唯一的最少操作次数。
eg：
A 为 [1,2,3,4,5]
返回 0
A 为 [1,2,2]
返回 1
思路：这个题来是 Sina 的笔试，用 hash 表，冲突的就往旁边的空坑填
# coding=utf-8
import
sys
def
minIncrementForUnique
(
A
)
:
"""
:type A: List[int]
:rtype: int
"""
total_nums
=
{
}
# 建立 hash 表
min_sum_nums
=
0
# 统计最少移动的次数
unique_nums
=
set
(
A
)
for
item
in
unique_nums
:
# 一个数字一个坑
total_nums
[
item
]
=
1
for
item
in
unique_nums
:
A
.
remove
(
item
)
leave_nums
=
A
[
:
]
# 所有有冲突（重复）的数字
for
i
in
leave_nums
:
# 遍历重复的元素，往移动，填 hash 表
if
total_nums
.
get
(
i
)
==
None
:
total_nums
[
i
]
=
1
else
:
while
(
total_nums
.
get
(
i
)
==
1
)
:
# 坑被占了，就+1看看下一个坑
i
+=
1
min_sum_nums
+=
1
# 移动次数加1
total_nums
[
i
]
=
1
# 占坑
return
min_sum_nums
调用
a
=
minIncrementForUnique
(
[
1
,
2
,
2
]
)
print
(
a
)
结果
1
2. 数组排序，使得交换的次数最少
给定一个数列，通过交换任意两个元素给数列重新排序，求最少需要多少次交换，能把数组排成升序！
输入第一行数列元素的个数
第二行数列
输出最小交换次数
eg；
输入
5
5 4 3 2 1
输出
2
这个题是优图的笔试。
思路：如果 n 个元素不重复，每次交换保证一个错位的回到他应该的位置
n
=
int
(
input
(
)
)
nums
=
list
(
map
(
int
,
input
(
)
.
split
(
" "
)
)
)
sorted_nums
=
sorted
(
nums
)
count
=
0
for
i
in
range
(
len
(
nums
)
)
:
# 遍历
if
nums
[
i
]
!=
sorted_nums
[
i
]
:
# 遇到错位的
for
j
in
range
(
i
,
len
(
nums
)
)
:
# nums[i]的归处
if
nums
[
i
]
==
sorted_nums
[
j
]
:
break
nums
[
i
]
,
nums
[
j
]
=
nums
[
j
]
,
nums
[
i
]
# 和他的归处交换
count
+=
1
print
(
count
)
上面的代码对有重复元素的不太 work。看看下面的解法
#include
参考
https://blog.csdn.net/kaiweisun/article/details/84053797
3. 按优先级排序（分奇偶）
偶数优先级高于奇数，大的数字的优先级高于小的数字
-
输入
数字（逗号隔开）；n -
输出
优先级最高的前 n 个数 -
示例
输入
1,2,3,4,5;2
输出
4,2
（拼多多）思路：这个很简单，注意输入输出的格式就行了
inputs
=
input
(
)
.
split
(
";"
)
array
=
inputs
[
0
]
k
=
int
(
inputs
[
1
]
)
nums
=
list
(
map
(
int
,
array
.
split
(
","
)
)
)
odd
=
[
]
# 偶数, 哈哈哈，odd 明明是奇数的意思，算了
s
=
[
]
# 奇数，偶数单词是 even
for
i
in
range
(
len
(
nums
)
)
:
# 奇偶分开
if
nums
[
i
]
%
2
==
0
:
odd
.
append
(
nums
[
i
]
)
else
:
s
.
append
(
nums
[
i
]
)
odd
=
sorted
(
odd
,
reverse
=
True
)
# 排序
s
=
sorted
(
s
,
reverse
=
True
)
for
i
in
range
(
len
(
s
)
)
:
odd
.
append
(
s
[
i
]
)
output
=
""
for
i
in
odd
[
:
k
]
:
output
+=
str
(
i
)
output
+=
','
print
(
output
[
:
-
1
]
)
4. 投骰子求期望（求期望）
扔 n 个骰子，第 i 个骰子有可能投掷出 x i x_i x i 种等概率的不同的结果，数字从 1 到 x i x_i x i 。所有骰子的结果的最大值将作为最终的结果，求最终结果的期望！
-
输入描述：
第一行整数 n n n ，表示 n n n 个骰子。 n ∈ [ 1 , 50 ] n \in [1,50] n ∈ [ 1 , 5 0 ]
第二行 n n n 个整数，表示每个骰子的结果 x i x_i x i 。 x i ∈ [ 2 , 50 ] x_i \in [2,50] x i ∈ [ 2 , 5 0 ] -
输出描述：
输出最终结果的期望，保留两位小数。 -
示例
输入
2
2 2
输出
1.75
（拼多多）思路：这个题目看了好久才看懂，意思是这样的，投 n 个骰子，每个骰子的最大值是第二行的结果，然后算最终结果的期望，期望怎么算呢？就是最终结果为 1 的概率乘 1，加最终结果为 2 的概率乘 2，加最终结果为 3 的概率乘以 3……
剖析下例子，两个骰子都只有两面，最终结果为 1 的概率是 1 / 2 ∗ 1 / 2 = 1 / 4 1/2 * 1/2 = 1/4 1 / 2 ∗ 1 / 2 = 1 / 4 ，最终结果为 2 的概率是 2 / 2 ∗ 2 / 2 − 1 / 4 = 3 / 4 2/2 * 2/2 - 1/4 = 3/4 2 / 2 ∗ 2 / 2 − 1 / 4 = 3 / 4 （-1/4就是减去全部为1的情况，不行你枚举，最大值是2的时候，确实是三种情况，1-2，2-1，2-2），所以期望为 1 ∗ 1 / 4 + 2 ∗ 3 / 4 = 1.75 1*1/4 + 2*3/4 = 1.75 1 ∗ 1 / 4 + 2 ∗ 3 / 4 = 1 . 7 5
再来个例子
3
2 2 3
结果为
2.25
解析：第一个骰子两面，第二个骰子两面，第三个骰子三面
结果为 1 的概率是：
1 / 2 ∗ 1 / 2 ∗ 1 / 3 = 1 / 12 1/2 *1/2 *1/3 = 1/12
1
/
2
∗
1
/
2
∗
1
/
3
=
1
/
1
2
结果为 2 的概率是：
2 / 2 ∗ 2 / 2 ∗ 2 / 3 − 结 果 为 1 的 概 率 = 7 / 12 2/2*2/2*2/3 - 结果为1的概率 = 7/12
2
/
2
∗
2
/
2
∗
2
/
3
−
结
果
为
1
的
概
率
=
7
/
1
2
（穷举的话确实是 7 种情况）
结果为 3 的概率是：
3 / 3 − 结 果 为 1 的 概 率 − 结 果 为 2 的 概 率 = 4 / 12 3/3 - 结果为1的概率 - 结果为2的概率 = 4/12
3
/
3
−
结
果
为
1
的
概
率
−
结
果
为
2
的
概
率
=
4
/
1
2
期望为 1 ∗ 1 / 12 + 2 ∗ 7 / 12 + 3 ∗ 5 / 12 = 9 / 4 = 2.25 1*1/12 + 2*7/12 + 3*5/12 = 9/4 = 2.25 1 ∗ 1 / 1 2 + 2 ∗ 7 / 1 2 + 3 ∗ 5 / 1 2 = 9 / 4 = 2 . 2 5
n
=
int
(
input
(
)
)
a
=
list
(
map
(
int
,
input
(
)
.
split
(
)
)
)
a
.
sort
(
)
# 按照骰子的面数排序
j
=
0
res
=
[
0
]
*
a
[
-
1
]
# 建立数组，存放结果的概率
for
i
in
range
(
1
,
a
[
-
1
]
+
1
)
:
# 结果取 i 时
s
=
1
while
a
[
j
]
<
i
:
# 把小于 i 的去掉，因为最大面为2的不可能投出来 3
j
+=
1
for
k
in
range
(
j
,
len
(
a
)
)
:
# 遍历数组
s
*=
i
/
a
[
k
]
# 计算概率，eg 2/2 * 2/2 * 2/3
s
-=
sum
(
res
)
# eg 排除全为 1 的情况 2/2 * 2/2 * 2/3 - 1/2 * 1/2 * 1/3
res
[
i
-
1
]
=
s
# 概率存放在列表中
res1
=
0
for
i
in
range
(
a
[
-
1
]
)
:
res1
+=
(
i
+
1
)
*
res
[
i
]
# 计算期望
print
(
'%.2f'
%
res1
)
# 注意输出的格式
代码来自 https://www.nowcoder.com/discuss/241391?type=post&order=time&pos=&page=1
