当前位置:网站首页>Leetcode hot topic Hot 100 day 33: "subset"
Leetcode hot topic Hot 100 day 33: "subset"
2022-07-05 04:24:00 【Ultimate brocade】
Continue to brush LeetCode Hot topic HOT 100 The subject of , And update my blog solutions. stay csdn In my blog, I will try to explain clearly in words , relevant Java Code, you can go to my Personal blog jinhuaiyu.com View in .
subject : A subset of
Give you an array of integers nums , Elements in an array Different from each other . Returns all possible subsets of the array ( Power set ).
Solution set You can't Contains a subset of repetitions . You can press In any order Returns the solution set .
Example 1:
Input :nums = [1,2,3]
Output :[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
Example 2:
Input :nums = [0]
Output :[[],[0]]
Tips :
1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums All elements in Different from each other
solution 1: Dynamic programming
We need to find the former i The set of all subsets of digits and the first i+1 The relationship between sets of all subsets of digits . Suppose the set of the former is f(i), Add numbers to each subset nums[i+1] Form a set add, be f(i+1) Namely f(i)+add. You can try this set rule by yourself .
In limine , We need to put an empty set in the set ( An empty set is a subset of all sets ), And then from 0 To traverse the nums Array , Start calculating layer by layer f(i). In each layer, the set obtained from the previous layer is copied and added with numbers nums[i], Then put back the collection .
solution 2: Binary corresponding subset
For all subsets , All individually correspond to one nums Array every take and don't take , Assume that 1 Do not take as 0, about nums by {5,2,9}, Subset empty set corresponds to binary number 000, A subset of {5,2} Corresponding to binary number 110. Altogether 2^n A subset of , It corresponds to 2^n Binary numbers (n position ,n by nums length ). And these binary numbers are continuous , Its decimal size ranges from 0 To 2^n - 1.
We can enumerate decimal values from 0 To 2^n - 1 Binary number of (n position , Front complement 0) To get all the corresponding subsets . For one of the binary numbers , If the first i Position as 1, be nums[i] Join the current subset .
To judge a decimal number m After converting to binary, the i Whether bit is bit 1, We can use it and 2^i Find the position and &. because 2^i Binary number of , Except for i Is it 1 The others are 0, If m Of the i It's also 0, Then the two are bitwise and must be 0, Otherwise 1.
solution 3: to flash back ( Depth-first search )
Depth first search , Each path corresponds to a different subset , Depth is nums.length. There are taking and not taking on each floor nums[i] Two options , Reach the leaf node ( The first n layer ) Record the subset corresponding to the current path . A lot of backtracking problems have been done before , This problem is simpler , There are only two options on each floor , You can put it first. nums[i] Join in , Then drill down , Go back and take out this number , And search down without taking the number .
Finally, The code with detailed comments is placed in my Personal blog http://jinhuaiyu.com/leetcode-subsets/
边栏推荐
- OWASP top 10 vulnerability Guide (2021)
- American 5g open ran suffered another major setback, and its attempt to counter China's 5g technology has failed
- 函數(易錯)
- Laravel8 export excel file
- Rust blockchain development - signature encryption and private key public key
- User behavior collection platform
- The development of mobile IM based on TCP still needs to keep the heartbeat alive
- level17
- Moco is not suitable for target detection? MsrA proposes object level comparative learning target detection pre training method SOCO! Performance SOTA! (NeurIPS 2021)...
- Threejs factory model 3DMAX model obj+mtl format, source file download
猜你喜欢
Power management bus (pmbus)
可观测|时序数据降采样在Prometheus实践复盘
Aperçu en direct | Services de conteneurs ACK flexible Prediction Best Practices
American 5g open ran suffered another major setback, and its attempt to counter China's 5g technology has failed
【thingsboard】替换首页logo的方法
Realize the attention function of the article in the applet
Threejs rendering obj+mtl model source code, 3D factory model
Threejs Internet of things, 3D visualization of farms (II)
Longyuan war "epidemic" 2021 network security competition web easyjaba
概率论与数理统计考试重点复习路线
随机推荐
American 5g open ran suffered another major setback, and its attempt to counter China's 5g technology has failed
Seven join join queries of MySQL
如何优雅的获取每个分组的前几条数据
Ffmepg usage guide
Aperçu en direct | Services de conteneurs ACK flexible Prediction Best Practices
Official announcement! The third cloud native programming challenge is officially launched!
kubernetes集群之调度系统
函数(基本:参数,返回值)
How to remove installed elpa package
这是一个不确定的时代
技术教程:如何利用EasyDSS将直播流推到七牛云?
Ctfshow 2022 Spring Festival welcome (detailed commentary)
Threejs loads the city obj model, loads the character gltf model, and tweetjs realizes the movement of characters according to the planned route
Mxnet imports various libcudarts * so、 libcuda*. So not found
揭秘技术 Leader 必备的七大清奇脑回路
About the project error reporting solution of mpaas Pb access mode adapting to 64 bit CPU architecture
A real day for Beijing programmers!!!!!
程序员应该怎么学数学
Hexadecimal to decimal
[phantom engine UE] realize the animation production of mapping tripod deployment