Source: making power button (LeetCode) | | to brush the topic card for stars ✨ | give a ❤ ️ attention, ❤ ️ thumb up, ❤ ️ encourages the author

[Opened] Task 1: Brush the question punch card * 10

Nezha’s life creed: If you like what you learn, there will be strong motivation to support it.

Learn programming every day, so that you can get a step away from your dream. Thank you for not living up to every programmer who loves programming. No matter how strange the knowledge point is, work with me to calm down the wandering heart and keep going. Welcome to follow me vx:xiaoda0423, welcome to like, favorites and comments

Time: March 1 ~ March 13

  • Force buckle (LeetCode)- Sum of two numbers, valid parentheses, sum of two numbers | brush questions punch card – March 1
  • LeetCode – Merges two ordered lists, removes duplicates in sorted arrays,JavaScript Notes | Flash cards – March 2
  • Force Button (LeetCode)- Maximum suborder sum,JavaScript Data Structures and Algorithms (Arrays) | Brush questions punched -3 March
  • Say something about CSS | Tech Review – March 4
  • Force Buckle (LeetCode)- Stack, parenthesis generation | brush questions punch card – 5 March
  • It wasn’t that hard! Vue mall development | technical review – on March 6
  • Force buckle (LeetCode)- Plus one, queue | brush questions punch – 7 March
  • JavaScript data structure of the chain table | technical review – March 8
  • JavaScript Data Structures – Collections | Technical Review – March 9

preface

If this article is helpful to you, give ❤️ a follow, ❤️ like, ❤️ encourage the author, accept the challenge? Article public account launch, concern programmer Doraemon first time access to the latest article

❤ ️ cartridge ❤ ️ ~

Stack, queue, linked list, set

Dictionaries and hash tables

  • Collections, dictionaries, and hash tables can store values that are not duplicated
  • In the dictionary, use[key, value]Store data in the form of
  • In the hash table[key, value]To store data in pairs
  • Dictionary keys are used to query for specific elements
  • Examples of dictionary data structures, an actual dictionary, and an address book

Create a dictionary

function Dictionary() {
 var items = {};
}
Copy the code

Methods used:

  • set(key,value)Add a new element to the dictionary
  • delete(key)Removes the data value corresponding to the key value from the dictionary by using the key value
  • has(key), returns true if a key exists in the dictionary, false otherwise
  • get(key)To find a specific value by key value and return it
  • clear()Delete all the elements in the dictionary
  • size(), returns the number of elements contained in the dictionary
  • keys()Returns all the key names contained in the dictionary as an array
  • values()Returns all values contained in the dictionary as an array

Has and set methods

Example:

this.has = function(key) { return key in items; ) ;Copy the code

Set method implementation:

This. set = function(key, value) {items[key] = value; };Copy the code

The delete method

Use JavaScript’s remove operator to remove the key property from the Items object

this.delete= function(key) { 
 if (this.has(key)) { 
 delete items[key]; 
 return true; 
 } 
 return false; 
};
Copy the code

Get and values methods

Looks up a particular item in the dictionary and retrieves its value

This. get = function(key) {return this.has(key)? items[key] : undefined; };Copy the code

Returns the values of all values instances in the dictionary as an array

