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);        }     } };

 

141. Linked List Cycle

Given a linked list, determine if it has a cycle in it.

 

解题思路：

#include<windows.h> #include<iostream> using namespace std; struct ListNode {     int val;     ListNode *next;     ListNode(int x) : val(x), next(NULL) {} };    class Solution { public:     bool hasCycle(ListNode *head) {         if(head==NULL||head->next==NULL)return false;         ListNode*p=head;         ListNode*q=head->next->next;         while(p!=NULL&&q!=NULL){             if(p==q)return true;             p=p->next;             if(q->next!=NULL)q=q->next->next;             else                 break;         }         return false;     } };

 

83. Remove Duplicates from Sorted List

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,

Given 1->1->2, return 1->2.

Given 1->1->2->3->3, return 1->2->3.

 

结题报告：

水题。。。

/**  * Definition for singly-linked list.  * struct ListNode {  *     int val;  *     ListNode *next;  *     ListNode(int x) : val(x), next(NULL) {}  * };  */ class Solution { public:     ListNode* deleteDuplicates(ListNode* head) {         if(head==NULL)return head;         ListNode*p=head;         ListNode*q=head->next;         while(q!=NULL){             if(q->val!=p->val){                 p->next=q;                 p=p->next;             }             q=q->next;         }         p->next=NULL;         return head;     } };