当前位置:网站首页>Leetcode brush questions day49
Leetcode brush questions day49
2022-07-07 17:07:00 【51CTO】
Today's key points — greedy
List of articles
55. Jumping game
Title Description
Given an array of nonnegative integers nums
, You're in the beginning of the array The first subscript .
Each element in the array represents the maximum length you can jump at that location .
Judge whether you can reach the last subscript .
Example 1:
Example 2:
Thought analysis
When I first saw this question, I might think : If the current location element is 3, What on earth am I doing , Or two steps , Or three steps , How many steps is the best ?
In fact, it doesn't matter how many steps you take , The key is the coverage that can jump !
In this range , Never mind how you jump , You can jump over anyway .
Then this question turns into whether the jump coverage can cover the end point !
Take the maximum number of jump steps per move ( Get maximum coverage ), Every unit moved , Update the maximum coverage .
Greedy algorithm local optimal solution : Take the maximum number of jump steps each time ( Take the maximum coverage ), The global optimal solution : Finally, the overall maximum coverage , See if we can reach the end .
The local optimum leads to the global optimum , No counterexample , Try greed !
Pictured :
i Each move can only be made in cover Moving within the limits of , Every time you move an element ,cover Get the supplement of the new coverage of this element , Give Way i Keep moving .
and cover Take only max( The range after the value of this element is supplemented , cover Scope of itself )
.
If cover Greater than or equal to the end subscript , direct return true That's all right. .
Reference code
45. Jumping game II
Title Description
Here's an array of nonnegative integers nums
, You are first in the array .
Each element in the array represents the maximum length you can jump at that location .
Your goal is Use the least number of hops to reach the last position of the array .
Suppose you can always reach the last position of the array .
Example 1:
Example 2:
Thought analysis
This problem is to calculate the minimum number of steps , Then you have to figure out when the steps must be added by one ?
Greedy thinking , Local optimum : At present, you can move as much as possible , If you haven't reached the end , Step number plus one . The overall best : Take as many steps as possible , So as to achieve the minimum number of steps .
Although the idea is like this , But when writing code, you can't really jump far and long , Then you don't know where you can jump the farthest in the next step .
So when you really solve a problem , Start with coverage , No matter how you jump , It must be possible to jump within the coverage , Increase coverage with minimum steps . Once the coverage covers the end point , The result is the minimum number of steps !
Here we need to count two coverage areas , The maximum coverage of the current step and the maximum coverage of the next step .
If the moving subscript reaches the maximum coverage distance of the current step , If you haven't reached the end , Then we must take another step to increase the coverage , Until the coverage covers the end .
Pictured :
Reference code
1005. K The maximum array and... After negation
Title Description
Give you an array of integers nums
And an integer k
, Modify the array as follows :
- Select a subscript
i
And will nums[i]
Replace with -nums[i]
.
Repeating this process happens to k
Time . You can select the same subscript multiple times i
.
After modifying the array in this way , Returns an array of The maximum possible and .
Example 1:
Example 2:
Example 3:
Thought analysis
Greedy thinking , Local optimum : Let a negative number with a large absolute value become a positive number , The current value reaches the maximum , The overall best : The sum of the entire array reaches the maximum .
So if you turn negative numbers into positive numbers ,K Still greater than 0, The problem at this point is a sequence of ordered positive integers , How to change K Secondary positive and negative , Give Way Array and Maximum .
Then it's another greedy : Local optimum : Only find the positive integer with the smallest value for inversion , The current value can reach the maximum ( For example, an array of positive integers {5, 3, 1}, reverse 1 obtain -1 Than reverse 5 Got -5 Mostly ), The best in the world : Whole Array and Maximum .
Then the steps to solve this problem are :
- First step : Sort the array according to the absolute value size from large to small , Pay attention to the size of the absolute value
- The second step : Traverse back and forth , When you encounter a negative number, change it to a positive number , meanwhile K–
- The third step : If K Greater than 0, Then repeatedly change the element with the lowest value , take K run out
- Step four : Sum up
Reference code
If there is harvest !!! I hope the old fellow will have three links. , give the thumbs-up 、 Collection 、 forward .
It's not easy to create , Don't forget to like it , More people can see this article , By the way, encourage me to write a better blog
边栏推荐
- QML初学
- LeetCode-SQL第一天
- QT video transmission
- The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
- LeetCode 1986. The minimum working time to complete the task is one question per day
- AI来搞财富分配比人更公平?来自DeepMind的多人博弈游戏研究
- Binary search tree (features)
- LeetCode 1155. 掷骰子的N种方法 每日一题
- Master this set of refined Android advanced interview questions analysis, oppoandroid interview questions
- dapp丨defi丨nft丨lp单双币流动性挖矿系统开发详细说明及源码
猜你喜欢
Sator推出Web3游戏“Satorspace” ,并上线Huobi
As an Android Developer programmer, Android advanced interview
【MySql进阶】索引详解(一):索引数据页结构
Direct dry goods, 100% praise
Sort out several important Android knowledge and advanced Android development interview questions
Sator推出Web3游戏“Satorspace” ,并上线Huobi
QT 图片背景色像素处理法
PLC:自动纠正数据集噪声,来洗洗数据集吧 | ICLR 2021 Spotlight
Binary search tree (features)
预售17.9万,恒驰5能不能火?产品力在线,就看怎么卖
随机推荐
LeetCode 312. 戳气球 每日一题
[Seaborn] implementation of combined charts and multi subgraphs
[image sensor] correlated double sampling CDs
Skimage learning (3) -- adapt the gray filter to RGB images, separate colors by immunohistochemical staining, and filter the maximum value of the region
The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
Binary search tree (features)
A tour of gRPC:03 - proto序列化/反序列化
字节跳动Android面试,知识点总结+面试题解析
LeetCode 1774. 最接近目标价格的甜点成本 每日一题
LeetCode 1477. Find two subarrays with sum as the target value and no overlap
掌握这个提升路径,面试资料分享
QML beginner
Sort out several important Android knowledge and advanced Android development interview questions
第九届 蓝桥杯 决赛 交换次数
LeetCode 1981. Minimize the difference between the target value and the selected element one question per day
[PHP] PHP interface inheritance and interface multi inheritance principle and implementation method
QT中自定义控件的创建到封装到工具栏过程(一):自定义控件的创建
QT picture background color pixel processing method
LeetCode 403. 青蛙过河 每日一题
Module VI