current position:Home>[algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)

[algorithm learning] LCP 06 Take coins (Java / C / C + + / Python / go / trust)

2022-01-30 23:50:21 White hat of the second leader

This is my participation 11 The fourth of the yuegengwen challenge 2 God , Check out the activity details :2021 One last more challenge

Thank you very much for reading this article ~ welcome 【 give the thumbs-up 】【 Collection 】【 Comment on 】~ It's not hard to give up , But persistence must be cool ~ I hope all of us can make a little progress every day ~ This paper is written by The white hat of the second leader https://juejin.cn/user/2771185768884824/posts Original blog ~


LCP 06. Take the coin :

It's on the table n Money is deducted from the pile , The number of each heap is stored in the array coins in . We can choose any pile at a time , Take one or two of them , Ask for the minimum number of times to deduct money from all efforts .

Examples 1

 Input :
	[4,2,1]
	
 Output :
	4

 explain :
	 The first pile of force deduction coins needs to take at least  2  Time , The second pile needs at least  1  Time , The third pile needs at least  1  Time , in total  4  You can get it all at once .
 Copy code 

Examples 2

 Input :
	[2,3,10]

 Output :
	8
 Copy code 

Tips

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

analysis

  • This algorithm problem two is in charge. I believe everyone can do it , But it has been carefully optimized ?
  • Pick one at a time , Obviously, each pile does not affect each other , So it is the desired result to accumulate and calculate the sum of at least several times for each pile .
  • You can take one or two at a time , Children also know how to take more , It must be the fastest to take two at a time , But if a pile of coins is odd , Then you can only take one at the last time .
  • Direct division 2 Words , Odd numbers will be counted less once , So we need to judge odd or even , If it's an odd number, count it again .
  • Can we handle odd and even numbers in a unified way ? You can directly add and divide again and again to two (coins[i] + 1) / 2. If it was even , Then it does not affect the division by 2 Result , If it is an odd number, it will divide the whole by 2 Add one... To the result .
  • Bit operations are faster than arithmetic operations , So we can optimize it 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;
        }
        return ans;
    }
}
 Copy 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 code 

c++

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

python

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

go

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

rust

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

 Insert picture description here


Original title transmission gate :https://leetcode-cn.com/problems/na-ying-bi/


copyright notice
author[White hat of the second leader],Please bring the original link to reprint, thank you.
https://en.pythonmana.com/2022/01/202201302350191752.html

Random recommended