当前位置:网站首页>Leetcode weekly The 280 game of the week is still difficult for the special game of the week's beauty team ~ simple simulation + hash parity count + sorting simulation traversal
Leetcode weekly The 280 game of the week is still difficult for the special game of the week's beauty team ~ simple simulation + hash parity count + sorting simulation traversal
2022-07-05 22:48:00 【Ape Xiaofu】
Content of this article :leetcode Once a week . Zhou saidI 280 Weekly match Meituan special It's still difficult ~ Simple simulation + Hash parity count + Sort simulation traversal
Article column :leetcode Clock in the week 《 Clock in every week 》
Recent updates :2022 year 1 month 30 Japan leetcode Once a week . Zhou saidI 278 Weekly match Netease special session Sure enough, the question is very difficult But you can still brush Simple order + Traverse Double pointer + The prefix and
Personal profile : A Junior Program ape in two colleges , In the spirit of paying attention to the foundation , Clock in algorithm , Sharing technology as a personal experience summary blogger , Although you may be lazy sometimes , But I will stick to it , If you like blog posts very much , Suggest looking at the following line ~( Crazy hints QwQ)
give the thumbs-up Collection Leaving a message. One key, three links Care program ape , From you and me
Contents of this article
Write it at the front
Here comes Xiaofu , Today, we will update the weekly competition column , Today, Xiao Fu played weekly for the fifth time
The first 280 Weekly match ——2022-02-13
T1.6004. obtain 0 The number of operations
subject
Here are two for you non-negative Integers num1 and num2 .
Each step operation in , If num1 >= num2 , You have to use num1 reduce num2 ; otherwise , You have to use num2 reduce num1 .
for example ,num1 = 5 And num2 = 4 , Should use the num1 reduce num2 , therefore , obtain num1 = 1 and num2 = 4 . However , If num1 = 4 And num2 = 5 , After one step operation , obtain num1 = 4 and num2 = 1 .
Return to make num1 = 0 or num2 = 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
A simple simulation question :
- It can be simulated directly
- It should be noted that : Only in
num1
andnum2
Is greater than 0 Under the circumstances Can be simulated
Code implementation
class Solution {
public int countOperations(int num1, int num2) {
int count = 0 ;
while (num1 > 0 && num2 > 0){
if (num1 >= num2)
num1 = num1 - num2;
else num2 = num2 - num1;
count ++ ;
}
return count;
}
}
Execution results
T2.6005. The minimum number of operands to make an array an alternating array
subject
I'll give you a subscript from 0 Starting array nums , The array consists of n It's made up of four positive integers .
If the following conditions are met , The array nums It's a Alternating array :
- nums[i - 2] == nums[i] , among 2 <= i <= n - 1 .
- nums[i - 1] != nums[i] , among 1 <= i <= n - 1 .
In one step operation in , You can choose the subscript i And will nums[i] change by any Positive integer .
Returns the that makes the array an alternating array The minimum number of operands .
Example
Example 1:
Example 2:
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 3:
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 <= 10^5
1 <= nums[i] <= 10^5
Ideas
Ideas and investigation points of this topic :
- The idea of this question is actually very simple, mainly based on
HashMap Record strange / The number of digits in even digits
, Find out The number of numbers of the maximum quantity and the second largest quantity - If
The current odd digit is inconsistent with the maximum number of digits on the even digit
Then directly use Total length of digits Subtract the sum of the two It can be concluded that Number of digits to be modified - On the contrary, if two numbers with the largest number are the same You need to get the minimum operand If only Compare when the sum of the largest number and the next largest number is the largest, the number of times can be minimized So we need to calculate
The maximum number of odd digits
AndEven bits a large number of digits
The sum of the AndThe maximum number of even digits
AndOdd bits, large bits
The sum of the Take the maximum value , Then we subtract the maximum value from the current length , Then the minimum operand is obtained .
Code implementation
class Solution {
public int minimumOperations(int[] nums) {
int n = nums.length;
HashMap<Integer,Integer> even = new HashMap<>();
HashMap<Integer,Integer> odd = new HashMap<>();
for(int i=0;i<n;i++) {
if(i%2==0) {
// Record the number of each digit on the even digit
even.put(nums[i],even.getOrDefault(nums[i],0)+1);
} else {
// Record the number of each digit on the odd digit
odd.put(nums[i],odd.getOrDefault(nums[i],0)+1);
}
}
// Find two map The two numbers with the most and the second most in key and val
int[][] evenMaxAndSubMax = check(even);
int[][] oddMaxAndSubMax = check(odd);
// If the current two largest numbers key inequality That is to say 1 != 2 In the case of Current length Subtract their frequency respectively Is the number of positive integers that need to be changed
if(evenMaxAndSubMax[0][0] != oddMaxAndSubMax[0][0]) {
n-= evenMaxAndSubMax[0][1];
n-= oddMaxAndSubMax[0][1];
} else {
// On the contrary, if two numbers with the largest number are the same You need to get the minimum operand If we compare the sum of the largest number and the next largest number, we can minimize the number
n-= Math.max(evenMaxAndSubMax[0][1]+oddMaxAndSubMax[1][1],oddMaxAndSubMax[0][1]+evenMaxAndSubMax[1][1]);
}
return n;
}
int[][] check(HashMap<Integer,Integer> map) {
int[][] maxAndSubMax = new int[2][2];
// For each number
for(Integer key:map.keySet()) {
// Get the current number key Of val
int val = map.get(key);
// Find the first two numbers of the number and store them in an array Save their key And val || res[0][0] Is the largest number of numbers key res[0][0] Is the largest number of numbers val
if(val>maxAndSubMax[0][1]) {
maxAndSubMax[1][0] = maxAndSubMax[0][0];
maxAndSubMax[1][1] = maxAndSubMax[0][1];
maxAndSubMax[0][0] = key;
maxAndSubMax[0][1] = val;
} else if(val>maxAndSubMax[1][1]){
// There are many times key And val
maxAndSubMax[1][0] = key;
maxAndSubMax[1][1] = val;
}
}
return maxAndSubMax;
}
}
Execution results
T3.6006. Take out the smallest number of magic beans
subject
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 .
Tips
1 <= beans.length <= 10^5
1 <= beans[i] <= 10^5
Ideas
The idea of this problem is relatively simple :
- But you will find that this problem is simple but The order of magnitude it gives is too large , The return value is a long Then there must be the possibility of timeout .
- Let's talk about ideas first :
- utilize
( Sort + The prefix and )
To solve - We can put each bag first If all bags are empty, record if all bags are set to zero So here The value obtained is the maximum value of beans , We asked for The minimum value must be below it .
- Set the scroll variable Traverse through enumeration get Every time bring
The number of magic beans in each bag is beans[i] Number of hours
The number of beans you need to take out
Code implementation
class Solution {
public long minimumRemoval(int[] beans) {
Arrays.sort(beans);
int n = beans.length;
long res = Long.MAX_VALUE;
long sum = 0 ;
// It can be understood as the maximum value of magic beans Take out all All zeros
for (int bean : beans){
sum += bean;
}
// Enumeration traversal get Every time bring The number of magic beans in each bag is beans[i] Number of hours The number of beans you need to take out
for (int i = 0 ;i< n;i++){
// Rolling variable records the minimum value It's this beans [i] * (n-i);
res = Math.min(res,sum-(long)beans[i] * (n-i));
}
return res;
}
}
Execution results
At the end
Xiaofu clocked in the fifth weekly race 2022-02-13
Try to solve the problems you can do All done That's all right.
I overslept today It's only half an hour when I get up =-=
This week's competition By the way, two questions
The third question has been overtime Directly break the defense
So it's still a good weekly experience
Last
Make progress every day Harvest some every day
May you A successful career Learn something
If it feels good Don't forget to click three times ~
边栏推荐
- Depth first DFS and breadth first BFS -- traversing adjacency tables
- Damn, window in ie open()
- Starting from 1.5, build a micro Service Framework -- log tracking traceid
- 點到直線的距離直線的交點及夾角
- MCU case -int0 and INT1 interrupt count
- Analysis of the problem that the cookie value in PHP contains a plus sign (+) and becomes a space
- Character conversion PTA
- opencv 判断点在多边形内外
- Metaverse Ape猿界应邀出席2022·粤港澳大湾区元宇宙和web3.0主题峰会,分享猿界在Web3时代从技术到应用的文明进化历程
- 3 find the greatest common divisor and the least common multiple
猜你喜欢
Qtquick3d real time reflection
IIC bus realizes client device
BFC block level formatting context
Post-90s tester: "after joining Ali, this time, I decided not to change jobs."
关于MySQL的30条优化技巧,超实用
Activate function and its gradient
Analysis of the problem that the cookie value in PHP contains a plus sign (+) and becomes a space
All expansion and collapse of a-tree
Ieventsystemhandler event interface
[untitled]
随机推荐
VOT toolkit environment configuration and use
Methods modified by static
记录几个常见问题(202207)
Metaverse Ape上线倒计时,推荐活动火爆进行
Oracle is sorted by creation time. If the creation time is empty, the record is placed last
Pinctrl subsystem and GPIO subsystem
第一讲:蛇形矩阵
傅里叶分析概述
The countdown to the launch of metaverse ape is hot
[agc009e] eternal average - conclusion, DP
Nanjing: full use of electronic contracts for commercial housing sales
Depth first DFS and breadth first BFS -- traversing adjacency tables
Metaverse ape received $3.5 million in seed round financing from negentropy capital
Arduino 测量交流电流
Global and Chinese markets of industrial pH meters 2022-2028: Research Report on technology, participants, trends, market size and share
Metaverse Ape获Negentropy Capital种子轮融资350万美元
Paddle Serving v0.9.0 重磅发布多机多卡分布式推理框架
The code generator has deoptimised the styling of xx/typescript.js as it exceeds the max of 500kb
FBO and RBO disappeared in webgpu
分布式解决方案选型