Code – 第250页

LeetCode 162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array where num[i] ≠ num[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that num[-1] = num[n] = -∞.

For example, in array [1, 2, 3, 1], 3 is a peak element and your function should return the index number 2.

class Solution {
public:
    int findPeakElement(vector<int>& nums) {
        if(nums.size() == 1 || (nums[0] > nums[1]))
            return 0;
        if(nums[nums.size() - 1] > nums[nums.size() - 2]) {
            return nums.size() - 1;
        }
        for(int i = 1; i < nums.size() - 1; i++) {
            if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {
                return i;
            }
        }
    }
};

class Solution {

public:

int findPeakElement(vector<int>& nums) {

if(nums.size() == 1 || (nums[0] > nums[1]))

return 0;

if(nums[nums.size() - 1] > nums[nums.size() - 2]) {

return nums.size() - 1;

}

for(int i = 1; i < nums.size() - 1; i++) {

if(nums[i] > nums[i - 1] && nums[i] > nums[i + 1]) {

return i;

}

};

LeetCode 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.

Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int *book = new int [nums.size() + 1];
        for(int i = 0; i <= nums.size(); i++) {
            book[i] = 0;
        }
        for(int i = 0; i < nums.size(); i++) {
            book[nums[i]] = 1;
        }
        for(int i = 0; i <= nums.size(); i++) {
            if(book[i] == 0) {
                return i;
            }
        }
    }
};

class Solution {

public:

int missingNumber(vector<int>& nums) {

int *book = new int [nums.size() + 1];

for(int i = 0; i <= nums.size(); i++) {

book[i] = 0;

}

for(int i = 0; i < nums.size(); i++) {

book[nums[i]] = 1;

}

for(int i = 0; i <= nums.size(); i++) {

if(book[i] == 0) {

return i;

}

};

LeetCode 137. Single Number II

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

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i <= nums.size() - 4; i = i + 3) {
            if(nums[i] != nums[i + 2]) {
                return nums[i];
            }
        }
        return nums[nums.size() - 1];
    }
};

class Solution {

public:

int singleNumber(vector<int>& nums) {

sort(nums.begin(), nums.end());

for(int i = 0; i <= nums.size() - 4; i = i + 3) {

if(nums[i] != nums[i + 2]) {

return nums[i];

}

return nums[nums.size() - 1];

}

};

LeetCode 141. Linked List Cycle

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

Follow up:
Can you solve it without using extra space?

update v2.0:
//后来想到了一个不赖皮的方法 用 set 存储 判断每次存入 next 结点后 set 的 size()有没有发生变化
//没有发生变化说明这个结点已经被存储过了 就说明是个环
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL)
            return false;
        set<ListNode *> s;
        ListNode *t;
        t = head;
        int cnt = 0;
        while(t->next != NULL) {
            s.insert(t);
            if(cnt == s.size()) {
                return true;
            }
            cnt = s.size();
            t = t->next;
        }
        return false;
    }
};



version 1.0:
//感觉自己做这道题的方法有点赖皮。。。唔。。。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head == NULL)
            return false;
        ListNode *p;
        p = head;
        p->val = 99999999;
        while(p->next != NULL) {
            p = p->next;
            if(p->val != 99999999) {
                p->val = 99999999;
            } else {
                return true;
            }
        }
        return false;
    }
};

update v2.0:

//后来想到了一个不赖皮的方法用 set 存储判断每次存入 next 结点后 set 的 size()有没有发生变化

//没有发生变化说明这个结点已经被存储过了就说明是个环

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

bool hasCycle(ListNode *head) {

if(head == NULL)

return false;

set<ListNode *> s;

ListNode *t;

t = head;

int cnt = 0;

while(t->next != NULL) {

s.insert(t);

if(cnt == s.size()) {

return true;

}

cnt = s.size();

t = t->next;

}

return false;

}

};

version 1.0:

//感觉自己做这道题的方法有点赖皮。。。唔。。。

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

