当前位置:网站首页>Niuke real problem programming - day14
Niuke real problem programming - day14
2022-07-07 14:52:00 【weixin_ forty-five million seven hundred and fifty thousand fou】
Programming environment :c++
1、 String value
describe : There is an interesting way to calculate the value of strings : Count the number of occurrences of each character in the string , Then find the sum of the squares of the number of all characters as the value of the string
for example : character string "abacaba", includes 4 individual 'a',2 individual 'b',1 individual 'c', So the value of this string is 4 * 4 + 2 * 2 + 1 * 1 = 21
Niuniu has a string s, And allow you to start from s Remove up to k Characters , Your goal is to minimize the value of the resulting string .
Algorithmic thought :
According to the title requirements , To remove the fixed number of characters , Strings are the least valuable , Then each time you remove the character that appears the most times in the current string . First, count the number of characters in the string , After removing one at a time , You need to reorder the array that counts the number of character occurrences , Make sure that each overflow is the string with the most occurrences . Finally, according to the string value formula , Calculate the minimum value of the final string .
Part of the code implementation :
2、 Under the kitchen
describe :
Niuniu wants to try some new dishes , Each dish needs some different materials , Ask how many different materials need to be prepared to complete all the dishes .
Input description : Each input contains 1 Test cases . The... Of each test case i That's ok , To complete the first i What materials are needed for this dish , Each material is separated by a space , The input contains only uppercase letters and spaces , Input files do not exceed 50 That's ok , No more than... Per line 50 Characters .
Algorithmic thought :
The number of lines entered in the title is uncertain , You need to decide whether there is any string input , Here I omit the concept of line , Store all the ingredients you need into a string array . For all ingredients , We need to de duplicate it , Get the number of ingredients you need to prepare . First, sort all strings , Then the same ingredients will come together , Traverse the sorted string array , When adjacent elements are different , It represents different ingredients ( Count +1). The number of ingredients required after weight removal is obtained after traversal .
3、 Asset package packaging
describe :
In financial asset transactions , It often involves the selection and packaging of asset packages . In the process of asset package packaging , Each type of asset has a fixed quantity and value , You need to select some assets to package , Maximize the total value of the asset package . When packaging, each asset can only be packaged as a whole , Indivisible . It is assumed that the existing can accommodate M Asset package of assets , In addition, there are N Types of assets . assets Na The number of Ta strip , The total value is Va element ; assets Nb The number of Tb strip , The total value is Vb element ; assets Nc The number of Tc strip , The total value is Vc element ......; assets Nn The number of Tn, The total value is Vn. Write algorithms , Choosing which types of assets to put into the asset package can maximize the total value of the asset package ?
Algorithmic thought :
Because the asset package can only be placed as a whole or not , So the topic is actually a 0/1 Dynamic programming of knapsack . set up j Is the total capacity ,wi For the first time i The weight of each item . If the total capacity of the backpack j Less than i Space occupied by items , The maximum value that can be obtained at this time is equivalent to considering 1 To the first i-1 The total storage capacity of items is j The backpack . otherwise , You can choose to put it or not i Item : If you don't put the first i Item , At this time, the maximum value and only put the front i-1 Same piece ; The first i When items are put into the backpack , The total capacity is j Your backpack must be allocated wi Space for i Item , And before the first 1 To the first i-1 Items can only be placed with a total capacity of j-wi In my backpack , The greater of the two cases . Initialize a result array dp, There's recursion :dp(i,j)=max {dp(i-1, j),dp(i-1, j-w)+vi}
The code part implements :
边栏推荐
- MicTR01 Tester 振弦采集模塊開發套件使用說明
- Apache multiple component vulnerability disclosure (cve-2022-32533/cve-2022-33980/cve-2021-37839)
- Navigation - are you sure you want to take a look at such an easy-to-use navigation framework?
- 13 ux/ui/ue best creative inspiration websites in 2022
- Ian Goodfellow, the inventor of Gan, officially joined deepmind as research scientist
- EfficientNet模型的完整细节
- 《微信小程序-进阶篇》组件封装-Icon组件的实现(一)
- Démontage de la fonction du système multi - Merchant Mall 01 - architecture du produit
- Instructions for mictr01 tester vibrating string acquisition module development kit
- What is the process of ⼀ objects from loading into JVM to being cleared by GC?
猜你喜欢
《微信小程序-进阶篇》组件封装-Icon组件的实现(一)
Apache multiple component vulnerability disclosure (cve-2022-32533/cve-2022-33980/cve-2021-37839)
用于增强压缩视频质量的可变形卷积密集网络
Leetcode one question per day (636. exclusive time of functions)
Pytorch model trains practical skills and breaks through the bottleneck of speed
今日睡眠质量记录78分
C 6.0 language specification approved
大厂做开源的五大痛点
拼多多败诉,砍价始终差0.9%一案宣判;微信内测同一手机号可注册两个账号功能;2022年度菲尔兹奖公布|极客头条...
WebRTC 音频抗弱网技术(上)
随机推荐
Es log error appreciation -maximum shards open
《微信小程序-进阶篇》组件封装-Icon组件的实现(一)
#yyds干货盘点# 解决名企真题:交叉线
「2022年7月」WuKong编辑器更版记录
FFmpeg----图片处理
半小时『直播连麦搭建』动手实战,大学生技术岗位简历加分项get!
Applet directory structure
WebRTC 音频抗弱网技术(上)
A laravel background management expansion package you can't miss - Voyager
大厂做开源的五大痛点
Read PG in data warehouse in one article_ stat
[server data recovery] a case of RAID data recovery of a brand StorageWorks server
Reading and understanding of eventbus source code
Cocoscreator operates spine for animation fusion
PAG体验:十分钟完成AE动效部署上线各平台!
How does the database perform dynamic custom sorting?
昇腾体验官第五期随手记I
Mlgo: Google AI releases industrial compiler optimized machine learning framework
MicTR01 Tester 振弦采集模塊開發套件使用說明
比尔·盖茨晒48年前简历:“没你们的好看”