簡單的算法,也有複雜的一面~
二分查找#
①樸素二分#
- 找一個精確對應的值
兩種情況 | 整數 | 浮點數 |
---|---|---|
while 條件 | L <= R | R - L > 0.00001 精確到小數點後4位 |
更新參數 | 更新公式 | 更新公式 |
mid | (L + R) / 2 為了避免溢出👇 ((long long) L + R) / 2 L + (R - L) / 2 | (L + R) / 2 |
L | mid + 1 | mid |
R | mid - 1 | mid |
- 浮點數情況放在②、③也成立
②⭐特殊二分#
- 找 0、1 的交界處的 1
兩種情況 | 000000111111 | 111111100000 |
---|---|---|
while 條件 | L != R 或者 L < R (不能是 L <= R,不會有 L> R 的情況) | 同左 |
更新參數 | 更新公式 | 更新公式 |
mid | (L + R) / 2 | (L + R + 1) / 2 (避免遇到 1 0 死循環) |
L | mid + 1 | mid (mid 可能是答案) |
R | mid (mid 可能是答案) | mid - 1 |
- C++ 裡實際帶有實現這個功能的函數
- lower_bound、upper_bound
- 參考關於 lower_bound () 和 upper_bound () 的常見用法-CSDN
③⭐⭐二分答案#
- 特殊二分+func (答案)
- 根據答案才得到判斷更新條件的值 func (答案)
- 判斷更新條件的值一般隱含著有序的條件
- 所以是否 sort 跟 func 求解方便與否有關,不是必須
HZOJ-380:大統領投票(sort)#
範例輸入
3
123456799
123456789132456789123456789
11111111111111
範例輸出
2
123456789132456789123456789
- 思路
- 票數很大,要作為字符串讀入,使用 string 類
- string 類重載了>,自帶字典序比較
- 利用 struct 類,結合對應的編號
- 利用 sort
- 先比較長度,strlen
- 長度一致,則使用字典序
- 票數很大,要作為字符串讀入,使用 string 類
- 代碼
-
- const node &a 的 & 是傳引用,可以刪去,但要加 const~
- 必須判斷長度,否則 53 比 12345 的字典序大
- 索引從 1 開始,否則引入了 (0, 0)
-
HZOJ-381:誰拿了最多獎學金(sort)#
範例輸入
4
YaoLin 87 82 Y N 0
ChenRuiyi 88 78 N Y 1
LiXin 92 88 N N 0
ZhangQin 83 87 Y N 1
範例輸出
ChenRuiyi
9000
28700
-
思路
- 獎金並列第一時,輸出最早出現的
- 所以要記錄編號,sort 是不穩定的
- 注意獎金計算規則細節即可
- 獎金並列第一時,輸出最早出現的
-
代碼
-
HZOJ-386:吃瓜群眾(①)#
範例輸入
5 3
1 3 26 7 15
26 99 3
範例輸出
3
0
2
- 思路
- 排序 + 樸素二分
- 瓜的數量和編號需揉成 struct
- 代碼
-
- mid 計算公式,防止溢出
- = ((long long)l + r) / 2
- = l + (r - l) / 2
- 沒找到就輸出 0,f 初始為 0
-
HZOJ-387:吃瓜群眾升級版(②)#
範例輸入
5 5
1 3 26 7 15
27 10 3 4 2
範例輸出
0
5
2
4
2
- 思路
- 抽象為一堆 0、一堆 1,找第一個為 1 的情況
- 考慮輸出 0 的情況
- 代碼
-
- 有兩種處理輸出 0 的情況
- 000000011111111
-
Leetcode-278:第一個錯誤的版本(②)#
示例
給定 n = 5,並且 version = 4 是第一個錯誤的版本。
調用 isBadVersion(3) -> false
調用 isBadVersion(5) -> true
調用 isBadVersion(4) -> true
所以,4 是第一個錯誤的版本。
- 思路
- 用特殊二分查找做
- 000000011111111
- 代碼
class Solution {
public:
int firstBadVersion(int n) {
int l = 1, r = n; // 版本號從1開始
while (l != r) {
int mid = ((long long)l + r) / 2; // 防止溢出方式一
// int mid = l + (r - l) / 2; // 防止溢出方式二
if (isBadVersion(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
};
HZOJ-390:原木切割(③)#
範例輸入
3 8
6
15
22
範例輸出
5
- 思路
- 左界→右界:1→max (Xi)
- 111111110000000
- ③ = ② + func(mid)
- func (mid):根據 mid 求出可以切出的段數,長度 mid 是要求的答案
- 代碼
-
- 右界需要確定一下,輸入的時候確定
-
HZOJ-389:暴躁的程序猿(③)#
範例輸入
5 3
1
2
8
4
9
範例輸出
3
- 思路
- 距離的上下界:1→max (Xi)
- 為了簡單,直接取1 和最大的工位編號
- 如果要精細,可以取最小和最大的工位編號之差
- 答案→判斷依據:距離→可以安排的人數
- 111111100000
- 距離的上下界:1→max (Xi)
- 代碼
-
- 排序了才好根據距離算可安排人數
- func()
- 要記錄上一个安排的人的位置 last
- 求可安排的人數 s
- 初始化:可安排人數 s 為 1,上一个安排的人的位置 last 為 num [0]
-
HZOJ-393:切繩子(小數③)#
範例輸入
4 11
8.02
7.43
4.57
5.39
範例輸出
2.00
- 思路
- 類似原木切割,但是數據是浮點數
- 條件、更新公式不一樣
- 確定查找的左右邊界、根據答案得判斷依據
- 類似原木切割,但是數據是浮點數
- 代碼
-
- 浮點數二分查找
- 直接舍掉小數點後 2 位後的數字的思路
- 思路一:*100→轉 int→除以 100.0→設置精度 %.2f
- 思路二:-0.005→設置精度 %.2f
- 供參考:C++ 取整:向下取整,向上取整,四捨五入取整,直接去小數點取整-CSDN
- %.2f、都是四捨五入機制
- 轉 int:直接去掉小數點及後面的小數取整
-
HZOJ-82:伐木#
範例輸入
4 9
20 17 15 10
範例輸出
14
- 思路
- 類似原木切割,但判斷依據是切下來的木材是否滿足需要的木材長度
- 上下界:0→max ()
- 注意數據範圍很大,相加有可能溢出,所以使用long long
- long long 要想好位置,如果想不好,可以索性全用
- 代碼
-
- 想清楚答案與判斷依據之間的關係
-
HZOJ-391:數列分段#
範例輸入
5 3
4
2
4
5
1
範例輸出
6
- 思路
- 最小的最大和
- 0000000111111,找第一個 1
- 答案(段數和)mid 小→判斷依據(段數)s 多,不滿足條件,對應 0
- 答案(段數和)mid 大→判斷依據(段數)s 少,算是滿足條件,對應 1
- 因為找的是最小的最大和,考慮交界處
- ❓❗如果是找最大的最大和,就會變成 111110000 情況
- 左右界:max (Ai)→sum (Ai)
- 代碼
-
-
- ⭐func 函數好好琢磨!
- 注意 long long 類型
-
HZOJ-394:跳石頭#
範例輸入
25 5 2
2
11
14
17
21
範例輸出
4
- 思路
- 最短跳躍距離的最大值
- 起點和終點隱含存在:min (D (i+1) - Di)→L(起點到終點的距離)
- 111110000
- 因為找的是最大值,越往右值越大,所以找最後一個 1
- 代碼
-
- 要記得存起點和終點!
- 對遍歷到終點石頭但不會移走終點石頭的思考
- 可以用移走前一塊石頭等效
-
HZOJ-392:丟瓶蓋#
範例輸入
5 3
1
2
3
4
5
範例輸出
2
- 思路
- 與上述暴躁的程序猿一模一樣!
- 代碼
HZOJ-395:複製書稿#
範例輸入
9 3
1 2 3 4 5 6 7 8 9
範例輸出
1 5
6 7
8 9
- 思路
- 每個人的抄書速度都一樣,數字就對應時間
- 必須連續,書不能拆分
- 步驟
- 第一步:求最大值,與上述的數列分段一模一樣!
- 第二步:每個人抄書的起止編號,存在數組裡
- 拿到最大值後,從後往前掃數列
- 如果有多解,讓前面的人少抄寫
- 稍有麻煩,考察代碼功底
- 拿到最大值後,從後往前掃數列
- 代碼
附加知識點#
- C++ 裡的 struct 為類
- 成員訪問權限默認私有,而 struct 默認公有
- sort <algorithm> 使用
int num[105];
sort(num, num + n, cmp);
-
- num:要排序的區間首地址;num + n:區間尾地址的下一地址;cmp:
- ⭐默認是不穩定的
- 底層使用快速排序,結合插入排序和堆排序
- 參考C++ 一道深坑面試題:STL 裡 sort 算法用的是什麼排序算法?- 知乎
- 對於 int、string:可以直接比較大小,默認從小到大排序
- 對於自定義結構
- 重載小於號
- 自己寫排序方法 cmp
bool cmp(node a, node b) {
return a.x > b.x; // 按照node裡的x從大到小排序
}