338.Counting Bits - Leetcode题解

Search…

7.Reverse Integer

9.Palindrome Number

13.Roman to Integer

19.Remove Nth Node from End of List

20.Valid Parentheses

21.Merge Two Sorted Lists

22.Generate Parentheses

26.Remove Duplicates from Sorted Array

27.Remove Element

28.Implement strStr()

35.Search Insert Position

38.Count and Say

46.Permutations

53.Maximum Subarray

58.Length of Last Word

59.Spiral Matrix II

70.Climbing Stairs

77.Combinations

83.Remove Duplicates from Sorted List

88.Merge Sorted Array

104.Maximum Depth of Binary Tree

107.Binary Tree Level Order Traversal II

108.Convert Sorted Array to Binary Search Tree

101.Symmetric Tree

105.Construct Binary Tree from Preorder and Inorder Traversal

110.Balanced Binary Tree

111.Minimum Depth of Binary Tree

118.Pascals Triangle

119.Pascals Triangle II

121.Best Time to Buy and Sell Stock

125.Valid Palindrome

131.Palindrome Partitioning

140.Word Break II

141.Linked List Cycle

143.Reorder List

167.Two Sum II- Input Array is Sorted

168.Excel Sheet Column Title

169.Majority Element

171.Excel Sheet Column Number

172.Factorial Trailing Zeroes

175.Combine Two Tables

181.Employee Earning More Than Their Managers

182.Duplicate Emails

183.Customers Who Never Order

189.Rotate Array

191.Number of 1 Bits

193.Valid Phone Numbers

196.Delete Duplicate Emails

197.Rising Temperature

198.House Robber

202.Happy Number

203.Remove Linked List Elements

204.Count Primes

205.Isomorphic Strings

206.Reverse Linked List

217.Contains Duplicate

219.Contains Duplicate II

225.Implement Stack Using Queues

226.Invert Binary Tree

231.Power of Two

232.Implement Queue Using Stack

234.Palindrome Linked List

237.Delete Node in a Linked List

240.Search a 2D Matrix II

242.Valid Anagram

257.Binary Tree Paths

263.Ugly Numbers

268.Missing Number

278.First Bad Version

284.Peeking Iterator

290.Word Pattern

303.Range Sum Query Immutable

338.Counting Bits

342.Power of Four

344.Reverse String

345.Reverse Vowels of a String

349.Intersection of Two Arrays

350.Intersection of Two Arrays II

367.Valid Perfect Square

371.Sum of Two Integers

374.Guess Number Higher or Lower

383.Ransom Note

387.First Unique Character in a String

401.Binary Watch

404.Sum of Left Leaves

405.Convert A Number to Hexadecimal

409.Longest Palindrome

414.Third Maximum Number

415.Add Strings

427.Construct Quad Tree

429.N Ary Tree Level Order Traversal

434.Number of Segments in a String

437.Path Sum III

438.Find All Anagrams in a String

441.Arranging Coins

443.String Compression

447.Number of Boomerangs

448.Find All Numbers Disappeared in an Array

453.Minimum Moves to Equal Array Elements

455.Assign Cookies

459.Repeated Substring Pattern

461.Hamming Distance

463.Island Perimeter

476.Number Complement

482.License Key Formatting

485.Max Consecutive Ones

492.Construct the Rectangle

496.Next Greater Element I

500.Keyboard Row

501.Find Mode in Binary Tree

506.Relative Ranks

507.Perfect Number

509.Fibonacci Number

520.Detect Capital

521.Longest Uncommon Subsequence I

530.Minimum Absolute Difference in BST

532.K-diff Pairs in an Array

535.Encode and Decode TinyURL

538.Convert BST to Greater Tree

541.Reverse String II

543.Diameter of Binary Tree

551.Student Attendace Record I

557.Reverse Words in a String

558.Quad Tree Intersection

559.Maxmium Depth of N Ary Tree

561.Array Partition I

563.Binary Tree Tilt

566.Reshape the Matrix

572.Subtree of Another Tree

575.Distribute Candies

581.Shortest Unsorted Continuous Subarray

589.N Ary Tree Preorder Traversal

590.N Ary Tree Postorder Traversal

594.Longest Harmonious Subsequence

595.Big Countires

596.Classes More Than 5 Students

598.Range Addition II

599.Minimum Index of Two Lists

605.Can Place Flowers

606.Construct String from Binary Tree

617.Merge Two Binary Trees

620.Not Boring Movies

627.Swap Salary

628.Maximum Product of Three Numbers

633.Sum of Square Numbers

637.Average of Levels in Binary Tree

643.Maximum Average Subarray I

645.Set Mismatch

653.Two Sum IV - Input is a BST

654.Maximum Binary Tree

657.Robot Return to Origin

661.Image Smoother

665.Non-Decreasing Array

669.Trim a Binary Search Tree

671.Second Minimum Node in a Binary Tree

680.Valid Palindrome II

682.Baseball Game

686.Repeated String Match

687.Longest Univalue Path

690.Employee Importance

693.Binary Number with Alternating Bits

696.Count Binary Substring

697.Degree of an Array

700.Search in a Binary Search Tree

701.Insert Into a Binary Search Tree

703.Kth Largest Element in a Stream

704.Binary Search

705.Design Hashset

706.Design Hashmap

707.Design Linked List

709.To Lower Case

713.Subarray Product Less Than K

717.1 Bit and 2 Bit Characters

720.Longest Word in Dictionary

724.Find Pivot Index

728.Self Dividing Numbers

739.每日温度

744.Find Smallest Letter Greater Than Target

746.Min Cost Climbing Stairs

