当前位置:网站首页>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
边栏推荐
- Redis master-slave replication cluster and recovery ideas for abnormal data loss # yyds dry goods inventory #
- Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
- Which financial products with stable income are good
- [FPGA tutorial case 9] design and implementation of clock manager based on vivado core
- What if the programmer's SQL data script coding ability is weak and Bi can't do it?
- Query for Boolean field as "not true" (e.g. either false or non-existent)
- Recursive execution mechanism
- Grabbing and sorting out external articles -- status bar [4]
- 揭露测试外包公司,关于外包,你或许听到过这样的声音
- 多模输入事件分发机制详解
猜你喜欢
Four pits in reentrantlock!
Applet live + e-commerce, if you want to be a new retail e-commerce, use it!
Operator explanation
[development of large e-commerce projects] performance pressure test - Optimization - impact of middleware on performance -40
Daily question brushing record (13)
The performance of major mainstream programming languages is PK, and the results are unexpected
“薪資倒掛”、“畢業生平替” 這些現象說明測試行業已經...
There is a new Post-00 exam king in the testing department. I really can't do it in my old age. I have
[wave modeling 1] theoretical analysis and MATLAB simulation of wave modeling
107. SAP UI5 OverflowToolbar 容器控件以及 resize 事件处理的一些细节介绍
随机推荐
各大主流编程语言性能PK,结果出乎意料
[wave modeling 1] theoretical analysis and MATLAB simulation of wave modeling
Operator explanation
[STM32] (I) overview and GPIO introduction
[circuit design] optocoupler use and circuit design summary
[development of large e-commerce projects] performance pressure test - Optimization - impact of middleware on performance -40
107. Some details of SAP ui5 overflow toolbar container control and resize event processing
程序员SQL数据脚本编码能力弱,BI做不出来怎么办?
Arbitrum:二维费用
[Yocto RM]11 - Features
Single step debugging of master data reading of SAP commerce cloud products
Chia Tai International Futures: what is the master account and how to open it?
Detailed explanation of multi-mode input event distribution mechanism
dotnet-exec 0.6.0 released
[development of large e-commerce projects] performance pressure test - Performance Monitoring - heap memory and garbage collection -39
Pycharm professional download and installation tutorial
多模输入事件分发机制详解
Les phénomènes de « salaire inversé » et de « remplacement des diplômés » indiquent que l'industrie des tests a...
Four pits in reentrantlock!
Expansion operator: the family is so separated