LeetCode Reverse String Write a function that takes a string as input and returns the string reversed. Example: Given s = “hello”, return “olleh”.

LeetCode Fizz Buzz Write a program that outputs the string representation of numbers from 1 to n. But for multiples of three it should output “Fizz” instead of the number and for the multiples of five output “Buzz”. For numbers which are multiples of both three and five output “FizzBuzz”. Example:

n = 15,
Return:
[
    "1",
    "2",
    "Fizz",
    "4",
    "Buzz",
    "Fizz",
    "7",
    "8",
    "Fizz",
    "Buzz",
    "11",
    "Fizz",
    "13",
    "14",
    "FizzBuzz"
]

num1 and num2 represented as string, return the sum of num1 and num2. Note:

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

LeetCode Number of Segments in a String 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

93. Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

Example:

Input: "25525511135"
Output: ["255.255.11.135", "255.255.111.35"]

本题需要给一个数字字符串添加点号，使其成为一个合法的IP地址。
递归求解。首先设置两个数组kMinLen和kMaxLen，表示剩余字符串的最小/大长度，比如开始时step=0，则字符串的长度范围应该是[4,12]。

const vector<int> kMinLen = { 4, 3, 2, 1 };
const vector<int> kMaxLen = { 12, 9, 6, 3 };

然后递归的切当前字符串最多前3个字符，转成int，看是否<=255，如果是，则继续递归。直到step==4且没有剩余字符时，得到一个合法的IP地址。

完整代码如下：

const vector<int> kMinLen = { 4, 3, 2, 1 };
const vector<int> kMaxLen = { 12, 9, 6, 3 };
class Solution {
public:
    void work(vector<string>& ans, string cand, string left, int step)
    {
        if (step == 4) {
            if (left.size() == 0) {
                ans.push_back(cand);
            }
            return;
        }
        if (left.size() >= kMinLen[step] && left.size() <= kMaxLen[step]) {
            int border = min(3, int(left.size()));
            for (int l = 1; l <= border; l++) {
                string part_str = left.substr(0, l);
                if (part_str != "0" && part_str[0] == ‘0’)
                    continue; // 防止"010"这样的leading zero
                int part_int = atoi(part_str.c_str());
                if (part_int <= 255) {
                    string tmp = cand + left.substr(0, l);
                    if (step < 3)
                        tmp += ".";
                    work(ans, tmp, left.substr(l), step + 1);
                }
            }
        }
    }
    vector<string> restoreIpAddresses(string s)
    {
        vector<string> ans;
        string cand = "";
        work(ans, cand, s, 0);
        return ans;
    }
};

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

二刷。使用数组保存ip地址更方便，代码如下：

class Solution {
public:
	void dfs(vector<string>& ans,vector<string>& cand, string &s, int idx) {
		if (cand.size() == 4 && idx == s.size()) {
			string ip = "";
			for (int i = 0; i < cand.size(); ++i) {
				ip = ip + cand[i] + ".";
			}
			ans.push_back(ip.substr(0, ip.size() - 1));
			return;
		}
		if (cand.size() == 4 && idx < s.size())return;
		if (cand.size() < 4 && idx >= s.size())return;
		for (int i = idx; i < s.size() && i < idx + 3; ++i) {
			string part = s.substr(idx, i - idx + 1);
			if (part[0] == '0'&&part.size() > 1)continue;
			int val = stoi(part);
			if (val <= 255) {
				cand.push_back(part);
				dfs(ans, cand, s, i + 1);
				cand.pop_back();
			}
		}
	}
	vector<string> restoreIpAddresses(string s) {
		vector<string> ans;
		vector<string> cand;
		dfs(ans, cand, s, 0);
		return ans;
	}
};

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

71. Simplify Path

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path.

In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level.

Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Example 1:

Input: "/home/"
Output: "/home"
Explanation: Note that there is no trailing slash after the last directory name.

Example 2:

Input: "/../"
Output: "/"
Explanation: Going one level up from the root directory is a no-op, as the root level is the highest level you can go.

Example 3:

