兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)
數(shù)組中只出現(xiàn)一次的數(shù)字
和為S的連續(xù)正序列
和為S的兩個(gè)數(shù)字（與上題類似）
兩個(gè)鏈表的第一個(gè)公共結(jié)點(diǎn)
題目描述：輸入兩個(gè)鏈表墩朦，找出它們的第一個(gè)公共結(jié)點(diǎn)扰柠。（注意因?yàn)閭魅霐?shù)據(jù)是鏈表囤热，所以錯(cuò)誤測(cè)試數(shù)據(jù)的提示是用其他方式顯示的，保證傳入數(shù)據(jù)是正確的）
我的方法（太笨了）
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; //第一個(gè)鏈表和第二個(gè)鏈表的差值
if(len1>=len2) //第一個(gè)鏈表比第二個(gè)長(zhǎng) 第一個(gè)鏈表先走差值
{
len=len1-len2;
while(len>0)
{
p1=p1->next;
len--;
}
}
else //第二個(gè)鏈表比第一個(gè)長(zhǎng) 第二個(gè)鏈表先走完差值
{
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;
}
};
長(zhǎng)度相同有公共結(jié)點(diǎn)瞎领，第一次就遍歷到；沒(méi)有公共結(jié)點(diǎn)，走到尾部NULL相遇怎棱，返回NULL;長(zhǎng)度不同有公共結(jié)點(diǎn)，第一遍差值就出來(lái)了绷跑，第二遍一起到公共結(jié)點(diǎn)拳恋；沒(méi)有公共，一起到結(jié)尾NULL砸捏。
class Solution {
public:
ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
/*
假定 List1長(zhǎng)度: a+n List2 長(zhǎng)度:b+n, 且 a<b
那么 p1 會(huì)先到鏈表尾部, 這時(shí)p2 走到 a+n位置,將p1換成List2頭部
接著p2 再走b+n-(n+a) =b-a 步到鏈表尾部,這時(shí)p1也走到List2的b-a位置谬运，還差a步就到可能的第一個(gè)公共節(jié)點(diǎn)隙赁。
將p2 換成 List1頭部，p2走a步也到可能的第一個(gè)公共節(jié)點(diǎn)梆暖。如果恰好p1==p2,那么p1就是第一個(gè)公共節(jié)點(diǎn)伞访。 或者p1和p2一起走n步到達(dá)列表尾部，二者沒(méi)有公共節(jié)點(diǎn)轰驳，退出循環(huán)厚掷。 同理a>=b.
時(shí)間復(fù)雜度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;
}
};
數(shù)組中只出現(xiàn)一次的數(shù)字
題目描述:一個(gè)整型數(shù)組里除了兩個(gè)數(shù)字之外，其他的數(shù)字都出現(xiàn)了兩次级解。請(qǐng)寫程序找出這兩個(gè)只出現(xiàn)一次的數(shù)字冒黑。
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的連續(xù)正數(shù)序列
題目描述：小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))勤哗。沒(méi)多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22÷盏現(xiàn)在把問(wèn)題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
輸出描述:輸出所有和為S的連續(xù)正數(shù)序列。序列內(nèi)按照從小至大的順序芒划，序列間按照開(kāi)始數(shù)字從小到大的順序冬竟。
我的方法（不好）
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; //當(dāng)前連續(xù)的和
j++; //從當(dāng)前開(kāi)始往下加
}
if(nowsum==sum)
{
vector<int> sub; //每次獲得到一個(gè)和為s的子串都要重新建一個(gè)數(shù)組
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; //存放結(jié)果
int phigh=2; //兩個(gè)起點(diǎn)，相當(dāng)于動(dòng)態(tài)窗口的兩邊民逼，根據(jù)其窗口內(nèi)的值的和來(lái)確定窗口的位置和大小
int plow=1;
while(phigh>plow)
{
int nowsum=(phigh+plow)*(phigh-plow+1)/2; //由于是連續(xù)的诱咏，差為1的一個(gè)序列，那么求和公式是(a0+an)*n/2
if(nowsum<sum) //如果當(dāng)前窗口內(nèi)的值之和小于sum缴挖，那么右邊窗口右移一下
phigh++;
if(nowsum==sum) //相等袋狞，那么就將窗口范圍的所有數(shù)添加進(jìn)結(jié)果集
{
vector<int> sub;
for(int i=plow;i<=phigh;i++)
sub.push_back(i);
res.push_back(sub);
plow++;
}
if(nowsum>sum) //如果當(dāng)前窗口內(nèi)的值之和大于sum，那么左邊窗口右移一下
plow++;
}
return res;
}
};
和為S的兩個(gè)數(shù)字（與上題相似）
題目描述：輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S映屋，在數(shù)組中查找兩個(gè)數(shù)苟鸯，使得他們的和正好是S，如果有多對(duì)數(shù)字的和等于S棚点，輸出兩個(gè)數(shù)的乘積最小的早处。
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> res;
int plow=0;
int phigh=array.size()-1; //從末尾開(kāi)始
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;
}
};
