当前位置:网站首页>Leetcode study - day 35
Leetcode study - day 35
2022-07-06 00:58:00 【Scholar's dream】
Day 35
I use C++, Sorry for the mistake , The original intention of this article is only to urge me to study , If it happens to help you , I will be very happy .
List of articles
One 、1143. Longest common subsequence
Give you an array of integers coins , Coins of different denominations ; And an integer amount , Represents the total amount .
Calculate and return the amount needed to make up the total amount The minimum number of coins . If no combination of coins can make up the total amount , return -1 .
You can think of the number of coins of each kind as infinite .
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/coin-change
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
My first thought is to decrease from the maximum face value , It turns out that such an approach cannot find a combination that meets the conditions , Many elements will be missed , Just looking for the minimum number , But missed the combination that might make up enough . Greed alone is not enough
class Solution {
public:
int coinChange(vector<int>& coins, int amount) {
// First spell with the one with the a large face value
int n = coins.size(), cnt = 0;
sort(coins.begin(), coins.end());
for (int i = n - 1; i >= 0; --i){
while(amount >= coins[i]){
amount -= coins[i];
++cnt;
}
}
if (amount == 0){
return cnt;
}
else {
return -1;
}
}
};
Two 、12. Integer to Roman number
Roman numerals contain the following seven characters : I, V, X, L,C,D and M.
character The number
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
for example , Rome digital 2 Write to do II , Two parallel 1.12 Write to do XII , That is to say X + II . 27 Write to do XXVII, That is to say XX + V + II .
Usually , The small numbers in roman numbers are to the right of the big ones . But there are special cases , for example 4 Do not write IIII, It is IV. Numbers 1 In number 5 Left side , The number represented is equal to the large number 5 Decimal reduction 1 Value obtained 4 . similarly , Numbers 9 Expressed as IX. This special rule only applies to the following six cases :
I Can be placed in V (5) and X (10) Left side , To express 4 and 9.
X Can be placed in L (50) and C (100) Left side , To express 40 and 90.
C Can be placed in D (500) and M (1000) Left side , To express 400 and 900.
Give you an integer , Turn it into Roman numerals .
source : Power button (LeetCode)
link :https://leetcode-cn.com/problems/integer-to-roman
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .
class Solution {
public:
string intToRoman(int num) {
// Check from high position , Special if yes 4、9, Need special treatment
const pair<int, string> Roman[] = {
{
1000, "M"},
{
900, "CM"},
{
500, "D"},
{
400, "CD"},
{
100, "C"},
{
90, "XC"},
{
50, "L"},
{
40, "XL"},
{
10, "X"},
{
9, "IX"},
{
5, "V"},
{
4, "IV"},
{
1, "I"},
};
string ans;
for (auto &[value, str] : Roman){
while (num >= value){
num -= value;
ans += str;
}
if (num == 0){
break;
}
}
return ans;
}
};
3、 ... and 、13. Roman numeral to integer
class Solution {
public:
unordered_map<char, int> Roman = {
{
'M', 1000},
{
'D', 500},
{
'C', 100},
{
'L', 50},
{
'X', 10},
{
'V', 5},
{
'I', 1},
};
int romanToInt(string s) {
// The key is to 4、9 To deal with
int n = s.size(), ans = 0;
for (int i = 0; i < n; ++i){
int value = Roman[s[i]];
if (i < n - 1 && value < Roman[s[i + 1]]){
// appear 4、9 The situation of
ans -= value;
}
else {
ans += value;
}
}
return ans;
}
};
边栏推荐
- Analysis of the combination of small program technology advantages and industrial Internet
- 测试/开发程序员的成长路线,全局思考问题的问题......
- Free chat robot API
- 猿桌派第三季开播在即,打开出海浪潮下的开发者新视野
- 关于#数据库#的问题:(5)查询库存表中每本书的条码、位置和借阅的读者编号
- For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
- Spark DF增加一列
- Kotlin core programming - algebraic data types and pattern matching (3)
- Pbootcms plug-in automatically collects fake original free plug-ins
- Spark AQE
猜你喜欢
How to use the flutter framework to develop and run small programs
[groovy] JSON serialization (convert class objects to JSON strings | convert using jsonbuilder | convert using jsonoutput | format JSON strings for output)
Spark SQL null value, Nan judgment and processing
For a deadline, the IT fellow graduated from Tsinghua suddenly died on the toilet
MCU realizes OTA online upgrade process through UART
Idea远程提交spark任务到yarn集群
Model analysis of establishment time and holding time
282. Stone consolidation (interval DP)
Introduction to robotics I. spatial transformation (1) posture, transformation
Free chat robot API
随机推荐
视频直播源码,实现本地存储搜索历史记录
Gartner released the prediction of eight major network security trends from 2022 to 2023. Zero trust is the starting point and regulations cover a wider range
cf:C. The Third Problem【关于排列这件事】
curlpost-php
在产业互联网时代,将会凭借大的产业范畴,实现足够多的发展
Intensive learning weekly, issue 52: depth cuprl, distspectrl & double deep q-network
图解网络:TCP三次握手背后的原理,为啥两次握手不可以?
Set data real-time update during MDK debug
Yolov5, pychar, Anaconda environment installation
详细页返回列表保留原来滚动条所在位置
curlpost-php
Why can't mathematics give machine consciousness
Cloud guide DNS, knowledge popularization and classroom notes
[day 30] given an integer n, find the sum of its factors
golang mqtt/stomp/nats/amqp
A preliminary study of geojson
2020.2.13
Mobilenet series (5): use pytorch to build mobilenetv3 and learn and train based on migration
Cf:d. insert a progression [about the insert in the array + the nature of absolute value + greedy top-down]
Arduino hexapod robot