非常感謝你閱讀本文~
歡迎【👍點贊】【?收藏】【📝評論】~
放棄不難，但堅持一定很酷~
希望我們大家都能每天進步一點點~
本文由 二當家的白帽子 https://le-yi.blog.csdn.net/ 博客原創~
文章目錄
- LCP 06. 拿硬幣：
- 樣例 1
- 樣例 2
- 提示
- 分析
- 題解
- java
- c
- c++
- python
- go
- rust
- 原題傳送門：https://leetcode-cn.com/problems/na-ying-bi/
LCP 06. 拿硬幣：
桌上有 n 堆力扣幣，每堆的數量保存在陣列 coins 中，我們每次可以選擇任意一堆，拿走其中的一枚或者兩枚，求拿完所有力扣幣的最少次數，
樣例 1
輸入：
[4,2,1]
輸出：
4
解釋：
第一堆力扣幣最少需要拿 2 次，第二堆最少需要拿 1 次，第三堆最少需要拿 1 次，總共 4 次即可拿完，
樣例 2
輸入：
[2,3,10]
輸出：
8
提示
- 1 <= n <= 4
- 1 <= coins[i] <= 10
分析
- 這道演算法題二當家的相信大家都能做出來，但是不是已經仔細優化過了呢？
- 每次任意選擇一堆去拿，很顯然每一堆之間互不影響，所以累加計算每一堆最少拿幾次之和就是想要的結果，
- 每次可以拿一枚或兩枚，孩子也知道往多了拿嘛，肯定每次都拿兩枚是最快的，只不過如果某一堆硬幣是奇數，那最后一次就只能拿一枚，
- 直接用二取整除的話，奇數就會少算一次，所以我們需要判斷奇數還是偶數，如果是奇數就要多算一次，
- 是不是可以統一處理奇數和偶數呢？可以直接先加一再用二取整除
(coins[i] + 1) / 2，如果原本是偶數，則不影響取整除的結果，如果是奇數則會使取整除的結果加一， - 位運算要比算術運算快，所以我們可以優化為
(coins[i] + 1) >> 1，
題解
java
class Solution {
public int minCount(int[] coins) {
int ans = 0;
for (int c : coins) {
ans += (c + 1) >> 1;
}
return ans;
}
}
c
int minCount(int* coins, int coinsSize){
int ans = 0;
for (int i = 0; i < coinsSize; ++i) {
ans += (coins[i] + 1) >> 1;
}
return ans;
}
c++
class Solution {
public:
int minCount(vector<int>& coins) {
int ans = 0;
for (int& c : coins) {
ans += (c + 1) >> 1;
}
return ans;
}
};
python
class Solution:
def minCount(self, coins: List[int]) -> int:
return sum([(c + 1) >> 1 for c in coins])
go
func minCount(coins []int) int {
ans := 0
for _, c := range coins {
ans += (c + 1) >> 1
}
return ans
}
rust
impl Solution {
pub fn min_count(coins: Vec<i32>) -> i32 {
coins.iter().map(|c|{
(c + 1) >> 1
}).sum()
}
}
原題傳送門：https://leetcode-cn.com/problems/na-ying-bi/
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/347133.html
標籤：python