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)
20220130 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 thumbsup 】【 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
Original title transmission gate ：https://leetcodecn.com/problems/nayingbi/
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
The sidebar is recommended
 Python notes (20): built in highorder functions
 Python notes (17): closure
 Python notes (18): decorator
 Python notes (16): generators and iterators
 Python notes (XV): List derivation
 Python tells you what timing attacks are
 Python  file and exception
 [Python from introduction to mastery] (IV) what are the builtin data types of Python? Figure out
 Python code to scan code to pay attention to official account login
 [algorithm learning] 1221 Split balanced string (Java / C / C + + / Python / go / trust)
guess what you like

Python notes (22): errors and exceptions

Python has been hidden for ten years, and once image recognition is heard all over the world

Python notes (21): random number module

Python notes (19): anonymous functions

Use Python and OpenCV to calculate and draw twodimensional histogram

Python, Hough circle transformation in opencv

A library for reading and writing markdown in Python: mdutils

Datetime of Python time operation (Part I)

The most useful decorator in the python standard library

Python iterators and generators
Random recommended
 [Python from introduction to mastery] (V) Python's builtin data types  sequences and strings. They have no girlfriend, not a nanny, and can only be used as dry goods
 Does Python have a, = operator?
 Go through the string common sense in Python
 Fanwai 4 Handling of mouse events and solutions to common problems in Python opencv
 Summary of common functions for processing strings in Python
 When writing Python scripts, be sure to add this
 Python web crawler  Fundamentals (1)
 Pandas handles duplicate values
 Python notes (23): regular module
 Python crawlers are slow? Concurrent programming to understand it
 Parameter passing of Python function
 Stroke tuple in Python
 Talk about ordinary functions and higherorder functions in Python
 [Python data acquisition] page image crawling and saving
 [Python data collection] selenium automated test framework
 Talk about function passing and other supplements in Python
 Python programming simulation poker game
 leetcode 160. Intersection of Two Linked Lists （python）
 Python crawler actual combat, requests module, python to grab the beautiful wallpaper of a station
 Fanwai 5 Detailed description of slider in Python opencv and solutions to common problems
 My friend's stock suffered a terrible loss. When I was angry, I crawled the latest data of securities with Python
 Python interface automation testing framework  if you want to do well, you must first sharpen its tools
 Python multi thread crawling weather website pictures and saving
 How to convert pandas data to excel file
 Python series tutorials 122
 Python Complete Guide  printing data using pyspark
 Python Complete Guide  tuple conversion array
 Stroke the list in python (top)
 Analysis of Python requests module
 Comments and variables in Python
 New statement match, the new version of Python is finally going to introduce switch case?
 Fanwai 6 Different operations for image details in Python opencv
 Python crawler native code learning (I)
 Python quantitative data warehouse building series 2: Python operation database
 Python code reading (Part 50): taking elements from list intervals
 Pyechart + pandas made word cloud pictures of 19 report documents
 [Python crawler] multithreaded daemon & join() blocking
 Python crawls cat pictures in batches to realize thousand image imaging
 Van * Python  simple crawling of a planet
 Input and output of Python practice