轉：鏈表相交問題 詳解

源地址：http://blog.163.com/bbluesnow@126/blog/static/27784545201251051156817/

鏈表相交問題??

2012-06-10 17:15:37|??分類：?算法?|??標簽：微軟面試題??|字號?訂閱

1、如何判斷一個單鏈表有環

2、如何判斷一個環的入口點在哪里

3、如何知道環的長度

4、如何知道兩個單鏈表（無環）是否相交

5、如果兩個單鏈表（無環）相交，如何知道它們相交的第一個節點是什么？

6、如何知道兩個單鏈表（有環）是否相交

7、如果兩個單鏈表（有環）相交，如何知道它們相交的第一個節點是什么？

?以下進行分析，并在最后附源代碼及測試：

1、采用快慢步長法。令兩個指針p和q分別指向頭結點，p每次前進一步，q每次前進兩步，如果p和q能重合，則有環。可以這么理解，這種做法相當于p靜止不動，q每次前進一步，所有肯定有追上p的時候。

我們注意到，指針p和q分別以速度為1和2前進。如果以其它速度前進是否可以呢？

假設p和q分別以速度為v1和v2前進。如果有環，設指針p和q第一次進入環時，他們相對于環中第一個節點的偏移地址分別為a和b（可以把偏移地址理解為節點個數）

這樣，可以看出，鏈表有環的充要條件就是某一次循環時，指針p和q的值相等，就是它們相對環中首節點的偏移量相等。我們設環中的結點個數為n,程序循環了m次。

由此可以有下面等式成立：(mod(n)即對n取余)

(a+m*v1)mod(n) = (b+m*v2) mod(n)

設等式左邊mod(n)的最大整數為k1，等式右邊mod(n)的最大整數為k2，則

(a+m*v1)-k1*n = (b+m*v2)-k2*n

整理以上等式：

m= |((k2-k1)*n+a-b)/( v2-v1)|???????①

如果是等式①成立，就要使循環次數m為一整數。顯然如果v2-v1為1，則等式成立。

這樣p和q分別以速度為v1和v2且|v2-v1|為1時，按以上算法就可找出鏈表中是否有環。當然|v2-v1|不為1時，也可能可以得出符合條件的m。

?

時間復雜度分析：假設甩尾（在環外）長度為 len1（結點個數），環內長度為 len2，鏈表總長度為n，則n=len1+len2。當p步長為1，q步長為2時，p指針到達環入口需要len1時間，p到達入口后，q處于哪里不確定，但是肯定在環內，此時p和q開始追趕，q最長需要len2時間就能追上p（p和q都指向環入口），最短需要1步就能追上p（p指向環入口，q指向環入口的前一個節點）。事實上，每經過一步，q和p的距離就拉近一步，因此，經過q和p的距離步就可以追上p。因此總時間復雜度為O(n)，n為鏈表的總長度。

?

?

2、分別從鏈表頭和碰撞點，同步地一步一步前進掃描，直到碰撞，此碰撞點即是環的入口。

證明如下：

鏈表形狀類似數字 6 。?

假設甩尾（在環外）長度為 a（結點個數），環內長度為 b 。?

則總長度（也是總結點數）為 a+b 。?

從頭開始，0 base 編號。

將第 i 步訪問的結點用 S(i) 表示。i = 0, 1 ...?

當 i＜a 時，S(i)=i ；?

當 i≥a 時，S(i)=a+(i-a)%b 。

分析追趕過程。?

兩個指針分別前進，假定經過 x 步后，碰撞。則有：S(x)=S(2x)?

由環的周期性有：2x=tb+x 。得到 x=tb 。?

另，碰撞時，必須在環內，不可能在甩尾段，有 x>=a 。

連接點為從起點走 a 步，即 S(a)。?

S(a) = S(tb+a) = S(x+a)。?

得到結論：從碰撞點 x 前進 a 步即為連接點。

根據假設易知 S(a-1) 在甩尾段，S(a) 在環上，而 S(x+a) 必然在環上。所以可以發生碰撞。?

而，同為前進 a 步，同為連接點，所以必然發生碰撞。

綜上，從 x 點和從起點同步前進，第一個碰撞點就是連接點。

?

?

時間復雜度分析：假設甩尾（在環外）長度為 len1（結點個數），環內長度為 len2 。則時間復雜度為“環是否存在的時間復雜度”+O（len1）

?

?