bool hasCycle(ListNode *head) {

if(head == NULL)

return false;

ListNode *p;

p = head;

p->val = 99999999;

while(p->next != NULL) {

p = p->next;

if(p->val != 99999999) {

p->val = 99999999;

} else {

return true;

}

return false;

}

};

LeetCode 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.

update v3.0:
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> v(num + 1);
        v[0] = 0;
        for(int i = 1; i < num + 1; i++) {
            v[i] = v[i >> 1] + i % 2;
        }
        return v;
    }
};


update v2.0:
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> v(num + 1);
        v[0] = 0;
        v[1] = 1;
        v[2] = 1;
        v[3] = 2;
        for(int i = 4; i < num + 1; i = i * 2) {
            for(int j = i; j < i + i/2 && j < num + 1; j++) {
                v[j] = v[j - i/2];
            }
            for(int j = i + i/2; j < i * 2 && j < num + 1; j++) {
                int temp = j;
                int cnt = 0;
                while(temp) {
                    cnt = cnt + temp % 2;
                    temp = temp/2;
                }
                v[j] = cnt;
            }
        }
        return v;
    }
};


version v1.0:
class Solution {
public:
    vector<int> countBits(int num) {
        vector<int> v(num + 1);
        for(int i = 0; i <= num; i++) {
            int temp = i;
            int cnt = 0;
            while(temp) {
                cnt = cnt + temp % 2;
                temp = temp / 2;
            }
            v[i] = cnt;
        }
        return v;
    }
};

update v3.0:

class Solution {

public:

vector<int> countBits(int num) {

vector<int> v(num + 1);

v[0] = 0;

for(int i = 1; i < num + 1; i++) {

v[i] = v[i >> 1] + i % 2;

}

return v;

}

};

update v2.0:

class Solution {

public:

vector<int> countBits(int num) {

vector<int> v(num + 1);

v[0] = 0;

v[1] = 1;

v[2] = 1;

v[3] = 2;

for(int i = 4; i < num + 1; i = i * 2) {

for(int j = i; j < i + i/2 && j < num + 1; j++) {

v[j] = v[j - i/2];

}

for(int j = i + i/2; j < i * 2 && j < num + 1; j++) {

int temp = j;

int cnt = 0;

while(temp) {

cnt = cnt + temp % 2;

temp = temp/2;

}

v[j] = cnt;

}

return v;

}

};

version v1.0:

class Solution {

public:

vector<int> countBits(int num) {

vector<int> v(num + 1);

for(int i = 0; i <= num; i++) {

int temp = i;

int cnt = 0;

while(temp) {

cnt = cnt + temp % 2;

temp = temp / 2;

}

v[i] = cnt;

}

return v;

}

};

LeetCode 260. Single Number III

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

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

Note:
The order of the result is not important. So in the above example, [5, 3] is also correct.
Your algorithm should run in linear runtime complexity. Could you implement it using only constant space complexity?

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        vector<int> v(2);
        int flag = 0;
        for(int i = 0; i < nums.size() - 1; i = i + 2) {
            if(nums[i] != nums[i + 1]) {
                v[0] = nums[i];
                for(int j = i + 1; j < nums.size() - 1; j = j + 2) {
                    if(nums[j] != nums[j + 1]) {
                        v[1] = nums[j];
                        flag = 1;
                        break;
                    }
                }
                break;
            }
        }
        if(flag == 0) {
            v[1] = nums[nums.size() - 1];
        }
        return v;
    }
};

class Solution {

public:

vector<int> singleNumber(vector<int>& nums) {

sort(nums.begin(), nums.end());

vector<int> v(2);

int flag = 0;

for(int i = 0; i < nums.size() - 1; i = i + 2) {

if(nums[i] != nums[i + 1]) {

v[0] = nums[i];

for(int j = i + 1; j < nums.size() - 1; j = j + 2) {

if(nums[j] != nums[j + 1]) {

v[1] = nums[j];

flag = 1;

break;

}

break;

}

if(flag == 0) {

v[1] = nums[nums.size() - 1];

}

return v;

}

};