14. Longest Common Prefix

Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string "".

Example 1:

Input: ["flower","flow","flight"]
Output: "fl"

Example 2:

Input: ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Note:

All given inputs are in lowercase letters a-z.

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs)
    {
        if (strs.size() == 0)
            return "";
        int max_common = INT_MAX;
        string longest_common = "";
        for (int i = 0; i < strs.size(); i++)
            if (strs[i].size() < max_common)
                max_common = strs[i].size();
        for (int i = 0; i < max_common; i++) {
            for (int j = 1; j < strs.size(); j++) {
                if (strs[j][i] != strs[0][i])
                    return longest_common;
            }
            longest_common += strs[0][i];
        }
        return longest_common;
    }
};

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

二刷。简洁版代码如下：

class Solution {
public:
	string longestCommonPrefix(vector<string>& strs) {
		int n = strs.size(), i = 0;
		if (n == 0)return "";
		while (true) {
			bool valid = true;
			for (int j = 0; j < n; ++j) {
				if (i >= strs[j].size() || strs[j][i] != strs[0][i]) {
					valid = false;
					break;
				}
			}
			if (!valid)break;
			else ++i;
		}
		return strs[0].substr(0, i);
	}
};

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

13. Roman to Integer

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

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

Example 1:

Input: "III"
Output: 3

Example 2:

Input: "IV"
Output: 4

Example 3:

Input: "IX"
Output: 9

Example 4:

Input: "LVIII"
Output: 58
Explanation: L = 50, V= 5, III = 3.

Example 5:

Input: "MCMXCIV"
Output: 1994
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

这一题是LeetCode Integer to Roman的姊妹篇，只需从左往右依次解析字符串即可，优雅版本如下：

class Solution {
public:
    int romanToInt(string s)
    {
        vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
        vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
        int ans = 0;
        for (int i = nums.size() – 1; i >= 0; i–) {
            int sz = symbol[i].size();
            while (s.size() >= sz && s.substr(0, sz) == symbol[i]) {
                ans += nums[i];
                s = s.substr(sz);
            }
        }
        return ans;
    }
};

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

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

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

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

本题要求把一个阿拉伯数字转换为罗马数字。 首先要了解罗马数字的表示形式，具体看Roman numerals WIKI。 罗马数字由上左图的7个基本字母组成，直接递归很容易求解。但是会有一些特殊情况，比如4，如果递归求解就是IIII，为了简便，采用5-1也就是IV的形式。上面右图就是基本的特殊情况。考虑特殊情况之后的递归代码如下：

class Solution {
public:
    string work(int num, string cur)
    {
        if (num >= 1000)
            return work(num – 1000, cur + "M");
        if (num >= 500) {
            if (num >= 900)
                return work(num – 900, cur + "CM");
            return work(num – 500, cur + "D");
        }
        if (num >= 100) {
            if (num >= 400)
                return work(num – 400, cur + "CD");
            return work(num – 100, cur + "C");
        }
        if (num >= 50) {
            if (num >= 90)
                return work(num – 90, cur + "XC");
            return work(num – 50, cur + "L");
        }
        if (num >= 10) {
            if (num >= 40)
                return work(num – 40, cur + "XL");
            return work(num – 10, cur + "X");
        }
        if (num >= 5) {
            if (num >= 9)
                return work(num – 9, cur + "IX");
            return work(num – 5, cur + "V");
        }
        if (num < 5) {
            if (num >= 4)
                return work(num – 4, cur + "IV");
            while (num > 0) {
                cur += "I";
                num–;
            }
            return cur;
        }
    }
    string intToRoman(int num) { return work(num, ""); }
};

本代码提交AC，用时32MS，这么多if语句，真是不够优雅。后来看到网上一种解法，简洁漂亮许多，贴出来学习一下：

class Solution {
public:
    string intToRoman(int num)
    {
        vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
        vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
        string ans = "";
        for (int i = nums.size() – 1; i >= 0; i--) {
            while (num >= nums[i]) {
                ans += symbol[i];
                num -= nums[i];
            }
        }
        return ans;
    }
};

本代码提交AC，用时56MS，比上一版稍慢，不够这版更好看。

11. Container With Most Water

Given n non-negative integers a₁, a₂, …, a_n , where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example:

Input: [1,8,6,2,5,4,8,3,7]
Output: 49

题意是x轴上立着一堆线段，从这些线段中找两根和x轴构成一个木桶，问哪个木桶能装最多的水。 暴力枚举的话，是$O(n^2)$的。我们可以用贪心的思路来解决：要使木桶装更多的水，短板越长越好，且两根线之间的距离越长也越好。 设置首尾指针i,j，计算由i,j夹到的木桶的体积（这里简单点，面积即可），如果height[i]<height[j]，则i++，因为短板越长越好，所以这相当于抛弃了height[i]，保留height[j]，底板减1。
完整代码如下：

