This is the second day of my participation in the November Gwen Challenge. Check out the details: the last Gwen Challenge 2021

Thank you very much for reading this article. Welcome [👍 like] [⭐ collect] [📝 comment] ~ Give up is not difficult, But insists it must be very cool ~ hope we all can be a little bit of progress every day ~ in this paper, from two headed white hat original ~ https://juejin.cn/user/2771185768884824/posts blog

LCP 06. Take coins:

There are n stacks of coins on the table, and the amount of each stack is stored in the array Coins. We can choose any pile at a time, take one or two of the coins, and find the minimum number of times to use up the strong deduction.

Sample 1

Input: [4,2,1] Output: 4 Explanation: The first pile of force deduction coins need to be taken at least twice, the second pile needs to be taken at least once, the third pile needs to be taken at least once, a total of 4 times.Copy the code

The sample 2

Input: [2,3,10] output: 8Copy the code

prompt

  • 1 <= n <= 4
  • 1 <= coins[i] <= 10

Analysis of the

  • This algorithm problem two master I believe we can make it, but has not been carefully optimized?
  • Pick any pile at a time, and obviously each pile has no effect on the other, so adding up the minimum number of times you pick each pile is the desired result.
  • You can take one or two coins at a time, but if you have an odd number of coins, you can only take one coin at the last time.
  • If you go straight into 2, the odd number is going to be counted one less time, so we have to figure out whether it’s odd or even, and if it’s odd we have to count it one more time.
  • Is it possible to uniformly deal with odd and even numbers? You can just add and divide by two(coins[i] + 1) / 2. If it is originally even, it does not affect the result of divisible by 2. If it is odd, it increases the result of divisible by 2 by one.
  • Bit operations are faster than arithmetic operations, so we can optimize to(coins[i] + 1) >> 1.

Answer key

java

class Solution {
    public int minCount(int[] coins) {
        int ans = 0;
        for (int c : coins) {
            ans += (c + 1) > >1;
        }
        returnans; }}Copy the code

c

int minCount(int* coins, int coinsSize){
    int ans = 0;
    for (int i = 0; i < coinsSize; ++i) {
        ans += (coins[i] + 1) > >1;
    }
    return ans;
}
Copy the code

c++

class Solution {
public:
    int minCount(vector<int>& coins) {
        int ans = 0;
        for (int& c : coins) {
            ans += (c + 1) > >1;
        }
        returnans; }};Copy the code

python

class Solution:
    def minCount(self, coins: List[int]) - >int:
        return sum([(c + 1) > >1 for c in coins])
Copy the code

go

func minCount(coins []int) int {
    ans := 0
	for _, c := range coins {
		ans += (c + 1) > >1
	}
	return ans
}
Copy the code

rust

impl Solution {
    pub fn min_count(coins: Vec<i32- > >)i32 {
        coins.iter().map(|c|{
            (c + 1) > >1
        }).sum()
    }
}
Copy the code

Portal: https://leetcode-cn.com/problems/na-ying-bi/