|
#1 Two Sum
#7 Reverse Integer
#9 Palindrome Number
#13 Roman to Integer
#14 Longest Common Prefix
#1 Two Sum
要求：给定数组，给定target，找出数组中的2个值和等于target，输出2个数字的索引
思路1：笨办法，二重循环,O(n^2)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int>result;
for(int i=0; i<nums.size()-1; i++)
for(int j=i+1; j<nums.size(); j++)
{
if(nums[i]+nums[j] == target)
{
result.push_back(i);
result.push_back(j);
break;
}
}
return result;
}
};
参考大神博客园：Grandyang
思路2：采用HashMap保存，HashMap查找为常数级。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>m;
vector<int>result;
for(int i=0; i<nums.size(); i++)
m[nums[i]]=i;
for(int j=0; j<nums.size(); j++)
{
int diff = target - nums[j];
if(m.count(diff) && j!= m[diff])
{
result.push_back(m[diff]);
result.push_back(j);
break;
}
}
return result;
}
};
思路2改进：将2层for循环缩减为1个
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>m;
for(int i=0; i<nums.size(); i++)
{
if(m.count(target-nums[i]))
return {i,m[target-nums[i]]};
m[nums[i]]=i;
}
return {};
}
};
#7 Reverse Integer
要求：将给定的整数反转
思路1：
先考虑大数（超过231-1和小于-2-31的，直接返回0）
记下符号正负；采用to_string()函数转换为int，记录位数，反转string；再转回int；
根据符号位，修正整数；
根据个数和0，修正结果；
问题：只能通过部分用例，大数用例(溢出)无法通过。
class Solution {
public:
int reverse(int x) {
if( x > (pow(2,31)-1) || x < -(pow(2,31)))
return 0;
int flag = 0;
if(x > 0)
flag = 1;
string str = to_string(x);
::reverse(str.begin(), str.end());
int result = atoi(str.c_str());
if(flag == 0)
result = -result;
if(str.size() <=1 && result == 0)
return 0;
return result;
}
};
参考大神博客园：Grandyang
思路2：根本没有我写的那么复杂，太菜了，取模后得到还是负数；
class Solution {
public:
int reverse(int x) {
int result = 0;
while(x!=0)
{
if(abs(result) > INT_MAX/10) return 0;
result = result*10 + x%10;
x /= 10;
}
return result;
}
};
思路2扩展代码
class Solution {
public:
int reverse(int x) {
long result = 0;
while(x!=0)
{
result = result*10 + x%10;
x /= 10;
}
return result > INT_MAX || result < INT_MIN ? 0 : result;
}
};
#9 Palindrome Number
要求：如果是回文数，例如12321，返回true
思路1：转为字符串1，反转得到字符串2；比较字符串1和2是否相同,一次通过.
class Solution {
public:
bool isPalindrome(int x) {
string str1 = to_string(x);
string str2 = str1;
::reverse(str2.begin(),str2.end());
return str1==str2 ? true : false;
}
};
思路2：如果是负数，返回false，反转数字，比较大小
class Solution {
public:
bool isPalindrome(int x) {
if(x<0) return false;
long res = 0;
int y = x;
while(y!=0)
{
res = res*10 + y%10;
y /= 10;
}
return res == x;
}
};
参考大神博客园：Grandyang
思路3：每次取出首尾数字，直接对比，学习了。
class Solution {
public:
bool isPalindrome(int x) {
if(x<0) return false;
int div = 1;
while( x/div >= 10) div*=10;
while(x>0)
{
int left = x/div;
int right = x%10;
if( left != right ) return false;
x = (x%div)/10;
div/=100;
}
return true;
}
};
思路4：都是大神的想法啊，佩服
反转后半部分，然后再和前半部分做对比
class Solution {
public:
bool isPalindrome(int x) {
if( x<0 || (x%10==0 && x>0) ) return false;
int reverseNum = 0;
while(x>reverseNum)
{
reverseNum = reverseNum*10 + x%10;
x/=10;
}
return x== reverseNum || x == reverseNum/10;
}
};
思路5：直接调用上一题的Reverse()函数，求得反转后的数字，做对比
class Solution {
public:
bool isPalindrome(int x) {
if( x<0 || (x%10==0 && x>0) ) return false;
return x == reverse(x);
}
int reverse(int x) {
int res = 0;
while (x != 0) {
if (res > INT_MAX / 10) return -1;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
};
#13 Roman to Integer
要求：按照罗马数字原则，给定string，返回整数
思路1：就是按照字母的样式，输出对应的数字，逐渐向后遍历相加，就是代码太丑陋了。。。
class Solution {
public:
int romanToInt(string s) {
int result = 0;
int len = s.size();
int i = 0;
while(i<s.size())
{
switch(s[i])
{
case 'I':
if(i+1<len)
{
if(s[i+1] == 'V') {result+=4;i+=2;break;}
else if(s[i+1] == 'X') {result+=9;i+=2;break;}
}
result+=1;i++;break;
case 'V':
{result+=5;i++;break;}
case 'X':
if(i+1<len)
{
if(s[i+1] == 'L') {result+=40;i+=2;break;}
else if(s[i+1] == 'C') {result+=90;i+=2;break;}
}
result+=10;i++;break;
case 'L':
{result+=50;i++;break;}
case 'C':
if(i+1<len)
{
if(s[i+1] == 'D') {result+=400;i+=2;break;}
else if(s[i+1] == 'M') {result+=900;i+=2;break;}
}
result+=100;i++;break;
case 'D':
{result+=500;i++;break;}
case 'M':
{result+=1000;i++;break;}
}
}
return result;
}
};
参考大神博客园：Grandyang
思路2：很妙；如果当前数字是最后一个||后一个数字比它小，直接加；否则减去这个数字。绝了。真厉害。
class Solution {
public:
int romanToInt(string s) {
unordered_map<char,int> m {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int result = 0;
for(int i = 0; i<s.size();i++)
{
int val = m[s[i]];
if(i == s.size()-1 || m[s[i]] >= m[s[i+1]]) result+=val;
else result-=val;
}
return result;
}
};
思路3：也很巧，先加，后边发现了再减去2倍即可，觉得我的脑子真是菜。。。
class Solution {
public:
int romanToInt(string s) {
unordered_map<char,int> m {{'I',1},{'V',5},{'X',10},{'L',50},{'C',100},{'D',500},{'M',1000}};
int result = 0;
for(int i = 0; i<s.size();i++)
{
if(i == 0 || m[s[i]] <= m[s[i-1]]) result+= m[s[i]];
else result = result + m[s[i]] -2*m[s[i-1]];
}
return result;
}
};
#14 Longest Common Prefix
要求：给定字符串数组，找最长公共前缀
思路1：没思路，主要是想复杂了。翻看了大神博文，我还以为是找出所有字符串中相同的部分。其实只是找出共同前缀就行，从下标0开始找。找不到即可。
按照二维数组，第一个单词的每个字符 作为外循环，依次查找，发现有的字符串很短，或者，遇到不相同的前缀，返回即可。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
string result = "";
for(int j = 0; j < strs[0].size(); j++)
{
char c = strs[0][j];
for(int i = 1; i<strs.size(); i++)
{
if( j > strs[i].size() || c!= strs[i][j] )
return result;
}
result.push_back(c);
}
return result;
}
};
参考大神博客园：Grandyang
思路2：思路同1，只是不保存字符，采用string的substr()函数，停止时，将先前的字符串提取出即可。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
for(int j = 0; j < strs[0].size(); j++)
{
for(int i = 0; i < strs.size();i++)
{
if(j> strs[i].size() || strs[i][j]!=strs[0][j])
return strs[i].substr(0,j);
}
}
return strs[0];
}
};
思路3：将字符串排个序，然后，找到共同的部分。取出。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.empty()) return "";
sort(strs.begin(),strs.end());
int i = 0, len = min(strs[0].size(),strs.back().size());
while(i<len && strs[0][i]== strs.back()[i]) i++;
return strs[0].substr(0,i);
}
};
|