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
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
The sidebar is recommended
- Python notes (20): built in high-order 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 built-in 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 two-dimensional 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 built-in 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 higher-order 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