338. Counting Bits

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:

For num = 5 you should return [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.

 

解题思路：

这个题目类似89. Gray Code，找规律

0 - 0

1 - 1

2 - 1

3 - 2

4 - 1

5 - 2

6 - 2

7 - 3

8 - 1

[2^(i-1),2^i-1]是由[0,2^(i-1)-1]数组+1得到的。例如上面的[4,7]的值是由[0,3]+1得到的。

class Solution { public:     vector<int> countBits(int num) {         vector<int>res(num+1,0);         int base=1;         int k=1;         while(k<=num){         for(int j=0;j<base&&k<=num;j++)                 res[k++]=res[j]+1;             base<<=1;         }         return res;               } };

 

 

202. Happy Number

Write an algorithm to determine if a number is "happy".

 

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

 

Example: 19 is a happy number

 

1^2 + 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

 

解题思路：

方法一：使用set保存中间值，每次判断中间结果是否在set中，或者判断中间结果是否为1.。

方法二：利用Happy Number的一个性质。。https://en.wikipedia.org/wiki/Happy_number

// using set costs 4ms class Solution { public:     bool isHappy(int n) {        set<int>s;        if(n==0)return false;        s.insert(n);        while(true){            int tmp=0;            while(n){                tmp+=(n%10)*(n%10);                n/=10;            }            n=tmp;            if(n==1)return true;            if(s.find(n)!=s.end())return false;            s.insert(n);        }        return false;     } };   // https://en.wikipedia.org/wiki/Happy_number // Happy_number has attribute all happy number ends in 1,all non-happy number ends in 4; // costs 0ms sometimes class Solution { public:     bool isHappy(int n) {        if(n==0)return false;        int tmp=0;        while(n!=1&&n!=4){            while(n){                tmp+=(n%10)*(n%10);                n/=10;            }            n=tmp;            tmp=0;        }        return n==1;     } };

 

 

263. Ugly Number

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

 

解题思路：

水题、、、、、

class Solution { public:     bool isUgly(int num) {         if(num<1)return false;         // 4ms         while((num&1)==0)num>>=1;         // 8ms         //while((num%2)==0)num/=2;         while(num%3==0)num/=3;         while(num%5==0)num/=5;         return num==1;     } };

 

 

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

 

解题思路：

斐波那契。。。

class Solution { public:     int climbStairs(int n) {         if(n<=2)return n;         int a=1,b=2;         for(int i=3;i<=n;i++){             int tmp=a+b;             a=b;             b=tmp;         }         return b;     } };

 

 

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [−2,1,−3,4,−1,2,1,−5,4],

the contiguous subarray [4,−1,2,1] has the largest sum = 6.

 

结题报告：

最大连续和，动态规划思想

class Solution { public:     int maxSubArray(vector<int>& nums) {         int n=nums.size();         if(n==0)return 0;         int max=0x80000000;         int s=0;         for(int i=0;i<n;i++){             if(s+nums[i]<nums[i])s=nums[i];             else             s+=nums[i];             if(s>max)max=s;         }         return max;     } };

 

 

22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

"((()))", "(()())", "(())()", "()(())", "()()()"

 

解题思路：

DFS

class Solution { public:     vector<string> generateParenthesis(int n) {         vector<string>res;         if(n==0)return res;         dfs(res,n,0,0,"");         return res;     }     void dfs(vector<string>&res,int n,int l,int r,string s){         if(l==n&&r==n){             res.push_back(s);             return ;         }         if(l==n){             dfs(res,n,l,r+1,s+")");             return ;         }         if(l==r){             dfs(res,n,l+1,r,s+"(");             return ;         }         dfs(res,n,l+1,r,s+"(");         dfs(res,n,l,r+1,s+")");               } };

 

 

108. Convert Sorted Array to Binary Search Tree

Given an array where elements are sorted in ascending order, convert it to a height balanced BST.

 

解题思路：

分开考虑n==0 n==1 n==2的情况，可将原来20ms时间提升至16ms

#include<windows.h> #include<vector> using namespace std; struct TreeNode {     int val;     TreeNode *left;     TreeNode *right;     TreeNode(int x) : val(x), left(NULL), right(NULL) {} };   class Solution { public:     // 20ms     TreeNode* sortedArrayToBST(vector<int>& nums) {         int n=nums.size();         if(n==0)return NULL;         // consider n==1 and n==2, it will get 16ms         if(n==1){             return new TreeNode(nums[0]);         }         if(n==2){             TreeNode*root=new TreeNode(nums[0]);             root->right=new TreeNode(nums[1]);             return root;         }         TreeNode* root=dfs(nums,0,n-1);         return root;     }     TreeNode * dfs(vector<int>&nums,int l,int r){         if(l>r)return NULL;         int mid=(l+r)/2;         TreeNode* root=new TreeNode(nums[mid]);         if(l==r)return root;         root->left=dfs(nums,l,mid-1);         root->right=dfs(nums,mid+1,r);     } };

 

137. Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

 

结题报告：

方法一：

使用map记录每个数字出现的次数，找到出现次数不为3的数。

class Solution { public:     // 52ms     int singleNumber(vector<int>& nums) {         map<int,int>m;         int n=nums.size();         for(int i=0;i<n;i++){             int tmp=0;             if(m.find(nums[i])!=m.end())tmp=m[nums[i]];             m[nums[i]]=tmp+1;         }         for(int i=0;i<n;i++)             if(m[nums[i]]!=3)return nums[i];         return -1;     } };

方法二：

Bit manipulate 记录每位出现的次数，与3求余，位不为0，则该位值为1.

class Solution { public:     // 16ms     int singleNumber(vector<int>& nums) {         vector<int>bit(32);         int n=nums.size();         for(int i=0;i<n;i++){             int tmp=nums[i];             for(int j=0;j<32;j++){                 bit[j]+=tmp&1;                 tmp>>=1;                 if(!tmp)break;             }         }         int ans=0;         for(int i=31;i>=0;i--){             bit[i]%=3;             ans<<=1;             if(bit[i])ans|=1;         }         return ans;     } };

方法三：

不是很理解 https://leetcode.com/discuss/81165/explanation-manipulation-method-might-easier-understand

 

One+ = (One ^ B) & (~Two)

Two+ = (~One+) & (Two ^ B)

class Solution { public:     // 12ms     int singleNumber(vector<int>& nums) {         int n=nums.size();         if(n<=2)return nums[0];         int one=0;         int two=0;         for(int i=0;i<n;i++){             one=(~two)&(one^nums[i]);             two=(~one)&(two^nums[i]);         }         return one;     } };

 

35. Search Insert Position

 Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

 

You may assume no duplicates in the array.

 

Here are few examples.

[1,3,5,6], 5 → 2

[1,3,5,6], 2 → 1

[1,3,5,6], 7 → 4

[1,3,5,6], 0 → 0

 

解题思路：

二分查找法。。

class Solution { public:     int searchInsert(vector<int>& nums, int target) {         int n=nums.size();         if(n==0)return 1;         int l=0,r=n-1;         while(l<=r){             int mid=(l+r)/2;             if(target==nums[mid])return mid;             else                 if(target>nums[mid])l=mid+1;                 else                     r=mid-1;         }         return l;     } };

 

116. Populating Next Right Pointers in Each Node

Given a binary tree

 

    struct TreeLinkNode {

      TreeLinkNode *left;

      TreeLinkNode *right;

      TreeLinkNode *next;

    }

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

 

Initially, all next pointers are set to NULL.

 

Note:

 

You may only use constant extra space.

You may assume that it is a perfect binary tree (ie, all leaves are at the same level, and every parent has two children).

For example,

Given the following perfect binary tree,

         1

       /  \

      2    3

     / \  / \

    4  5  6  7

After calling your function, the tree should look like:

         1 -> NULL

       /  \

      2 -> 3 -> NULL

     / \  / \

    4->5->6->7 -> NULL

 

结题报告：

使用一个指针队列保存树结点，并记录结点索引（从1开始），每层的最后一个结点的next指向null，同层其他结点指向其下一个兄弟结点，每层最后一个结点的索引分别为1，3，7，15，k… 可以看出 k+1是2的幂次方（使用 x&(x-1)==0?判断是否为2的幂次方）。

class Solution { public:     // 28ms     void connect(TreeLinkNode *root) {        queue<TreeLinkNode*>q;        if(root==NULL)return ;        q.push(root);        int k=0;        while(!q.empty()){            TreeLinkNode*p=q.front();            q.pop();            k++;            if(((k+1)&k)!=0&&!q.empty())p->next=q.front();            if(p->left!=NULL)q.push(p->left);            if(p->right!=NULL)q.push(p->right);        }     } };

方法与上类似，只是使用vector来存储树结点。。

class Solution { public:     // 24ms     void connect(TreeLinkNode *root) {        vector<TreeLinkNode*>q;        if(root==NULL)return ;        q.push_back(root);        int k=0;        while(k<q.size()){            TreeLinkNode*p=q[k++];            if(((k+1)&k)!=0&&!q.empty())p->next=q[k];            if(p->left!=NULL)q.push_back(p->left);            if(p->right!=NULL)q.push_back(p->right);        }     } };