总是觉得时间飞逝却又总是抓不住时间，再有几十分钟就要进入2017年了。回头看这2016年，上半年轻松惬意，下半年紧张了不少。写这种总结文字总是觉得很矫情，权当是碎碎念，反正也没有什么人会看到┑(￣Д ￣)┍。

年初从一月份开始在家呆了近四个月，超长假期+很水的毕设=废人一个。要说干了啥……好像看完了《代码大全》，但是我觉得有点看早了，里面有的点能get到，有的点不明觉厉，总体感觉囫囵吞枣。三月底的时候趁着樱花季去日本转了两周，要说是穿越了国界反而更像是穿越了次元壁呢……大阪-奈良-京都-箱根-东京自由行下来感觉就是……以后还要去啊啊啊啊！！！对于动画厨来说简直逛不够啊！而且一个人旅行真的很舒服。

四月份回成都，五月份毕设结束，六月份本科毕业。四年的时光走到了尽头，相比于四年前的那个高中生成长了很多很多，人生的际遇总是那么不可思议，四年前的我怎么也想象不到毕业时的样子吧。

暑假在家，心血来潮准备从头刷LeetCode，也是为明年的面试做准备。这个大坑到现在我还没有填完T_T。暑假看了《Effective STL》，收获不小。

下半年来广州，只上两门课。CMU的课程真的让我觉得跟国内不同，一学期CSAPP从头讲到尾，配套9个Lab，而且是针对没有CS基础的同学，我至少有点基础，不会太费力，但是对其他专业背景的同学要求真的是很高。要说我觉得课程与国内最大的不同就是课后作业的重视程度，不仅数量大，而且难度也不小。

说到明年，希望我能顺利到达美国，能找到一个工作。这大概就是我的新年愿望了吧。

对了，马上就是我着任提督一周年的日子了，嘛，到时候专门写一篇吧:-)

题目描述：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Now your job is to find the total Hamming distance between all pairs of the given numbers.

Example:

1 2 3 4 5 6 7

Input: 4, 14, 2 Output: 6 Explanation: In binary representation, the 4 is 0100, 14 is 1110, and 2 is 0010 (just showing the four bits relevant in this case). So the answer will be: HammingDistance(4, 14) + HammingDistance(4, 2) + HammingDistance(14, 2) = 2 + 2 + 2 = 6.

Note:

1. Elements of the given array are in the range of 0to 10^9
2. Length of the array will not exceed 10^4.

跟 461. Hamming Distance 这道题类似，不过数量增加了。我们可以对int的每一位分别求HammingDistance再求和。n个二进制位中有i个0和j个1，那么它们两两组合成0与1的种类有i*j种。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    int totalHammingDistance(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            int num[2] = {0, 0};
            for(auto j : nums){
                if(j & (1 << i))
                    num[1]++;
                else
                    num[0]++;
            }
            ans += (num[0] * num[1]);
        }
        return ans;
    }
};

题目描述：

The Hamming distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y, calculate the Hamming distance.

Note: 0 ≤ x, y < 231.

Example:

1 2 3 4 5 6 7 8 9 10

Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different.

把两个数异或之后看结果有多少个1.

1
2
3
4
5
6
7
8
9
10
11
12

class Solution {
public:
    int hammingDistance(int x, int y) {
        unsigned int z = x ^ y;
        int ans = 0;
        while(z > 0){
            if(z & 1) ans++;
            z >>= 1;
        }
        return ans;
    }
};

题目描述:

Winter is coming! Your first job during the contest is to design a standard heater with fixed warm radius to warm all the houses.

Now, you are given positions of houses and heaters on a horizontal line, find out minimum radius of heaters so that all houses could be covered by those heaters.

So, your input will be the positions of houses and heaters seperately, and your expected output will be the minimum radius standard of heaters.

Note:

1. Numbers of houses and heaters you are given are non-negative and will not exceed 25000.
2. Positions of houses and heaters you are given are non-negative and will not exceed 10^9.
3. As long as a house is in the heaters’ warm radius range, it can be warmed.
4. All the heaters follow your radius standard and the warm radius will the same.

Example 1:

1 2 3 4

Input: [1,2,3],[2] Output: 1 Explanation: The only heater was placed in the position 2, and if we use the radius 1 standard, then all the houses can be warmed.