this.values = function() { var values = []; For (var k in items) {if (this.has(k)) {// Use the has function to verify that the key does exist values.push(items[k]); // add its value to values array}} return values; };Copy the code

The clear, the size, keys, getItems method

Example:

this.keys = function() { 
 return Object.keys(items); 
};
Copy the code
this.getItems = function() { 
 return items; 
}
Copy the code

Use the Dictionary class

Implement an email address book:

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');
Copy the code

Hash table

  • HashTableClass (HashMapClass), which isDictionaryClass a hash table implementation
  • If you use a hash function, you know exactly where the value is, so you can quickly retrieve it
  • The hash function gives a key value and returns the address of the value in the table

Creating a hash table

Function HashTable() {var table = []; }Copy the code
  • put(key,value)To add a new item to the hash table
  • remove(key)Removes a value from the hash table based on the key value
  • get(key)Returns a specific value retrieved based on the key value

Example:

Var loseloseHashCode = function (key) {// Given a key argument, // We need a variable to store the sum. Var hash = 0; for (var i = 0; i < key.length; I ++) {// Iterate over key hash += key.charcodeat (I); } return hash % 37; // To get a smaller number, we'll use the hash value and an arbitrary remainder of the division};Copy the code

Implement the PUT method

this.put = function(key, value) { var position = loseloseHashCode(key); Console. log(position + '-' + key); // Calculate its position in the table based on the hash function created. table[position] = value; // Add the value argument to the corresponding position calculated by the hash function};Copy the code

Implement a GET method

Get = function (key) {return table[loseloseHashCode(key)]; return table[loseloseHashCode(key)]; };Copy the code

Implement a remove method

This. remove = function(key) {table[loseloseHashCode(key)] = undefined; };Copy the code

Hash tables and hash sets

  • You can use hash collections to store all English words
  • Hash sets store only unique, non-repeating values
  • A hash set consists of a collection, but when elements are inserted, removed, or retrieved, the hash function is used

Example:

This. print = function() {for (var I = 0; i < table.length; ++ I) {if (table[I]! Console. log(I + ": "+ table[I]); == undefined) {console.log(I + ":" + table[I]); // Output position and corresponding value}}};Copy the code

Sometimes, some keys will have the same hash value. When different values correspond to the same position in a hash table, we call it a conflict. There are several ways to handle collisions: split chaining, linear probing, and double hashing

Example one: separate links

The split chaining method involves creating a linked list for each position in the hash table and storing the elements in it.

Var ValuePair = function(key, value){this.key = key; this.value = value; this.toString = function() { return '[' + this.key + ' - ' + this.value + ']'; }};Copy the code

Put method

this.put = function(key, value){ var position = loseloseHashCode(key); If (table[position] == undefined) {table[position] = new LinkedList(); } table[position]. Append (new ValuePair(key, value)); // The implemented append method adds a ValuePair instance (key and value) to the LinkedList instance};Copy the code

The get method

this.get = function(key) { var position = loseloseHashCode(key); if (table[position] ! == undefined){var current = table[position].gethead (); While (current-element.key === key){if (current-element.key === key){if (current-element.key == key){ Return current. Element. value; //current. } current = current. Next; If (current.element.key === key){return current.element.value; } } return undefined; };Copy the code

WeakMap class and WeakSet class

  • Weakened version,WeakSet and WeakMap
  • The Map and SetBetween its weakened version,The WeakSet or WeakMap class has no entries, keys, and valuesMethods such as
  • You can only use objects as keys
  • There’s no way to extract the value unless you know the key

Simple algorithm: 0001 Sum of two numbers 👍, 0020. Valid parentheses 👍,0021. Merge two ordered lists, 0026. Delete duplicates from sorted array,0053. Maximum suborder sum,0066 plus one

88. Merge two ordered arrays

1. Title Description

Merge nums2 into nums1 to make nums1 an ordered array.

Initialize nums1 and nums2 to m and n, respectively. You can assume that nums1 has a space size equal to m + n so that it has enough space to hold elements from Nums2.

Input: nums1 =,2,3,0,0,0 [1], m = 3, nums2 = [6] 2, n = 3 output: input,2,2,3,5,6 [1] : nums1 = [1], m = 1, nums2 = [], n = 0 output: [1]Copy the code

Second, train of thought analysis

This is actually a merge process, and it’s the most important step in merge sort. For two ordered arrays. We can create an array temp of size (m+n). Use two Pointers I and j to point to nums1 and nums2 respectively. Then compare the size of the two Pointers and place the smaller one in temp. Once the array is iterated through, you simply place the remaining elements into Temp.

  • Tag: Traverses the array from back to front

  • Because NUMs1’s space is concentrated in the back, it’s better to process sorted data from back to front, saving space and filling in values as you traverse

  • Set pointer len1 and len2 to point to nums1 and nums2, respectively, and start the comparison traversal from the tail value. At the same time, set pointer len to point to the end of nums1. After each traversal, the comparison value will be filled

  • When Len1 <0, the traversal ends, at this time, the data obtained in NUMs2 is not completely copied, it is directly copied before NUMs1, and the result array is finally obtained

  • Time complexity: O(m+n)O(m+n)

  • Double pointer

  1. Write pointer current, used to record the current fill to that position
  2. M is used to record which element nums1 is processed to
  3. N is used to record which element nums2 array is processed to
  • Gray represents the num2 array elements that have been processed
  • Red represents the element that is currently being compared
  • Green represents elements that are already in place

Answer code

/** * @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) {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)); Len2 +1 arrayCopy(nums2, 0, nums1, 0, len2+1); };Copy the code
Var merge = function (nums1, m, nums2, n) {var merge = function (nums1, m, n) {var merge = function (nums1, m, n) {var merge = function (nums1, m, n) { Let current = m + n-1; let current = m + n-1; While (current >= 0) {if (n == 0) return; If (m < 1) {nums1[current--] = nums2[--n]; continue; } if (n < 1) { nums1[current--] = nums1[--m]; continue; } if (nums1[m-1] > nums2[n-1]) {nums1[current--] = nums1[--m]; } else { nums1[current--] = nums2[--n]; }}};Copy the code

conclusion

Merges two ordered arrays, dictionaries, and hash tables

Go back to my previous articles and you may get more!

  • A qualified junior front-end engineer needs to master module notes
  • Vue.js pen test questions Solve common business problems
  • [Primary] Personally share notes of Vue front-end development tutorial
  • A long summary of JavaScript to consolidate the front end foundation
  • ES6 comprehensive summary
  • Dada front-end personal Web share 92 JavaScript interview questions with additional answers
  • [Illustrated, like collection oh!] Re-study to reinforce your Vuejs knowledge
  • 【 Mind Mapping 】 Front-end development – consolidate your JavaScript knowledge
  • 14 – even liver 7 nights, summed up the computer network knowledge point! (66 items in total)
  • This was my first JavaScript primer
  • LocalStorage and sessionStorage localStorage
  • Drag and drop in HTML5
  • Challenge the front-end HTTP/ECMAScript
  • Must learn must learn – Audio and video
  • 170 Interview questions + answer Learn to organize (conscience making)
  • Front-end HTML5 interviewers and candidates ask and answer questions
  • Ne Zha is sweeping the sea
  • Tencent location service development applications
  • [Advanced] The interviewer asked me how Chrome renders (6000 words)
  • The interviewer started by asking me about Chrome’s underlying principles and HTTP protocol (swastika)
  • Staying up late summed up the “HTML5 Canvas”
  • This /call/apply/bind
  • The HTTP/HTTPS/HTTP2 / DNS/TCP/classic problem
  • Execute context/scope chain/closure/first-class citizen
  • Web page creation basics
  • Learn the summary of HTML5 finger front-end (suggested collection, illustrated)

❤️ follow + like + favorites + comments + forward ❤️, original is not easy, encourage the author to create better articles

Likes, favorites and comments

I’m Jeskson, thanks for your talent: likes, favorites and comments, and we’ll see you next time! ☞ Thank you for learning with me.

See you next time!

This article is constantly updated. You can search “Programmer Doraemon” on wechat to read it for the first time, and reply [information] there are materials of first-line big factories prepared by me, which have been included in this article www.dadaqianduan.cn/#/

Star: github.com/webVueBlog/…

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign