204. Count Primes

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

Example:

Input: 10
Output: 4
Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.

本题要求从1~n共有多少个素数。Hint里一步步深入写得非常详细了，简要概括一下，有两种方法，一种是常规的从1~n一个个判断是否为非数，另一种是比较巧妙的Hash方法。 常规方法。首先看看判断一个数n是否为素数的方法，因为如果n为合数，则n可以分解为p×q，又n=p×q=(√n)×(√n)，假设p是较小数的话，则p≤(√n)。所以我们只需要从2~(√n)判断能否被n整除，时间复杂度为O(n^0.5)。从1~n都需要判断是否为素数，所以总的时间复杂度为O(n^1.5)。 完整代码如下：

class Solution {
private:
    bool isPrime(int x)
    {
        if (x <= 1)
            return false;
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0)
                return false;
        }
        return true;
    }
public:
    int countPrimes(int n)
    {
        int ans = 0;
        for (int i = 1; i < n; ++i) {
            if (isPrime(i))
                ++ans;
        }
        return ans;
    }
};

本代码提交TLE，在n很大的时候无法通过测试。

后来看了Hint，解法还是很巧妙的。如果一个数n是素数，则n的倍数肯定不是素数了，比如2是素数，则4=2*2、6=2*3、8=2*4…这些数肯定就不是素数了。所以我们可以建立一个1~n的Hash表，表示一个数是否为素数。初始的时候Hash[1~n]=true。然后从2开始，如果Hash[i]为true，说明i是素数，则2*i, 3*i,…都不是素数了，即Hash[2*i], Hash[3*i]..=false。如果Hash[i]为false，说明i不是素数，则i可以分解为i=p*q，使得p（或q）为素数，则之前测试p时，已经把p的所有倍数都置为false了，而i的倍数肯定也是p的倍数，所以不需要对i的倍数再置false了。

循环的终止条件是i>(√n)，和第一种解法的分析一样，如果某个合数x大于(√n)，则其肯定有一个素因子i是小于(√n)的，所以在测试i时，就已经把x置为false了。

另外对于素数i，我们之前分析的是要把所有2*i, 3*i…都置为false。其实这里也可以优化，我们可以从i*i开始置为false，而不需要每次都从2*i开始。比如i=5，常规是要把所有2*5, 3*5, 4*5, 5*5,…都置为false，但其实2*5, 3*5, 4*5都已经被之前的素数2或3置为false了。所以每次我们只需要从i*i开始，下标以i递增的置为false就好。（从i*i到i*i+(i-1)之间的合数被比i小的合数置为false了）总的来说，这一题加速的技巧很多，完整代码如下：

class Solution {
public:
    int countPrimes(int n)
    {
        vector<bool> mark(n, true);
        for (int i = 2; i * i < n; ++i) {
            if (!mark[i])
                continue;
            for (int j = i * i; j < n; j += i) {
                mark[j] = false;
            }
        }
        int ans = 0;
        for (int i = 2; i < n; ++i)
            ans += (mark[i] ? 1 : 0);
        return ans;
    }
};

本代码提交AC，用时29MS。

189. Rotate Array

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

• Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
• Could you do it in-place with O(1) extra space?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

• 1 <= nums.length <= 2 * 10^4
• It’s guaranteed that nums[i] fits in a 32 bit-signed integer.
• k >= 0

本题要把一个数组向右旋转k步，尽量想出3种方法。
首先，无论什么解法，都先判断一下n是否小于2，如果是的话，不管k是多少，都不必旋转了。其次，执行k%=n，因为移动n的倍数位相当于没移动。
暴力解法是每次保留最后一位数字，然后把前n-1个数往后移动一位，重复操作k次。代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        while (k–) {
            int last = nums[n – 1];
            int j = n – 2;
            while (j >= 0) {
                nums[j + 1] = nums[j];
                –j;
            }
            nums[0] = last;
        }
    }
};

