程序员进阶之算法练习（四十九）LeetCode
正文
题目1.两数之和
题目链接 题目大意： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
题目解析： 先不考虑复杂度，直接两个for循环，对于每个数字nums[i]，寻找target-nums[i]是否也在数组； 这样的时间复杂度为O(N^2)，可以牺牲一些空间来换取更快的速度：比如说把已经出现过的数字用hash表直接存下来，这样下次用hash表直接循环该数字是否存在。 题目的要求还要输出数组下标，那么可以用hash表的值来存数组下标。
class Solution {
unordered_map<int, int> mp;
public:
vector<int> twoSum(vector<int>& nums, int target) {
mp.clear();
vector<int> ans;
for (int i = 0; i < nums.size(); ++i) {
if (mp[target - nums[i]]) {
ans.push_back(i);
ans.push_back(mp[target - nums[i]] - 1);
break;
}
mp[nums[i]] = i + 1;
}
return ans;
}
}leetcode;2.整数反转
题目链接 题目大意： 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1: 输入: 123 输出: 321
示例 2: 输入: -123 输出: -321
示例 3: 输入: 120 输出: 21
注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
题目解析： 将负号单独拿出来考虑，只考虑整数的翻转。
因为最终结果可能超过int范围，那么可以用long long来处理。
class Solution {
public:
int reverse(int x) {
lld ret = 0, flag = x < 0 ? -1 : 1;
lld tmp = abs(x), sz = 1;
while (tmp) {
ret = tmp % 10 + ret * 10;
tmp /= 10;
}
lld intLeft = -(1LL << 31), intRight = (1LL << 31) - 1;
if (ret < intLeft || ret > intRight) {
ret = 0;
}
return (int)ret * flag;
}
}leetcode;注意： 1在位移的时候，是按int来处理的，需要改成1LL；
3.字符串转换整数 (atoi)
题目链接 题目大意： 请你来实现一个 atoi 函数，使其能将字符串转换成整数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下： 如果第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字字符组合起来，形成一个有符号整数。 假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成一个整数。 该字符串在有效的整数部分之后也可能会存在多余的字符，那么这些字符可以被忽略，它们对函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。 在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示： 本题中的空白字符只包括空格字符 ' ' 。 假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。
示例 1: 输入: "42" 输出: 42
示例 2: 输入: " -42" 输出: -42 解释: 第一个非空白字符为 '-', 它是一个负号。 我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。
示例 3: 输入: "4193 with words" 输出: 4193 解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。
示例 4: 输入: "words and 987" 输出: 0 解释: 第一个非空字符是 'w', 但它不是数字或正、负号。 因此无法执行有效的转换。
示例 5: 输入: "-91283472332" 输出: -2147483648 解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 因此返回 INT_MIN (−231) 。
题目解析： 按照题目的要求实现，拆分出来具体的过程。 1、还未进行数字转换的状态，hasConvert=false，此时可以允许空格跳过； 2、遇到+、-、数字之后，hasConvert=true，不允许空格跳过，遇到非数字符号结束转化； 3、符号和数字分开处理，超过int大小分别出来，可以用long long来暂存；
整体代码不复杂。
class Solution {
public:
int myAtoi(string str) {
long long ret = 0;
int flag = 0; // 前置符号， 0表示还没放过， 1 是正数，-1是负数
bool hasConvert = false;
for (int i = 0; i < str.length(); ++i) {
if (str[i] == '-' || str[i] == '+') {
if (flag) {
return flag * ret;
}
flag = str[i] == '-' ? -1 : 1;
hasConvert = true;
}
else if (str[i] >= '0' && str[i] <= '9') {
if (!flag) flag = 1;
hasConvert = true;
ret = ret * 10 + str[i] - '0';
if (flag * ret < -(1LL << 31)) {
return -(1LL << 31);
}
if (flag * ret > (1LL << 31) - 1) {
return (1LL << 31) - 1;
}
}
else if (!hasConvert && str[i] == ' ') {
continue;
}
else {
return flag * ret;
}
}
return flag * ret;
}
}lc;注意： 题目很坑，+1 这种数据也没有说明； +03这种，会认为是数字3，题目的严谨程度较差；
4.回文数
题目链接 题目大意： 判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
示例 1: 输入: 121 输出: true
示例 2: 输入: -121 输出: false 解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3: 输入: 10 输出: false 解释: 从右向左读, 为 01 。因此它不是一个回文数。
题目解析： 将数字转成字符串，然后开始从左右两边开始遍历，如果遇到不一样的字符串则输出false； 如果没有发现不一样的字符，则左右边界递进，则最后输出true；
class Solution {
public:
bool isPalindrome(int x) {
char s[20];
sprintf(s, "%d", x);
int end = strlen(s) - 1, st = 0;
while (st < end) {
if (s[st] != s[end]) {
return false;;
}
++st;
--end;
}
return true;
}
}leetcode;思考： 如果是要在字符串中找出最长的回文串呢？
5.最长公共前缀
题目链接 题目大意： 编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1: 输入: ["flower","flow","flight"] 输出: "fl"
示例 2: 输入: ["dog","racecar","car"] 输出: ""
解释: 输入不存在公共前缀。 说明: 所有输入只包含小写字母 a-z 。
题目解析： 前缀和，直接for循环遍历。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string ret;
while (true && strs.size()) {
for (int i = 0; i < strs.size(); ++i) {
if (strs[i].size() < ret.length() + 1) {
return ret;
}
if (i > 0 && strs[i][ret.length()] != strs[0][ret.length()]) {
return ret;
}
}
ret.push_back(strs[0][ret.length()]);
}
return ret;
}
}leetcode;注意： vector为空的情况。
总结
题目1，需要用hash来降低复杂度，unordered_map是很不错的hash选项； 题目2，反过来计算整数即可，边界问题是int范围，改一改就是很不错的题目； 题目3，这是一道题意比较复杂的模拟题，但是拆分出几点规则之后，代码还是比较清爽； 题目4，直接转成字符串，走字符串匹配；（思考题 O(N)回文串算法-Manacher） 题目5，直接遍历计算，算法的复杂度也没有太多优化空间；