力扣 (LeetCode)-合并兩個(gè)有序數(shù)組,字典,散列表
Github來(lái)源：力扣 (LeetCode)｜刷題打卡 | 求星星 ? | 給個(gè)??關(guān)注，??點(diǎn)贊，??鼓勵(lì)一下作者
[已開(kāi)啟]任務(wù)一：刷題打卡 * 10 篇
哪吒人生信條：如果你所學(xué)的東西 處于喜歡 才會(huì)有強(qiáng)大的動(dòng)力支撐。
每天學(xué)習(xí)編程，讓你離夢(mèng)想更新一步，感謝不負(fù)每一份熱愛(ài)編程的程序員，不論知識(shí)點(diǎn)多么奇葩，和我一起，讓那一顆四處流蕩的心定下來(lái)，一直走下去，加油，2021加油！歡迎關(guān)注加我vx:xiaoda0423，歡迎點(diǎn)贊、收藏和評(píng)論
時(shí)間：3 月 1 日 ～ 3 月 13 日
力扣 (LeetCode)-兩數(shù)之和,有效的括號(hào),兩數(shù)相加｜刷題打卡-3月1日 力扣 (LeetCode)-合并兩個(gè)有序鏈表,刪除排序數(shù)組中的重復(fù)項(xiàng),JavaScript筆記｜刷題打卡-3月2日 力扣 (LeetCode)-最大子序和,JavaScript數(shù)據(jù)結(jié)構(gòu)與算法（數(shù)組）｜刷題打卡-3月3日 針對(duì)CSS說(shuō)一說(shuō)｜技術(shù)點(diǎn)評(píng)-3月4日 力扣 (LeetCode)-棧,括號(hào)生成 ｜刷題打卡-3月5日 原來(lái)也沒(méi)有那么難！Vue商城開(kāi)發(fā) | 技術(shù)點(diǎn)評(píng)-3月6日 力扣 (LeetCode)-加一，隊(duì)列 ｜刷題打卡-3月7日 JavaScript數(shù)據(jù)結(jié)構(gòu)之鏈表 | 技術(shù)點(diǎn)評(píng)-3月8日 JavaScript的數(shù)據(jù)結(jié)構(gòu)-集合 ｜技術(shù)點(diǎn)評(píng)-3月9號(hào)
前言
如果這篇文章有幫助到你，給個(gè)??關(guān)注，??點(diǎn)贊，??鼓勵(lì)一下作者，接收好挑戰(zhàn)了嗎？文章公眾號(hào)首發(fā)，關(guān)注 程序員哆啦A夢(mèng) 第一時(shí)間獲取最新的文章
??筆芯??~
棧，隊(duì)列，鏈表，集合
字典和散列表
集合，字典，散列表可以存儲(chǔ)不重復(fù)的值 在字典中，使用 [鍵，值]的形式來(lái)存儲(chǔ)數(shù)據(jù)散列表中也是以 [鍵，值]對(duì)的形式來(lái)存儲(chǔ)數(shù)據(jù)字典中鍵名是用來(lái)查詢特定元素的 字典數(shù)據(jù)結(jié)構(gòu)的例子，一個(gè)實(shí)際的字典，以及一個(gè)地址簿
創(chuàng)建字典
function Dictionary() {
var items = {};
}
使用到的方法：
set(key,value)，向字典中添加新元素delete(key)，通過(guò)使用鍵值來(lái)從字典中移除鍵值對(duì)應(yīng)的數(shù)據(jù)值has(key)，如果某個(gè)鍵值存在于這個(gè)字典中，則返回true，反之則返回falseget(key)，通過(guò)鍵值查找特定的數(shù)值并返回clear()，將這個(gè)字典中的所有元素全部刪除size()，返回字典所包含元素的數(shù)量keys()，將字典所包含的所有鍵名以數(shù)組形式返回values()，將字典所包含的所有數(shù)值以數(shù)組形式返回
has和set方法
示例：
this.has = function(key) {
return key in items;
);
set方法的實(shí)現(xiàn)：
// 將value設(shè)為items對(duì)象的key屬性的值
this.set = function(key, value) {
items[key] = value;
};
delete方法
使用JavaScript的remove操作符來(lái)從items對(duì)象中移除key屬性
this.delete= function(key) {
if (this.has(key)) {
delete items[key];
return true;
}
return false;
};
get和values方法
在字典中查找一個(gè)特定的項(xiàng)，并檢索它的值
this.get = function(key) {
// 通過(guò)查找key值
return this.has(key) ? items[key] : undefined;
};
以數(shù)組的形式返回字典中所有values實(shí)例的值
this.values = function() {
var values = [];
for (var k in items) { //遍歷items對(duì)象的所有屬性值
if (this.has(k)) {
// 使用has函數(shù)來(lái)驗(yàn)證key確實(shí)存在
values.push(items[k]); //將它的值加入values數(shù)組
}
}
return values;
};
clear,size,keys,getItems方法
示例：
this.keys = function() {
return Object.keys(items);
};
this.getItems = function() {
return items;
}
使用
Dictionary類
實(shí)現(xiàn)一個(gè)電子郵件地址簿：
var dictionary = new Dictionary();
dictionary.set('da1', '[email protected]');
dictionary.set('da2', '[email protected]');
dictionary.set('da3', '[email protected]');
console.log(dictionary.has('da1'));
console.log(dictionary.size());
console.log(dictionary.keys());
console.log(dictionary.values());
console.log(dictionary.get('da2'));
dictionary.delete('da1');
散列表
HashTable類(HashMap類)，它是Dictionary類的一種散列表實(shí)現(xiàn)方式如果使用散列函數(shù)，就知道值的具體位置，因此能夠快速檢索到該值 散列函數(shù)的作用是給定一個(gè)鍵值，然后返回值在表中的地址
創(chuàng)建散列表
// 使用數(shù)組來(lái)表示我們的數(shù)據(jù)結(jié)構(gòu)
function HashTable() {
var table = [];
}
put(key,value)，向散列表增加一個(gè)新的項(xiàng)remove(key)，根據(jù)鍵值從散列表中移除值get(key)，返回根據(jù)鍵值檢索到的特定的值
示例：
// HashTable類中的一個(gè)私有方法
var loseloseHashCode = function (key) {
// 給定一個(gè)key參數(shù)，我們就能根據(jù)組成key的每個(gè)字符的ASCII碼值的和得到一個(gè)數(shù)字
// 需要一個(gè)變量來(lái)存儲(chǔ)這個(gè)總和
var hash = 0;
for (var i = 0; i < key.length; i++) { //遍歷key
hash += key.charCodeAt(i);
//使用JavaScript的String類中的charCodeAt方法
}
return hash % 37;
//為了得到比較小的數(shù)值，我們會(huì)使用hash值和一個(gè)任意數(shù)做除法的余數(shù)
};
實(shí)現(xiàn)put方法
this.put = function(key, value) {
var position = loseloseHashCode(key);
//根據(jù)所創(chuàng)建的散列函數(shù)計(jì)算出它在表中的位置
console.log(position + ' - ' + key);
table[position] = value;
//將value參數(shù)添加到用散列函數(shù)計(jì)算出的對(duì)應(yīng)的位置上
};
實(shí)現(xiàn)一個(gè)get方法
this.get = function (key) {
// 使用所創(chuàng)建的散列函數(shù)來(lái)求出給定key所對(duì)應(yīng)的位置
// 根據(jù)這個(gè)位置從數(shù)組table中獲得這個(gè)值
return table[loseloseHashCode(key)];
};
實(shí)現(xiàn)一個(gè)remove方法
this.remove = function(key) {
// 求出元素的位置
table[loseloseHashCode(key)] = undefined;
};
散列表和散列集合
可以使用散列集合來(lái)存儲(chǔ)所有的英語(yǔ)單詞 散列集合只存儲(chǔ)唯一的不重復(fù)的值 散列集合由一個(gè)集合構(gòu)成，但是插入、移除或獲取元素時(shí)，使用的是散列函數(shù)
示例：
// 實(shí)現(xiàn)print的方法
this.print = function() {
for (var i = 0; i < table.length; ++i) { //遍歷數(shù)組中的所有元素
if (table[i] !== undefined) { //當(dāng)某個(gè)位置上有值的時(shí)候
console.log(i + ": " + table[i]);//輸出位置和對(duì)應(yīng)的值
}
}
};
有時(shí)候，一些鍵會(huì)有相同的散列值。不同的值在散列表中對(duì)應(yīng)相同位置的時(shí)候，我們稱其為 沖突。處理沖突有幾種方法：分離鏈接、線性探查和雙散列法
示例說(shuō)明一個(gè)：分離鏈接
分離鏈接法包括為散列表的每一個(gè)位置創(chuàng)建一個(gè)鏈表并將元素存儲(chǔ)在里面。
// 在HashTable類內(nèi)部定義
var ValuePair = function(key, value){
this.key = key;
this.value = value;
this.toString = function() {
return '[' + this.key + ' - ' + this.value + ']';
}
};
put方法
this.put = function(key, value){
var position = loseloseHashCode(key);
if (table[position] == undefined) { //將驗(yàn)證要加入新元素的位置是否已經(jīng)被占據(jù)
table[position] = new LinkedList();
// 會(huì)在這個(gè)位置上初始化一個(gè)LinkedList類的實(shí)例
}
table[position].append(new ValuePair(key, value));
//實(shí)現(xiàn)的append方法向LinkedList實(shí)例中添加一個(gè)ValuePair實(shí)例（鍵和值）
};
get方法
this.get = function(key) {
var position = loseloseHashCode(key);
if (table[position] !== undefined){
//確定在特定的位置上是否有元素存在
//遍歷鏈表來(lái)尋找鍵/值
var current = table[position].getHead(); //獲取鏈表表頭的引用
while(current.next){ //從鏈表的頭部遍歷到尾部
// Node鏈表包含next指針和element屬性
if (current.element.key === key){
//current.element.key來(lái)獲得Node鏈表的key屬性
return current.element.value;
//如果key值相同，就返回Node的值
}
current = current.next; //如果不相同，就繼續(xù)遍歷鏈表，訪問(wèn)下一個(gè)節(jié)點(diǎn)
}
//檢查元素在鏈表第一個(gè)或最后一個(gè)節(jié)點(diǎn)的情況
if (current.element.key === key){
return current.element.value;
}
}
return undefined;
};
WeakMap 類和 WeakSet 類
弱化版本， WeakSet和WeakMapMap和Set與其弱化版本之間，WeakSet或WeakMap類沒(méi)有entries、keys和values等方法只能用對(duì)象作為鍵 除非你知道鍵，否則沒(méi)有辦法取出值
簡(jiǎn)單算法：0001兩數(shù)之和 ??，0020. 有效的括號(hào) ??,0021. 合并兩個(gè)有序鏈表，0026. 刪除排序數(shù)組中的重復(fù)項(xiàng),0053. 最大子序和,0066. 加一
88. 合并兩個(gè)有序數(shù)組
一、題目描述
給你兩個(gè)有序整數(shù)數(shù)組 nums1 和 nums2，請(qǐng)你將 nums2 合并到 nums1 中，使 nums1 成為一個(gè)有序數(shù)組。
初始化 nums1 和 nums2 的元素?cái)?shù)量分別為 m 和 n 。你可以假設(shè) nums1 的空間大小等于 m + n，這樣它就有足夠的空間保存來(lái)自 nums2 的元素。
輸入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
輸出：[1,2,2,3,5,6]
輸入：nums1 = [1], m = 1, nums2 = [], n = 0
輸出：[1]
二、思路分析
其實(shí)這是一個(gè)歸并的過(guò)程，也是歸并排序中最核心的一步。對(duì)于兩個(gè)有序的數(shù)組。我們可以新建一個(gè)數(shù)組temp，大小為（m+n）。使用兩個(gè)指針i和j分別指向nums1和nums2，之后分別比較兩個(gè)指針?biāo)冈氐拇笮?，并把小的那一個(gè)放到temp中即可。待一個(gè)數(shù)組遍歷完之后，只需將剩下的元素放到temp中即可。
標(biāo)簽：從后向前數(shù)組遍歷
因?yàn)?
nums1的空間都集中在后面，所以從后向前處理排序的數(shù)據(jù)會(huì)更好，節(jié)省空間，一邊遍歷一邊將值填充進(jìn)去設(shè)置指針
len1 和 len2分別指向nums1 和 nums2的有數(shù)字尾部，從尾部值開(kāi)始比較遍歷，同時(shí)設(shè)置指針len指向nums1的最末尾，每次遍歷比較值大小之后，則進(jìn)行填充當(dāng)
len1<0時(shí)遍歷結(jié)束，此時(shí)nums2中獲取數(shù)據(jù)未拷貝完全，將其直接拷貝到nums1的前面，最后得到結(jié)果數(shù)組時(shí)間復(fù)雜度：
O(m+n)O(m+n)雙指針
寫(xiě)指針 current， 用于記錄當(dāng)前填補(bǔ)到那個(gè)位置了 m 用于記錄 nums1 數(shù)組處理到哪個(gè)元素了 n 用于記錄 nums2 數(shù)組處理到哪個(gè)元素了
灰色代表 num2 數(shù)組已經(jīng)處理過(guò)的元素 紅色代表當(dāng)前正在進(jìn)行比較的元素 綠色代表已經(jīng)就位的元素
三、答案代碼
/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
let len1 = m - 1;
let len2 = n - 1;
let len = m + n - 1;
while(len1 >= 0 && len2 >= 0) {
// 注意--符號(hào)在后面，表示先進(jìn)行計(jì)算再減1，這種縮寫(xiě)縮短了代碼
nums1[len--] = nums1[len1] > nums2[len2] ? nums1[len1--] : nums2[len2--];
}
function arrayCopy(src, srcIndex, dest, destIndex, length) {
dest.splice(destIndex, length, ...src.slice(srcIndex, srcIndex + length));
}
// 表示將nums2數(shù)組從下標(biāo)0位置開(kāi)始，拷貝到nums1數(shù)組中，從下標(biāo)0位置開(kāi)始，長(zhǎng)度為len2+1
arrayCopy(nums2, 0, nums1, 0, len2 + 1);
};
var merge = function (nums1, m, nums2, n) {
// 設(shè)置一個(gè)指針，指針初始化指向nums1的末尾（根據(jù)#62，應(yīng)該是index為 m+n-1 的位置，因?yàn)閚ums1的長(zhǎng)度有可能更長(zhǎng)）
// 然后不斷左移指針更新元素
let current = m + n - 1;
while (current >= 0) {
// 沒(méi)必要繼續(xù)了
if (n === 0) return;
// 為了方便大家理解，這里代碼有點(diǎn)贅余
if (m < 1) {
nums1[current--] = nums2[--n];
continue;
}
if (n < 1) {
nums1[current--] = nums1[--m];
continue;
}
// 取大的填充 nums1的末尾
// 然后更新 m 或者 n
if (nums1[m - 1] > nums2[n - 1]) {
nums1[current--] = nums1[--m];
} else {
nums1[current--] = nums2[--n];
}
}
};
總結(jié)
合并兩個(gè)有序數(shù)組,字典,散列表
回看筆者往期高贊文章，也許能收獲更多喔！
一個(gè)合格的初級(jí)前端工程師需要掌握的模塊筆記 Vue.js筆試題解決業(yè)務(wù)中常見(jiàn)問(wèn)題 【初級(jí)】個(gè)人分享Vue前端開(kāi)發(fā)教程筆記 長(zhǎng)篇總結(jié)之JavaScript，鞏固前端基礎(chǔ) 前端面試必備ES6全方位總結(jié) 達(dá)達(dá)前端個(gè)人web分享92道JavaScript面試題附加回答 【圖文并茂，點(diǎn)贊收藏哦！】重學(xué)鞏固你的Vuejs知識(shí)體系 【思維導(dǎo)圖】前端開(kāi)發(fā)-鞏固你的JavaScript知識(shí)體系 14期-連肝7個(gè)晚上，總結(jié)了計(jì)算機(jī)網(wǎng)絡(luò)的知識(shí)點(diǎn)！（共66條） 這是我的第一次JavaScript初級(jí)技巧 localStorage和sessionStorage本地存儲(chǔ) HTML5中的拖放功能 挑戰(zhàn)前端知識(shí)點(diǎn)HTTP/ECMAScript 必學(xué)必會(huì)-音頻和視頻 前端170面試題+答案學(xué)習(xí)整理（良心制作） 前端HTML5面試官和應(yīng)試者一問(wèn)一答 哪吒鬧海，席卷圖文學(xué)習(xí)前端Flex布局 騰訊位置服務(wù)開(kāi)發(fā)應(yīng)用 【進(jìn)階】面試官問(wèn)我Chrome瀏覽器的渲染原理（6000字長(zhǎng)文） 面試官一上來(lái)就問(wèn)我Chrome底層原理和HTTP協(xié)議（萬(wàn)字長(zhǎng)文） 熬夜總結(jié)了 “HTML5畫(huà)布” 的知識(shí)點(diǎn) this/call/apply/bind（萬(wàn)字長(zhǎng)文） HTTP/HTTPS/HTTP2/DNS/TCP/經(jīng)典題 執(zhí)行上下文/作用域鏈/閉包/一等公民 Web頁(yè)面制作基礎(chǔ) 學(xué)習(xí)總結(jié)之HTML5劍指前端（建議收藏，圖文并茂）
??關(guān)注+點(diǎn)贊+收藏+評(píng)論+轉(zhuǎn)發(fā)??，原創(chuàng)不易，鼓勵(lì)筆者創(chuàng)作更好的文章
點(diǎn)贊、收藏和評(píng)論
我是Jeskson(達(dá)達(dá)前端)，感謝各位人才的：點(diǎn)贊、收藏和評(píng)論，我們下期見(jiàn)！(如本文內(nèi)容有地方講解有誤，歡迎指出?謝謝，一起學(xué)習(xí)了)
我們下期見(jiàn)！
文章持續(xù)更新，可以微信搜一搜「 程序員哆啦A夢(mèng) 」第一時(shí)間閱讀，回復(fù)【資料】有我準(zhǔn)備的一線大廠資料，本文 http://www.dadaqianduan.cn/#/ 已經(jīng)收錄
github收錄，歡迎Star：https://github.com/webVueBlog/WebFamily