preface
😆 Hi! my name is OFEII, a Front-end Developer rookie……
😅Still 0 offer in this cold 2020 Spring.
😀 amateurs. As a senior front-end rookie, I still have zero offer in 20 spring recruitment (I think there will be two HR interviews next week). I have been brushing LeetCode out of interest. I find it very interesting to brush algorithm with JS and feel the charm of data structure and algorithm. I love JS, I love algorithms, I love the front end.
😅 funny. This week’s LeetCode Week 185 is the “Byte LeetCode Week”, I was trying to reach the top 300 to get a bytedance internal push interview, but I found that I was beaten by various algorithms dalao, but I was too bad, I only did two courses within the set time, now I think it is really funny!
🙂 practice. Although I started late, I have been reviewing the front-end knowledge, checking and filling in the gaps, making up for data structure and algorithm, computer network, brushing problems, brushing Leetcode, writing problem solutions and summarizing in recent months. Practice dragon slaying skills, come on! Read a lot of nuggets on the article, heartfelt thanks nuggets this platform!
😛 dew. After the game, I studied today’s game again, wrote a summary of the solution, and published my first article on the Nuggets. My goal is to write a “front-end JS algorithm – interview written test crash method”! Though it feels far away. Write an article for the first time, have inadequacy place asks everybody dalao many to give directions.
🙏 made vows. Finally, I wish the offer of Shanghai Zhongan Insurance.
Leetcode Week 185-1: 💾reformat reformat
The title
You are given a string s that is a mixture of numbers and letters, all of which are lowercase.
You can reformat the string so that any two adjacent characters have different types. That is, letters should be followed by numbers, while numbers should be followed by letters.
Return the reformatted string. If it cannot be reformatted as required, an empty string is returned.
Specific topics and examples 🌰
💡
A splicing method 💾
- Create two arrays A1, A2 to store numbers and letters, and RES to store results
- Walk through it once, sorting numbers and letters with number.isFinite () (regular is ok)
- Concatenated string array: ① len2(letter) > len1(number) first letter ② vice versa, number first
- (1) Len1,len2 are both less than 0; (2) len1, the difference between len2 is greater than 1
Code 📃
//
let reformat = (s) = > {
let arr = s.split(' '), n = arr.length
let nArr = arr.map(e= >+e)
let a1 = [], a2 =[], res=[]
for(let i = 0; i < n; i++){
Number.isFinite(nArr[i]) ? a1.push(nArr[i]) : a2.push(arr[i])
}
let l1 =a1.length,l2 =a2.length
for (let i = 0; i < n; i++) {
l2 > l1 ? res.push(a2[i],a1[i]) : res.push(a1[i],a2[i])
}
return ((l1 <=0 && l2<=0) | |Math.abs(l1-l2)>1)? "" : res.slice(0, n).join(' ')
};
Copy the codeLeetcode week 185-2: 🍣displayTable a la carte displayTable
The title
Give you the orders an array, said clients completed orders in the restaurant, specifically, the orders [I] = [customerNamei tableNumberi, foodItemi], including customerNamei is the customer’s name, TableNumberi is the table number of the customer’s table, and foodItemi is the name of the meal the customer ordered.
Please return to the menu of the restaurant. In this Table, the first column in the Table is the title, the first column is the Table number “Table”, and each column is the name of the food in alphabetical order. The items in the next row represent the number of food ordered for each table. The first column should be filled with the corresponding table number, followed by the number of food ordered.
Note: Customer names are not part of the order sheet. In addition, rows of data in the table should be arranged in ascending order by table number.
Specific topics and examples 🌰
💡
I. Hash method 🍣
- Create a table(map) to store the number of dishes at each table, a Foods (set) to store the types of dishes (foods) on the menu, and res to store the results
- Iterate through the Orders array –> general operation –> get
- Table: table number of each table (key) –> [Type of dishes on each table (key) –> and corresponding quantity (value)] (value) Is essentially a map nested map
- Foods: Types of foods that are de-weighted
- Res passes the title ‘Table’+ sorted foods (with the extension operator… Convert set to array)
- Iterate through each table of the table, item exists, pass in quantity, otherwise pass in 0, notice that this is converted to STR. In each iteration, the table number and order quantity of each table are passed into an array temp, which is then passed to RES.
- Sort (a,b)=>a[0]-b[0] sort(a,b)=>a[0]-b[0]
Code 📃
// Hash method
let displayTable = (orders) = > {
let table = new Map(), foods = new Set(), res = []
for(let [a, b, c] of orders){ //a:name b:table c: food ordered
foods.add(c)
if(table.has(b)){
let map = table.get(b)
table.set(b, map.set(c, map.has(c) ? map.get(c)+1 : 1))
}else{
let map = new Map(a)
table.set(b, map.set(c, 1))
}
}
let menu = [...foods].sort()
res.push(['Table'. menu])
for(let [t, o] of table){ // t:tableId o: all ordered food in tableId
let temp = []
for(let n of menu){
temp.push(o.has(n) ? ' ' + o.get(n) : '0')
}
res.push([t,...temp])
}
return res.sort((a,b) = >a[0]-b[0])
};
Copy the codeLeetcode Week 185-3: 🐸minNumberOfFrogs Count frogs
The title
You are given the string croakOfFrogs, which represents a combination of croaks made by different frogs (the string “croak”). Since more than one frog can croak at a time, croakOfFrogs are mixed with multiple croaks. Return the minimum number of different frogs required to simulate all the frogs in the string.
Note: To make the frog’s croak, the frog must produce the letters’ C ‘, ‘r’, ‘O’, ‘A’, and ‘k’ in sequence. If all five letters are not printed, then it will not make a sound.
If the string croakOfFrogs is not a mixture of several valid “croak” characters, return -1.
Specific topics and examples 🌰
💡
One, counting method 🐸
- Iterating over the string, counting c R O A K, and returning -1 if there are other characters
- The valid combination condition is C –> R –> O –> A –> K, otherwise -1 is returned
- Minimum number of different frogs required for all croaks CNT –> maximum number of simultaneous c– > CNT = math.max (CNT, c)
- Judge the value of k, if k==1, a frog’s croak ends, c, R, O, a, k are reduced by 1
- After traversal, return -1 if there is extra c, R, O, a, k
Code 📃
// 1
let minNumberOfFrogs = (croakOfFrogs) = > {
let c=0, r=0, o=0, a=0, k=0, cnt=0
for(let x of croakOfFrogs){
if(x=='c') c++
else if(x=='r') r++
else if(x == 'o') o ++
else if(x == 'a') a ++
else if(x == 'k') k ++
else return - 1
if(r>c || o>r || a>o || k>a) return - 1
cnt = Math.max(c, cnt)
if(k==1) {
c--
r--
o--
a--
k--
}
}
return (c || r || o || a || k)? - 1 : cnt
};
Copy the codeLeetcode Week 185-4: 🍨numOfArrays generate arrays
The title
You are given three integers n, m and k. The algorithm described below is used to find the largest element in an array of positive integers.
Generate an array arr with the following properties:
- Arr has n integers.
- 1 <= arr[I] <= m where (0 <= I < n).
- Applying the algorithm mentioned above to ARR, the value of search_cost is equal to k.
Returns the number of ways to generate array arr under the above conditions. Since the answer may be large, mod 10^9 + 7 is required
Specific topics and examples 🌰
💡
1. 3D DP 🍨
Dp status definition: dp[I][j][k] represents the first I element, the maximum value is J, and search_cost is the number of schemes of K.
Dp transfer equation: for 1<= x <= m+1, there are two different cases:
-
J < x <= m, dp[I + 1][x][k + 1] += dp[I][j][k]
-
When 1 <= x <= j, dp[I + 1][J][k] += DP [I][j][k]
(Mod 1e9+7 after each dp)
Spatial complexity: 3D DP O(NMK)
Time complexity: O(NMKM)
Code 📃
// 3d dp
let numOfArrays = (n, m, k) = > {
let dp = new Array(n+1).fill(0).map((a)= >new Array(m+1).fill(0).map((a)= >new Array(k+1).fill(0)))
let mod = 1e9+7, res = 0
dp[0] [0] [0] = 1
for(let i = 0; i < n; i++)
for(let j = 0; j <= m; j++)
for(let k = 0; k <= i; k++)
for(let x = 1; x <= m; x++){
if(x > j){
dp[i + 1][x][k + 1] += dp[i][j][k]
dp[i + 1][x][k + 1] %= mod
}
else {
dp[i + 1][j][k] += dp[i][j][k]
dp[i + 1][j][k] %= mod
}
}
for(let i=1; i<=m; i++){
res += dp[n][i][k]
res %= mod
}
return res
};
Copy the codeThis article is formatted using MDNICE