Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

解法1：Dummy Node O(N + M)

对于head不明确的linkedlist的题目，都考虑建立Dummy Node，然后返回Dummy->next的办法解决。
C++
用C++注意在最后需要delete掉dummy防止memory leak

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

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1->val <= l2->val) {
                tail->next = l1;
                l1 = l1->next;
            } else {
                tail->next = l2;
                l2 = l2->next;
            }
            tail = tail->next;
        }
        while (l1 != NULL) {
            tail->next = l1;
            l1 = l1->next;
            tail = tail->next;
        }
        while (l2 != NULL) {
            tail->next = l2;
            l2 = l2->next;
            tail = tail->next;
        }
        ListNode* res = dummy->next;
        delete dummy;
        return res;
    }
};

Java

1

Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.

Example 1:
Input: “abab”

Output: True

Explanation: It’s the substring “ab” twice.
Example 2:
Input: “aba”

Output: False
Example 3:
Input: “abcabcabcabc”

Output: True

Explanation: It’s the substring “abc” four times. (And the substring “abcabc” twice.)

解法1：O(k * N), k是n的约数个数，n是字符串的长度

由于要分成相同的几个字串相连，那么字串的长度一定是原字符串的一个约数。这种情况下，约数的个数是有限制的，1 到 n / 2。
暴力解法，从n/2到1一个一个试，然后拼接出原字符长度比较。
C++

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

class Solution {
public:
    bool repeatedSubstringPattern(string str) {
        if (str.empty()) return false;
        int n = str.size();
        for (int i = n / 2; i >= 1; --i) {
            if (n % i == 0) {
                string sub = str.substr(0, i);
                string copy = "";
                for (int j = 0; j < (n / i); ++j) {
                    copy += sub;
                }
                if (str.compare(copy) == 0) {
                    return true;
                }
            }
        }
        return false;
    }
};

Java

1

解法2： KMP with O(N) Time

本题还有KMP的解法，显然不是我想出来的。先把网上看到的解释贴在这里。
用到的关于KMP的算法的详细说明。
深深的怀疑面试会期望给出这个答案。。
还有是关于本题的解释

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example:

Input: “Hello, my name is John”
Output: 5

解法1：O(N)

按每一个segment的开头来判断一个segment的开始。

C++

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

class Solution {
public:
    int countSegments(string s) {
        int res = 0;
        for (int i = 0; i < s.size(); ++i) {
            if (s[i] != ' ' && (i == 0 || s[i - 1] == ' ')) {
                ++res;
            }
        }
        return res;
    }
};

Java

1

Given n points in the plane that are all pairwise distinct, a “boomerang” is a tuple of points (i, j, k) such that the distance between i and j equals the distance between i and k (the order of the tuple matters).

Find the number of boomerangs. You may assume that n will be at most 500 and coordinates of points are all in the range [-10000, 10000] (inclusive).

Example:
Input:
[[0,0],[1,0],[2,0]]

Output:
2

Explanation:
The two boomerangs are [[1,0],[0,0],[2,0]] and [[1,0],[2,0],[0,0]]

解法1：O(N^2)

排列组合的题。假设有a,b,c。如果bc和a的距离相等，那么可以产生abc或者acb两种排列。如果是bcd和a的距离相等，那么可以产生6种排列。对于有n个数和a相等的情况，总共的个数是n*(n-1)。
那么问题就转化为，对于每一个pair作为a，计算每一种距离的pair的个数，然后再把总和相加就是答案。
C++

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

class Solution {
public:
    int numberOfBoomerangs(vector<pair<int, int>>& points) {
        if (points.size() < 3) {
            return 0;
        }
        int res = 0;
        for (int i = 0; i < points.size(); ++i) {
            unordered_map<int, int> map;
            for (int j = 0; j < points.size(); ++j) {
                if (i == j) {
                    continue;
                }
                int x = points[i].first - points[j].first;
                int y = points[i].second - points[j].second;
                ++map[x * x + y * y];
            }
            for (auto iter = map.begin(); iter != map.end(); ++iter) {
                res += iter->second * (iter->second - 1);
            }
        }
        return res;
    }
};

Java

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

