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

 

 

242. Valid Anagram

Given two strings s and t, write a function to determine if t is an anagram of s.

For example,

s = "anagram", t = "nagaram", return true.

s = "rat", t = "car", return false.

Note:

You may assume the string contains only lowercase alphabets.

 

 

解题思路：

只要s和t的字符以及字符所使用的次数相同即返回true。这题中使用的字符都是小写字符，因此可直接使用固定大小的数组作为hash数组，记录字符串中字符出现的次数。。。。

class Solution { public:     // 12ms     bool isAnagram(string s, string t) {         int n=s.length();         if(n!=t.length())return false;         if(n==0)return true;         int a[26]={0};         for(int i=0;i<n;i++){             a[s[i]-'a']++;             a[t[i]-'a']--;         }         for(int i=0;i<26;i++)             if(a[i]!=0)return false;         return true;     } };   或者 class Solution { public:     // 12ms     bool isAnagram(string s, string t) {         int n=s.length();         if(n!=t.length())return false;         if(n==0)return true;         int a[26]={0};         for(int i=0;i<n;i++){             a[s[i]-'a']++;         }         for(int i=0;i<n;i++)             if(a[t[i]-'a']==0)return false;             else                 a[t[i]-'a']--;         return true;     } };

 

还有另一种方法就是使用map记录每个字符出现的次数，过程与上类似。。。

238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

 

解题思路：

不使用除法，返回一个数组，数组中第i个元素的值为nums[1]*..nums[i-1]*nums[i+1]…nums[n-1]。

利用前n个元素的乘积数组和后n个数组的乘积数组，得到结果。

暂时是能达到60ms

class Solution { public:     vector<int> productExceptSelf(vector<int>& nums) {         int n=nums.size();         vector<int>a=vector<int>(n,0);         a[0]=1;         for(int i=1;i<n;i++){             a[i]=a[i-1]*nums[i-1];         }         for(int i=n-1;i>0;i--){             a[i-1]=a[i-1]*nums[i];             nums[i-1]=nums[i]*nums[i-1];         }         //for(int i=0;i<n;i++)cout<<a[i]<<" ";         return a;     } };