3、從碰撞點開始，兩個指針p和q，q以一步步長前進，q以兩步步長前進，到下次碰撞所經過的操作次數即是環的長度。這很好理解，比如兩個運動員A和B從起點開始跑步，A的速度是B的兩倍，當A跑玩一圈的時候，B剛好跑完兩圈，A和B又同時在起點上。此時A跑的長度即相當于環的長度。

假設甩尾（在環外）長度為 len1（結點個數），環內長度為 len2 ，則時間復雜度為“環是否存在的時間復雜度”+O(len2)。

?

4、法一：將鏈表A的尾節點的next指針指向鏈表B的頭結點，從而構造了一個新鏈表。問題轉化為求這個新鏈表是否有環的問題。

? ???時間復雜度為環是否存在的時間復雜度，即O（length(A)+length(B)），使用了兩個額外指針

? ? ?法二：兩個鏈表相交，則從相交的節點起，其后的所有的節點都是都是兩個鏈表共有的。因此，如果它們相交，則最后一個節點一定是共有的。因此，判斷兩鏈表相交的方法是：遍歷第一個鏈表，記住最后一個節點。然后遍歷第二個鏈表，到最后一個節點時和第一個鏈表的最后一個節點做比較，如果相同，則相交。

? ???時間復雜度：O（length(A)+length(B)），但是只用了一個額外指針存儲最后一個節點

?

5、將鏈表A的尾節點的next指針指向鏈表B的頭結點，從而構造了一個環。問題轉化為求這個環的入口問題。
時間復雜度：求環入口的時間復雜度

?

6、分別判斷兩個鏈表A、B是否有環（注，兩個有環鏈表相交是指這個環屬于兩個鏈表共有）

如果僅有一個有環，則A、B不可能相交

如果兩個都有環，則求出A的環入口，判斷其是否在B鏈表上，如果在，則說明A、B相交。

時間復雜度：“環入口問題的時間復雜度”+O（length（B））

?

7、分別計算出兩個鏈表A、B的長度LA和LB（環的長度和環到入口點長度之和就是鏈表長度），參照問題3。

如果LA>LB，則鏈表A指針先走LA-LB，鏈表B指針再開始走，則兩個指針相遇的位置就是相交的第一個節點。

如果LB>LA，則鏈表B指針先走LB-LA，鏈表A指針再開始走，則兩個指針相遇的位置就是相交的第一個節點。

時間復雜度：O（max（LA,LB））

源碼，并沒有封裝成類，存在某些重復運算：

islistJunction.

?

/******************************************************************************************************
Description?? : 檢查鏈表是否有環
Prototype???? : template<typename T>
????bool checkCircle(T* head)
Input Param?? : head，鏈表的頭結點指針
Output Param? : 無
Return Value? : bool變量，TRUE為有環，FALSE為沒有環
********************************************************************************************************/
template<typename T>
bool checkCircle(T* head)
{
?if(NULL == head)
??returnfalse;
?T* low = head;
?T* fast = head;

?while(low->next!= NULL &&(fast->next!= NULL)&&(fast->next)->next!= NULL)
?{
??low = low->next;
??fast =(fast->next)->next;
??if(low == fast)
??{
???returntrue;
??}
?}
?returnfalse;
}

/******************************************************************************************************
Description?? : 判斷兩個鏈表是否相交
Prototype???? : template<typename T>
????bool isListJunction(T* head1,T* head2)
Input Param?? : head1，第一個鏈表的頭結點；head2，第二個鏈表的頭結點
Output Param? : 無
Return Value? : bool變量，true為有交集，false為沒有交集
********************************************************************************************************/
template<typename T>
bool isListJunction(T* head1,T* head2)
{
?if(NULL == head1 || NULL == head2)
?{
??returnfalse;
?}
?// 如果頭結點相同，代表相同的鏈表，肯定是相交
?if(head1 == head2)
?{
??returntrue;
?}
?
?// 檢測是否有環
?bool b1 = checkCircle(head1);
?bool b2 = checkCircle(head2);
?// 若相交，則兩個鏈表要么都無環，要么都有環
?if(b1 != b2)
?{
??returnfalse;
?}
?
?// 若都無環，b1==b2==0,尾節點必然相同，是Y字形
?if(!b1)
?{
??while(head1 != NULL)
??{
???head1 = head1->next;
??}
??while(head2 != NULL)
??{
???head2 = head2->next;
??}
??if(head1 == head2)
??{
???returntrue;
??}
?}

?// 若有環，則找出鏈表1的環入口，看是否在鏈表2上
?if(b1)
?{
??T* port = findLoopPort(head1);
??if(port != NULL)
??{
???T* temp = head2;
???int length2 = getLoopLength(head2)+ getTailLength(head2);
???while(port != temp &&(length2--)>=0)
????temp = temp->next;

???if(port == temp)
????returntrue;
???else
????returnfalse;
??}
?}
?
?returnfalse;
}

