leetcode刷题记录

3. 无重复字符的最长子串

3. 无重复字符的最长子串

思路：

滑动窗口方法，构造出散列表

var lengthOfLongestSubstring = function(s) {
    /*构造*/
    const occ = new Set();
    const n = s.length;
    let rk = -1,ans = 0;/*右指针*/
    for(let i=0;i<n;++i){
        if(i!=0){
            occ.delete(s.charAt(i-1));
        }
         while (rk + 1 < n && !occ.has(s.charAt(rk + 1))) {
             occ.add(s.charAt(rk+1));
             ++rk;
         }
        ans = Math.max(ans, rk - i + 1);

    }
    return ans;
};

4. 寻找两个正序数组的中位数

4. 寻找两个正序数组的中位数

思路：

1. 调用concat()函数将两个数组合并
2. 将数组排序(不用数组自带的arr.sort()方法是因为该方法无法正确判断当数组有负数的情况，所以需要另外写一个排序函数)
3. 根据数组长度的奇偶求中位数（注意，当长度n为偶数时，中位数为数组的第n/2位和第n/2-1位，因为数组开头是0）

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
function sort(nums){
        for(let i=0;i<nums.length-1;i++){
            for(let j=0;j<nums.length-1-i;j++){
                if(nums[j]>nums[j+1]){
                    let temp = nums[j+1];
                    nums[j+1] = nums[j];
                    nums[j] = temp;
                }
            }
        }
        return nums;
    }
var findMedianSortedArrays = function(nums1, nums2) {
    var num3 = nums1.concat(nums2);
    num3 = sort(num3);
    var ansNum = num3.length;
    
    if(ansNum%2 != 0){
        return num3[Math.floor(ansNum/2)];
    }else{
        var ans = num3[ansNum/2]+num3[ansNum/2-1];
        return ans/2;
    }
    return null;
};

56.合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda x: x[0])

        merged = []
        for interval in intervals:
            # 如果列表为空，或者当前区间与上一区间不重合，直接添加
            if not merged or merged[-1][1] < interval[0]:
                merged.append(interval)
            else:
                # 否则的话，我们就可以与上一区间进行合并
                merged[-1][1] = max(merged[-1][1], interval[1])

        return merged

94. 二叉树的中序遍历

94. 二叉树的中序遍历

var inorderTraversal = function(root) {
    const res = [];
    const inorder = (root) => {
        if (!root) {
            return;
        }
        inorder(root.left);
        res.push(root.val);
        inorder(root.right);
    }
    inorder(root);
    return res;
};

102. 二叉树的层序遍历

102.二叉树的层序遍历

var levelOrder = function(root){
    const ret = [];
    if(!root){
        return ret;
    }

    const q = [];
    q.push(root);

    while(q.length !== 0){
        const currentLevelSize =q.length;
        ret.push([]);
        for(let i = 1;i<=currentLevelSize;i++){
            const node = q.shift();
            ret[ret.length-1].push(node.val);
            if(node.left) q.push(node.left);
            if(node.right) q.push(node.right);

        }
    }
    return ret;
}

寻找6174

给定任一个各位数字不完全相同的4位正整数，如果我们先把4个数字按非递增排序，再按非递减排序，然后用第1个数字减第2个数字，将得到
一个新的数字。一直重复这样做，我们很快会停在有“数字黑洞”之称的6174，这个神奇的数字也叫Kaprekar常数。

例如，我们从6767开始，将得到

7766 - 6677 = 1089
9810 - 0189 = 9621
9621 - 1269 = 8352
8532 - 2358 = 6174
7641 - 1467 = 6174
… …

现给定任意4位正整数，请编写程序演示到达黑洞的过程。

function  findNum(num) {
    var str = '';
    var node = '->';
    var chazhi = num;

    str = str+chazhi.toString();
    while(chazhi!=6174){
        var temp = (chazhi+'').split("");
        var small = parseInt(temp.sort().join(""));
        var big = parseInt(temp.reverse().join(""));
        chazhi  = big-small;
        str = str+node+chazhi.toString();
    }


    return str;
}
console.log(findNum(2021));