class Solution {
    public int numberOfBoomerangs(int[][] points) {
        if (points == null || points.length == 0) {
            return 0;
        }
        if (points[0] == null || points[0].length == 0) {
            return 0;
        }
        int res = 0;
        // Do the calculation
        for (int i = 0; i < points.length; i++) {
            HashMap<Integer, Integer> map = new HashMap<>();    // record the count of each distance between two points
            for (int j = 0; j < points.length; j++) {
                if (i == j) continue;
                int x = points[i][0] - points[j][0];
                int y = points[i][1] - points[j][1];
                int dist = x * x + y * y;
                map.put(dist, map.getOrDefault(dist, 0) + 1);
            }
            for (int key : map.keySet()) {
                res += map.get(key) * (map.get(key) - 1);
            }
        }
        return res;
    }
}

Given a roman numeral, convert it to an integer.
Input is guaranteed to be within the range from 1 to 3999.

解法1：O(N) Time

Roman to Integer 是较容易的。需要记忆的是几个关键的Roman字母和数值的对应关系。
从后往前扫描，如果前面的数值比后面的数值小，则需要减去，否则加上。

1
2
3

| I | V | X  | L | C | D | M  |
|---|---|----|---|---|---|--- |
| 1 | 5 | 10 |50 |100|500|1000|

C++

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

class Solution {
  public:
  int romanToInt(string s) {
      if (s.empty()) {
          return 0;
      }
      int res = 0;
      res += romans[toupper(s[s.size() - 1])];
      for (int i = s.size() - 2; i >= 0; --i) {
          if (romans[toupper(s[i])] < romans[toupper(s[i + 1])]) {
              res -= romans[toupper(s[i])];
          } else {
              res += romans[toupper(s[i])];
          }
      }
      return res;
  }
  private:
    unordered_map<char, int> romans {{'I',1},{'V',5},{'X',10}, {'L',50}, {'C', 100}, {'D',500}, {'M',1000}};
}

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 romanToInt(String s) {
        Map<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);
        int res = 0;
        res += map.get(s.charAt(s.length() - 1));
        for (int i = s.length() - 2; i >= 0; i--) {
            int current = map.get(s.charAt(i));
            int last = map.get(s.charAt(i + 1));
            if (current < last) {
                res -= current;
            } else {
                res += current;                
            }
        }
        return res;        
    }
}

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：O(M) M is number of total set bits

运用n & (n -1)消掉最高位的set bit的思想，可以不停重复这个操作直到n变为0，
这样的复杂度可以减少为所有1的个数
C++

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

class Solution {
public:
    int hammingWeight(uint32_t n) {
        if (n == 0) {
            return 0;
        }
        int count = 0;
        while (n != 0) {
            ++count;
            n = n & (n - 1);
        }
        return count;
    }
};

解法2：O(N) N is number of total bits

用右移的方法来判断每一位是否是1直到n变为0
C++

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

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int res = 0;
        while (n != 0) {
            res += n & 1;
            n =  n >> 1;
        }
        return res;
    }
};

Java

1

Given two non-negative numbers num1 and num2 represented as string, return the sum of num1 and num2.

Note:

The length of both num1 and num2 is < 5100.
Both num1 and num2 contains only digits 0-9.
Both num1 and num2 does not contain any leading zero.
You must not use any built-in BigInteger library or convert the inputs to integer directly.
Show Company Tags
Show Tags
Show Similar Problems

解法1：Two pointers, O(N + M) Time

经典的两数相加问题，主要的考察就是每一位上怎么计算digit和carry。digit = (temp + carry) % 10, carry = (temp + carry) / 10;
容易忘记的几个点：

1. 如果两个string的长度不相等，最后要遍历剩下较长的string
2. 最后要判断carry是否为0，如果不是，要在string的最前面加上carry的值

C++

C++ 里的几个用法：

• char& to int: 只能用c - ‘0’这种办法
• int to string: 在c++ 11里有std::to_string 的函数，用法为std::to_string(string& s)

  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

  class Solution { public: string addStrings(string num1, string num2) { if (num1.empty()) { return num2; } if (num2.empty()) { return num1; } string res = ""; int carry = 0; int i, j; for (i = num1.size() - 1, j = num2.size() - 1; i >= 0 && j >= 0; --i, --j) { int temp = num1[i] - '0' + num2[j] - '0'; int digit = (temp + carry) % 10; carry = (temp + carry) / 10; res = to_string(digit) + res; } for (; i >= 0; --i) { int temp = num1[i] - '0'; int digit = (temp + carry) % 10; carry = (temp + carry) / 10; res = to_string(digit) + res; } for (; j >= 0; --j) { int temp = num2[j] - '0'; int digit = (temp + carry) % 10; carry = (temp + carry) / 10; res = to_string(digit) + res; } if (carry > 0) { res = to_string(carry) + res; } return res; } };

