上期填坑
leetcode, 1791. 找出星型圖的中心節(jié)點
有一個無向的 星型 圖，由 n 個編號從 1 到 n 的節(jié)點組成衅澈。
星型圖有一個 中心 節(jié)點谬墙，并且恰有 n - 1 條邊將中心節(jié)點與其他每個節(jié)點連接起來经备。
給你一個二維整數(shù)數(shù)組 edges 侵蒙，其中 edges[i] = [ui, vi] 表示在節(jié)點 ui 和 vi 之間存在一條邊傅蹂。
請你找出并返回 edges 所表示星型圖的中心節(jié)點
public int findCenter(int[][] edges) {
int n = edges.length + 1;
int[] degrees = new int[n + 1];
for (int[] edge : edges) {
degrees[edge[0]]++;
degrees[edge[1]]++;
}
for (int i = 1; ; i++) { //星型圖中中心節(jié)點的度為n-1，其余節(jié)點為1
if (degrees[i] == n - 1) {
return i;
}
}
}
范式的概念
在設(shè)計數(shù)據(jù)庫時犁功，要遵循不同的規(guī)范要求婚夫，這些規(guī)范要求就被稱為范式(Normal Form，NF)。 范式的作用是使設(shè)計的表結(jié)構(gòu)更合理侍筛，減少數(shù)據(jù)的冗余撒穷，消除數(shù)據(jù)增刪改的異常; 目前常見的范式分為六種，各種范式呈層級遞增禽笑，越高的范式數(shù)據(jù)庫冗余越小蛤奥。具體的關(guān)系如下如所示：
數(shù)據(jù)庫的碼
碼又稱為鍵（key），是能唯一標(biāo)識實體的屬性蟀伸。根據(jù)碼的范圍與性質(zhì)的不同缅刽，有可以分為以下幾種：
針對下面的學(xué)生信息表，對不同的碼進行說明：
CREATE TABLE student (
id int(11) NOT NULL PRIMARY KEY COMMENT '主鍵ID',
sno int(11) DEFAULT NULL COMMENT '學(xué)號',
scardid varchar(255) DEFAULT NULL COMMENT '身份證號'迟蜜，
classid int(11) DEFAULT NULL COMMENT '課程號'啡省，
teacher varchar(255) DEFAULT NULL COMMENT '教師'髓霞，
sinfo varchar(255) DEFAULT NULL COMMENT '學(xué)生信息(包含姓名酸茴，性別兢交，年齡)')，
foreign key classid references class(id)
)
超碼
一個或者多個屬性的集合酪穿，能唯一標(biāo)識元組晴裹。
如果A是一個超碼，那么任何包含A的屬性集合都是超碼涧团。
在student表中泌绣，id，sno阿迈，scardid苗沧，都可以唯一標(biāo)識一條數(shù)據(jù)，它們都是碼待逞，亦是超碼。那么包含其中任意一個的屬性集合也是超碼蜈膨。
候選碼
從超碼中選出的最小超碼牺荠，即是候選碼。所謂最小超碼灶壶，就是該超碼任意真子集都不能成為超碼杈曲。
在student表中胸懈，候選碼有（id)趣钱、（sno）胚宦、（scardid），那么包含其中任意一個的屬性集合枢劝，都不在可能是候選碼您旁。
主碼
即主鍵，從候選碼中選擇的蚕脏，通常選擇那些極少改變的候選碼侦锯。
在student表中，（id)率触、（sno）葱蝗、（scardid）都可以作為主碼细燎，但是選擇了（id）作為主碼。
因為主碼不可以包含空值悼凑，但（sno）璧瞬、（scardid）默認(rèn)為空。故不選擇渔欢。
主碼也可以是由多個屬性組成瘟忱。
外碼
即外鍵苫幢，另一張表中的主碼垫挨，表示該表與另一張表中的關(guān)聯(lián)。 在student表中哀峻，(classid)即為外碼帚屉。
屬性
? 主屬性：包含在任一候選碼中的屬性攻旦，即主屬性是候選碼所有屬性的并集。
? 非主屬性：除了主屬性之外的屬性牢屋。
函數(shù)依賴
定義：設(shè)R(U)是一個屬性集U上的關(guān)系模式烙无，X和Y是U的子集。若對于R(U)的任意一個可能的關(guān)系r截酷，r中不可能存在兩個元組在X上的屬性值相等迂苛，而在Y上的屬性值不等，則稱“X函數(shù)確定Y"或“Y函數(shù)依賴于X”就漾，記作X->Y念搬。
說人話就是，在屬性集中首妖，確定了屬性X爷恳，就唯一確定了屬性Y，即是Y函數(shù)依賴于X妒貌。類似與數(shù)學(xué)中的Y=f(X)函數(shù)關(guān)系一樣。
在student表中菊碟，確定了sno(學(xué)號)在刺，就唯一確定了sinfo（學(xué)生信息），即是sinfo函數(shù)依賴于sno魄幕，記作sno -> sinfo.
完全和部分函數(shù)依賴
在R(U)中颖杏，如果X決定Y，并且X存在多個翼抠，確定Y時必須依賴全部的X获讳，則稱Y對X是完全函數(shù)依賴， 確定Y時不必需要依賴全部的X量愧，X中的部分屬性就可以唯一確定Y帅矗，則稱Y對X是部分函數(shù)依賴损晤。
假設(shè)在student表中红竭，X為（sno，cardid）最冰，Y為 （sinfo）稀火，X -> Y，現(xiàn)在 只要知道sno篇裁，就可以唯一確定sinfo，那么就說Y部分依賴于X团甲；
傳遞函數(shù)依賴
在R(U)中黍聂，Z函數(shù)依賴于Y，且Y函數(shù)依賴于X匹厘，并且Y不函數(shù)依賴于X脐区，X不函數(shù)依賴于Y，那么我們就稱Z傳遞函數(shù)依賴于X扰路。
類似我們數(shù)學(xué)中學(xué)到的大小關(guān)系的傳遞倔叼。X -> Y丈攒，Y -> Z；X->Z际插。
在student表中显设，假設(shè)通過sno -> classid，而classid -> teacher ,那么就可以說teacher傳遞依賴于sno.
六種范式
學(xué)習(xí)完前置的概念瑟枫，接下來學(xué)習(xí)六種范式指攒。
第一范式（1NF）
數(shù)據(jù)表中每個字段的值必須具有原子性允悦，每一列都是不可分割的基本數(shù)據(jù)項。
下面的student表就不符合第一范式：
CREATE TABLE student (
sno int(11) DEFAULT NULL COMMENT '學(xué)號',
scardid varchar(255) DEFAULT NULL COMMENT '身份證號'架馋，
classid int(11) DEFAULT NULL COMMENT '課程號'，
teacher varchar(255) DEFAULT NULL COMMENT '教師'铣墨，
sinfo varchar(255) DEFAULT NULL COMMENT '學(xué)生信息(包含姓名办绝，性別，年齡)')屡律，
)
sinfo(學(xué)生信息)，它還可以拆分成顆粒度更細(xì)的字段佳鳖，不符合數(shù)據(jù)庫設(shè)計對第一范式要求的“每個字段的值必須具有原子性”系吩。 將student_info拆分后如下:
CREATE TABLE student (
sno int(11) DEFAULT NULL COMMENT '學(xué)號',
sname varchar DEFAULT NULL COMMENT '姓名',
ssex varchar DEFAULT NULL COMMENT '性別',
sage int DEFAULT NULL COMMENT '年齡'，
scardid varchar(255) DEFAULT NULL COMMENT '身份證號'月弛，
classid int(11) DEFAULT NULL COMMENT '課程號'科盛，
teacher varchar(255) DEFAULT NULL COMMENT '教師'，
第二范式（2NF）
在滿足第一范式的基礎(chǔ)上厉萝，還要滿足數(shù)據(jù)表里的每一條數(shù)據(jù)記錄都是可唯一標(biāo)識的榨崩，即要有主碼蜡饵。非主屬性必須完全依賴于候選碼(在1NF基礎(chǔ)上消除非主屬性對主碼的部分函依賴)胳施。
例如，假設(shè)在如下student表中焦辅，
CREATE TABLE student (
sno int(11) DEFAULT NULL COMMENT '學(xué)號',
sname varchar DEFAULT NULL COMMENT '姓名',
ssex varchar DEFAULT NULL COMMENT '性別',
sage int DEFAULT NULL COMMENT '年齡'筷登，
classid int(11) DEFAULT NULL COMMENT '課程號'，
teacher varchar(255) DEFAULT NULL COMMENT '教師'狈醉，
主碼都為（sno(學(xué)號)惠险， classid(課程號)）,那就可以得出如下的關(guān)系：
(sno,classid) -> (sname, ssex, sage, teacher)
但是上面的關(guān)系中，還存在著如下對應(yīng)關(guān)系：
(classid) -> (teacher)渣慕，這種就違背了第二范式的“非主屬性對主碼的完全函依賴抱慌，對于非主屬性來說，并非完全依賴候選碼强经。
為了避免上面的問題出現(xiàn)寺渗，我們就需要進行拆分表結(jié)構(gòu)來滿足第二范式户秤，拆分方式如下：
student= (U={sno, sname, ssex，sage})
class = (U={classid, teacher})
第三范式（3NF）
在第二范式的基礎(chǔ)上转砖，確保數(shù)據(jù)表中的每一個非主屬性字段都要和主碼直接相關(guān)鲸伴，也就是說，要求數(shù)據(jù)表中的所有非主屬性字段不能依賴于其它非主屬性字段(就是在2NF基礎(chǔ)上消除傳遞依賴)姓赤。
在2NF中我們拆分成了滿足要求的class表中加兩個字段，如下：
student= (U={sno仲吏，sname不铆， ssex蝌焚，sage})
class = (U={classid， teacher誓斥，sdept只洒，mname })
要滿足第三范式則需要“非主屬性字段不能依賴于其它非主屬性字段”，
但可以看出class表中的非主屬性（teacher劳坑，sdept毕谴，mname）里面的（sdept, mname）構(gòu)成了傳遞依賴，
其中非主屬性sdept(專業(yè))依賴于classid(課程號), 而非主屬性mname(系主任名稱)則可以依賴于非主屬性sdept(專業(yè))距芬，
因為通過專業(yè)可以找到具體的專業(yè)里的系主任，所以需要如下修改框仔，拆分學(xué)生表達到第三范式：
student= (U={sno忠寻，sname， ssex存和，sage})
class = (U={classid奕剃， teacher，sdept})
dept = (U={sdept, mname})
巴斯科德范式（BCNF）
BCNF只是對第三范式中設(shè)計規(guī)范要求更強捐腿，使得數(shù)據(jù)庫冗余度更小纵朋。所以，稱為是修正的第三范式茄袖，或擴充的第三范式操软。
BCNF主要就是消除主屬性對碼（單碼或復(fù)合碼）的部分函數(shù)依賴和傳遞函數(shù)依賴
假設(shè)有一張表STJ表屬性為U={S(學(xué)生),T(教師),J(課程)}
如上表關(guān)系：每一教師只教一門課。每門課有若干教師宪祥，某一學(xué)生選定某門課聂薪，就對應(yīng)一個固定的教師
那么其中分析主屬性（S,J,P）,候選碼為(S,J), (S,T)
由語義可得到函數(shù)依賴: (S,J)->T, (S,T)->J, T->J
(S,J)->T：通過學(xué)生和課程字段可以得出教師
(S,T)->J：通過學(xué)生和教師字段可以得出課程
T->J：因為每一教師只教一門課，所以通過教師可以得出課程
關(guān)系模式中沒有非主屬性對碼傳遞依賴或部分依賴蝗羊，所以滿足第三范式
因為主屬性T部分依賴于候選碼藏澳，所以當(dāng)前表不滿足BCNF。
判斷是否為BCNF耀找，只需要判斷主屬性內(nèi)部是否存在部分函數(shù)依賴和傳遞函數(shù)依賴翔悠，如果不存在則是BCNF；
第四范式（4NF）
限制關(guān)系模式的屬性之間不允許有非平凡且非函數(shù)依賴的多值依賴野芒。
在之前范式中蓄愁，研究的都是屬性的函數(shù)依賴關(guān)系（X與Y之前的關(guān)系），而第四范式研究的更為特殊的多值依賴問題（X狞悲、Y和Z之間的關(guān)系）撮抓。
舉例：教師、課程和參考書的關(guān)系：
在某個學(xué)校中摇锋，一門課程可能由多個教師講授丹拯，每個教師可能講授多門課程站超。
同時，每本參考書可能被多門課程使用咽笼。
這種關(guān)系可以通過一個非規(guī)范化的關(guān)系來表示顷编，其中教師(T)戚炫、課程(C)和參考書(B)之間的關(guān)系可以表示為Teaching(C,T,B)剑刑。
在這個例子中，如果一個課程增加了一名講課教師或去掉了一本參考書双肤，那么必須插入或刪除多個元組施掏，這表明了多值依賴的存在
第五范式（5NF）
也被稱為完美范式。它要求關(guān)系模式R的依賴關(guān)系完全由R的候選碼所隱含茅糜，即屬性均為候選碼七芭。
第五范式旨在通過分隔語義連接的關(guān)系來存儲多值事實，以減少關(guān)系數(shù)據(jù)庫中的冗余蔑赘。
反范式
范式的優(yōu)點：數(shù)據(jù)的標(biāo)準(zhǔn)化有助于消除數(shù)據(jù)庫中的數(shù)據(jù)冗余狸驳，消除增刪改的異常。
范式的缺點：可能降低查詢的效率缩赛。
因為范式等級越高耙箍，設(shè)計出來的數(shù)據(jù)表就越多、越精細(xì)酥馍，數(shù)據(jù)的冗余度就越低辩昆，進行數(shù)據(jù)查詢的時候就可能需要關(guān)聯(lián)多張表，這不但代價昂貴旨袒，也可能使一些索引策略無效汁针。
范式只是提出了設(shè)計的標(biāo)準(zhǔn)，實際上設(shè)計數(shù)據(jù)表時砚尽，未必一定要符合這些標(biāo)準(zhǔn)施无。
開發(fā)中，我們會出現(xiàn)為了性能和讀取效率違反范式化的原則
通過增加少量的冗余或重復(fù)的數(shù)據(jù)來提高數(shù)據(jù)庫的讀性能
必孤，減少關(guān)聯(lián)查詢帆精，JOIN表的次數(shù)，實現(xiàn)空間換取時間的目的隧魄。
因此在實際的設(shè)計過程中要理論結(jié)合實際卓练，靈活運用。
范式本身沒有優(yōu)劣之分购啄，只有適用場景不同襟企。沒有完美的設(shè)計，只有合適的設(shè)計狮含，我們在數(shù)據(jù)表的設(shè)計中顽悼，還需要根據(jù)需求將范式和反范式混合使用曼振。
在實際開發(fā)設(shè)計中，遵循業(yè)務(wù)優(yōu)先的原則蔚龙，首先滿足業(yè)務(wù)需求冰评，再盡量減少冗余。
每日一算
leetcode,108. 將有序數(shù)組轉(zhuǎn)換為二叉搜索樹 給你一個整數(shù)數(shù)組 nums 木羹，其中元素已經(jīng)按 升序 排列甲雅，請你將其轉(zhuǎn)換為一棵平衡二叉搜索樹。