class Solution {
public:
    int maxArea(vector<int>& height)
    {
        int mA = 0, i = 0, j = height.size() – 1;
        while (i != j) {
            int cur = min(height[i], height[j]) * (j – i);
            if (cur > mA)
                mA = cur;
            if (height[i] < height[j])
                i++;
            else
                j--;
        }
        return mA;
    }
};

本代码提交AC，用时24MS。
二刷。
证明贪心方法的正确性一般用反证法，推出矛盾即可，证明过程见讨论区：https://discuss.leetcode.com/topic/503/anyone-who-has-a-o-n-algorithm。

三刷。反证法过程：刚开始的时候l=0,r=n-1，假设此时height[l]<height[r]，则此时的组合对l来说是它能形成最大面积的情况。因为x轴长度最大，当r往左边走的时候，x肯定会变小；如果r往左走遇到比l更短的y，则总的y变短，面积变小；如果r往左走遇到比l更长的y，则依然是l作为y，但因为x已经变小了，所以面积依然变小。总之，每一次组合，都是对更短的那个柱子的最大面积，而更长的柱子还有可能和其他柱子组成更大的面积，所以我们每次丢掉短柱子，保留长柱子。

9. Palindrome Number

Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.

Example 1:

Input: 121
Output: true

Example 2:

Input: -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:

Input: 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Follow up:

Coud you solve it without converting the integer to a string?

这一题很有意思，要我们判断一个整数是否是回文数。 首先负数不是回文数，个位数是回文数。但是怎样判断大于9的整数是否是回文数呢？ 首先想到的是把int转换为string表示，这样就很方便判断了，但是题目要求不能用额外的存储空间，也就是不能用和x位数线性以上的存储空间，当然几个常数空间是可以的。 后来想依次取出数字的首尾数字，判断是否相等。但是中间有0出现时会有问题，比如1000021，去掉首尾1之后只剩int x=2了，导致判断错误。 还有一个办法是将x转换为x的逆序x’，然后依次判断x和x’的末尾是否相等，但是x’可能超出int表示范围，又作罢。 后来观察发现，回文数字765567在转换为逆序数的过程中，肯定有某个状态，x==x’，比如765=765，而这时x’肯定不会超出int的表示范围。所以我们可以在边逆序的时候边判断。 完整代码如下：

class Solution {
public:
    bool isPalindrome(int x)
    {
        if (x < 10)
            return x >= 0;
        if (x % 10 == 0)
            return false;
        int y = 0;
        while (x > y) {
            y = y * 10 + x % 10;
            if (x == y) //76567
                return true;
            x /= 10;
            if (x == y) //765567
                return true;
        }
        return false;
    }
};

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

二刷。常规解法，取出每一位数字进行判断：

class Solution {
public:
    bool isPalindrome(int x) {
        if(x < 0) return false;
        if(x == 0) return true;
        if(x % 10 == 0) return false;
        
        vector<int> digits;
        while(x != 0) {
            digits.push_back(x % 10);
            x /= 10;
        }
        int l = 0, r = digits.size() - 1;
        while(l < r) {
            if(digits[l] != digits[r]) return false;
            ++l;
            --r;
        }
        return true;
    }
};

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

7. Reverse Integer

Given a 32-bit signed integer, reverse digits of an integer.

Example 1:

Input: 123
Output: 321

Example 2:

Input: -123
Output: -321

Example 3:

Input: 120
Output: 21

Note:
Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2³¹,  2³¹ − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows.

题意就是要我们把整数逆序，需要注意当逆序之后超出int表示范围时，返回0。所以我们用double来保存逆序之后的整数，将其和INT_MAX比较，如果大于INT_MAX，则输出0。 完整代码如下：

class Solution {
public:
    int reverse(int x)
    {
        unsigned int y = (x > 0) ? x : -x;
        double ans = 0;
        while (y) {
            ans = ans * 10 + (y % 10);
            y = y / 10;
        }
        if (ans > INT_MAX)
            return 0;
        return x < 0 ? -ans : ans;
    }
};

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

二刷。如果不用double存储的话，该怎么办？难就难在如何处理越界的问题。我们可以在计算y的过程中判断y是否越界，代码如下。

如果tmp=y*10+reminder>INT_MAX，有两种情况。一种情况是y*10本身就已经>INT_MAX了，此时即y>INT_MAX/10。另一种情况是y*10没>INT_MAX，是加上reminder之后大于的，由于INT_MAX=2147483647，所以如果reminder>7的话，y*10+reminder就会大于INT_MAX。INT_MIN的情况类似。另外，负数的余数也是负数，所以正负数的情况可以合并考虑。

class Solution {
public:
	int reverse(int x) {

		int y = 0;
		while (x != 0) {
			int reminder = x % 10;
			x /= 10;
			if (y > INT_MAX / 10 || (y == INT_MAX / 10 && reminder > 7))return 0;
			if (y < INT_MIN / 10 || (y == INT_MIN / 10 && reminder < -8))return 0;
			y = y * 10 + reminder;
			
		}
		return y;
	}
};

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