/******************************************************************************************************
Description?? : 判斷兩個鏈表是否相交
Prototype???? : template<typename T>
????bool isListJunction(T* head1,T* head2)
Input Param?? : head1，第一個鏈表的頭結點；head2，第二個鏈表的頭結點
Output Param? : 無
Return Value? : bool變量，true為有交集，false為沒有交集
********************************************************************************************************/
template<typename T>
bool isListJunction(T* head1,T* head2,T *&junctionNode)
{
?if(NULL == head1 || NULL == head2)
?{
??returnfalse;
?}
?// 如果頭結點相同，代表相同的鏈表，肯定是相交
?if(head1 == head2)
?{
??junctionNode = head1;
??returntrue;
?}
?
?// 檢測是否有環
?bool b1 = checkCircle(head1);
?bool b2 = checkCircle(head2);
?// 若相交，則兩個鏈表要么都無環，要么都有環
?if(b1 != b2)
?{
??returnfalse;
?}
?
?// 若都無環，b1==b2==0,尾節點必然相同，是Y字形
?if(!b1)
?{
??T* node1 = head1;
??T* node2 = head2;
??while(node1 != NULL)
??{
???node1 = node1->next;
??}
??while(node2 != NULL)
??{
???node2 = node2->next;
??}
??if(node1 == node2)
??{
???// 相交，把第一個鏈表的尾節點指向第二個鏈表
???node1->next= head2;
???junctionNode = findLoopPort(head1);
???returntrue;
??}
?}

?// 若有環，則找出鏈表1的環入口，看是否在鏈表2上
?if(b1)
?{
??int length1 = getLoopLength(head1)+ getTailLength(head1);
??int length2 = getLoopLength(head2)+ getTailLength(head2);
??int len = length2;
??T* port = findLoopPort(head1);
??if(port != NULL)
??{
???T* temp = head2;
???while(port != temp &&(len--)>=0)
????temp = temp->next;

???if(port == temp)
???{
????// 若長度相等，同步尋找相同的節點
????if(length1 == length2)
????{
?????while(head1 != head2)
?????{
??????head1 = head1->next;
??????head2 = head2->next;
?????}
?????junctionNode = head1;
????}
????// 若長度不等，長的先剪掉長度差，然后再同步遞增
????elseif(length1 > length2)
????{
?????int step = length1 - length2;
?????while(step--)
?????{
??????head1 = head1->next;
?????}
?????while(head1 != head2)
?????{
??????head1 = head1->next;
??????head2 = head2->next;
?????}
?????junctionNode = head1;
????}
????else
????{
?????int step = length2 - length1;
?????while(step--)
?????{
??????head2 = head2->next;
?????}
?????while(head1 != head2)
?????{
??????head1 = head1->next;
??????head2 = head2->next;
?????}
?????junctionNode = head1;
????}
????returntrue;
???}
???else
???{
????returnfalse;
???}
??}
?}
?
?returnfalse;
}

/******************************************************************************************************
Description?? : 查找環的入口
Prototype???? : template<typename T>
????T* findLoopPort(T* head)
Input Param?? : head，鏈表的頭結點
Output Param? : 無
Return Value? : 環入口點的指針
********************************************************************************************************/
template<typename T>
T* findLoopPort(T* head)
{
?// 判斷是否有環，五環返回NULL
?checkCircle(head);
?if(!checkCircle(head))
??return NULL;

?T* low = head;
?T* fast = head;

?// low按照步長1增加，fast按照步長2增加，找到碰撞點
?while(1)
?{
??low = low->next;
??fast = fast->next->next;
??if(low == fast)
???break;
?}
?
?// 分別從頭結點和碰撞節點開始按照步長1增加，遍歷鏈表，第一個節點相同的點是環入口點
?low = head;
?while(low != fast)
?{
??low = low->next;
??fast = fast->next;
?}

?return low;?
}

