leetcode简单题2

发表于   |   分类于   |  

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.

1
2
3
4
5
6
7
class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());//vector排序
        return nums[nums.size()/2];
    }
};

Reverse Linked List

反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(head==NULL)
        return NULL;
        if(head->next==NULL)
        return head;
        ListNode*p=head->next;
        ListNode*pre=head;
        head->next=NULL;//记得把第一个的next设置为NULL
        while(p->next!=NULL)
        {
            ListNode* temp=p->next;
            p->next=pre;
            pre=p;
            p=temp;
        }
        p->next=pre;
        return p;
    }
};

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of ’1’ bits it has (also known as the Hamming weight).

For example, the 32-bit integer ’11’ has binary representation 00000000000000000000000000001011, so the function should return 3.

解法一(按位判断)

1
2
3
4
5
6
7
8
9
10
11
 int hammingWeight(uint32_t n) 
 {
    int count=0;
    for(int i=31;i>=0;i--)
    {
        int k=(n>>i)&1;
        if(k)
            count++;
    }
     return count;
}

解法二
每当n&(n-1)一次，n就会少一位1(最后一位1没了)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int hammingWeight(uint32_t n) {
        int count=0;
        while(n!=0)
        {
            n=n&(n-1);
            ++count;
        }
        return count;
    }
};

Power of Two

Given an integer, write a function to determine if it is a power of two.

如果n是2的指数，则n的二进制表达中只有一个1，可以通过上题解决

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    bool isPowerOfTwo(int n) {
        if(n<=0)
        	return false;
        if(n&(n-1))
        	return false;
        return true;
    }
};

Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?
如果不是3的指数，则求出的幂指数不为整数，如12,求出的幂指数为2.26186，则 2.26186-int(2.26186)不为0；

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n<=0)
            return false;
        double k=log10(n)/log10(3);
        if(k-int(k)==0)
            return true;
        return false;
    }
};

判断浮点数的大小关系时，首先要判断他们是否相等，不相等再判断大小关系。例如A>B，不一定就是A大于B，有可能他们相等。

1
2
3
4
int dequals(double a, double b)
{
	return fabs(a-b) < 0.000001;
}