[数据结构与算法]数据结构系列---[一周leetcode刷题记录]

• 苍天为鉴,但愿发博能激发 虚荣心,然后就可以每天能按时刷题了😂
• 仅作记录,系列更完 会 整理为一篇博客
• 每天刷题真是死亡难受!!!苍天啊!!!我什么时候能不掉头发地刷题???

2022.2.16

一、 146. LRU 缓存

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

2022.2.17

一、 144. 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var preorderTraversal = function(root) {
    const res = [];
    const dfs = (root)=>{
        if(root === null) return ;
        res.push(root.val);
        dfs(root.left);
        dfs(root.right);
    }
    dfs(root);
    return res;
    

};

c,上午PicGo炸了，没法子，不截图了。500！！！，ccccc

二、 145. 二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number[]}
 */
var postorderTraversal = function(root) {
    const res= [];
    const dfs = (root)=>{
        if(root === null) return;
        dfs(root.left);
        dfs(root.right);
        res.push(root.val);
    }
    dfs(root);
    return res;

};

三 、100. 相同的树

给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {boolean}
 */
var isSameTree = function(p, q) {
    // 两个都空
    if(p === null && q === null) return true;
    // 一个空一个非空
    if(p === null || q === null) return false;
    if(p.val !== q.val) return false;

    return isSameTree(p.left,q.left)&&isSameTree(p.right,q.right);
};

四、 面试题 04.05. 合法二叉搜索树

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @return {boolean}
 */
var isValidBST = function(root) {
    return isValidBST2(root,null,null);
};

let isValidBST2 = (root,min,max) => {
    if(root === null) return true;
    if(min != null && root.val <= min.val) return false;
    if(max != null && root.val >= max.val) return false;
    // 确保右子树小于 最大值root，确保左子树大于最小值root
    return isValidBST2(root.left, min, root) && isValidBST2(root.right, root, max);
}

五、 98. 验证二叉搜索树

六、 700. 二叉搜索树中的搜索

遇到bug

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */


 var searchBST = function(root, val) {
    if(!root) {
        return null;
    }
    if(root.val === val){
        return root;
    }
    // if(root.val <= val){
    //     searchBST(root.left, val);
    // }
    // if(root.val >= val){
    //     searchBST(root.right, val);
    // }
    return searchBST(val < root.val ? root.left : root.right, val);
};

2022.2.21

一、 701. 二叉搜索树中的插入操作

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} val
 * @return {TreeNode}
 */
var insertIntoBST = function(root, val) {
    // 空位置
    if(root === null) return new TreeNode(val);
    // 已存在
    if (root.val === val) return root;
    //
     root.val < val ? root.right = insertIntoBST(root.right, val) : root.left = insertIntoBST(root.left, val);
     return root;

};

2022.2.22

一、 450. 删除二叉搜索树中的节点

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @param {number} key
 * @return {TreeNode}
 */
var deleteNode = function(root, key) {
    if(root === null) return null;
    // 找到key值对应的节点
    if(root.val === key){
        // 该节点无左右子树其一
        if(root.left === null) return root.right;
        if(root.right === null) return root.left;
        // 左右子树都在
        // if(root.left !== null && root.right !== null){
            // 找右子树最小节点：最左边
            let minNode = getMin(root.right);
            // key值的跟节点变成最小节点
            root.val = minNode.val;
            // 删除minNode
            root.right = deleteNode(root.right, minNode.val);
        // }
    } else if(root.val > key){
        root.left = deleteNode(root.left,key);
    }else if(root.val < key){
        root.right = deleteNode(root.right,key);
    }
    return root;
};

  let getMin = (node) => {
        while(node.left !== null){
            node = node.left;  
        }
        return node;
    }

2022.2.23

一、 222. 完全二叉树的节点个数

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
 // 普通树的遍历
var countNodes = function(root) {
    if(root === null) return 0;
    return 1 + countNodes(root.left) + countNodes(root.right);
};