/******************************************************************************************************
Description?? : 計算環的長度
Prototype???? : template<typename T>
????int getLoopLength(T* head)
Input Param?? : head，鏈表的頭結點
Output Param? : 無
Return Value? : int，表示長度
********************************************************************************************************/
template<typename T>
int getLoopLength(T* head)
{
?if(!checkCircle(head))
??return0;
?

?T* low = head;
?T* fast = head;
?int length =0;

?// low按照步長1增加，fast按照步長2增加，找到碰撞點,然后接著循環直到下一次碰撞，
?// 計算兩次碰撞之間的循環次數即為長度
?while(1)
?{
??low = low->next;
??fast = fast->next->next;
??if(low == fast)
???break;
?}
?while(1)
?{
??low = low->next;
??fast = fast->next->next;
??length++;
??if(low == fast)
???break;

?}
?return length;
}

/******************************************************************************************************
Description?? : 計算有環鏈表的尾長度
Prototype???? : template<typename T>
????int getTailLength(T* head)
Input Param?? : head，鏈表的頭結點
Output Param? : 無
Return Value? : int，表示長度
********************************************************************************************************/
template<typename T>
int getTailLength(T* head)
{
?T* port = findLoopPort(head);
?int length =0;
?T* temp = head;

?while(temp != port)
?{
??length++;
??temp = temp->next;
?}
?return length;
}

main.cpp

#include"isListJunction.h"
#include<string>

template<typename T>
struct listNode
{
?T val;
?listNode *pre;
?listNode *next;

?listNode()
?{
??pre = NULL;
??next= NULL;
?}

?listNode(T value)
?{
??val = value;
??pre = NULL;
??next= NULL;
?}
};

int main(int argc,char** argv)
{
?string first ="my is";
?string second ="your";
?string three ="is";
?string four ="king";
?string five ="name";
?string first2 ="speak";
?string second2 ="what";

?list<string> firstlist;
?firstlist.push_back(first);
?firstlist.push_back(second);
?firstlist.push_back(three);
?firstlist.push_back(four);
?firstlist.push_back(five);

?list<string> secondlist;
?secondlist.push_back(first2);
?secondlist.push_back(second2);
?secondlist.push_back(four);
?secondlist.push_back(five);

?// 鏈表1，無環
?listNode<string>*head1 =new listNode<string>(first);
?listNode<string>*pnode2 =new listNode<string>(second);
?head1->next= pnode2;
?listNode<string>*pnode3 =new listNode<string>(three);
?pnode2->next= pnode3;
?listNode<string>*pnode4 =new listNode<string>(four);
?pnode3->next= pnode4;
?listNode<string>*pnode5 =new listNode<string>(five);
?pnode4->next= pnode5;

?// 鏈表2，無環
?listNode<string>*head2 =new listNode<string>(first2);
?listNode<string>*pnode22 =new listNode<string>(second2);
?head2->next= pnode22;
?pnode22->next= pnode4;
?pnode4->next= pnode5;

?// 鏈表1、2相交
?bool bJunction = isListJunction(head1,head2);
?std::cout<< bJunction<<std::endl;

?std::cout<< checkCircle(head1)<<endl;
?std::cout<< checkCircle(head2)<<endl;


?string first3 ="1";
?string second3 ="2";
?string three3 ="3";
?string four3 ="4";
?string five3 ="5";
?string six3 ="6";
?string seven3 ="7";

?// 鏈表3，有環
?listNode<string>*head3 =new listNode<string>(first3);
?listNode<string>*pnode32 =new listNode<string>(second3);
?head3->next= pnode32;
?listNode<string>*pnode33 =new listNode<string>(three3);
?pnode32->next= pnode33;
?listNode<string>*pnode34 =new listNode<string>(four3);
?pnode33->next= pnode34;
?listNode<string>*pnode35 =new listNode<string>(five3);
?pnode34->next= pnode35;
?listNode<string>*pnode36 =new listNode<string>(six3);
?pnode35->next= pnode36;
?pnode36->next= pnode33;

?cout<<findLoopPort(head3)->val<<endl;
?cout<<getLoopLength(head3)<<endl;

?// 鏈表4，有環
?listNode<string>*head4 =new listNode<string>(seven3);
?head4->next= pnode32;
?cout<<isListJunction(head3,head4)<<endl;

?cout<<"the length of list3 : "<<getLoopLength(head3)+ getTailLength(head3)<<endl;
?cout<<"the length of list4 : "<<getLoopLength(head4)+ getTailLength(head3)<<endl;
?
?listNode<string>*junctionNode =new listNode<string>;
?cout<<isListJunction(head3,head4,junctionNode)<<endl;
?cout<<"list3 與 list4的交點： "<<junctionNode->val<<endl;
?return0;
}