Input: "/home//foo/"
Output: "/home/foo"
Explanation: In the canonical path, multiple consecutive slashes are replaced by a single one.

Example 4:

Input: "/a/./b/../../c/"
Output: "/c"

Example 5:

Input: "/a/../../b/../c//.//"
Output: "/c"

Example 6:

Input: "/a//b////c/d//././/.."
Output: "/a/b/c"

简化Unix路径字符串。使用栈数据结构，扫描字符串，获取/之前的字符串，如果是一点.则保持当前路径，什么也不做；如果是两点..则弹栈，否则把字符串压栈。 需要注意的是/../，/.，/…等情况，三个点应该认为一个合法的路径字符串，虽然在Windows上并不合法。所以我们在进行算法之前，不管原始字符串末尾是否包含/，我们都在末尾添加上斜杠/，以便后续统一处理。 扫描完一次字符串之后，把栈内字符串依次弹出并组合成一个简化的路径。 完整代码如下：

class Solution {
public:
    string simplifyPath(string path)
    {
        path += "/";
        stack<string> sPath;
        string p1 = "";
        for (int i = 0; i < path.size(); i++) {
            if (path[i] == ‘/’) {
                if (p1 == "" || p1 == ".") {
                }
                else if (p1 == "..") {
                    if (!sPath.empty())
                        sPath.pop();
                }
                else {
                    sPath.push(p1);
                }
                p1 = "";
            }
            else
                p1 += path[i];
        }
        if (sPath.empty())
            return "/";
        string ans = "";
        while (!sPath.empty()) {
            ans = "/" + sPath.top() + ans;
            sPath.pop();
        }
        return ans;
    }
};

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

二刷。更简洁代码：

class Solution {
public:
	string simplifyPath(string path) {
		stack<string> stk;
		int n = path.size();
		int i = 0, j = 0;
		while (i < n) {
			while (i < n&&path[i] == '/')++i;
			if (i >= n)break;
			j = i + 1;
			while (j < n&&path[j] != '/')++j;
			string name = path.substr(i, j - i);
			if (name == ".." && !stk.empty())stk.pop();
			if (name != "."&&name != "..")stk.push(name);
			i = j;
		}
		string ans = "";
		while (!stk.empty()) {
			ans = "/" + stk.top() + ans;
			stk.pop();
		}
		if (ans == "")return "/";
		else return ans;
	}
};

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

43. Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

1. The length of both num1 and num2 is < 110.
2. Both num1 and num2 contain only digits 0-9.
3. Both num1 and num2 do not contain any leading zero, except the number 0 itself.
4. You must not use any built-in BigInteger library or convert the inputs to integer directly.

把两个以字符串形式存储的非负整数相乘起来，输出字符串结果。很考验基本功的一个题目，使用小学学过的乘法来做，一位一位相乘，然后把每一位相乘的结果加起来得到最终结果。 比如35*423，先调个位置423*35，确保num2长度短于num1，然后我们循环num2的每一位，比如首先5*423=2115，然后3*423=1269，但是加起来的时候要注意，1269要往前缩进一位成12690。最终结果为2115+12690=14805。 所以整个过程需要实现两个辅助函数，两个字符串相加，以及一个字符和字符串相乘的函数。完整代码如下：