本代码提交TLE，过不了最后一个大数据集，因为最坏是O(n^2)复杂度。
稍微高明一点的方法是，先把末尾k位数保存到一个临时数组中，然后一次性把前n-k个数移动到末尾，最后再把临时数组中的数据回帖到原数组开头。完整代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        vector<int> right(nums.begin() + n – k, nums.end());
        int i = n – k – 1, j = n – 1;
        while (i >= 0)
            nums[j–] = nums[i–];
        i = 0;
        while (i < k) {
            nums[i] = right[i];
            ++i;
        }
    }
};

本代码提交AC，用时29MS。
还可以对上述解法稍加变换，即把末尾k位数保存到临时数组right中，然后把原数组的前n-k个数拼接到right的后面，vector的拼接可以用insert。思路和上述算法是一样的。代码如下：

class Solution {
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        vector<int> right(nums.begin() + n – k, nums.end());
        right.reserve(n);
        right.insert(right.end(), nums.begin(), nums.begin() + n – k);
        nums = right;
    }
};

本代码提交AC，用时19MS。
最后还有一种很巧妙的方法，比如题目中的例子，要对1,2,3,4,5,6,7向右旋转3位，我们可以首先对整个数组逆序一下（reverse），编程7,6,5,4,3,2,1，然后再对前k=3，后n-k=4个数分别逆序，得到5,6,7,1,2,3,4，这不就是最终答案吗，很有意思。数组逆序可以直接用STL中的reverse，其实也可以自己实现，就是收尾元素不断交换swap。这种解法是常数空间复杂度、O(n)时间复杂度的，代码如下：

class Solution {
private:
    void my_reverse(vector<int>::iterator bg, vector<int>::iterator ed)
    {
        –ed;
        while (bg < ed) {
            swap(*bg, *ed);
            ++bg;
            –ed;
        }
    }
public:
    void rotate(vector<int>& nums, int k)
    {
        int n = nums.size();
        if (n < 2 || k % n == 0)
            return;
        k %= n;
        my_reverse(nums.begin(), nums.end());
        my_reverse(nums.begin(), nums.begin() + k);
        my_reverse(nums.begin() + k, nums.end());
    }
};

本代码提交AC，用时19MS。

172. Factorial Trailing Zeroes

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

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

本题要求n的阶乘结果中末尾有多少个数字0。暴力方法就是先把n!求出来，然后不断除10算末尾0的个数，但是暴力方法无法满足log(n)的时间复杂度。 参考网上的题解：http://www.geeksforgeeks.org/count-trailing-zeroes-factorial-number/，分析得还是很详细的。 要产生一个尾数0，必须是10=2*5，所以算n!中min(2的素因子，5的素因子），就有多少个0。简单考察一下5!= (2 * 2 * 2 * 3 * 5)，11!= (2 ⁸ * 3⁴ * 5² * 7)，即n!中2的素因子个数肯定要比5的素因子个数要多，这个也是可以证明的。比如从5k+1到5(k+1)，只多了一个5的素因子， 但是[5k+1, 5k+2]至少多了一个2的素因子，从[5k+3, 5k+4]又至少多了一个2的素因子。所以2的素因子要多于5的素因子。
下面就把问题转换为求n!中5的素因子的个数。

举一个例子20!=1*2*3*4*5*6*7*8*9*10*11*12*13*14*15*16*17*18*19*20，能够分解出5的素因子的数只有5,10,15,20，一共4=floor(20/5)。所以20!=2432902008176640000有4个尾数0。所以n!中5的素因子的个数是floor(n/5)？

且慢，如果n=25，floor(n/5)=5，但是25=5*5能分解出两个5的素因子，所以25!中应该有六个5的素因子。所以每增加一个25的倍数的数，5的素因子的个数加1；同理每增加一个125的倍数的数，5的素因子要加2，但因为125的倍数的数肯定是25的倍数的数，所以我们在求25的倍数的数的时候已经求过一次125倍数的数的个数了，结果就是5的个数=floor(n/5)+floor(n/25)+floor(n/125)+…
完整代码如下，注意i要是long long类型的，否则可能溢出。

class Solution {
public:
    int trailingZeroes(int n)
    {
        int ans = 0;
        for (long long i = 5; n / i >= 1; i *= 5) {
            ans += n / i;
        }
        return ans;
    }
};

本代码提交AC，用时3MS。
还有一种解法，思路是一样的：

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