// 满二叉树 + 普通树
var countNodes = function(root) {
    let l = root, r = root;
    let hl = 0,hr = 0;
    while(l !== null){
        l = l.left;
        hl++;
    }
    while(r !== null){
        r = r.right;
        hr++;
    }
    // 满二叉树
    if(hr === hl){
        return Math.pow(2,hl) - 1;
    }
    return 1+ countNodes(root.left) +countNodes(root.right);

};

二、 606. 根据二叉树创建字符串

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {string}
//  */
var tree2str = function(root) {
    // base case
    if (root === null)  return "";
    if (!root.left&& !root.right) return root.val+"";
    // 前序遍历
    let leftStr = tree2str(root.left);
    let rightStr = tree2str(root.right);

    // 按要求生成字符串
    // 只存在左子树
    if(root.left && !root.right) {
        return root.val+`(${leftStr})`;
    }
    if(root.right && !root.left) {
        return root.val+`()(${rightStr})`;
    }
    else{
        return root.val+`(${leftStr})(${rightStr})`
    }
};

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-eHZRbEq9-1645967624280)(https://gitee.com/hannah_bingo/yyy/raw/master/image-20220224172252264.png)]

2022.2.24

一、1008. 前序遍历构造二叉搜索树

球球了，救救我吧！！！

2022.2.25 ： 还看不懂，就背下来了？？？

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {number[]} preorder
 * @return {TreeNode}
 */
var bstFromPreorder = function(preorder) {

    // 701. 二叉搜索树中的插入操作 题解
    var insertIntoBST = function(root, val) {
        if (root) {
            if (root.val > val) {
                root.left = insertIntoBST(root.left, val)
            } else {
                root.right = insertIntoBST(root.right, val)
            }
            return root
        } else {
            return new TreeNode(val)
        }
    };

    // 遍历数组插入二叉搜索树
    // 参数acc的初值为null
    return preorder.reduce((acc,v) => insertIntoBST(acc, v), null)
};

2022.2.25

一、 449. 序列化和反序列化二叉搜索树

序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。

设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

编码的字符串应尽可能紧凑。

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

/**
 * Encodes a tree to a single string.
 *
 * @param {TreeNode} root
 * @return {string}
 */
 // 序列化
var serialize = function(root) {
    let res ='';

    let preserialize = (root, res) =>{
        if (root === null){
            res.concat('NULL',',');
            return;
        }
        res.concat(root.val, ',');
        preserialize(root.left, res);
        preserialize(root.right, res);
    }
    preserialize(root, res);
    return res;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function(data) {
    // 字符串转换成列表
    let preorder = data.split(' ').map(item => {
        return Number.parseInt(item);
    })
    let nodes = [...preorder];
    const predeserialize = (nodes) => {
        const first = nodes.shift();
        if(first === null) return null;
        let root = new TreeNode(first);

        root.left = predeserialize(nodes);
        root.right = predeserialize(nodes);

        return root;
    }


    return predeserialize(nodes);
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */

我很生气，但是我解决不了，呜呜呜

我TM头回见这报错！！！

二、 剑指 Offer II 048. 序列化与反序列化二叉树

三、 236. 二叉树的最近公共祖先

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
var lowestCommonAncestor = function(root, p, q) {
    // base case
    if(root === null) return null;
    if(root === p || root === q) return root;

    let left = lowestCommonAncestor(root.left,p,q);
    let right = lowestCommonAncestor(root.right,p,q);

    // 情况一
    if (left !== null && right !== null)
        return root;
    if (left === null && right === null)
        return null;
    return left === null ? right : left;
};

四、 剑指 Offer 68 - II. 二叉树的最近公共祖先

五、 235. 二叉搜索树的最近公共祖先

六、 剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

同一题解过了四道题事什么情况，挺开心，哈哈哈

2022.2.27

一、 496. 下一个更大元素 I

var nextGreaterElement = function(nums1, nums2) {
    const map = new Map();
    const stack = [];
    for (let i = nums2.length - 1; i >= 0; --i) {
        const num = nums2[i];
        while (stack.length && num >= stack[stack.length - 1]) {
            stack.pop();
        }
        map.set(num, stack.length ? stack[stack.length - 1] : -1);
        stack.push(num);
    }
    const res = new Array(nums1.length).fill(0).map((_, i) => map.get(nums1[i]));
    return res;
};