class Solution {
public:
    string add(string num1, string num2)
    {
        int i = num1.size() – 1, j = num2.size() – 1;
        string ans = "";
        bool carry = false;
        while (i >= 0 || j >= 0) {
            int sum = (i >= 0 ? (num1[i] – ‘0’) : 0) + (j >= 0 ? (num2[j] – ‘0’) : 0);
            sum += carry ? 1 : 0;
            if (sum >= 10) {
                ans.push_back(sum – 10 + ‘0’);
                carry = true;
            }
            else {
                ans.push_back(sum + ‘0’);
                carry = false;
            }
            i–;
            j–;
        }
        if (carry)
            ans.push_back(‘1’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, char c)
    {
        if (c == ‘0’)
            return "0";
        if (c == ‘1’)
            return num1;
        string ans = "";
        int i = num1.size() – 1;
        int carry = 0;
        while (i >= 0) {
            int prod = (num1[i] – ‘0’) * (c – ‘0’);
            prod += carry;
            if (prod >= 10) {
                ans.push_back(prod % 10 + ‘0’);
                carry = prod / 10;
            }
            else {
                ans.push_back(prod + ‘0’);
                carry = 0;
            }
            i–;
        }
        if (carry > 0)
            ans.push_back(carry + ‘0’);
        reverse(ans.begin(), ans.end());
        return ans;
    }
    string multiply(string num1, string num2)
    {
        if (num1.size() < num2.size()) { // 确保num1长于num2 string tmp = num2; num2 = num1; num1 = tmp; } string ans = "0"; int j = num2.size() – 1, k = 0; // k:缩进的位数 while (j >= 0) { string p = multiply(num1, num2[j]); for (int i = 0; i < k; i++) p.push_back(‘0’); ans = add(ans, p); j–; k++; } return ans; } };

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

二刷。上述解法不够简洁，讨论区有一种很漂亮的解法：https://discuss.leetcode.com/topic/30508/easiest-java-solution-with-graph-explanation/60，图片解释如下：

也就是可以算出来两个digit相乘的结果在最终结果中的下标位置，比如上图中123*45，num1的2乘以num2的4的结果是8，对应的下标分别是num1的i=1和num2的j=0，两个digit相乘结果最多可以占两位，这两位在最终结果中的下标是i+j和i+j+1，这个例子就是i+j=1,j+j+1=2，相乘结果08正好叠加在最终结果的第1和2位。
完整代码如下：

class Solution {
public:
    string multiply(string num1, string num2)
    {
        int n1 = num1.size(), n2 = num2.size();
        vector<int> ans(n1 + n2, 0);
        for (int i = n1 – 1; i >= 0; –i) {
            for (int j = n2 – 1; j >= 0; –j) {
                int mul = (num1[i] – ‘0’) * (num2[j] – ‘0’);
                int p1 = i + j, p2 = i + j + 1;
                int sum = mul + ans[p2];
                ans[p1] += sum / 10;
                ans[p2] = sum % 10;
            }
        }
        string ret = "";
        int i = 0;
        while (i < n1 + n2 && ans[i] == 0)
            ++i;
        if (i >= n1 + n2)
            return "0";
        while (i < n1 + n2) {
            ret.push_back(‘0’ + ans[i]);
            ++i;
        }
        return ret;
    }
};

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

三刷。巧妙方法还是没记住，下面依然是小学生解法，只不过代码好看一点。

class Solution {
public:
	string SingleMultiply(string s, char c) {
		string ans = "";
		int vc = c - '0';
		int carry = 0;
		for (int i = s.size() - 1; i >= 0; --i) {
			int vs = s[i] - '0';
			int prod = vc * vs + carry;
			ans.push_back('0' + (prod % 10));
			carry = prod / 10;
		}
		if (carry > 0)ans.push_back(carry + '0');
		return ans;
	}
	string multiply(string num1, string num2) {
		int n1 = num1.size(), n2 = num2.size();
		if (n1 > n2)return multiply(num2, num1);
		if (num1 == "0")return "0";
		vector<string> prods;
		int max_len = 0;
		for (int i = n1 - 1; i >= 0; --i) {
			string prod = string(n1 - i - 1, '0') + SingleMultiply(num2, num1[i]);
			max_len = prod.size() > max_len ? prod.size() : max_len;
			prods.push_back(prod);
		}
		string ans = "";
		int carry = 0;
		for (int i = 0; i < max_len; ++i) {
			int val = 0;
			for (int j = 0; j < prods.size(); ++j) {
				if (i < prods[j].size())val += (prods[j][i] - '0');
			}
			val += carry;
			ans.push_back('0' + (val % 10));
			carry = val / 10;
		}
		if (carry > 0)ans.push_back('0' + carry);
		reverse(ans.begin(), ans.end());
		return ans;
	}
};

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