【当前排名59118】挑战leetcode进入前1w名

王一之

ggnb 多少名了

李恒道

王一之 发表于 2024-5-2 16:34
ggnb 多少名了

还没名次，貌似要打到几百题才有10w名以内

李恒道

没想出来思路
双指针单调性问题
但是单调性太难证了...
最后看了一下题解
巧妙

/**
 * @param {number[]} height
 * @Return {number}
 */
var maxArea = function (height) {
    let l = 0
    let r = height.length - 1;
    const calcCapacity = () => {
        return (r - l) * Math.min(height[l], height[r])
    }
    let result = calcCapacity()
    while (r >= l) {
        let isSet = false
        if (height[r] < height[l]) {
            // r移动
            for (let index = r - 1; index > l; index--) {
                if (height[index] > height[r]) {
                    r = index
                    isSet = true
                    break;
                }
            }

        } else {
            // 大于等于，l移动
            for (let index = l + 1; index < r; index++) {
                if (height[index] > height[l]) {
                    l = index
                    isSet = true
                    break;
                }
            }
        }
        if(!isSet){
            break;
        }
        result = Math.max(result, calcCapacity())
    }
    return result
};

//  2 1  3  1 3 2

console.log(maxArea([1, 8, 6, 2, 5, 4, 8, 3, 7]))

李恒道

https://leetcode.cn/problems/3sum/?envType=study-plan-v2&envId=top-100-liked

这道题也没凹出来
看的答案都卡了好久
核心思路是排序之后
利用a<b<c的双指针做处理
但是还不允许重复
这里只需要控制a和b跳就可以了
c因为在b相等时候构成，而b不等于之前的值
则a+b+c一定会超过0，所以只控制a，b不等即可

var threeSum = function (nums) {
    nums = nums.sort((a,b)=>a-b)
    const result = []
    for (let index = 0; index < nums.length; index++) {
        const a = nums[index];
        if (nums[index - 1] == a) {
            continue;
        }

        let indey = index + 1;
        let indez = nums.length - 1
        while (indey < nums.length && indez != index && indey < indez) {
            const b = nums[indey]
            if (nums[indey - 1] == b&&indey - 1!=index) {
                indey++;
                continue;
            }
            const c = nums[indez]
            const num = a + b + c
            if (num === 0) {
                result.push([a, b, c])
                indey++;
                indez--;
            } else if (num < 0) {
                indey++;
            } else {
                indez--;
            }
        }
    }
    return result
};

李恒道

https://leetcode.cn/problems/trapping-rain-water/solutions/692342/jie-yu-shui-by-leetcode-solution-tuvc/?envType=study-plan-v2&envId=top-100-liked
双指针问题
但是我个人不喜欢这道
官方题解是两个人互相攻擂，挑较小的继续算
left一定小于等于leftIndex
这个时候右方一定存在一个大于或等于的才可以计算
所以可以确保结果

实际上感觉比较抽象
我更喜欢对比右边界而不是right的算法

var trap = function (height) {
    let leftIndex = 0
    let rightIndex = height.length - 1
    let left = leftIndex 
    let right = rightIndex 
    let total = 0
    while (left <= right) {
        if (height[left] >= height[leftIndex]) {
            leftIndex = left
        }
        if (height[right] >= height[rightIndex]) {
            rightIndex = right
        }
        if (height[left]<height[rightIndex] ) {
            total += Math.min(height[leftIndex], height[rightIndex]) - height[left]
            left++
        } else if(height[right]<height[leftIndex] ) {
            total += Math.min(height[leftIndex], height[rightIndex]) - height[right]
            right--
        }else{
            left++
        }
    }
    return total
};

李恒道

https://leetcode.cn/problems/longest-substring-without-repeating-characters/?envType=study-plan-v2&envId=top-100-liked
简单滑窗题

var lengthOfLongestSubstring = function (s) {
    if(s.length==0){
        return 0
    }
    let left = 0, right = 0;
    let max = 1;
    const charSet = new Set()
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        while (charSet.has(char)) {
            charSet.delete(s[left])
            left++
        }
        charSet.add(char)
        right++;
        max = Math.max(max, right - left )
    }
    return max
};

李恒道

https://leetcode.cn/problems/find-all-anagrams-in-a-string/solutions/1123971/zhao-dao-zi-fu-chuan-zhong-suo-you-zi-mu-xzin/?envType=study-plan-v2&envId=top-100-liked
简单滑窗，这题也不用思考

var findAnagrams = function (s, target) {
    if (s.length == 0) {
        return 0
    }
    let targetStr = new Array(26).fill(0);
    for (let index = 0; index < target.length; index++) {
        targetStr[target[index].charCodeAt() - 97]++;
    }
    targetStr = targetStr.toString()
    let left = 0, right = 0;
    let result = [];
    let compareArr = new Array(26).fill(0);
    for (let index = 0; index < s.length; index++) {
        const char = s[index];
        if (right - left == target.length) {
            if (compareArr.toString() === targetStr) {
                result.push(left)
            }
            compareArr[s[left].charCodeAt() - 97]--
            left++;
        }
        compareArr[char.charCodeAt() - 97]++
        right++;
    }
    if (compareArr.toString() === targetStr) {
        result.push(left)
    }
    return result
};

李恒道

https://leetcode.cn/problems/intersection-of-two-linked-lists/submissions/557408809/?envType=study-plan-v2&envId=top-100-liked
假设A多余的是a，b多余的是b，共同的是c
则a+c-(b+c)=a-b的差
取最长的链扣掉差，两链相等，则同时步进即可

var getIntersectionNode = function (headA, headB) {
    let numA = 0
    let numB = 0
    let firstA = headA
    let firstB = headB
    while (firstA !== null || firstB !== null) {
        if (firstA !== null) {
            firstA = firstA.next
            numA++
        }
        if (firstB !== null) {
            firstB = firstB.next
            numB++
        }
    }
    let nextHead = numA > numB ? headA : headB
    let lastHead = nextHead === headA ? headB : headA
    const nextStep = Math.abs(numA - numB)
    for (let index = 0; index < nextStep; index++) {
        nextHead = nextHead.next
    }
    while (nextHead!=null&&lastHead!=null) {
        if(nextHead==lastHead){
            return nextHead
        }else{
            nextHead = nextHead.next
            lastHead = lastHead.next
        }
    }
    return null
};

李恒道

https://leetcode.cn/problems/reverse-linked-list/submissions/557412237/?envType=study-plan-v2&envId=top-100-liked
链表反转，简单题
var reverseList = function (head) {
let ret = null
while (head != null) {
let next = head.next
head.next = ret
ret = head
head = next
}
return ret
};

李恒道

https://leetcode.cn/problems/binary-tree-inorder-traversal/submissions/557412974/?envType=study-plan-v2&envId=top-100-liked
中序，简单题

var inorderTraversal = function(root,ret=[]) {
    if(root==null){
        return ret
    }
    inorderTraversal(root.left,ret)
    ret.push(root.val)
    inorderTraversal(root.right,ret)
    return ret
};