preface
Today is the third day of my hard steel algorithm, my foundation is really poor. The article focuses on the record summary, I am also curious about how long I will insist, I only in the form of writing an article to record the question brush every day to keep a positive attitude, or every time to see a while lazy ðŸ˜. Only when I see your feedback can I continue to stick to it!
Past articles:
# 👨💻 First day of learning algorithms from scratch ~ (binary search, double pointer, add two numbers, longest loop substring)
# 👨💻 Second day of learning algorithms from scratch ~ (longest public prefix, valid parentheses, moving zero)
Brush the topic
Delete the NTH node from the list
This problem I think to my promotion is very big, especially for the fast and slow pointer and linked list of some operations are helpful.
The difficulty of deleting the NTH node from a linked list is that the structure of the list cannot be directly indexed, unlike an array, and we do not know the length of the list.
The simplest solution is to go through the list once to get the length of the list, and then find the NTH to the last node based on the length and return it out. But using a fast or slow pointer method, we don’t need to know the length of the list to solve the problem.
Define two Pointers, let the first pointer run N steps, the other pointer does not move, and then walk through the list. When the first pointer runs N steps to the end of the list, the last pointer soon happens to be the NTH node from the bottom
var removeNthFromEnd = function(head, n) {
let fast,slow
fast = slow = head
while(n--){
fast = fast.next
}
if(! fast){return head.next
}
while(fast.next){
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return head
};
Copy the code3. The oldest string without repeating characters
The solution to this problem is to continuously judge whether the value of the substring in the window is repeated through a sliding window. If there is no repetition, enlarge the window; if there is repetition, move the window. That may seem abstract. You can order this link watching animations www.bilibili.com/video/BV14Q… Especially vivid and intuitive
/ * * *@param {string} s
* @return {number}* /
var lengthOfLongestSubstring = function(s) {
if(! s.length){return 0
}
let left=0,right=1
let maxLength = 0
while(right<=s.length){
const nowStr = s.substring(left,right)
const index = nowStr.indexOf(s[right])
if(index ! = = -1){
left += index+1
}
maxLength = Math.max(maxLength,nowStr.length)
right ++
}
return maxLength
};
Copy the codeThis problem really tortured me so much today. From the first time I submitted the code, I could pass almost half of the test cases. It took me a long time to pass the test, but I didn’t look at the problem and insisted on solving it by myself.
567. Permutation of strings
This one I was trying to figure out by myself, because you don’t have to worry about sorting, you just have to worry about what value there is and how many times that value occurs, so I chose to use a map, which is an object that iterates through a short string and stores it, so we know what characters there are and how many times they occur.
Then we iterate over the long string, where I fixed a range of short string lengths, and each time we determine whether the truncated string is the same as the short string map if converted to a map. We can use json.stringify to compare JSON strings. We can use json.stringify to compare JSON strings. But this wastes a lot of performance.
Therefore, I adopted a loan-to-repay strategy. The value in the map of the short string is the borrowed money, and when we iterate over the truncated string, it is a loan-to-repay operation. When we iterate over the same property, we reduce its value by one, simulating a loan-to-repay process. If it is zero, delete it, and finally determine whether the number of attributes of the object is 0. If it is 0, it indicates that the money is paid back.
/ * * *@param {string} s1
* @param {string} s2
* @return {boolean}* /
var checkInclusion = function(s1, s2) {
if(s1.length>s2.length){
return false
}
const map = {}
for(let item of s1){
if(map[item]){
map[item]++
}
else{
map[item] = 1}}let left = 0
let right = s1.length
while(right <= s2.length){
lettempMap = {... map}const curStr = s2.substring(left,right)
for(let item of curStr){
if(tempMap[item]>1){
tempMap[item] -=1
}
else if(tempMap[item]===1) {delete tempMap[item]
}
}
if(!Object.keys(tempMap).length){
return true
}
right++
left++
}
return false
};
Copy the codeThe way I wrote it didn’t perform very well, so I looked at the optimal solution.
So let me show you the optimal solution, which I didn’t write, but I looked at it and realized that the idea is pretty much the same as mine. But instead of using a map to store the money owed, the optimal solution uses an array of numbers with a length of 26. The index corresponds to the position of 26 letters, and the value is the number of occurrences of a certain letter, followed by a process of traversing the return of the money.
var checkInclusion = function(s1, s2) {
// A custom method to compare the data in a sliding window with the target data
function equal(a,b){
for(let i =0; i<a.length; i++){if(a[i]! ==b[i])return false
}
return true
}
let arrP=new Array(26).fill(0),
arr=new Array(26).fill(0)
// Put the target data into an array, which is then used to compare with the sliding window
for(let i =0; i<s1.length; i++) arrP[s1.charCodeAt(i)-'a'.charCodeAt()]++
// Iterate over the entire string, using a sliding window inside the string
for(let i =0; i<s2.length; i++){// Create a sliding window array. The sliding window array should be the same length as the target array
arr[s2.charCodeAt(i)-'a'.charCodeAt()]++
console.log(s2.charCodeAt(i))
// Do nothing until the sliding window is created
if(i>=s1.length-1) {
// Immediately after the slider is created, it starts to compare with the target window, and returns true if the comparison is consistent
if(equal(arr,arrP)) return true
else{
// If the comparison is inconsistent, the sliding window slides to the right, the leftmost character exits the window, and enters the next cycle. In the next cycle, the first character outside the window to the right will be put into the window
arr[s2.charCodeAt(i-s1.length+1) -'a'.charCodeAt()]--
}
}
}
// If no matching data is found, false is returned
return false
};
Copy the codeThe charCodeAt method is used to return Unicode for the first character of a string. This step helps convert letters to numbers for storage.
We can see a lot of XXX – ‘a’.charcodeat () operations, this step is actually assuming that our a-z represents 10-35, so we want a-z to represent 0-25 we just need to subtract 10 from each value. Here ‘a’.charcodeat () is converted to a number that you can read as the value of 10, just to make it easier to use as an array index
conclusion
I have been working so hard these days that I have less time to brush the questions and the difficulty of the questions is gradually increasing. I have been trying every question for a long time ha ha ha. But overall there has been a lot of progress in thinking, it’s only been three days ~ keep up the good work!