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

Hello everyone, I’m Nezha. Nice to meet you ~~

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

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 ❤ ️ ~

The stack

A stack is a last-in, first-out ordered collection. New elements added or to be removed are stored at the same end of the stack, called the top, and the other end is called the bottom.

Create a stack

Create a class to represent the Stack :(how to use the Stack class)

Function Stack() {// various attributes and methods declaration}Copy the code

Declare an array to hold elements in the stack:

let items = []
Copy the code
  • push()To add one or more new elements to the top of the stack
  • pop(), removes the top element of the stack, and returns the removed element
  • peek()Returns the element at the top of the stack without making any changes to the stack
  • isEmpty(), return true if there are no elements in the stack, false otherwise
  • clear()Remove all elements from the stack
  • size(), returns the number of elements in the stack

Add elements to the stack (add new elements to the stack)

Example:

This.push = function(element) {items.push(element); });Copy the code

Removing elements from the stack (removing the last element added)

Example:

this.pop = function() {
 return items.pop();
};
Copy the code

Look at the top of the stack (used to find the last element added to the stack)

For example, return the element at the top of the stack:

this.peek = function() {
 return items[items.length-1];
};
Copy the code

Check whether the stack is empty

Returns true if the stack is empty, false otherwise.

Example:

this.isEmpty = function() {
 return items.length == 0;
};
Copy the code

Return stack length:

this.size = function() {
 return items.length;
};
Copy the code

Empty and print stack elements

The clear method is used to remove all elements from the stack.

this.clear = function() {
 items = [];
};
Copy the code

Print all the elements in the stack:

this.print = function() {
 console.log(item.toString());
};
Copy the code

Use the Stack class

Initialize the Stack class:

let stack = new Stack(); console.log(stack.isEmpty()); // The output is trueCopy the code

Add some elements to the stack

stack.push(1); 
stack.push(2);
Copy the code

If the peek method is called, it prints 2

console.log(stack.peek()); 2 / / outputCopy the code

How to declare the Stack class with ES6

Code:

// Declare in the class constructor that ES6 classes are prototype-based. class Stack { constructor() { this.items = []; } push(element) { this.items.push(element); }}Copy the code

Prototype-based analogies to function-based classes save more memory and are better for creating multiple instances, but they cannot declare private properties or methods.

  • withES6Is scopedSymbolThe implementation class

ES6 adds a basic type called Symbol, which is immutable and can be used as an attribute of an object.

Example:

// declare the variable _items of type Symbol and initialize its value in the constructor function let _items = Symbol(); class Stack { constructor() { this[_items] = []; }}Copy the code

New Object. Use ES6 getOwnPropertySymbols method can take all the Symbols attribute to the class declaration.

let stack = new Stack(); stack.push(2); stack.push(3); let objectSymbols = Object.getOwnPropertySymbols(stack); console.log(objectSymbols.length); // 1 console.log(objectSymbols); // [Symbol()] array Symbols property console.log(objectSymbols[0]); // Symbol() stack[objectSymbols[0]].push(1); stack.print(); // Output 2, 3, 1Copy the code

Access stack[objectSymbols[0]] to get _items. The _items property is an array and can be used for any array operations. So you shouldn’t use this method.

  • ES6In theWeakMapThe implementation class

Properties are ensured to be private using WeakMap, which stores key-value pairs where keys are objects and values can be arbitrary data types.

Example:

Const items = new WeakMap(); // Declare a WeakMap type variable items const items = new WeakMap(); Class Stack {constructor () {constructor () {// From constructor, store the array representing the Stack into items items.set(this, []); } push(element) {// Retrieve value from WeakMap, i.e. value from items with this key let s = items.get(this); s.push(element); } pop() { let s = items.get(this); let r = s.pop(); return r; } // Other methods}Copy the code

Itmes are really all properties in the Stack class now.

Using closures:

