144. Binary Tree Preorder Traversal

Given a binary tree, return the preorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

 

解题思路：

题目很简单，就是求一个二叉树的前序遍历。。使用栈实现递归过程。。。这里分别给出保存TreeNode的栈和保存TreeNode指针的栈。。

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<int> preorderTraversal(TreeNode* root) {         vector<int>res;         stack<TreeNode>s;         if(root==NULL)return res;         s.push(*(root));         while(!s.empty()){             TreeNode tmp=s.top();             s.pop();             res.push_back(tmp.val);             if(tmp.right!=NULL)s.push(*(tmp.right));             if(tmp.left!=NULL)s.push(*(tmp.left));         }         return res;     } };

 

/**  * Definition for a binary tree node.  * struct TreeNode {  *     int val;  *     TreeNode *left;  *     TreeNode *right;  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}  * };  */ class Solution { public:     vector<int> preorderTraversal(TreeNode* root) {         vector<int>res;         stack<TreeNode*>s;         if(root==NULL)return res;         s.push(root);         while(!s.empty()){             TreeNode* tmp=s.top();             s.pop();             res.push_back(tmp->val);             if(tmp->right!=NULL)s.push(tmp->right);             if(tmp->left!=NULL)s.push(tmp->left);         }         return res;     } };

 

java如果使用栈或者递归方法，耗时2ms，在discuss那里看到不用stack，用rights数组保存遍历过程中遇到的右结点，当当前结点的左结点为空，则从rights数组中找到最近的右结点。。。该方法耗费空间。。

/**  * Definition for binary tree  * public class TreeNode {  *     int val;  *     TreeNode left;  *     TreeNode right;  *     TreeNode(int x) { val = x; }  * }  */ public class Solution {    public List<Integer> preorderTraversal(TreeNode root) {             List<Integer>order=new ArrayList<Integer>();             List<TreeNode>rights=new ArrayList<TreeNode>();             if(root==null)return order;             TreeNode cur=root;             int ind=-1;             while(cur!=null){                 order.add(cur.val);                 if(cur.right!=null){                     ind++;                     rights.add(ind,cur.right);                 }                 if(cur.left!=null)cur=cur.left;                 else{                     cur=ind<0?null:rights.get(ind);                     ind--;                 }                               }             return order;         } }

 

 

206. Reverse Linked List

Reverse a singly linked list.

 

解题思路：

求一个链表的逆序。一种方法是遍历链表，将节点保存到stack中，在一个个出栈加到链表中；另一个方法是遍历链表，将每个节点插入到队首。。

 

C++ 8ms

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

 

Java 0ms

/**  * Definition for singly-linked list.  * public class ListNode {  *     int val;  *     ListNode next;  *     ListNode(int x) { val = x; }  * }  */ public class Solution {    public ListNode reverseList(ListNode head) {         if(head==null)return head;         ListNode p=head;         ListNode root=new ListNode(0);         while(p!=null){             ListNode q=p.next;             p.next=root.next;             root.next=p;             p=q;         }         return root.next;     } }

 

3ms

public class Solution {    public ListNode reverseList(ListNode head) {         if(head==null)return head;         Stack<Integer>stack=new Stack<Integer>();         ListNode p=head;         while(p!=null){             stack.push(p.val);             p=p.next;         }         p=head;         while(p!=null){             p.val=stack.pop();             p=p.next;         }         return head;     } }

 

 

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times.

You may assume that the array is non-empty and the majority element always exist in the array.

解题思路：

思路请看剑指offer的面试29.。。。。。

class Solution { public:     int majorityElement(vector<int>& nums) {         int n=nums.size();         if(n==1)return nums[0];         int pre=nums[0];         int cnt=1;         for(int i=0;i<n;i++){             if(nums[i]==pre)cnt++;             else                 cnt--;             if(cnt==0){                 pre=nums[i];                 cnt=1;             }         }         return pre;     } };

 

 

268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find the one that is missing from the array.

For example,

Given nums = [0, 1, 3] return 2.

 

解题思路：

题目意思是给出一个数组，是从0,1,…,n中取出n个数，找出不在这个数组中的数。

方法一：sum

class Solution { public:     // 36ms     int missingNumber(vector<int>& nums) {        int n=nums.size();        if(n==0)return 0;        int s=n&1?((n+1)>>1)*n:(n>>1)*(n+1);        for(int i=0;i<n;i++)         s-=nums[i];         return s;     } };

方法二：xor

n个数异或，同时与0,1,2,3…,n这几个数异或，这样在数组中出现的数一定出现了两次，对异或结果没有影响，只有那个不在数组中的数出现一次。

class Solution { public:     // 32ms     int missingNumber(vector<int>& nums) {        int n=nums.size();        if(n==0)return 0;        if(n==1)return 1-nums[0];        int s=0;        for(int i=1;i<=n;i++)         s^=i^nums[i-1];         return s;     } };

方法三：binary search

首先对数组进行排序，再二分查找。。。。有点不好理解。。

class Solution { public:     // 68ms     int missingNumber(vector<int>& nums) {         int n=nums.size();         if(n==0)return 0;         sort(nums.begin(),nums.end());         int l=0,r=n;         int mid;         while(l<=r){             mid=l+((r-l)>>1);             if(nums[mid-1]+1!=nums[mid])return nums[mid-1]+1;             if(nums[mid]!=mid)r=mid-1;             else                 l=mid+1;         }         return mid;     } };