747.Largest Number At Least Twice Of Others

748.Shortest Completing Word

754.Reach A Number

762.Prime Number of Set Bits in Binary Representation

766.Toeplitz Matrix

771.Jewels and Stones

783.Minimum Distance Between BST Nodes

784.Letter Case Permutation

788.Rotated Digits

796.Rotate String

804.Unique Morse Code Words

806.Number of Lines to Write String

807.Max Increase to Keep City Skyline

811.Subdomain Visit Count

812.Largest Triangle Area

814.Binary Tree Pruning

819.Most Common Word

821.Shortest Distance to a Character

829.Consecutive Numbers Sum

830.Position of Large Groups

831.Masking Personal Information

832,Flipping an Image

833.Find And Replace in String

835,Image Overlap

836.Rectangle Overlap

840.Magic Squares In Grid

844.Backspace String Compare

848.Shifting Letters

849.Maximize Distance to Closest Person

852.Peak Index in A Mountain Array

859.Buddy Strings

860.Lemonade Change

861.Score After Flipping Matrix

864.Shortest Path to Get All Keys

865.Smallest Subtree with all the Deepest Nodes

866.Prime Palindrome

872.Leaf Similar Trees

874.Walking Robot Simulation

876.Middle of the Linked List

883.Projection Area of 3D Shapes

884.Uncommon Words from Two Sentences

887.Super Egg Drop

888.Fair Candy Swap

892.Surface Area of 3D Shapes

893.Groups of Special Equivalent Strings

894.All Possible Full Binary Trees

896.monotonic array

897.increasing order search tree

900.RLE Iterator

901.Online Stock Span

905.Sort Array by Parity

908.Smallest Range I

910.Smallest Range II

913.Cat and Mouse

914.X of a Kind in a Deck of Cards

915.Partition Array into Disjoint Intervals

916.Word Subsets

917.Reverse Only Letters

922.Sort Array by Parity II

925.Long Pressed Name

929.Unique Email Address

937.Reorder Log Files

938.Range Sum of BST

941.Valid Mountain Array

942.Di String Match

944.Delete Column to Make Sorted

949.Largest Time For Given Digits

950.Reveal Cards in Increasing Order

953.Verifying an Alien Dictionary

961.N Repeated Element in Size 2N Array

965.Univalued Binary Tree

970.Powerful Integers

974.Subarray Sums Divisible By K

976.Largest Perimeter Triangle

977.Squares of a Sorted Array

985.Sum of Even Numbers After Queries

989.Add to Array-Form of Integer

990.Satisfiability of Equality Equations

993.Cousins in Binary Tree

994.Rotting Oranges

997.Find the Town Judge

999.Available Captures for Rook

1002.Find Common Characters

1005.Maximise Sum of Array after K Negations

1008.Construct Binary Search Tree from Preorder Traversal

1021.Remove Outermost Parentheses

1025.Divisor Game

1029.Tow City Scheduling

1030.Matrix Cells in Distance Order

1033.Moving Stones Until Consecutive

1037.Valid Boomerang

1038.Binary Search Tree to Greater Sum Tree

1041.Robot Bounded in Circle

1042.Flower Planting with no Adjacent

1046.Last Stone Weight

1089.Duplicate Zeros

1013.Partition Array Into Three Parts with Equal Sum

1018.Binary Prefix Divisible By 5

1022.Sum of Root To Leaf Binary Numbers

1071.Greatest Common Divisor of Strings

1079.Letter Tile Possibilities

1103.Distribute Candies to People

1114.Print in Order

1115.Print FooBar Alternately

1116.Print Zero Even Odd

1117.Building H2O

1128.Number of Equivalent Domino Pairs

1169.Invalid Transactions

1176.Diet Plan Performance

1282.用户分组

1329.Sort the Matrix Diagonally

1379.Find a Corresponding Node of a Binary Tree in a Clone of That Tree

1395.Count Number of Teams

面试题 16.01

面试题 16.18

Powered By GitBook

338.Counting Bits

338.Counting Bits
难度:Medium
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
Example 1:
​
Input: 2
Output: [0,1,1]
Example 2:
​
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
​
It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
Space complexity should be O(n).
Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
这题可以采用与78.subsets相似的方法，循环，然后判断位数。
class Solution {
public:
    vector<int> countBits(int num) {
        int s= log(num)/log(2);
        if(pow(2,s) <num) s+=1;
        int N= 1;
        int count =1;
        vector<int> res(num+1, 0);
       for(int i=1;i<=num;i++)
       {
           int count =0;
           for(int j=0;j<=s;j++)
           if(i & (1<<j)) count++;
           res[i] = count;
       }
        return res;
    }
};
执行用时 :152 ms, 在所有 C++ 提交中击败了8.83%的用户
内存消耗 :9.9 MB, 在所有 C++ 提交中击败了3.54%的用户
但是效率较低，可以采用动态规划的方法，对于一个数，通过该数的1/2的位数和该数末尾是否为1来确定该数的位数。
class Solution {
vector <int > counts={0,1,1,2,1};
public:
    vector<int> countBits(int num) {
      if(num <counts.size()) 
      {
          vector<int > res(counts.begin(), counts.begin()+num+1);
          return res;
      }
      for(int i=counts.size(); i<=num;i++)
      counts.push_back( counts[i/2] + i%2);
       return counts;
    }
};
执行用时 :84 ms, 在所有 C++ 提交中击败了67.28%的用户
内存消耗 :10.8 MB, 在所有 C++ 提交中击败了5.19%的用户

303.Range Sum Query Immutable

342.Power of Four

Last modified 8mo ago

Copy link