第一种解法是固定分子不变，第二种解法是固定分母不变，结果是一样的。

165. Compare Version Numbers

Compare two version numbers version1 and version2.
If version1 > version2 return 1; if version1 < version2 return -1;otherwise return 0.

You may assume that the version strings are non-empty and contain only digits and the . character.

The . character does not represent a decimal point and is used to separate number sequences.

For instance, 2.5 is not “two and a half” or “half way to version three”, it is the fifth second-level revision of the second first-level revision.

You may assume the default revision number for each level of a version number to be 0. For example, version number 3.4 has a revision number of 3 and 4 for its first and second level revision number. Its third and fourth level revision number are both 0.

Example 1:

Input: version1 = "0.1", version2 = "1.1"
Output: -1

Example 2:

Input: version1 = "1.0.1", version2 = "1"
Output: 1

Example 3:

Input: version1 = "7.5.2.4", version2 = "7.5.3"
Output: -1

Example 4:

Input: version1 = "1.01", version2 = "1.001"
Output: 0
Explanation: Ignoring leading zeroes, both “01” and “001" represent the same number “1”

Example 5:

Input: version1 = "1.0", version2 = "1.0.0"
Output: 0
Explanation: The first version number does not have a third level revision number, which means its third level revision number is default to "0"

Note:

1. Version strings are composed of numeric strings separated by dots . and this numeric strings may have leading zeroes.
2. Version strings do not start or end with dots, and they will not be two consecutive dots.

本题要求比较两个版本号的大小。简单题，按点.分隔，然后转换为int依次比较就好。 为了防止有的版本号没有点.，开始先给两个版本号末尾添加上一个点。另外1.0和1这两个版本号是相等的，所以如果版本位数有差别时，需要补0，而不是简单的认为长的比短的大。 完整代码如下：

class Solution {
public:
    int compareVersion(string version1, string version2)
    {
        version1 += ".";
        version2 += ".";
        size_t p1 = version1.find(‘.’), p2 = version2.find(‘.’);
        int v1, v2;
        while (p1 != string::npos || p2 != string::npos) {
            if (p1 == string::npos)
                v1 = 0;
            else {
                v1 = atoi(version1.substr(0, p1).c_str());
                version1 = version1.substr(p1 + 1);
                p1 = version1.find(‘.’);
            }
            if (p2 == string::npos)
                v2 = 0;
            else {
                v2 = atoi(version2.substr(0, p2).c_str());
                version2 = version2.substr(p2 + 1);
                p2 = version2.find(‘.’);
            }
            if (v1 < v2)
                return -1;
            else if (v1 > v2)
                return 1;
        }
        return 0;
    }
};

本代码提交AC，用时3MS。

二刷。更简洁的代码：

class Solution {
private:
	void ParseVersion(const string &version, vector<int> &v) {
		int n = version.size();
		int i = 0, j = 0;
		while (i < n) {
			j = i + 1;
			while (j < n&&version[j] != '.')++j;
			int tmp = atoi(version.substr(i, j - i).c_str());
			v.push_back(tmp);
			i = j + 1;
		}
	}
public:
	int compareVersion(string version1, string version2) {
		vector<int> v1, v2;
		ParseVersion(version1, v1);
		ParseVersion(version2, v2);
		int i = 0, j = 0, n1 = v1.size(), n2 = v2.size();
		while (i < n1 || j < n2) {
			int a = (i < n1 ? v1[i] : 0);
			int b = (j < n2 ? v2[j] : 0);
			if (a > b)return 1;
			else if (a < b)return -1;
			else {
				++i;
				++j;
			}
		}
		return 0;
	}
};

本代码提交AC，用时8MS。

155. Min Stack

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

本题要实现一个最小栈，使得push, pop, top以及getMin都是以O(1)的时间完成。