Let Stack = (function () {const items = new WeakMap(); const items = new WeakMap(); class Stack { constructor () { items.set(this, []); } return Stack; // When called, returns an instance of the Stack class})(); // With this approach, extension classes cannot inherit private attributesCopy the code

Decimal to binary problem algorithm

Example:

function divideBy2(decNumber){ var remStack = new Stack(), rem, binaryString = ''; while (decNumber > 0){ rem = Math.floor(decNumber % 2); remStack.push(rem); decNumber = Math.floor(decNumber / 2); } while (! remStack.isEmpty()){ binaryString += remStack.pop().toString(); } return binaryString; }Copy the code

Convert decimal to any base

Example:

function baseConverter(decNumber, base){ var remStack = new Stack(), rem, baseString = '', // digits digits = '0123456789ABCDEF'; While (decNumber > 0){rem = math.floor (decNumber % base); remStack.push(rem); decNumber = Math.floor(decNumber / base); } while (! remStack.isEmpty()){ baseString += digits[remStack.pop()]; } return baseString; }Copy the code

The sum of two Numbers

Answer:

  • Violence law
  • Hash table method

Sample pseudocode:

func(nums,target) -> [] result = []; For I in [0, len(nums)]; For j in [I +1, len(nums)]; Sum = nums[I]+nums[j]; if sm == target; result[0] = i result[1] = j result resultCopy the code

Pseudo code:

func(nums, target) -> []; result = [] map = HashTable() for i in [0, len(nums)]; map.add(nums[i], i); for j in [0, len(nums)]; diff = target - nums[j] if(map.containskey(diff) and map.get(diff) ! = j) result[0] = j result[1] = map.get(diff) return resultCopy the code

The two together

  • Iterative method
  • The recursive method

Pseudo code:

Func (l1, l2) -> Listnode total = 0 next1 = 0 = null and l2 ! = null); total = l1.val + l2.vale + next1 cur.next = ListNode(total%10) next1 = total / 10 l1 = l1.next l2 = l2.next cur = cur.next while l1 ! = null total = l1.val + next1 cur.next = ListNode(total%10) nextl = total / 10 l1 = l1.next cur = cur.next while l2 ! = null total = l2.val + next1 cur.next = ListNode(total%10) next1 = total / 10 l2 = l2.next cur = cur.next if next1 ! = 0 cur.next = ListNode(next1) return reult.nextCopy the code

Recursive method:

Pseudo code:

func (l1, l2) -> ListNode total = l1.val + l2.val next1 = total / 10 res = ListNode(total % 10) if( l1.next ! = null or l2.next ! = null or next1 ! = 0 ) if(l1.next ! = null) l1 = l1.next else l2 = ListNode(0) if(l2.next ! = null) l2 = l2.next else l2 = ListNode(0) l1.val = l1.val + next1 res.next = fun(l1,l2) return resCopy the code

Valid parentheses

Stack solution:

var isValid = function (s) { let valid = true; const stack = []; const mapper = { "{": "}", "[": "]", "(": ")", }; for (let i in s) { const v = s[i]; if (["(", "[", "{"].indexOf(v) > -1) { stack.push(v); } else { const peak = stack.pop(); if (v ! == mapper[peak]) { return false; } } } if (stack.length > 0) return false; return valid; };Copy the code

Merges two ordered lists

  • Iterative method
  • The recursive method

/** * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */ const mergeTwoLists = function (l1, l2) { if (l1 === null) { return l2; } if (l2 === null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; } else { l2.next = mergeTwoLists(l1, l2.next); return l2; }};Copy the code

22. Parenthesis generation

1. Title Description

The number n represents the logarithm of parentheses generated. Design a function that generates all possible and valid parentheses combinations.

Example 1: input: n = 3 output: [" ((())) ", "() () ()", "() () ()", "() () ()", "() () ()"] example 2: input: n = 1 output: [" () "] hint: 1 < = n < = 8Copy the code

Second, train of thought analysis

  • backtracking

Pseudo code:

Fun (n) -> [] result = [] backtracking(n,result,0,0, "") return result backtracking(n,result,left,right,str) -> void if right > left return if left == right == n result.add(str) return if left<n backtracking(n,result,left+1,right,str+"(") if right<left backtracking(n,result,left,right+1,str+")")Copy the code

Answer code

Example:

/** * @param {number} n * @return {string[]} * @param l left parentheses are used * @param r right parentheses are used * @param STR is the result of the current recursion */ const generateParenthesis = function (n) {const res = []; function dfs(l, r, str) { if (l == n && r == n) { return res.push(str); } if (l < r) {return; } // if (l < n) {DFS (l + 1, r, STR + "("); } / / r < l Can be inserted right parenthesis if (r (l) {DFS (l, r + 1, STR + ") "); } } dfs(0, 0, ""); return res; };Copy the code

Four,

Stack, parenthesis generation analysis

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)

❤️ 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