-
两个链表的第一个公共结点
-
数组中只出现一次的数字
-
和为S的连续正序列
-
和为S的两个数字（与上题类似）
两个链表的第一个公共结点
题目描述：输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
我的方法（太笨了）
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode* p=pHead1;
ListNode* q=pHead2;
for(p=pHead1;p!=NULL;p=p->next)
{
for(q=pHead2;q!=NULL;q=q->next)
{
if(q==p)
return p;
}
}
return NULL;
}
};
更好的方法：找差值
class Solution {
public:
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
ListNode* p1=pHead1;
ListNode* p2=pHead2;
int len1=getLength(pHead1);
int len2=getLength(pHead2);
int len=0; //第一个链表和第二个链表的差值
if(len1>=len2) //第一个链表比第二个长 第一个链表先走差值
{
len=len1-len2;
while(len>0)
{
p1=p1->next;
len--;
}
}
else //第二个链表比第一个长 第二个链表先走完差值
{
len=len2-len1;
while(len>0)
{
p2=p2->next;
len--;
}
}
while(p1!=p2)
{
p1=p1->next;
p2=p2->next;
}
return p1;
}
int getLength(ListNode* p)
{
int len=0;
ListNode* current=p;
while(current!=NULL)
{
len++;
current=current->next;
}
return len;
}
};
长度相同有公共结点，第一次就遍历到；没有公共结点，走到尾部NULL相遇，返回NULL;长度不同有公共结点，第一遍差值就出来了，第二遍一起到公共结点；没有公共，一起到结尾NULL。
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
/*
假定 List1长度: a+n List2 长度:b+n, 且 a<b
那么 p1 会先到链表尾部, 这时p2 走到 a+n位置,将p1换成List2头部
接着p2 再走b+n-(n+a) =b-a 步到链表尾部,这时p1也走到List2的b-a位置，还差a步就到可能的第一个公共节点。
将p2 换成 List1头部，p2走a步也到可能的第一个公共节点。如果恰好p1==p2,那么p1就是第一个公共节点。 或者p1和p2一起走n步到达列表尾部，二者没有公共节点，退出循环。 同理a>=b.
时间复杂度O(n+a+b)
*/
ListNode* p1 = pHead1;
ListNode* p2 = pHead2;
while(p1 != p2) {
if(p1 != NULL) p1 = p1->next;
if(p2 != NULL) p2 = p2->next;
if(p1 != p2) {
if(p1 == NULL) p1 = pHead2;
if(p2 == NULL) p2 = pHead1;
}
}
return p1;
}
};
数组中只出现一次的数字
题目描述:一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
map<int,int> mp;
vector<int> res;
for(int i=0;i<data.size();i++)
{
mp[data[i]]++;
}
for(int i=0;i<data.size();i++)
{
if(mp[data[i]]==1)
res.push_back(data[i]);
}
*num1=res[0];
*num2=res[1];
}
};
和为S的连续正数序列
题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。
我的方法（不好）
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;
for(int i=1;i<sum;i++)
{
int nowsum=0;
int j=i;
while(nowsum<sum)
{
nowsum+=j; //当前连续的和
j++; //从当前开始往下加
}
if(nowsum==sum)
{
vector<int> sub; //每次获得到一个和为s的子串都要重新建一个数组
for(int k=i;k<j;k++)
sub.push_back(k);
res.push_back(sub);
}
}
return res;
}
};
双指针：
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res; //存放结果
int phigh=2; //两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int plow=1;
while(phigh>plow)
{
int nowsum=(phigh+plow)*(phigh-plow+1)/2; //由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
if(nowsum<sum) //如果当前窗口内的值之和小于sum，那么右边窗口右移一下
phigh++;
if(nowsum==sum) //相等，那么就将窗口范围的所有数添加进结果集
{
vector<int> sub;
for(int i=plow;i<=phigh;i++)
sub.push_back(i);
res.push_back(sub);
plow++;
}
if(nowsum>sum) //如果当前窗口内的值之和大于sum，那么左边窗口右移一下
plow++;
}
return res;
}
};
和为S的两个数字（与上题相似）
题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> res;
int plow=0;
int phigh=array.size()-1; //从末尾开始
while(phigh>plow)
{
if(array[phigh]+array[plow]<sum)
plow++;
if(array[phigh]+array[plow]>sum)
phigh--;
if(array[phigh]+array[plow]==sum)
{
res.push_back(array[plow]);
res.push_back(array[phigh]);
break; //最外层的就是乘积最小的
}
}
return res;
}
};
网友评论