文章目錄
- 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
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
