什么是并查集 在計算機科學(xué)中,并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不交集(Disjoint Sets)的合并及查詢問題。有一個聯(lián)合-查找算法(Union-find Alg...
什么是并查集 在計算機科學(xué)中,并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不交集(Disjoint Sets)的合并及查詢問題。有一個聯(lián)合-查找算法(Union-find Alg...
什么是滑動窗口(Sliding Window) The Sliding Problem contains a sliding window which is a sub – ...
題目說明 給定一個整數(shù)數(shù)組 nums ,找到一個具有最大和的連續(xù)子數(shù)組(子數(shù)組最少包含一個元素),返回其最大和。 示例: 進(jìn)階: 如果你已經(jīng)實現(xiàn)復(fù)雜度為 O(n) 的解法,嘗...
如何理解分治算法 分治算法(divide and conquer)的核心思想就四個字:分而治之,就是將原問題劃分成 n 個規(guī)模較小,并且結(jié)構(gòu)與原問題相似的子問題,遞歸地解決這...
什么是貪心算法 貪心算法(英語:greedy algorithm),又稱貪婪算法,是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)(即最有利)的選擇,從而希望導(dǎo)致結(jié)果是最好或...
什么是回溯算法 回溯算法實際上一個類似枚舉的搜索嘗試過程,主要是在搜索嘗試過程中尋找問題的解,當(dāng)發(fā)現(xiàn)已不滿足求解條件時,就 “回溯” 返回,嘗試別的路徑。 回溯法是一種選優(yōu)搜...
前言 上一節(jié)通過兩個經(jīng)理案例初步認(rèn)識動態(tài)規(guī)劃,今天這一節(jié)主要講動態(tài)規(guī)劃的理論知識。 “一個模型三個特征”理論講解 實際上,動態(tài)規(guī)劃作為一個非常成熟的算法思想,這部分理論總結(jié)為...
前言 今天開始學(xué)習(xí)動態(tài)規(guī)劃,一共有三節(jié),分別是:初識動態(tài)規(guī)劃、動態(tài)規(guī)劃理論、動態(tài)規(guī)劃實戰(zhàn)。今天這一節(jié)就是初識動態(tài)規(guī)劃。 動態(tài)規(guī)劃比較適合用來求解最優(yōu)問題,比如最大值、最小值等...
什么是搜索算法 上一節(jié)介紹了圖的基本概念,這一節(jié)介紹圖的搜索算法。 圖的搜索算法,最直觀的理解就是從一個頂點到另一個頂點的路徑。 最簡單的是廣度優(yōu)先搜索和深度優(yōu)先搜索,這也是...
基本概念 圖是一種非線性的數(shù)據(jù)結(jié)構(gòu),相比樹來說,更加復(fù)雜。 圖的元素叫頂點,樹的元素叫節(jié)點。 度:頂點相連的邊的條數(shù)叫度。 圖的分類有無向圖、有向圖、帶權(quán)圖 無向圖 邊沒有方...
上一節(jié)我們學(xué)習(xí)了堆和堆排序的一些理論知識(點擊查看),今天我們就來講一講,堆這種數(shù)據(jù)結(jié)構(gòu)的幾個非常重要的應(yīng)用。 應(yīng)用一:優(yōu)先級隊列 優(yōu)先隊隊列,是一個按優(yōu)先級進(jìn)出的特殊隊列,...
今天我們來學(xué)習(xí)堆和堆排序。 什么是堆 堆是一種特殊的樹,滿足以下兩點要求: 堆是一個完全二叉樹。 堆中每個節(jié)點的值都必須大于等于(或小于等于)其子樹中每個節(jié)點的值。 通過要求...
前言 在排序那一節(jié)里,講到排序時,利用遞推公式推導(dǎo)時間復(fù)雜度來求解歸并排序、快速排序的時間復(fù)雜度,但有些情況,例如快速排序的平均時間復(fù)雜度,利用遞推公式,會涉及很復(fù)雜的數(shù)據(jù)推...
前言 二叉查找樹是最常用的一種二叉樹,它支持快速查找、插入、刪除操作。性能與樹的高度成正比,理想情況下,時間復(fù)雜為是O(logn)。 不過頻繁的更新,二叉樹的高度會遠(yuǎn)大于lo...
二叉查找樹 二叉查找樹是二叉樹中最常用的一種類型,也叫二叉搜索樹。 二叉查找樹要求,在樹中的任意一個節(jié)點,其左子的每個節(jié)點的值,都要小于這個節(jié)點的值,而右子樹節(jié)點的值都大于這...
概念 樹:是一種數(shù)據(jù)結(jié)構(gòu),像一顆倒掛的樹。樹的每個元素叫作“節(jié)點”;用來連續(xù)相鄰節(jié)點之間的關(guān)系,叫作“父子關(guān)系”。 關(guān)于高度(Height)、深度(Depth)、層(Leve...
前言 上一節(jié)我們講了哈希算法的四個應(yīng)用,分別是安全加密、數(shù)據(jù)校驗、唯一標(biāo)識、散列函數(shù)。今天再來看看剩下的三個應(yīng)用:負(fù)載均衡、數(shù)據(jù)分片、分布式存儲。 可能大家已經(jīng)發(fā)現(xiàn)了,這三個...
什么是哈希算法 將任意長度的二進(jìn)制值串映射為固定長度的二進(jìn)制值串,這個映射的規(guī)則就是哈希算法。而通過原始數(shù)據(jù)映射之后得到的二進(jìn)制值串就是哈希值。 一個優(yōu)秀的哈希算法要滿足幾點...
有兩種數(shù)據(jù)結(jié)構(gòu)(散列表和鏈表)經(jīng)常會被放在一起使用。前面的章節(jié)中有兩個地方講到散列表和鏈表的組合使用,分別是: 04——鏈表 13——跳表 另外,Java中有一個容器Link...