当前位置:网站首页>Game 280 of leetcode week
Game 280 of leetcode week
2022-07-05 01:08:00 【Science class people who advocate learning technology】
Blog's front page : Those who advocate learning technology
Today's article is《LeetCode The first 280 Weekly match 》
I hope you guys can finish reading this article patiently
Bloggers are also in the learning stage , If problems are found , Please inform , Thank you very much
At the same time, thank you very much for your support
List of articles
<1> The first question is
subject
obtain 0 The number of operations
Here are two for you non-negative Integers
num1
andnum2
.
Each step operation in , Ifnum1 >= num2
, You have to usenum1
reducenum2
; otherwise , You have to use >num2
reducenum1
.
- for example ,
num1 = 5
Andnum2 = 4
, Should use thenum1
reducenum2
, therefore , obtainnum1 = 1
andnum2 = 4
. However , Ifnum1 = 4
Andnum2 = 5
, After one step operation , obtainnum1 = 4
andnum2 = 1
.Return to make
num1 = 0
ornum2 = 0
Of Operands .
Example
Example 1
:
Input :num1 = 2, num2 = 3
Output :3
explain :
- operation 1 :num1 = 2 ,num2 = 3 . because num1 < num2 ,num2 reduce num1 obtain num1 = 2 ,num2 = 3 - 2 = 1 .
- operation 2 :num1 = 2 ,num2 = 1 . because num1 > num2 ,num1 reduce num2 .
- operation 3 :num1 = 1 ,num2 = 1 . because num1 == num2 ,num1 reduce num2 .
here num1 = 0 ,num2 = 1 . because num1 == 0 , No more action is required .
So the total operand is 3 .
Example 2
:
Input :num1 = 10, num2 = 10
Output :1
explain :
- operation 1 :num1 = 10 ,num2 = 10 . because num1 == num2 ,num1 reduce num2 obtain num1 = 10 - 10 = 0 .
here num1 = 0 ,num2 = 10 . because num1 == 0 , No more action is required .
So the total operand is 1 .
Tips
0 <= num1, num2 <= 10^5
Ideas
Ideas
This question is a sign in question , My approach is to simulate this process , When num1 > num2
when , it num1 = num1 - num2
And count ; When num1 < num2
when , We will num2 = num2 - num1
And count ; If the two numbers are equal, count and exit the loop .
Code implementation
class Solution {
public int countOperations(int num1, int num2) {
int cnt = 0;
while(num1 != 0 && num2 != 0){
if(num1 > num2){
num1 = num1 - num2;
}else if(num1 < num2){
num2 = num2 - num1;
}else{
cnt ++;
break;
}
cnt++;
}
return cnt;
}
}
Running results
<2> The second question is
subject
The minimum number of operands to make an array an alternating array
I'll give you a subscript from
0
Starting arraynums
, The array consists ofn
It's made up of four positive integers .
If the following conditions are met , The arraynums
It's a Alternating array :
nums[i - 2] == nums[i]
, among2 <= i <= n - 1
.nums[i - 1] != nums[i]
, among1 <= i <= n - 1
.In one step operation in , You can choose the subscript
i
And willnums[i]
change by any Positive integer .
Returns the that makes the array an alternating array The minimum number of operands .
Example
Example 1
:
Input :nums = [3,1,3,2,4,3]
Output :3
explain :
One way to turn an array into an alternating array is to convert the array to [3,1,3,1,3,1] .
under these circumstances , The operands are 3 .
Can prove that , Operands are less than 3 Under the circumstances , Cannot make an array into an alternating array .
Example 2
:
Input :nums = [1,2,2,2,2]
Output :2
explain :
One way to turn an array into an alternating array is to convert the array to [1,2,1,2,1].
under these circumstances , The operands are 2 .
Be careful , Array cannot be converted to [2,2,2,2,2] . Because in this case ,nums[0] == nums[1], The condition of alternating array is not satisfied .
Tips
1 <= nums.length <= 105
1 <= nums[i] <= 105
Ideas
Ideas
Because our main purpose here is to count the numbers of odd and even subscripts , Then select the number with the largest number of odd and even subscripts as the number we want to modify to . Therefore, we need to sort the number of occurrences from large to small . If you use a hash table , Then you can't sort by the number of occurrences . After the sorting , Then if the number of occurrences is not equal , We use these two numbers directly ; Otherwise, we need to choose the number with the largest number of occurrences to find the minimum value and return .
Code implementation
class Solution {
public int minimumOperations(int[] nums) {
int[][] cnt1 = new int[100010][2];
int[][] cnt2 = new int[100010][2];
for(int i = 0; i < cnt1.length; i ++){
cnt1[i][0] = i;
cnt2[i][0] = i;
}
for(int i = 0; i < nums.length; i ++){
if(i % 2 == 0){
cnt1[nums[i]][1] ++;
}else if(i % 2 == 1){
cnt2[nums[i]][1] ++;
}
}
Arrays.sort(cnt1,(a1,b1) -> b1[1] - a1[1]);
Arrays.sort(cnt2,(a1,b1) -> b1[1] - a1[1]);
if(cnt1[0][0] != cnt2[0][0]) return nums.length - (cnt1[0][1] + cnt2[0][1]);
return nums.length - Math.max(cnt1[0][1] + cnt2[1][1], cnt1[1][1] + cnt2[0][1]);
}
}
Running results
<3> Third question
subject
Take out the smallest number of magic beans
To give you one just An array of integers
beans
, Each integer represents the number of magic beans in a bag .
Please... From each bag take out Some beans ( It's fine too Don't take out ), Make the rest Non empty In the bag ( namely At least also One Magic bean bag ) Number of magic beans equal . Once the magic beans are removed from the bag , You can't put it in any other bag .
Please return to where you need to take out the magic beans Minimum number .
Example
Example 1
:
Input :beans = [4,1,6,5]
Output :4
explain :
- We never had 1 Take it out of a magic bean bag 1 A magic bean .
The number of magic beans left in the bag is :[4,0,6,5]
- Then we have 6 Take it out of a magic bean bag 2 A magic bean .
The number of magic beans left in the bag is :[4,0,4,5]
- Then we have 5 Take it out of a magic bean bag 1 A magic bean .
The number of magic beans left in the bag is :[4,0,4,4]
A total of 1 + 2 + 1 = 4 A magic bean , The number of magic beans left in the non empty bag is equal .
Nothing is better than taking out 4 A plan with fewer magic beans .
Example 2
:
Input :beans = [2,10,3,2]
Output :7
explain :
- We never had 2 Take it out of one of the bags of magic beans 2 A magic bean .
The number of magic beans left in the bag is :[0,10,3,2]
- Then we have... From another 2 Take it out of a magic bean bag 2 A magic bean .
The number of magic beans left in the bag is :[0,10,3,0]
- Then we have 3 Take it out of a magic bean bag 3 A magic bean .
The number of magic beans left in the bag is :[0,10,0,0]
A total of 2 + 2 + 3 = 7 A magic bean , The number of magic beans left in the non empty bag is equal .
Nothing is better than taking out 7 A plan with fewer magic beans .
Tips
1 <= beans.length <= 105
1 <= beans[i] <= 105
Ideas
Ideas
And what we have here is enumeration beans
All possible values in the array , Then it will be less than beans[i]
The number of is set to 0
, Will be bigger than the beans[i]
The number of drops to beans[i]
. Here we are preprocessing out a Prefixes and arrays
To assist , Then it is to find the minimum .
Code implementation
class Solution {
public long minimumRemoval(int[] beans) {
/** This problem is similar to acwing A problem of resetting the sequence of numbers in the weekly competition in . Its problem is the number of operations required to change all numbers into the same number , But here he is, we can manipulate numbers in an interval , Its practice there is to enumerate the numbers of all ranges */
long ans = Long.MAX_VALUE;
int len = beans.length;
long[] s = new long[len + 1];
Arrays.sort(beans);
for(int i = 1; i <= len; i ++) s[i] = s[i - 1] + beans[i - 1];
for(int i = 0; i < len; i ++){
ans = Math.min(ans,s[i + 1] + (s[len] - s[i + 1]) - (long)beans[i] * (len - i));
}
return ans;
}
}
Running results
边栏推荐
- Call Huawei order service to verify the purchase token interface and return connection reset
- Analysis and comparison of leetcode weekly race + acwing weekly race (t4/t3)
- ||Interview questions you will encounter
- 潘多拉 IOT 开发板学习(RT-Thread)—— 实验4 蜂鸣器+马达实验【按键外部中断】(学习笔记)
- 【大型电商项目开发】性能压测-优化-中间件对性能的影响-40
- Single step debugging of master data reading of SAP commerce cloud products
- [FPGA tutorial case 9] design and implementation of clock manager based on vivado core
- 全网最全正则实战指南,拿走不谢
- NPM install error forced installation
- Basic operations of database and table ----- create index
猜你喜欢
dotnet-exec 0.6.0 released
NPM install error forced installation
Several simplified forms of lambda expression
A simple SSO unified login design
Parameter passing mechanism of member methods
Grabbing and sorting out external articles -- status bar [4]
Expose testing outsourcing companies. You may have heard such a voice about outsourcing
Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
[STM32] (I) overview and GPIO introduction
pycharm专业版下载安装教程
随机推荐
7. Scala process control
【海浪建模1】海浪建模的理论分析和matlab仿真
There is a new Post-00 exam king in the testing department. I really can't do it in my old age. I have
Poap: the adoption entrance of NFT?
107. SAP UI5 OverflowToolbar 容器控件以及 resize 事件处理的一些细节介绍
BGP comprehensive experiment
To sort out messy header files, I use include what you use
pycharm专业版下载安装教程
【FPGA教程案例9】基于vivado核的时钟管理器设计与实现
[circuit design] optocoupler use and circuit design summary
Take you ten days to easily complete the go micro service series (IX. link tracking)
Expansion operator: the family is so separated
What if the programmer's SQL data script coding ability is weak and Bi can't do it?
Jcenter () cannot find Alibaba cloud proxy address
The difference between string STR and new string
【大型电商项目开发】性能压测-优化-中间件对性能的影响-40
Insert sort of sort
Global and Chinese market of network connected IC card smart water meters 2022-2028: Research Report on technology, participants, trends, market size and share
leetcode518,377
What you learned in the eleventh week