文章目录
- 1.两数之和
- Python实现
- C++版本
- 2.两数相加
- Python实现
- C++版本
- 3.无重复的最长子串
- Python
- C++版本
- 4.两个排序数组的中位数
- Python版本
- C++版本的代码与python代码的第二种方法相同。
- 5.最长回文子串
- Python实现
- C++ 版本与python版本思想相同
- 6.Z字形变换
- python实现
- C++版本
- 7.字符串转数字（atoi）
- Python实现
- C++实现
- 9.判断是否是回文数
- C++版本
- 10.正则表达式匹配
- Python版本
- C++版本
代码 Python和C++
1.两数之和
给定一个整数数组如[2,7,11,15]和一个目标值target=9，找出数组中和为目标值的两个数，返回结果索引[0,1]。
算法思想：遍历数组数组的字典保存需要的值也就是target - numbers，当后面遍历的数字存在于该字典时满足条件返回，只需遍历一次数组。
Python实现
class Solution(object):
def twosum(self,nums,target):
"""
:param nums: list
:param target: int
:return: list index
"""
d={}
for i,num in enumerate(nums):
if target-num in d:
print([d[target-num],i])
return [d[target-num],i] # 返回对应原列表的两个索引
d[num] = i
b = Solution()
b.twosum([2,3,4,5,6],9) C++版本
#include <iostream>
#include <vector>
#include<unordered_map>
// Two Sum
using namespace std;
class Solution{
public:
vector<int> twosum(vector<int> numbers,int target){
unordered_map<int,int> m;
vector<int>result;
for(int i=0;i<numbers.size();i++){
if(m.find(numbers[i])==m.end()){ //number[i]不在m中
m[target-numbers[i]]=i; // 将key=target-numbers[i]的索引i计入unordered map的value中
}
else{
result.push_back(m[numbers[i]]+1); //第一个值的索引
result.push_back(i+1); // 第二个值的索引
break;
}
}
return result;
}
};
int main(){
vector<int> numbers{2,3,4,5,6},out;
int target=9;
vector<int> (Solution::*pfunc)(vector<int> numbers,int target) = &Solution::twosum; // 调用类成员函数
Solution test;
out=(test.*pfunc)(numbers,target);
for(int i=0;i<out.size();i++) cout<<out[i]<<" ";
cout<<""<<endl;
return 0;
} 2.两数相加
给定两个非空链表表示两个非负整数，位数按逆序方式存储，每个节点只存储单个数字，将两数相加返回一个新列表。
输入： (2->4->3) + (5->6->4)
输出：7->0->8
算法思想：一步步取值，计算sum通过取余和取整获取每一步计算结果。
Python实现
class Listnode(object):
def __init__(self,x):
self.val = x
self.next = None
class Solution(object):
def addtwonumbers(self,l1,l2):
p = dummy = Listnode(-1)
carry = 0
while l1 and l2:
p.next = Listnode(l1.val + l2.val + carry)
carry = p.next.val // 10
p.next.val %= 10
p = p.next
l1 = l1.next
l2 = l2.next
res = l1 or l2
while res:
p.next = Listnode(res.val + carry)
carry = p.next.val // 10
p.next.val %= 10
p = p.next
res = res.next
if carry:
p.next = Listnode(carry)
return dummy.next
x = Listnode(2)
x.next = Listnode(4)
x.next.next = Listnode(3)
x.next.next.next = None
y = Listnode(5)
y.next = Listnode(6)
y.next.next = Listnode(4)
y.next.next.next = None
test = Solution()
dummy = test.addtwonumbers(x,y)
while(dummy):
print(dummy.val)
dummy = dummy.next C++版本
#include <iostream>
#include <vector>
#include<unordered_map>
// Two Sum
using namespace std;
struct Lnode{
int data;
Lnode *next;
};
// 遍历并打印链表
void Ourlist(Lnode *head){ // 输入的是指针的复制，所以并不会改变外部指针的指向
Lnode *pcur=head;
while(pcur!=NULL){
cout<<pcur->data<<"";
pcur=pcur->next;
}
cout<<"\n"<<"";
}
class Solution{
public:
Lnode *addtwonum(Lnode *l1,Lnode *l2){
int x=0,y=0,carry=0,sum=0;
Lnode *h=NULL,**t=&h;
while(l1!=NULL || l2!=NULL){
x=getvalue(l1);
y=getvalue(l2);
sum=carry+x+y;
Lnode *node=new Lnode();
node->data=sum%10;
*t=node; // 指向node
t=(&node->next); // 将node的next指针的地址赋给t
carry=sum/10;
}
if(carry>0){
Lnode *node=new Lnode();
node->data=carry;
*t=node;
}
return h;
}
private:
int getvalue(Lnode* &l){ // 这里&表示复制的是指针的本体
int x=0;
if(l!=NULL){
x=l->data;
l=l->next;
}
return x;
}
};
int main(){
Lnode *pl1,*pl2,*pout;
vector<int> vp1={2,4,3};
vector<int> vp2={5,6,4};
Lnode *l1=(Lnode*)malloc(3*sizeof(Lnode));
Lnode *l2=(Lnode*)malloc(3*sizeof(Lnode));
for(int i=0;i<3;i++){
l1[i].data=vp1[i];
l1[i].next=&l1[i+1];
l2[i].data=vp2[i];
l2[i].next=&l2[i+1];
}
l1[2].next=NULL;
l2[2].next=NULL;
pl1=&l1[0];
pl2=&l2[0];
Ourlist(pl1);
Ourlist(pl2);
Lnode *(Solution::*pfunc)(Lnode *l1,Lnode *l2)=&Solution::addtwonum;
Solution test;
pout=(test.*pfunc)(pl1,pl2); // // pout = test.addtwonum(pl1,pl2)
Ourlist(pout);
} 3.无重复的最长子串
给定一个字符串"abcabcbb"，输出没有重复的最长子串"abc"的长度3。
算法思想：可以通过字典的方式，将已有的元素作为字典的索引，将其索引作为字典的值，这样如果出现相同的值，则会计算子串长度，同时也要考虑一个细微的情况，是每当计算一个重复元素后，需要将后续的计算从该重复元素后开始。
Python
class Solution(object):
def longest1(self,s):
num = len(s)
maxlen = 0
sub = ""
for i in range(num):
if s[i] not in sub:
sub = sub + s[i]
print(sub)
if i==num-1:
lensub = len(sub)
maxlen = max(maxlen,lensub)
else:
j = sub.find(s[i])
lensub = len(sub)-j
maxlen = max(maxlen,lensub)
sub = sub[j+1:]
sub = sub +s[i]
print(sub)
print(maxlen)
return maxlen
def longest2(self,s):
d = {}
start = 0
ans = 0
for i,c in enumerate(s):
if c in d:
start = max(start,d[c]+1) # max必须要有start保存着sub的起始位置
d[c] = i
ans = max(ans,i-start+1) # 保存最大值
print(ans)
return ans
def longest3(self,s):
d = collections.defaultdict(int)
l = ans = 0
for i,c in enumerate(s):
while(l>0) and d[c]>0:
d[s[i-1]] -= 1
l -= 1
d[c] += 1
l += 1
ans = max(ans, l)
print(ans)
return ans
x = "bbcbcbaadef"
y = "abbdcbabcdfd"
test = Solution()
test.longest3(x) C++版本
int lensub1(string s){
map<char,int> m;
int maxlen=0;
int lastrepeat=-1;
for(int i=0;i<s.size();i++){
if(m.find(s[i])!=m.end() && lastrepeat<m[s[i]]){
lastrepeat=m[s[i]];
}
if(i-lastrepeat>maxlen){
maxlen=i-lastrepeat;
}
m[s[i]]=i;
}
return maxlen;
}
int lensub2(string s){
const int MAX_CHARS=256;
int m[MAX_CHARS];
memset(m, -1, sizeof(m)); // 初始化m的所有元素值为-1
int maxlen=0;
int lastrepeat=-1;
for(int i=0;i<s.size();i++){
if(m[s[i]]!=-1&&lastrepeat<m[s[i]]){
lastrepeat=m[s[i]];
}
if(i-lastrepeat>maxlen) {
maxlen=i-lastrepeat;
}
m[s[i]]=i;
}
return maxlen;
}
int main(int argc,char** argv){
string s="abcabcbb";
cout<<s<<":"<<lensub1(s)<<endl;
s="bbbb";
cout<<s<<":"<<lensub2(s)<<endl;
s="bbabcdb";
cout<<s<<":"<<lensub2(s)<<endl;
if (argc>1) {
s=argv[1];
cout<<s<<":"<<lensub2(s)<<endl;
}
return 0;
} 4.两个排序数组的中位数
给定两个大小m和n的有序数组，请找出两个数组的中位数，要求算法的复杂度为O(long(m+n))。
算法思想：1.找到索引相加为最终数组中位数索引值的两个数组的两个数。2.最终数组的元素个数影响着中位数的选取。
Python版本
def median1(A,B):
m,n = len(A),len(B)
if m>n:
A,B,m,n = B,A,n,m
if n ==0:
raise ValueError
imin,imax,half_len = 0,m,(m+n+1)//2
while imin <= imax:
i = (imin+imax)//2
j = half_len-i
if i<m and B[j-1]>A[i]:
imin = i+1
elif i>0 and A[i-1]>B[j]:
imax = i-1
else:
if i==0: max_of_left = B[j-1]
elif j==0: max_of_left = A[i-1]
else:max_of_left = max(A[i-1],B[j-1])
if(m+n)%2==1:
return max_of_left
if i==m: min_of_right = B[j]
elif j==n: min_of_right = A[i]
else: min_of_right = min(A[i],B[j])
return (max_of_left + min_of_right)/2.0
def median2(A,B):
a,b = sorted([A,B],key=len)
m,n = len(a),len(b)
after = (m+n-1)//2
lo,hi = 0,m
while lo<hi:
i = (lo+hi)//2
if after-i-1<0 or a[i]>=b[after-i-1]:
hi=i
else:
lo = i+1
i = lo
nextfew = sorted(a[i:i+2]+b[after-i:after-i+2])
return (nextfew[0]+nextfew[1-(m+n)%2])/2.0
mid = median2([2,4,6,8,9],[1,3,5,7])
print(mid) C++版本的代码与python代码的第二种方法相同。
float median(int a[],int b[],int m,int n){
if(m>n){
int *p=a;
int temp=n;
a = b; b = p;
n = m; m = temp;
for (int i=0;i<m;i++){
cout<<a[i]<<" ";
}
cout<<endl;
for(int i=0;i<n;i++){
cout<<b[i]<<" ";
}
}
int after = (m+n-1)/2;
int lo=0,hi=m,i=0;
while (lo<hi) {
i = (lo+hi)/2;
if((after-i-1<0)||(a[i]>=b[after-i-1])){
hi = i;
}
else lo = i+1;
}
i = lo;
int c[] = {a[i],a[i+1],b[after-i],b[after-i+1]};
sort(c,c+4);
cout<<endl;
for(int i=0;i<4;i++){
cout<<c[i]<<" ";
}
cout<<endl;
return (m+n)%2==1 ? c[0] : (c[0]+c[1])/2.0;
}
int main(){
int b[]={1,3,5,7};
int a[]={2,4,6,8,9};
int m=sizeof(a)/sizeof(a[0]);
int n=sizeof(b)/sizeof(b[0]);
float med = median(a, b, m, n);
cout<<"中位数："<<med<<endl;
return 0;
} 5.最长回文子串
给定一个字符串s，找出s中的最长回文子串。
算法思想：常见的思路是，遍历每个元素和每个元素+下一个元素（回文中间可能为一个或两个相同的元素），找到最长回文子串。
Python实现
class Solution(object):
def longestpal(self,s):
left=right=0
n=len(s)
for i in range(n-1):
if 2*(n-i)+1<right-left+1:
break
l=r=i
while l>=0 and r<n and s[l]==s[r]:
l -= 1
r += 1
if r-l-2>right-left:
left = l+1
right = r-1
l=i
r=i+1
while l>=0 and r<n and s[l]==s[r]:
l -= 1
r += 1
if r-l-2>right-left:
left = l+1
right = r-1
return s[left:right+1]
test = Solution()
print(test.longestpal("cabba")) C++ 版本与python版本思想相同
// int & 变量的引用
void findpal(string s,int left,int right,int& start,int& len){
long n=s.size();
while (left>=0&&right<=n-1&&s[left]==s[right]) {
left--;
right++;
}
if(right-left-1>len){
len=right-left-1;
start=left+1;
}
}
string longestpal(string s){
long n=s.size();
if(n<=1) return s;
int start=0,len=0;
for(int i=0;i<n;i++){
findpal(s,i,i,start,len);
findpal(s,i,i+1,start,len);
}
return s.substr(start,len);
}
int main(){
string s="cabba";
string longest=longestpal(s);
long n=longest.size();
for(int i=0;i<n;i++){
cout<<longest[i];
}
cout<<endl;
return 0;
} 6.Z字形变换
给定一个字符串和变换的行数，输出变换后的字符串，如给定"PAYPALISHIRING",如果变换行数为4，则每一行为：
PIN
ALSIG
YAHR
PI
则输出"PINALSIGYAHRPI"
算法思想：这里提供两种思路，一是按照其规律构建一个包含string的向量，循环每个元素依次添加，C++实现；第二种是找到每一行构建的索引规律，循环每一行。
python实现
class Solution(object):
def convert(self,s,nrows):
if nrows<=1: return s
n = len(s)
ans = []
step = 2*nrows - 2
for i in range(nrows):
one = i
two = -i
while one<n or two<n:
if 0<=two<n and one !=two and i !=nrows-1:
ans.append(s[two])
if one<n:
ans.append(s[one])
one += step
two += step
return "".join(ans)
test = Solution()
print(test.convert("PAYPALISHIRING",4))
#索引规律
#0 6 12
#1 5 7 11 13
#2 4 8 10 14
#3 9 15 C++版本
string convert(string s,int nrows){
if(nrows<=1 || nrows>=s.size()) return s;
vector<string> r(nrows);
int row = 0;
int step = 1;
for(int i=0;i<s.size();i++){
if(row==nrows-1) step=-1;
if(row==0) step=1;
r[row] += s[i];
row += step;
}
string result;
for(int i=0;i<nrows;i++){
result += r[i];
}
return result;
}
int main(int argc,char**argv){
string s;
int r;
s = "PAYPALISHIRING";
r = 4;
cout<<s<<":"<<convert(s, r)<<endl;
} 7.字符串转数字（atoi）
将字符串转为整数，如果不能有效的转换返回0，这里数字可能会有“+” “-”号。
算法思想：数据类型判断好即可，C++指针的运用可以使代码精简。
Python实现
"""8.字符串转整数（atoi）"""
def myatoi(s):
s = s.strip()
sigh = 1
if s[0] in ["+","-"]:
if s[0]=="-":
sigh = -1
s = s[1:]
ans = 0
for c in s:
if c.isdigit():
ans = ans*10 +int(c)
else:
break
ans *= sigh
if ans > 2147483647:
return 2147483647
if ans < -2147483648:
return -2147483648
return ans
print(myatoi("-33"))
print(myatoi("43")) C++实现
int atoi(const char *str){
if (str==NULL || *str=='\0'){
return 0;
}
int ret=0;
for(;isspace(*str);str++);
bool neg=false;
if(*str=='-'||*str=='+'){
neg=(*str=='-');
str++;
}
for(;isdigit(*str);str++){
int digit=(*str-'0'); // -'0'避免取ascii码值
if(neg){
if(-ret<(INT_MIN+digit/10)){
return INT_MIN;
}
}
else{
if(ret>(INT_MAX-digit)/10){
return INT_MAX;
}
}
ret = ret*10 + digit;
}
return neg?-ret:ret;
}
int main(){
cout<<(atoi("-34ww"))<<endl;
} 9.判断是否是回文数
给出一个整数，判断这个整数正序和倒序读是否一致。
算法思想：可以将其转化为字符串处理，也可以将整数翻转来判断是否一致，这里还有一种方法取整数一半做判断。
def ispal1(num):
if num<0: return False
s = str(num)
left = 0
right = len(s)-1
while(left<right):
if(s[left]!=s[right]):
return False
left += 1
right -= 1
return True
print(ispal1(121))
print(ispal1(12))
print(ispal1(-2))
def ispal2(num):
if num<0 or (num !=0 and num % 10==0):
return False
half = 0
while num > half:
half = half * 10 + num % 10
num =num // 10
return half==num or (half//10)==num
print(ispal2(121))
print(ispal2(12))
print(ispal2(-2)) C++版本
class Solution{
public:
bool ispalindrome(int x){
if(x<0){
return false;
}
int len=1;
for(len=1;(x/len)>=10;len *=10);
while(x!=0){
int left=x/len;
int right =x%10;
if(left!=right){
return false;
}
x = (x%len)/10;
len /=100;
}
return true;
}
bool ispalindrome2(int x){
return (x>0&&x==reverse(x));
}
private:
int reverse(int x){
int y=0;
int n;
while(x!=0){
n = x%10;
y = y*10 + n;
x /=10;
}
return y;
}
};
int main(){
Solution s;
cout<<s.ispalindrome(123)<<endl;
cout<<s.ispalindrome2(11)<<endl;
} 10.正则表达式匹配
给定一个字符串(s)和一个字符模式§实现支持’.‘和’*'的正则表达式匹配
- '.'匹配任意单个字符，这里在样例貌似有点歧义，代码实现是按照任意单个字符，而不是单个或多个字符
- '*'匹配零个或多个前面的元素
- s可能为空，且只包含
a-z
- p可能为空，且只包含从
a-z
的小写字母，以及字符.和*
s = ‘aa’ 匹配 p = ‘a*’
s = ‘ab’ 匹配 p = ‘.’
s = ‘aab’ 匹配 p = ‘cab’ //这里c匹配零个，a匹配两个
Python版本
def ismatch(s,p):
dp = [[False]*(len(p)+1) for _ in range(len(s)+1)]
dp[0][0] = True
for j in range(1,len(p)+1):
if p[j-1] == "*":
dp[0][j] = dp[0][j-2]
for i in range(1,len(s)+1):
for j in range(1,len(p)+1):
if p[j-1] != "*":
dp[i][j] = dp[i-1][j-1] and (s[i-1] == p[j-1] or p[j-1] == ".")
else:
# 前一步为True and 当前步的两种情况满足一种即可(p中当前元素前一个即j-2与i-1相同或者当前元素后一个j与i-1相同)
# 但是这里代码的两种情况，与上述描述有点出入，我再想想...
dp[i][j] = dp[i][j-2] or dp[i-1][j] and (p[j-2] == s[i-1] or p[j-2] == ".")
return dp[-1][-1]
print(ismatch("aaabc","a*.c"))
print(ismatch("abc","aa*bc"))
print(ismatch("aac","a*c"))
print(ismatch("abc","aac")) C++版本
bool ismatch(const char *s,const char *p){
if(*p=='\0'){
return *s=='\0';
}
// 当前不含有*的情况，只需要调用递归算法
if (*(p+1)=='\0'||*(p+1)!='*'){
if(*s=='\0'||(*p!='.'&&*s!=*p)){
return false;
}
return ismatch(s+1, p+1);
}
// 当有p+1=‘*’，需要尝试得到*重复的次数
int len = strlen(s);
int i=-1;
while (i<len&&(i<0||*p=='.'||*p==*(s+i))) {
if(ismatch(s+i+1, p+2)){ //尝试*重复的数目：从0到最大len个
return true;
}
i++;
}
return false;
}
int main(int argc, char** argv){
const char* s="aaa";
const char* p="a.*";
if (argc>2){
s = argv[1];
p = argv[2];
}
cout<<s<<","<<p<<":"<<ismatch(s, p)<<endl;
} ![笔试面试题目：滑动窗口(二)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)