2 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头
分析：法一：分段计算，法二：补0等长
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
//分段法
/*
if(l1==nullptr)return l2;
if(l2==nullptr)return l1;
int nval=0;
ListNode *p;
p=l1;
while(p!=nullptr&&l2!=nullptr)
{
int v=p->val+l2->val+nval;
nval=v/10;
p->val=v%10;
if(p->next!=nullptr&&l2->next!=nullptr)
{ p=p->next;
l2=l2->next;
}else break;
}
if(l2->next!=nullptr)
{
p->next=l2->next;
}
while(p->next!=nullptr){
p=p->next;
int v=p->val+nval;
nval=v/10;
p->val=v%10;
}
if(nval==1) p->next=new ListNode(1);
return l1;
}
*/
//补0
int len1=0,len2=0;
ListNode*p1=l1,*p2=l2;
while(p1->next!=nullptr)
{
len1++;
p1=p1->next;
}
while(p2->next!=nullptr)
{
len2++;
p2=p2->next;
}
//p1=l1;p2=l2;
if(len1<len2){
for(int i=0;i<len2-len1;i++)
{
p1->next=new ListNode(0);
p1=p1->next;
}
}
if(len1>len2){
for(int i=0;i<len1-len2;i++)
{
p2->next=new ListNode(0);
p2=p2->next;
}
}
int len=(len1>=len2)?len1:len2;
p1=l1;p2=l2;
int nval=0;
while(p2!=nullptr)
{
int v=p1->val+p2->val+nval;
nval=v/10;
p1->val=v%10;
if(p1->next!=nullptr)
{
p1=p1->next;
p2=p2->next;
}else break;
}
if(nval==1) p1->next=new ListNode(1);
return l1;
}
};
//while(!p){comute,p=p->next;}
//while(p->next){p=p->next;comute;}
//两个序列对应相加，但是不等长；
//方法一，补成等长
//方法二，分段计算
//while(!p){comute ,if(!p->next)p=p->next;}先计算，再下行一个，此情况保留最后一次下行；
给定两个大小为 m 和 n 的正序（从小到大）数组nums1和nums2。请你找出并返回这两个正序数组的中位数。
进阶：你能设计一个时间复杂度为O(log (m+n))的算法解决此问题吗？
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
//第k小元素
//每次比较两个余下序列的中间值大小，排除掉其中较小元素的左侧元素，移动指针；
//考虑序列各自的奇偶
int m=nums1.size(),n=nums2.size();
return (findKth(nums1,0,nums2,0,(m+n+1)/2)+findKth(nums1,0,nums2,0,(m+n+2)/2))/2.0;
}
int findKth(vector<int >&nums1,int i,vector<int >&nums2,int j,int k)
{
if(i>=nums1.size())return nums2[j+k-1];
if(j>=nums2.size())return nums1[i+k-1];
if(k==1){
return std::min(nums1[i],nums2[j]);
}
int mid1=(i+k/2-1>=nums1.size())?INT_MAX:nums1[i+k/2-1];
int mid2=(j+k/2-1>=nums2.size())?INT_MAX:nums2[j+k/2-1];
if(mid1<mid2)
return findKth(nums1,i+k/2,nums2,j,k-k/2);
else
return findKth(nums1,i,nums2,j+k/2,k-k/2);
}
};
5 给你一个字符串s，找到s中最长的回文子串。
分析：以元素或者两个元素间隔作为中心，向两边扩散判断是否回文
class Solution {
public:
string longestPalindrome(string s) {
int len=s.size();
if(len==0||len==1)
return s;
int start=0;
int end=0;
int mlen=0;
for(int i=0;i<len;i++)
{
int len1=isPa(s,i,i);
int len2=isPa(s,i,i+1);
mlen=max(max(len1,len2),mlen);
if(mlen>end-start+1)
{
start=i-(mlen-1)/2;
end=i+mlen/2;
}
}
return s.substr(start,mlen);
}
private:
int isPa(string s,int left,int right)
{
int L=left;
int R=right;
while(L>=0 && R<s.length() && s[R]==s[L])
{
L--;
R++;
}
return R-L-1;
}
};