Example 2:

1 2 3

Input: [1,2,3,4],[1,4] Output: 1 Explanation: The two heater was placed in the position 1 and 4. We need to use radius 1 standard, then all the houses can be warmed.

我使用二分搜索, 对每个房子搜索与它最近的heater, 维护一个最长的最短距离.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
public:
    int findRadius(vector<int>& houses, vector<int>& heaters) {
        sort(heaters.begin(), heaters.end());
        int ans = 0;
        for(auto i : houses){
            int index = binSearch(heaters, i);
            if(index == heaters.size()) index--;
            int tmp = min(abs(heaters[index] - i), abs(index < heaters.size() - 1 ? heaters[index + 1] - i : INT_MAX));
            tmp = min(tmp, abs(index > 0 ? heaters[index - 1] - i : INT_MAX));
            ans = max(ans, tmp);
        }
        return ans;
    }
    
    int binSearch(vector<int>&heaters, int target){
        int left = 0, right = heaters.size(), mid = (left + right) / 2;
        while(left < right){
            if(heaters[mid] == target) return mid;
            else if(heaters[mid] > target) right = mid;
            else left = mid + 1;
            
            mid = (left + right) / 2;
        }
        return left;
    }
};

题目描述:

In this problem, your job to write a function to check whether a input string is a valid IPv4 address or IPv6 address or neither.

IPv4 addresses are canonically represented in dot-decimal notation, which consists of four decimal numbers, each ranging from 0 to 255, separated by dots ("."), e.g.,172.16.254.1;

Besides, you need to keep in mind that leading zeros in the IPv4 is illegal. For example, the address 172.16.254.01 is illegal.

IPv6 addresses are represented as eight groups of four hexadecimal digits, each group representing 16 bits. The groups are separated by colons (":"). For example, the address 2001:0db8:85a3:0000:0000:8a2e:0370:7334 is a legal one. Also, we could omit some leading zeros among four hexadecimal digits and some low-case characters in the address to upper-case ones, so 2001:db8:85a3:0:0:8A2E:0370:7334 is also a valid IPv6 address(Omit leading zeros and using upper cases).

However, we don’t replace a consecutive group of zero value with a single empty group using two consecutive colons (::) to pursue simplicity. For example, 2001:0db8:85a3::8A2E:0370:7334 is an invalid IPv6 address.

Besides, you need to keep in mind that extra leading zeros in the IPv6 is also illegal. For example, the address 02001:0db8:85a3:0000:0000:8a2e:0370:7334 is also illegal.

Note: You could assume there is no extra space in the test cases and there may some special characters in the input string.

Example 1:

1 2 3 4 5 6

Input: "172.16.254.1" Output: "IPv4" Explanation: This is a valid IPv4 address, return "IPv4".

Example 2:

1 2 3 4 5 6

Input: "2001:0db8:85a3:0:0:8A2E:0370:7334" Output: "IPv6" Explanation: This is a valid IPv6 address, return "IPv6".

Example 3:

1 2 3 4 5

Input: "256.256.256.256" Output: "Neither" Explanation: This is neither a IPv4 address nor a IPv6 address.

判断合法的IP地址, 比较简单, 注意前导零就行.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60

class Solution {
public:
    string validIPAddress(string IP) {
        if(validIPv4(IP)) return string("IPv4");
        else if(validIPv6(IP)) return string("IPv6");
        return string("Neither");
    }
    
    bool validIPv4(string IP){
        int p = 0, q = 0;
        for(int i = 0; i < 4; i++){
            q = IP.find('.', p);
            if(q == string::npos && i != 3){
                return false;
            }
            else if(i == 3){
                q = IP.length();
            }
            string part = IP.substr(p, q - p);
            if(part.empty() || part.length() > 3) return false;
            for(auto c : part){
                if(!isDigit(c)) return false;
            }
            bool leadingZero = part[0] == '0' ? true : false;
            if(leadingZero && part.length() > 1) return false;
            int t = stoi(part);
            if(t > 255 || t < 0) return false;
            p = q + 1;
        }
        return true;
    }
    
