文章目錄
- 簡介
- 弗洛伊德簡介
- 構造一個環
- 環的檢測和入口定位
- 判斷是否有環
- 找到環的入口
- 找到環的長度
簡介
環檢測應該是一個非常常見的演算法問題，怎么判斷是否有環的問題呢？
一個很簡單的做法就是用HashSet來保存要遍歷的資料，如果出現了重復就知道這個鏈表是有環的，但是這個方法需要保存遍歷過的所有的元素，所以其空間復雜度是o(n)，
有沒有什么方法可以不用保存之前的元素也能夠判斷是否有環呢？
來看看弗洛伊德的兔子和烏龜演算法吧，
弗洛伊德簡介
有的同學會說了，弗洛伊德（Sigmund Freud）誰不知道，夢的決議的作者，大名鼎鼎的心理學專家，精神分析學派的創始人，
但是這里我們講的弗洛伊德全名是Robert W．Floyd（羅伯特·弗洛伊德）而不是Sigmund Freud，
羅伯特·弗洛伊德是計算機科學家，圖靈獎得主，前后斷言法的創始人，堆排序演算法和Floyd-Warshall演算法的創始人之一，
它獲得了1978年圖靈獎，是一位“自學成才的計算機科學家”，
這個兔子和烏龜演算法就是他發明的一種環檢測演算法，
構造一個環
在
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/123613.html
標籤：其他
上一篇：Python高效編程之88條軍規（2）：你真的會格式化字串嗎？
下一篇：Hadoop環境配置與測驗