LeetCode OJ – 第46页

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;

}

};

LeetCode 136. Single Number

Given an array of integers, every element appears twice 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() - 1; i = i + 2) {
            if(nums[i] != nums[i + 1]) {
                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() - 1; i = i + 2) {

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

return nums[i];

}

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

}

};

LeetCode 172. Factorial Trailing Zeroes

Given an integer n, return the number of trailing zeroes in n!.

Note: Your solution should be in logarithmic time complexity.

Credits:
Special thanks to @ts for adding this problem and creating all test cases.

题目大意：在logn的时间内找到n！末尾有几个零

//5*2 = 10出现一个0，n*(n-1)*(n-2)...1当中能被5整除的数少于能被2整除的数
//所以能被5整除的5的个数就是0的个数
//比如25！,25 = 5 * 5有两个5，20，15，10，5各含一个5，这六个5分别和2结合相乘就能得到末尾6个0
//所以只要count每个因子中5的个数就行

class Solution {
public:
    int trailingZeroes(int n) {
        int cnt = 0;
        while(n != 0) {
            cnt = cnt + n / 5;
            n = n / 5;
        }
        return cnt;
    }
};

//5*2 = 10出现一个0，n*(n-1)*(n-2)...1当中能被5整除的数少于能被2整除的数

//所以能被5整除的5的个数就是0的个数

//比如25！,25 = 5 * 5有两个5，20，15，10，5各含一个5，这六个5分别和2结合相乘就能得到末尾6个0

//所以只要count每个因子中5的个数就行

class Solution {

public:

int trailingZeroes(int n) {

int cnt = 0;

while(n != 0) {

cnt = cnt + n / 5;

n = n / 5;

}

return cnt;

}

};