轉載于:https://www.cnblogs.com/xuhj001/p/3389137.html

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/377664.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/377664.shtml
英文地址，請注明出處：http://en.pswp.cn/news/377664.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！

相關文章

VS 如何修改C++編譯標準

VS 如何修改C++編譯標準

第一步&#xff0c;打開項目資源管理器的屬性頁面 第二步&#xff0c;選擇配置屬性->C/C>語言->C語言標準 第三步&#xff0c;選擇合適的標準&#xff0c;一般來說選最新即可
閱讀更多...
維吉尼亞密碼和一次性密碼本_密碼學中的一次性密碼

維吉尼亞密碼和一次性密碼本_密碼學中的一次性密碼

維吉尼亞密碼和一次性密碼本The One-time Pad cipher is almost similar to the Vernam cipher, as, like the vernam cipher, this cipher technique also encrypts the plain text by working on the binary level of the text. The only difference between the two is that…
閱讀更多...
十一、紡織面料下架功能的實現

十一、紡織面料下架功能的實現

一、數據庫 數據庫仍用yy_textile表&#xff0c;前幾篇博文都敘述過這里就不再敘述 在fiber_yy數據庫下創建yy_textile表 初始數據庫信息 二、頁面 admin_undercarriage 三、代碼實現 admin_undercarriage using System; using System.IO; using System.Data; using S…
閱讀更多...
svg和canvas的應用場景分析【轉載】

svg和canvas的應用場景分析【轉載】

原文地址&#xff1a;http://blogs.msdn.com/b/weizhong/archive/2011/07/16/canvas-svg.aspx 思考什么時候使用Canvas 和SVG wzhong 15 Jul 2011 9:07 PM 0HTML5 Canvas 和 SVG 是 IE9 中引入的兩項令人激動的圖形功能。上周在拉斯維加斯舉辦的 MIX11 大會對這兩個功能進行了介…
閱讀更多...
【C++grammar】文件系統以及path類使用

【C++grammar】文件系統以及path類使用

目錄1.文件系統概述1、關于路徑2、如何將某個路徑下的所有文件遞歸地找出來&#xff1f;2.路徑類及操作1、path類的成員函數2、path類的非成員函數示例1&#xff1a;展示C17中的path對象的用法示例2&#xff1a;展示Path類中用于分解路徑成分的函數示例3&#xff1a;展示path相…
閱讀更多...
scala hashmap_如何在Scala中將Hashmap轉換為Map？

scala hashmap_如何在Scala中將Hashmap轉換為Map？

scala hashmapLets first understand what are maps and hashmaps? 首先讓我們了解什么是map和hashmap &#xff1f; map in Scala is a collection that stores its elements as key-value pairs, like a dictionary. Scala中的map是一個集合&#xff0c;將其元素存儲為鍵值…
閱讀更多...
十二、所有功能實現效果演示

十二、所有功能實現效果演示

一、系統項目架構 Ⅰ&#xff0c;fiber_yy數據庫下有五張表 yy_admin&#xff1a;管理員登錄賬號和密碼 yy_textile&#xff1a;紡織面料數據信息 yy_textile_record&#xff1a;用戶購買紡織面料信息所存儲的面料流水信息 yy_user&#xff1a;用戶登錄注冊信息 yy_user_reco…
閱讀更多...
行業軟件之PTV微觀軟件VISSIM4.3 5.0 5.1 5.2 5.3 5.4下載和相關資料

行業軟件之PTV微觀軟件VISSIM4.3 5.0 5.1 5.2 5.3 5.4下載和相關資料

他是干什么的&#xff1a;http://baike.baidu.com/view/3656765.htm 中國代理銷售的公司的網址&#xff1a;辟途威交通科技(上海)有限公司 官網&#xff1a;http://www.ptvchina.cn/ 看看視頻中軟件的運行效果&#xff1a;http://v.youku.com/v_show/id_XMzExMjg1MDEy.html 如何…
閱讀更多...
一、單個神經元網絡構建

一、單個神經元網絡構建

一、本人使用編譯器為Jupyter Notebook&#xff0c;tensorflow版本為1.13.1 import tensorflow as tf print(tf.__version__) """ 1.13.1 """二、訓練單個神經元網絡 x為-1.0, 0.0, 1.0, 2.0, 3.0, 4.0 y為-3.0, -1.0, 1.0, 3.0, 5.0, 7.0 人用…
閱讀更多...
ruby 生成隨機字符串_Ruby程序生成隨機數

