leetcode解题思路分析（二）8-14题

本文主要是介绍leetcode解题思路分析（二）8-14题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

请你来实现一个 atoi 函数，使其能将字符串转换成整数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

说明：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

不算优秀的做法

class Solution {
public:int myAtoi(string str) {int result = 0;stringstream ss;ss << str;ss >> result;return result;}
};

先排除特殊情况，再逐步检查

class Solution {
public:int myAtoi(string str) {int res = 0;int i = 0;int flag = 1;// 1. 检查空格while (str[i] == ' ') { i++; }// 2. 检查符号if (str[i] == '-') { flag = -1; }if (str[i] == '+' || str[i] == '-') { i++; }// 3. 计算数字while (i < str.size() && isdigit(str[i])) {int r = str[i] - '0';// ------ 4. 处理溢出，这是关键步骤 ------if (res > INT_MAX / 10 || (res == INT_MAX / 10 && r > 7)) { return flag > 0 ? INT_MAX : INT_MIN;}// ------------------------------------res = res * 10 + r;i++;}return flag > 0 ? res : -res;}
};

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。

本题有两种做法：1.转化为字符串再进行检索 2. 获取一半的整数和另一半比较。第二种空间使用更少，更优

class Solution {
public:bool isPalindrome(int x) {// 特殊情况：// 如上所述，当 x < 0 时，x 不是回文数。// 同样地，如果数字的最后一位是 0，为了使该数字为回文，// 则其第一位数字也应该是 0// 只有 0 满足这一属性if(x < 0 || (x % 10 == 0 && x != 0)) {return false;}int revertedNumber = 0;while(x > revertedNumber) {revertedNumber = revertedNumber * 10 + x % 10;x /= 10;}// 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。// 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，// 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。return x == revertedNumber || x == revertedNumber/10;}
};

正则表达式匹配
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 ‘.’ 和 ‘*’ 的正则表达式匹配。

‘.’ 匹配任意单个字符
‘*’ 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖整个字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。

采用从后向前检索的方式进行

class Solution {
public:vector<vector<int> > memo;int dfs(const string& s, const string& p, int i, int j) {if (i == s.size()) return j == p.size() ? 1 : -1;if (j == p.size()) return i == s.size() ? 1 : -1;if (memo[i][j] != 0) return memo[i][j];if (j == p.size() - 1 || p[j + 1] != '*') {if (p[j] == '.' || p[j] == s[i]) {memo[i][j] = dfs(s, p, i + 1, j + 1);return memo[i][j];}} else {if (dfs(s, p, i, j + 2) > 0) {memo[i][j] = 1;return memo[i][j];}if (p[j] == '.' || p[j] == s[i]) {bool t = dfs(s, p, i + 1, j + 2) > 0 || dfs(s, p, i + 1, j) > 0;memo[i][j] = t ? 1 : -1;return memo[i][j];}}memo[i][j] = -1;return memo[i][j];}bool isMatch(string s, string p) {s += '#';p += '#';memo = vector<vector<int> >(s.size(), vector<int>(p.size(), 0));return dfs(s, p, 0, 0) > 0;}
};

盛最多水的容器
给定 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

最简单无脑的做法：直接双层循环：

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

第二种思路是：形成的区域受限制于较短的那条，同时距离越远则可能的收益越大。因此我们从最左和最右开始检索，移动较短的那端。

    int maxArea(vector<int> &height){int result = 0;int heightSize = int(height.size());int leftIndex = 0;int rightIndex = heightSize - 1;while (leftIndex != rightIndex){int tmpHeight;int tmpWidth = rightIndex - leftIndex;//短的一侧向中间移动if (height[leftIndex] < height[rightIndex]){tmpHeight = height[leftIndex];leftIndex++;}else{tmpHeight = height[rightIndex];rightIndex--;}int tmpResult = tmpWidth * tmpHeight;if (tmpResult > result){result = tmpResult;}}return result;}

整数转罗马数字

最简单的方式就是将罗马数字存储在数组中，然后依次查找填表即可，简单粗暴但是低效而且不美观：

class Solution {
public:string intToRoman(int num){string result;vector<string> tmpVec1 = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};vector<string> tmpVec2 = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};vector<string> tmpVec3 = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};vector<string> tmpVec4 = {"", "M", "MM", "MMM"};vector<vector<string>> store = {tmpVec1, tmpVec2, tmpVec3, tmpVec4};result.append(store[3][num / 1000 % 10]);result.append(store[2][num / 100 % 10]);result.append(store[1][num / 10 % 10]);result.append(store[0][num % 10]);return result;}
};

更好的做法是贪心算法：存储一个特殊数字的情况，挨个查找并减少数字

class Solution {
public:string intToRoman(int num){string result;int store[] = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};string strs[] = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};//贪心法for (int i = 0; i < 13; i++){while (num >= store[i]){result.append(strs[i]);num -= store[i];}}return result;}
};

罗马数字转整数

class Solution {
public:int romanToInt(string s) {unordered_map<char, int> mp;mp['I'] = 1;mp['V'] = 5;mp['X'] = 10;mp['L'] = 50;mp['C'] = 100;mp['D'] = 500;mp['M'] = 1000;int pos = 0, neg = 0;for (int i = 0;i < s.size()-1;++i){if (mp[s[i]] < mp[s[i+1]])neg -= mp[s[i]];elsepos += mp[s[i]];}pos += mp[s.back()];return pos + neg;           }
};

最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 “”。

最简单的办法就是循环迭代查找，该方法时间复杂度和空间复杂度均很低，而且容易想到。除此之外，还可以使用分治的方法，但是结果并没有更优秀

class Solution {
public:string longestCommonPrefix(vector<string>& strs) {int count = 0;int size = 0;char c;bool end = true;string ret;if (strs.size() == 0)return ret;vector<string>::iterator iter;iter = strs.begin();while (iter != strs.end()){if (size < (*iter).size())size = (*iter).size();iter++;}while (end){iter = strs.begin();c = (*iter)[count];while ((iter + 1) != strs.end()){iter++;if (c != (*iter)[count]){end = false;break;}}if (end){ret += c;count++;}	if (count >= size)return ret;}return ret;}
};