Network Security Internet Technology Development Database Servers Mobile Phone Android Software Apple Software Computer Software News IT Information

In addition to Weibo, there is also WeChat

Please pay attention

WeChat public account

Shulou

How to delete and get points in LeetCode

2025-04-05 Update From: SLTechnology News&Howtos shulou NAV: SLTechnology News&Howtos > Internet Technology >

Share

Shulou(Shulou.com)06/01 Report--

Editor to share with you how to delete LeetCode and get points, I believe most people do not know much about it, so share this article for your reference, I hope you can learn a lot after reading this article, let's go to know it!

one

Topic description

Given an integer array nums, select any nums [I] in each operation, delete it and get the points of nums [I], and delete each element equal to nums [I]-1 or nums [I] + 1 synchronously. The initial number of points is 0, which returns the maximum number of points that can be obtained. For example: nums= [3Jing 4jue 2], return 6. (first select 4, accumulate 4 points, delete 3 at the same time, select 2, and then accumulate 2 points, for a total of 6 points. The points accumulated in other ways are less than 6)

two

Answer to the question

Idea: dynamic planning through the title requirements, the first thing to be clear is: when you select a value to get its points, other same values will also be selected. Because when you select a value, the adjacent values have been deleted, so the other same values will not be deleted and must be selected. So you can create a list value with values as the subscript to record the number of points you can get when you select each value. For example, value [2] = 2, 2], [3] = 3, [4] = 4: 1, so we finally get value= [0].

Intermediate state: where the intermediate state dp [I] represents the maximum number of points that can be obtained from 1 selection to I.

State transition: there are only two possibilities for a value to be deleted and the number of points to be obtained, and whether it is obtained or not will affect the selection of other values. Therefore, if a new number is not selected, then DP [I] = DP [I-1]; if elected, iMui 1 cannot be selected, then DP [I] = DP [I-2] + value [I], so eventually dp [I] = max (DP [I-1], DP [I-2] + value [I]).

Class Solution: def deleteAndEarn (self, nums: List [int])-> int: if not nums: return 0 dp = [0] * (max (nums) + 1) value = dp.copy () # value = [0] * (max (nums) + 1) for an in enumerate (nums): value [a] + = a dp [1] = value [1] for i in range (2) Max (nums) + 1): dp [I] = max (DP [I-1], DP [I-2] + value [I]) return dp [- 1] above are all the contents of the article "how to delete and get points by LeetCode" Thank you for reading! I believe we all have a certain understanding, hope to share the content to help you, if you want to learn more knowledge, welcome to follow the industry information channel!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.

Views: 0

*The comments in the above article only represent the author's personal views and do not represent the views and positions of this website. If you have more insights, please feel free to contribute and share.

Share To

Internet Technology

Wechat

© 2024 shulou.com SLNews company. All rights reserved.

12
Report