ruby 生成隨機字符串_Ruby程序生成隨機數

ruby 生成隨機字符串產生隨機數 (Generating random number) The task is to generate and print random number. 任務是生成并打印隨機數。 Generating random numbers means that any number can be provided to you which is not dependent on any pre-specified condition…
閱讀更多...
leetcode 322. 零錢兌換 思考分析

leetcode 322. 零錢兌換 思考分析

目錄1、題目2、思路分析3、參考鏈接1、題目 給定不同面額的硬幣 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬幣個數。如果沒有任何一種硬幣組合能組成總金額&#xff0c;返回 -1。 你可以認為每種硬幣的數量是無限的。 提示&#xff1a; 1 …
閱讀更多...
linux上的英文字體monospace可以在windows用嗎？

linux上的英文字體monospace可以在windows用嗎？

linux的字體都是開源的&#xff0c;應該可以官方下載本地下載轉載于:https://www.cnblogs.com/52linux/archive/2012/03/14/2396103.html
閱讀更多...
Flash Builder 創建CSS

Flash Builder 創建CSS

1.global 選擇器將樣式應用于所有控件 在 Flash Builder 中創建新MXML 文件并切換到設計模式 屬性視圖右側的外觀視圖可更改外觀 Flash Builder 自動創建CSS 文件 CSS 文件有2 個命名空間&#xff1a; s 指 Spark 組件 mx 指 MX 組件 1. Global 與Application 選擇器 global …
閱讀更多...
ruby打印_Ruby程序打印數字的力量

ruby打印_Ruby程序打印數字的力量

ruby打印Ruby中數字的冪 (Power of a number in Ruby) The task to develop a program that prints power of a number in Ruby programming language. 開發可以用Ruby編程語言打印數字冪的程序的任務。 If we want to calculate the power of a number manually then we have…
閱讀更多...
二、訓練fashion_mnist數據集

二、訓練fashion_mnist數據集

一、加載fashion_mnist數據集 fashion_mnist數據集中數據為28*28大小的10分類衣物數據集 其中訓練集60000張&#xff0c;測試集10000張 from tensorflow import keras import tensorflow as tf import matplotlib.pyplot as plt import numpy as npfashion_mnist keras.data…
閱讀更多...
jquerymobile 切換頁面時候閃爍問題

jquerymobile 切換頁面時候閃爍問題

https://github.com/jquery/jquery-mobile/commit/acbec71e29b6acec6cd2087e84e8434fecc0053f 可以修改css好像是個bug -4,9 4,10 * Dual licensed under the MIT (MIT-LICENSE.txt) or GPL (GPL-LICENSE.txt) licenses.*/.spin {--webkit-animation-name: spin;--webkit-an…
閱讀更多...
二分法：兩個有序數組長度為N，找到第N、N+1大的數

二分法：兩個有序數組長度為N，找到第N、N+1大的數

題目 兩個有序數組長度為N&#xff0c;找到第N、N1大的數 思路1&#xff1a;雙指針&#xff0c;O(N)復雜度 簡述思路&#xff1a; 如果當前A指針指向的數組A的內容小于B指針指向的數組B的內容&#xff0c;那么A指針往右移動&#xff0c;然后nums(當前已經遍歷過的數字個數)也…
閱讀更多...
Javascript -- In

Javascript -- In

http://www.caveofprogramming.com/articles/javascript-2/javascript-in-using-the-in-operator-to-iterate-through-arrays-and-objects/ http://msdn.microsoft.com/en-us/library/ie/9k25hbz2(vvs.94).aspx轉載于:https://www.cnblogs.com/daishuguang/p/3392310.html
閱讀更多...
三、自動終止訓練

三、自動終止訓練

有時候&#xff0c;當模型損失函數值預期的效果時&#xff0c;就可以結束訓練了&#xff0c;一方面節約時間&#xff0c;另一方面防止過擬合 此時&#xff0c;設置損失函數值小于0.4&#xff0c;訓練停止 from tensorflow import keras import tensorflow as tf import matplo…
閱讀更多...
矩陣形狀| 使用Python的線性代數

矩陣形狀| 使用Python的線性代數

Prerequisite: Linear Algebra | Defining a Matrix 先決條件&#xff1a; 線性代數| 定義矩陣 In the python code, we will add two Matrices. We can add two Matrices only and only if both the matrices have the same dimensions. Therefore, knowing the dimensions o…
閱讀更多...
最新文章

Copyright @ 2022~2023