Java

1

A binary watch has 4 LEDs on the top which represent the hours (0-11), and the 6 LEDs on the bottom represent the minutes (0-59).

Each LED represents a zero or one, with the least significant bit on the right.

For example, the above binary watch reads “3:25”.

Given a non-negative integer n which represents the number of LEDs that are currently on, return all possible times the watch could represent.

Example:

Input: n = 1
Return: [“1:00”, “2:00”, “4:00”, “8:00”, “0:01”, “0:02”, “0:04”, “0:08”, “0:16”, “0:32”]
Note:
The order of output does not matter.
The hour must not contain a leading zero, for example “01:00” is not valid, it should be “1:00”.
The minute must be consist of two digits and may contain a leading zero, for example “10:2” is not valid, it should be “10:02”.

解法1：Backtracking/Recursion

好久没有写backtracking的题目了,搞了好久才搞出来。code也不一定简略但好歹是过了OA。
基本思路就是建立两个vector存储可能的时针值和分针值，然后记录已经用过的时针值和分针值。
要注意的是要去重，所以我用了一个unordered_set来记录当前所有的答案，如果有重复的则不插入。
另外要判断时针和分针的有效性。
C++

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

class Solution {
public:
    vector<string> readBinaryWatch(int num) {
        if (num == 0) {
            return vector<string> {"0:00" };
        }
        vector<bool> hour_used(hours.size(), false);
        vector<bool> minute_used(minutes.size(), false);
        unordered_set<string> resSet;
        vector<string> res;
        helper(num, 0, 0, hour_used, minute_used, resSet);
        for (auto iter = resSet.begin(); iter != resSet.end(); ++iter) {
            res.emplace_back(*iter);
        }
        std::sort(res.begin(), res.end());
        return res;
    }
    void helper(int num, int hour, int minute, vector<bool>& hour_used, vector<bool>& minute_used, unordered_set<string>& res) {
        // Termination condition
        if (hour > 11 || minute > 59)
            return;
        if (num == 0) {
            string s;
            if (minute < 10) {
                s = to_string(hour) + ":0" + to_string(minute);
            } else {
                s = to_string(hour) + ":" + to_string(minute);
            }
            if (res.find(s) == res.end()) {
                res.emplace(s);    
            }
            return;
        }
        for (int i = 0; i < hours.size(); ++i) {
            if (!hour_used[i]) {
                hour_used[i] = true;
                helper(num - 1, hour + hours[i], minute, hour_used, minute_used, res);
                hour_used[i] = false;
            }
        }
        for (int i = 0; i < minutes.size(); ++i) {
            if (!minute_used[i]) {
                minute_used[i] = true;
                helper(num -1, hour, minute + minutes[i], hour_used, minute_used, res);    
                minute_used[i] = false;
            }
        }
    }
private:
    vector<int> hours {1,2,4,8};
    vector<int> minutes {1,2,4,8,16,32};
};

Java

1

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

解法1：

经典的算法，如果是pot，那么只有最高位为1，如果将此数减1之后再和原来的数取AND，结果一定为0.
要注意的是要规避：1. 负数 2. 0
这两种情况都不是power of two
C++

1
2
3
4
5
6
7
8
9

class Solution {
public:
    bool isPowerOfTwo(int n) {
        if (n <= 0) return false;
        return (n & ( n - 1)) == 0;
    }
};

Java

1

Reverse a singly linked list.
A linked list can be reversed either iteratively or recursively. Could you implement both?

解法1：Iteratively

经典的答案，没啥好说的。要背下来。
C++

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

/**
 * 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) {
        ListNode* ptr = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = ptr;
            ptr = head;
            head = temp;
    }
    return ptr;
    }
};

Java

1

解法2： Recursively

C++

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

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* newhead = reverseList(head->next);
        head->next->next = head;
        head->next = NULL;
        return newhead;
    }
};