    bool validIPv6(string IP){
        int p = 0, q = 0;
        for(int i = 0; i < 8; i++){
            q = IP.find(':', p);
            if(q == string::npos && i != 7){
                return false;
            }
            else if(i == 7){
                q = IP.length();
            }
            string part = IP.substr(p, q - p);
            if(part.empty() || part.length() > 4) return false;
            for(auto c : part){
                if(!isHex(c)) return false;
            }
            p = q + 1;
        }
        return true;
    }
    
    bool isDigit(char c){
        return c >= '0' && c <= '9';
    }
    
    bool isHex(char c){
        return isDigit(c) || (c >= 'A' && c <= 'F') || (c >= 'a' && c <= 'f');
    }
};

题目描述:

Reverse a singly linked list.

翻转一个单向链表, 就是从前往后依次翻转即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/**
 * 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) return NULL;
        ListNode *p1 = head, *p2 = head->next, *p = head->next;
        if(!p1 || !p2) return head;
        while(p2 && p1){
            ListNode *t = p2->next;
            p2->next = p1;
            p1 = p2;
            p2 = t;
        }
        head->next = NULL;
        return p1;
    }
};

题目描述:

Given two strings s and t, determine if they are isomorphic.

Two strings are isomorphic if the characters in s can be replaced to get t.

All occurrences of a character must be replaced with another character while preserving the order of characters. No two characters may map to the same character but a character may map to itself.

For example, Given "egg", "add", return true.

Given "foo", "bar", return false.

Given "paper", "title", return true.

Note: You may assume both s and t have the same length.

依次建立替换的映射, 无法完成转换的条件有两个:

1. s中两个不同的字符映射到了同一个字符. 用一个数组来记录每个字符是否被映射过, 出现重复时则返回false.
2. s中的两个相同字符映射到不同字符. 每次比较字符的映射是否相同.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

class Solution {
public:
    bool isIsomorphic(string s, string t) {
        vector<int> s2t(128, -1), tCnt(128, 0);
        for(int i = 0; i < s.size(); i++){
            char sc = s[i], tc = t[i];
            if(s2t[sc] == -1){
                if(tCnt[tc] == 1) return false;
                s2t[sc] = tc;
                tCnt[tc] = 1;
            }
            else if(s2t[sc] != tc) return false;
        }
        return true;
    }
};

题目描述:

Description:

Count the number of prime numbers less than a non-negative number, n.

使用筛法, 从小到大剔除每个遇到的素数的小于n的倍数, 直到$\sqrt n$, 每剔除一个就将素数个数减1. sum一开始减2是为了去掉1和n自身.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
	int countPrimes(int n) {
	    if(n <= 1) return 0;
		vector<int> s(n, 0);
		int sum = n - 2;
		for (int i = 2; i * i < n; i++) {
		    if(s[i]) continue;
			for (int j = i; i * j < n; j++) {
			    int index = i * j;
			    if(!s[index]) {
			        sum--;
				    s[index] = 1;
			    }
			}
		}
		return sum;
	}
};

题目描述:

Remove all elements from a linked list of integers that have value val.

Example Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6 Return: 1 --> 2 --> 3 --> 4 --> 5

就是单纯的删除链表节点.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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

题目描述:

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

**Example: **19 is a happy number

• 12 + 92 = 82
• 82 + 22 = 68
• 62 + 82 = 100
• 12 + 02 + 02 = 1

最直观的解法可以使用hash表.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

class Solution {
public:
    bool isHappy(int n) {
        unordered_set<int> s;
        s.insert(n);
        int t = n;
        while(t != 1){
            long long sum = 0;
            while(t > 0){
                sum += ((t % 10) * (t % 10));
                t /= 10;
            }
            t = sum;
            if(s.count(t)) return false;
            else s.insert(t);
        }
        return true;
    }
};

但是仔细想想, 输入数据最多为一个十位数, 每一位数字的平方最多为81, 因此中间过程所产生的数肯定落在[1,810]之间, 我们只要开一个较大的数组来保存某个数是否出现过就可以了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    bool isHappy(int n) {
        vector<int> s(1000, 0);
        int t = n;
        while(t != 1){
            int sum = 0;
            while(t > 0){
                sum += ((t % 10) * (t % 10));
                t /= 10;
            }
            t = sum;
            if(s[t]) return false;
            else s[t] = 1;
        }
        return true;
    }
};