Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

64th Day 2021.03.15

2044. Count the number of subsets that can be maximized by bit

  • Leetcode: leetcode-cn.com/problems/co…
  • Difficulty: Medium
  • Methods: DFS

Topic describes

  • I give you an array of integersnumsPlease find outnumsAnd returns the number of different non-empty subsets that can be maximized by bitwise or by bitwise.
  • If the arrayaYou can use an array bDelete some elements (or not delete) to get, then consider an arrayaIs an arraybA subset of. If the selected elements have different subscripts, the two subsets are considered different.
  • An arraya Perform bitwise or, and the result is equal toa[0] OR a[1] OR ... OR a[a.length - 1](subscript from0Start).

The sample

  • Example 1
Input: nums = [3,1] Output: 2 There are two subsets that may be bitwise 3: - [3] - [3,1]Copy the code
  • Example 2
Input: nums = [2,2,2] Output: 7 Explanation: bitwise or of all non-empty subsets of [2,2,2] yields 2. There are 23 minus 1 is equal to 7 subsets.Copy the code
  • Example 3
Input: nums = [3,2,1,5] output: 6 explanation: the maximum bitwise or possible value of the subset is 7. There are six subset bitwise or can get 7: - (3, 5] - [3,1,5] -,2,5 [3] - [3,2,1,5] - [2, 5) -,1,5 [2]Copy the code

Pay attention to

  • ||Or operator.
  • |To operate by bit or

Train of thought

  • Similar topic 1601. Maximum number of flat change requests that can be made
  • Again, the idea of choice and non-choice, the question is a little bit simpler than this similar question. After processing, you need to restore all the states back.

Initial idea

  • The two-layer loop enumerates the situation of each subset by force, stores the bitwise or value of each subset, and finally selects the largest output
  • Existing problems:forThe double-layer traversal of the loop does not cover all cases, for example:,6,2 [3]
    • [3]、[3,6]、[3,6,2]、[6]、[6,2]、[2]
    • Fall off the[3, 2]situation
  • This is a case where there are only three numbers in the array, and the more you have, the more cases you lose. So switch ideas useddfs

Final idea

  • The formation of a subset, essentially, is to do with or without this element, so it followsdfs.

expand

  • dfsApproach:
    • 1. Determine the return value and parameters
    • 2. Determine termination conditions
    • 3. Determine the logic of each layer
  • dfsThe use of parameter passing
    • Global (no return value) : the subject of writing, DFS (pos + 1, nums [0] | ans)
    • Return value: Be sure to write a return statement at the end of each layer
  • Select and unselect are the same for each element and can therefore be useddfsTo solve it.

ACcode

/ * * *@param {number[]} nums
 * @return {number}* /
var countMaxOrSubsets = function(nums) {
  let len = nums.length;
  // There is a problem with subsets, because this calculation can only count the number of consecutive subsets
  // Use DFS to select and deselect
  // 1. Parameters and return values
  // 2. Termination conditions
  // 3. Single-layer logic
  let pos = 0;
  let map = new Map(a);let ans = 0;
  function dfs(pos, ans) {
    if(pos > nums.length - 1) {// We also need to replenish the map collection records
      // console.log('pos:',pos,ans,'map',map)
      if(map.has(ans)){
        map.set(ans, map.get(ans) + 1);
      }else {
        map.set(ans, 1);
      }
      return;
    }
    / / don't choose
    dfs(pos + 1, ans);
    // Select, xor is required
    dfs(pos + 1, ans | nums[pos]);
  }
  // Return value: bitwise xor; Parameter: The subscript of the numeric value of each bit
  // Terminating condition: find the last bit of the array and record the final xOR value in the map collection
  // Single-layer logic: select and unselect,
     // No xOR is required
     // Select, the value of the previous xor needs to be xor with this xor
  dfs(pos, ans);
  let max = 0;
  map.forEach((value, key) = > {
    if(value > max){ max = value; }});// console.log(map)
  return max;
};
Copy the code

conclusion

  • We need to work on that,DFSPractice, three steps.