leetcode
lc1 & lc15& lc 16 & lc 18
多数之和问题
https://www.jianshu.com/p/0b91c4b3a135
lc 3 & lc11 &lc 42 &lc19 & lc26-双指针
https://www.jianshu.com/p/a69766441eb8
4.找两个数组的中位数
有一种解法是vector直接放在一起，然后排序得到中位数。
我过去的解法：用归并排序做的。归并排序也是用一个新的vector<int>放结果。
还有一种方法，双指针，↓，双指针一个一直移动。
不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 00 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
第一种思路的时间复杂度是 O(m+n)，空间复杂度是 O(m+n)。第二种思路虽然可以将空间复杂度降到 O(1)，但是时间复杂度仍是 O(m+n)。
也可以用二分查找方法，
（二分查找方法，我试了一下，然后被边界和情况绕晕了。）（见LeetCode题解）
二分查找的时间复杂度是O(log(m+n))
6.z字形变换
计算格子差（模拟）
class Solution {
public:
string convert(string s, int numRows) {
if(numRows==0)
return "";
if(numRows==1||s.length()==0)
return s;
if(numRows==2){
string s1="";
string s2="";
for(int i=0;i<s.length();i++){
// cout<<s1<<" "<<s2<<endl;
if(i%2==0){
s1+=s[i];
}else{
s2+=s[i];
}
}
return s1+s2;
}
string res = "";
// vector<string> resarr(5);
string resarr[numRows];//用vector初始化貌似有问题，vector合适的初始化方式
fill(resarr,resarr+numRows,"");
// fill(resarr.begin(),resarr.end(),"");//vector这样不可，但是数组可。
for(int i=0;i<numRows;i++){
int index = i;
int op=0;
int lastindex=-1;
while(index<s.length()){
if(lastindex!=index){
resarr[i]+=s[index];
lastindex=index;
}
if(op==0){
index += 2*numRows-2*i-2;
op=1;
}else if(op==1){
index += 2*i;
op=0;
}
}
}
for(int i=0;i<numRows;i++){
res+=resarr[i];
// cout<<res<<endl;
}
return res;
}
};
7.整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
示例 1：
输入：x = 123
输出：321
示例 2：
输入：x = -123
输出：-321
示例 3：
输入：x = 120
输出：21
示例 4：
输入：x = 0
输出：0
提示：
-231 <= x <= 231 - 1
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-integer
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
对于大数的运用。用了取余和连乘。
#include<cmath>
class Solution {
public:
int reverse(int x) {
long a=INT_MAX;
long b=INT_MIN;
long long result=0;
long long y=(long long)abs((long)x);
long z=y;
while(y>0){
int x=y%10;
result=(result*10+x);
y=y/10;
}
if(result>a || result<b){
return 0;
}
// int a[wei];
// int index=0;
// while(z>0){
// }
if(x>0)
return result;
else
return -result;
}
};
8.字符串转换整数（atoi)
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。
示例 1：
输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："42"（读入 "42"）
^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。
示例 2：
输入：s = " -42"
输出：-42
解释：
第 1 步：" -42"（读入前导空格，但忽视掉）
^
第 2 步：" -42"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步：" -42"（读入 "42"）
^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。
示例 3：
输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。
示例 4：
输入：s = "words and 987"
输出：0
解释：
第 1 步："words and 987"（当前没有读入字符，因为没有前导空格）
^
第 2 步："words and 987"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
^
第 3 步："words and 987"（由于当前字符 'w' 不是一个数字，所以读入停止）
^
解析得到整数 0 ，因为没有读入任何数字。
由于 0 在范围 [-231, 231 - 1] 内，最终结果为 0 。
示例 5：
输入：s = "-91283472332"
输出：-2147483648
解释：
第 1 步："-91283472332"（当前没有读入字符，因为没有前导空格）
^
第 2 步："-91283472332"（读入 '-' 字符，所以结果应该是负数）
^
第 3 步："-91283472332"（读入 "91283472332"）
^
解析得到整数 -91283472332 。
由于 -91283472332 小于范围 [-231, 231 - 1] 的下界，最终结果被截断为 -231 = -2147483648 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/string-to-integer-atoi
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
思路：
完全按照要求写下来，可能需要注意很多细节。
这里需要使用long。
C++里最大最小 INT_MIN,INT_MAX
class Solution {
public:
int myAtoi(string str) {
int index=0;
while(str[index]==' '&&index<str.length()){//去掉空格
index++;
}
if(index==str.length())
return 0;
if (!(str[index]>='0'&&str[index]<='9')&&str[index]!='-'&&str[index]!='+')//非正常字符
return 0;
int abss=1;//判断符合的正负
long count=0;
int nowindex=index;
while(index<str.length()){
//cout<<str[nowindex]<<endl;
if(nowindex!=-1&&str[nowindex]=='-'){//判断符号
abss=-1;
index++;
nowindex=-1;
continue;
}
if(nowindex!=-1&&str[nowindex]=='+'){
abss=1;
index++;
nowindex=-1;
continue;
}
if(!(str[index]>='0'&&str[index]<='9'))
break;
count=count*10;
count+=(str[index]-'0');
// cout<<count<<endl;
index++;
if(abss==1&&count>INT_MAX)//注意截断，考虑绝对值要注意最大最小值不同
return INT_MAX;
if((abss==-1) &&-count<INT_MIN){
// cout<<count<<endl;
return INT_MIN;}
}
if(abss==1)
return count;
else
return -count;
}
};
9.回文数
判断数字是否是回文数字。
1.121 回文数字 1200001不是回文数字，-121不是，因为有负号
这道题转为字符串很好做。
另一个思路是把数字倒过来，然后看看是不是相等。
class Solution {
public:
bool isPalindrome(int x) {
if(x<0){
return false;
}
//会做字符串版的
//int 转字符串
//但是另一种思路是：数字反转后 数字和原数大小相同
// res=res*10+x%10 x/=10 比较res==temp(原数字)
// string xx=to_string(x);
// for(int i=0;i<xx.length()/2;i++){
// if(xx[i]!=xx[xx.length()-1-i])
// return false;
// }
int tmp=x;
int res=0;
while(x>0&&res<=(INT_MAX-x%10)/10){//要考虑溢出
res=res*10+x%10;
x=x/10;
}
return res==tmp;
}
};
10.【动态规划-没有看完】正则匹配
开始想用分情况讨论讨论出来，后来发现居然是动态规划。
分情况没有通过↓，只能过280个例子
class Solution {
public:
bool isMatch(string s, string p) {
int i=0;
int index2=0;
while(i<s.length()&&index2<p.length()){
// cout<<i<<'\t'<<index2<<endl;
if(s[i]==p[index2]||p[index2]=='.'){//匹配成功
i++;
index2+=1;
continue;
}
if(p[index2]=='*'){
if(s[i]==p[index2-1]||p[index2-1]=='.')//前面匹配成功，就可以继续go on
i++;
else{
index2+=1;
}
continue;
}
//
//这次没有匹配成功，看是不是前面有*，有*无所谓
if(index2-1>0&&p[index2-1]=='*'&&i>1&&p[index2]==s[i-1]){
index2+=1;
continue;
}
//没有匹配成功，后面有*也无所谓
if(index2<p.length()-1&&p[index2+1]=='*'){
index2+=2;
continue;
}
return false;
}
// cout<<i<<index2<<endl;
if(i<s.length())
return false;
if(index2<p.length()){//看看后面有没有*
string nowstr = p.substr(index2+1);
if(nowstr.find('*')==nowstr.npos){
// cout<<s.substr(s.length()-nowstr.length())<<endl;
if(nowstr.length()>s.length())
return false;
return nowstr==s.substr(s.length()-nowstr.length());
}
if(p[p.length()-1]!='*')//p还有
return false;
if(p[index2]=='*'){
while(index2<p.length()){
if(p[index2]!='*')
return false;
index2+=2;
}
}
if(index2+1<p.length()&&p[index2+1]=='*'){
index2=index2+1;
while(index2<p.length()){
if(p[index2]!='*')
return false;
index2+=2;
}
}
}
return true;
}
};
lc12 整数转罗马数字
1.特殊情况特殊考虑
2.除法和取余，从大到小，逐个计算。
class Solution {
public:
string intToRoman(int num) {
//考虑时间复杂度
// int a[]={1,5,10,50,100,500,1000};
// string s[]={"I","V","X","L","C","D","M"};
int a[]={1,4,5,9,10,40,50,90,100,400,500,900,1000};
string s[]={"I","IV","V","IX","X","XL","L","XC","C","CD","D","CM","M"};
if(num==4)
return "IV";
if(num==9)
return "IX";
if(num==40)
return "XL";
if(num==90)
return "XC";
if(num==400)
return "CD";
if(num==900)
return "CM";
int i=12;
for(;i>=0;i--){
if(num>=a[i])
break;
}
string res="";
bool ex=true;
//利用数组，实现一一对应（其实这里可以用map）
//map是自带排序的
while(ex){
int tmp=num/a[i];//得到多少个
int yu=num%a[i];//得到剩下的数字
for(int j=tmp;j>0;j--){
res+=s[i];
}
num=yu;
i--;
if(yu==0){//没有剩下的数字了
ex=false;
}
}
return res;
}
};
lc13 罗马数字转整数
1.罗马数字有一些特殊的，需要提前写出来。
2.如果存在特殊的，则优先计算特殊的，否则就正常加数字。
class Solution {
public:
int romanToInt(string s) {
map<string,int> c2num={{"I",1},{"V",5},{"X",10},{"L",50},{"C",100},{"D",500},{"M",1000},{"IV",4},{"IX",9},{"XL",40},{"XL",40},{"XC",90},{"CD",400},{"CM",900}};
if(c2num.find(s)!=c2num.end()){
return c2num[s];
}
int res=0;
for(int i=0;i<s.length();i++){
if(i+1<s.length()&&c2num.find(s.substr(i,2))!=c2num.end()){
res+=c2num[s.substr(i,2)];
i=i+1;
}else{
string xx = s.substr(i,1);
res+=c2num[xx];
}
}
return res;
}
};
lc14 最长公共子缀
横向比较，纵向比较
https://www.jianshu.com/p/41a662d6127e
lc17 电话号码-dfs
https://www.jianshu.com/p/1a6b37b15f42
lc20 括号
直接用栈，如果有就消掉一对括号。
class Solution {
public:
bool isValid(string s) {
stack<char> tmp;
for(int i=0;i<s.length();i++){
if(s[i]=='('||s[i]=='['||s[i]=='{'){
tmp.push(s[i]);
}else{
if(tmp.empty())
return false;
if(s[i]==')'){
if(tmp.top()!='('){
return false;
}
}else if(s[i]==']'&& tmp.top()!='[')
return false;
else if(s[i]=='}'&& tmp.top()!='{')
return false;
tmp.pop();
}
}
if(!tmp.empty())
return false;
return true;
}
};
网友评论