这是一个非常经典的双栈法题目，我居然不知道。同时使用两个栈，一个普通的用于存放所有数据allStack，另一个只用于存储最小值序列minStack。 push的时候，每次都把x push进allStack。如果minStack为空，则是第一次push，要把x push进minStack；如果minStack非空，则当x小于等于minStack栈顶时，可以把x push进minStack。注意当x等于minStack栈顶的时候也是需要进栈的，因为有可能有重复元素，比如对0,1,0依次进栈，遇到后面的0时，minStack只有前一个0，此时如果后一个0不进栈，如果下一步是pop的话，就会把minStack中的上一个0 pop掉，那么此时getMin时就会出错，因为此时minStack里没东西了，但allStack还保留着0和1，正确的最小值应该是前一个0。 pop时，allStack正常pop。如果pop出来的值等于minStack的栈顶，则minStack也需要pop。 top就取allStack的top。 getMin就取minStack的top。 完整代码如下：

class MinStack {
private:
    stack<int> allStack, minStack;

public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty()) {
            minStack.push(x);
        }
        else if (x <= minStack.top()) { // 注意是<=而不是<
            minStack.push(x);
        }
        allStack.push(x);
    }
    void pop()
    {
        int top = allStack.top();
        allStack.pop();
        if (top == minStack.top()) {
            minStack.pop();
        }
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC，用时29MS。

二刷。其实可以更简单一点，辅助的minStack大小始终和allStack一样，当新入元素小于minStack栈顶元素时，自然入minStack；否则，就把minStack栈顶的元素再入一次栈。这样就使得两个栈的大小一样，pop的时候可以同时pop，减少了各种if判断。
完整代码如下：

class MinStack {
private:
    stack<int> allStack, minStack;
public: /** initialize your data structure here. */
    MinStack() {}
    void push(int x)
    {
        if (minStack.empty() || x < minStack.top()) {
            minStack.push(x);
        }
        else {
            minStack.push(minStack.top());
        }
        allStack.push(x);
    }
    void pop()
    {
        allStack.pop();
        minStack.pop();
    }
    int top() { return allStack.top(); }
    int getMin() { return minStack.top(); }
};

本代码提交AC，用时29MS。

150. Evaluate Reverse Polish Notation

Evaluate the value of an arithmetic expression in Reverse Polish Notation.

Valid operators are +, -, *, /. Each operand may be an integer or another expression.

Note:

• Division between two integers should truncate toward zero.
• The given RPN expression is always valid. That means the expression would always evaluate to a result and there won’t be any divide by zero operation.

Example 1:

Input: ["2", "1", "+", "3", "*"]
Output: 9
Explanation: ((2 + 1) * 3) = 9

Example 2:

Input: ["4", "13", "5", "/", "+"]
Output: 6
Explanation: (4 + (13 / 5)) = 6

Example 3:

Input: ["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"]
Output: 22
Explanation: 
  ((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22

本题要对一个逆波兰表达式求值。简单题，借助一个堆栈，遇到数字压栈，遇到操作符，把栈顶两个元素弹栈并进行运算。需要注意的是，假设先后弹出来的两个元素是v1,v2，则后续的所有操作都应该是v2 op v1，不要搞错了。 完整代码如下：

class Solution {
public:
    int evalRPN(vector<string>& tokens)
    {
        stack<int> expression;
        for (size_t i = 0; i < tokens.size(); ++i) {
            if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {
                int v1 = expression.top();
                expression.pop();
                int v2 = expression.top();
                expression.pop();
                if (tokens[i] == "+")
                    expression.push(v2 + v1);
                else if (tokens[i] == "-")
                    expression.push(v2 – v1);
                else if (tokens[i] == "*")
                    expression.push(v2 * v1);
                else if (tokens[i] == "/")
                    expression.push(v2 / v1);
            }
            else
                expression.push(atoi(tokens[i].c_str()));
        }
        return expression.top();
    }
};

本代码提交AC，用时9MS。

148. Sort List

Sort a linked list in O(n log n) time using constant space complexity.

Example 1:

Input: 4->2->1->3
Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0
Output: -1->0->3->4->5

本题要求用O(nlogn)的时间复杂度和常数空间复杂度对一个链表排序。 O(nlgn)的排序算法有快速排序、堆排序、归并排序，快排和堆排都需要对元素的随机访问，不适用于链表，这里我们可以用归并排序实现。 归并的思路是不断把链表对分成两个子链表，直到只剩一个节点，此时一个节点是有序的，然后不断的两两归并，mergeList就好办多了。 完整代码如下：

class Solution {
private:
    ListNode* mergeList(ListNode* h1, ListNode* h2)
    {
        if (!h1)
            return h2;
        else if (!h2)
            return h1;
        ListNode *head = new ListNode(0), *h = head;
        while (h1 && h2) {
            if (h1->val < h2->val) {
                h->next = h1;
                h1 = h1->next;
            }
            else {
                h->next = h2;
                h2 = h2->next;
            }
            h = h->next;
        }
        if (h1)
            h->next = h1;
        else if (h2)
            h->next = h2;
        return head->next;
    }
public:
    ListNode* sortList(ListNode* head)
    {
        if (!head || !head->next)
            return head;
        ListNode *slow = head, *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        ListNode* left = sortList(head);
        ListNode* right = sortList(fast);
        return mergeList(left, right);
    }
};

本代码提交AC，用时56MS。

二刷，归并排序还可以写得简单点：

class Solution {
public:
	ListNode* sortList(ListNode* head) {
		if (head == NULL || head->next == NULL)return head;
		ListNode *slow = head, *fast = head, *pre = head;
		while (fast != NULL && fast->next != NULL) {
			pre = slow;
			slow = slow->next;
			fast = fast->next->next;
		}
		pre->next = NULL;
		ListNode *left = sortList(head), *right = sortList(slow);
		ListNode *dummy = new ListNode(0);
		ListNode *lst = dummy;
		while (left != NULL || right != NULL) {
			int l = left != NULL ? left->val : INT_MAX;
			int r = right != NULL ? right->val : INT_MAX;
			if (l < r) {
				lst->next = left;
				left = left->next;
			}
			else {
				lst->next = right;
				right = right->next;
			}
			lst = lst->next;
		}
		return dummy->next;
	}
};

本代码提交AC，用时44MS。

143. Reorder List

Given a singly linked list L: L₀→L₁→…→L_n-1→L_n,
reorder it to: L₀→L_n→L₁→L_n-1→L₂→L_n-2→…

You may not modify the values in the list’s nodes, only nodes itself may be changed.

Example 1:

Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:

Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

本题要求把单链表重新排序，规则是第一个节点接最后一个节点，第二个节点接倒数第二个节点，以此类推。要求in-place，不能借助额外的空间。 这个题我一开始想到的是递归解法，就是首先把L0和Ln接好，然后递归的在L1->…->L(n-1)重排序。但是这样的算法性能肯定很差，因为首先要找到尾节点就很麻烦，还要递归的找尾节点。

看了网上的题解，发现真是巧妙。把链表重排序之后的结果其实相当于先把链表从中点分成前后两段，然后把后半段链表逆序，最后合并两个链表，合并的时候交替从两个链表中取节点拼接起来。 举个例子，0->1->2->3->4，中点是2，分成两段之后就是0->1和2->3->4，然后把第二个链表逆序为4->3->2，最后交替拼接这两个链表，结果就是0->4->1->3->2。、 所以知道思路之后就好办了，找中点可以用快慢指针法，链表逆序用头插法，最后拼接也不是什么难事，不过整合起来代码稍微有点长。 完整代码如下：

class Solution {
public:
    void reorderList(ListNode* head)
    {
        if (head == NULL || head->next == NULL || head->next->next == NULL)
            return; // find mid node
        ListNode *slow = head, *fast = head, *pre = slow;
        while (slow->next != NULL && fast != NULL && fast->next != NULL) {
            pre = slow;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = NULL;
        // reverse [mid,end]
        ListNode *par = new ListNode(0), *tail;
        while (slow) {
            tail = slow->next;
            slow->next = par->next;
            par->next = slow;
            slow = tail;
        }
        //merge 2 list
        par = par->next;
        ListNode *new_head = new ListNode(0), *h = new_head;
        while (head || par) {
            if (head == NULL) {
                h->next = par;
                par = par->next;
            }
            else {
                h->next = head;
                head = head->next;
                h = h->next;
                h->next = par;
                par = par->next;
            }
            h = h->next;
        }
        head = new_head->next;
    }
};

本代码提交AC，用时59MS。