/** * @param {number} index * @return {number} */ MyLinkedList.prototype.get = function (index) { let cur = this for (let i = 0; i <= index; i++) { if (cur.next) { cur = cur.next } else { return -1 } } return cur.val }
/** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function (val) { const newNode = newMyLinkedList() newNode.val = val newNode.next = this.next // 从这一行可以清楚的看出,这是添加虚拟节点的操作方式 this.next = newNode }
/** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function (val) { const newNode = newMyLinkedList() newNode.val = val newNode.next = null let cur = this while (cur.next) { cur = cur.next } cur.next = newNode }
/** * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function (index, val) { const newNode = newMyLinkedList() newNode.val = val let cur = this for (let i = 0; i < index; i++) { if (cur.next) { cur = cur.next } else { return } } newNode.next = cur.next cur.next = newNode }
/** * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function (index) { let cur = this for (let i = 0; i < index; i++) { if (cur.next) { cur = cur.next } else { return } } if (!cur.next) return cur.next = cur.next.next }
/** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
MyLinkedList.prototype.get = function (index) { let cur = this for (let i = 0; i <= index; i++) { if (cur.next) { cur = cur.next } else { return -1 } } return cur.val }
/** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtHead = function (val) { const newNode = newMyLinkedList() newNode.val = val newNode.next = this.next newNode.prev = this this.next = newNode }
/** * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtTail = function (val) { const newNode = newMyLinkedList() newNode.val = val newNode.next = null let cur = this while (cur.next) { cur = cur.next } newNode.prev = cur cur.next = newNode }
/** * @param {number} index * @param {number} val * @return {void} */ MyLinkedList.prototype.addAtIndex = function (index, val) { const newNode = newMyLinkedList() newNode.val = val let cur = this for (let i = 0; i < index; i++) { if (cur.next) { cur = cur.next } else { return } } newNode.next = cur.next newNode.prev = cur cur.next = newNode }
/** * @param {number} index * @return {void} */ MyLinkedList.prototype.deleteAtIndex = function (index) { let cur = this for (let i = 0; i < index; i++) { if (cur.next) { cur = cur.next } else { return } } if (!cur.next) return cur.next.prev = cur cur.next = cur.next.next }
/** * Your MyLinkedList object will be instantiated and called as such: * var obj = new MyLinkedList() * var param_1 = obj.get(index) * obj.addAtHead(val) * obj.addAtTail(val) * obj.addAtIndex(index,val) * obj.deleteAtIndex(index) */
var sortedSquares = function(nums) { // 初始化两个指针 let left =0; let right = nums.length - 1; // 初始化存放结果的数组 let res = newArray(nums.length); // 从后往前依次填满res let point = right while(left <= right){ if(nums[left]**2 > nums[right]**2){ res[point] = nums[left]**2; left++; } else{ res[point] = nums[right]**2; right--; } point-- } return res };
var findSubstring = function(s, words) { let res = [] let wordLen = words[0].length let wordNum = words.length let wordMap = newMap() for (let word of words) { wordMap.set(word, wordMap.has(word) ? wordMap.get(word) + 1 : 1) } // 这里i的设置比较难理解,但是如果理解了后面while中的逻辑,就懂了 // 从i开始,right直接到最后可能的位置,也就是for中的一次遍历可以找到0或多个res,而不是1个 for (let i = 0; i < wordLen; i++){ let left = i let right = i letwindow = newMap() let count = 0 while (right + wordLen <= s.length) { let w = s.slice(right, right + wordLen) right += wordLen if (!wordMap.has(w)) { window.clear() count = 0 left = right } else { window.set(w, window.has(w) ? window.get(w) + 1 : 1) count++ while (window.get(w) > wordMap.get(w)) { let l = s.slice(left, left + wordLen) left += wordLen window.set(l, window.get(l) - 1) count-- } if (count === wordNum) { res.push(left) } } } } return res }
Text
1 2 3 4 5 6 7 8 9 10 11 12 13
这段代码的主要逻辑是使用滑动窗口来遍历字符串 s,并检查每个窗口是否包含 words 中的所有单词。
1、let left = i 和 let right = i:初始化滑动窗口的左右边界。 2、let window = new Map():创建一个哈希映射 window 来存储当前窗口中每个单词出现的次。 3、let count = 0:初始化一个计数器 count 来存储当前窗口中的单词总数。 4、while (right + wordLen <= s.length):当窗口的右边界加上单词的长度不超过字符串 s 的长度时,继续循环。 5、let w = s.slice(right, right + wordLen):获取窗口右边界的单词 w。 6、right += wordLen:将窗口的右边界向右移动一个单词的长度。 7、if (!wordMap.has(w)):如果 w 不在 wordMap 中,那么清空 window,重置 count,并将窗口的左边界移动到 right。 8、else:如果 w 在 wordMap 中,那么更新 window 和 count,并检查 window 中 w 的数量是否超过了 wordMap 中 w 的数量。如果超过了,那么从窗口的左边移除单词,直到 window 中 w 的数量不超过 wordMap 中 w 的数量。 9、if (count === wordNum):如果 count 等于 wordNum,那么将窗口的左边界添加到结果数组 res 中。
这个滑动窗口的策略确保了我们能够有效地遍历字符串 s,并找出所有包含 words 中所有单词的子串的起始索引。