leetCode 刷题

716.最大栈 MaxStack

details

class MaxStack {
    constructor() {
        this.stack = [];
        this.maxStack = [];
    }

    push(x) {
        this.stack.push(x);
        if (this.maxStack.length === 0 || x >= this.maxStack[this.maxStack.length - 1]) {
            this.maxStack.push(x);
        } else {
            this.maxStack.push(this.maxStack[this.maxStack.length - 1]);
        }
    }

    pop() {
        this.maxStack.pop();
        return this.stack.pop();
    }

    top() {
        return this.stack[this.stack.length - 1];
    }

    getMax() {
        return this.maxStack[this.maxStack.length - 1];
    }
}

2363. 合并相似的物品

var mergeSimilarItems = function (items1, items2) {
    const map = new Map();
    for (const v of items1) {
        map.set(v[0], (map.get(v[0]) || 0) + v[1]);
    }
    for (const v of items2) {
        map.set(v[0], (map.get(v[0]) || 0) + v[1]);
    }

    const res = [];
    for (const [k, v] of map.entries()) {
        const pair = [];
        pair.push(k);
        pair.push(v);
        res.push(pair);
    }
    res.sort((a, b) => a[0] - b[0]);
    return res;
};

704. 二分查找

有序数组中查找

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function (nums, target) {
    let left = 0,
        right = nums.length - 1;
    while (left <= right) {
        const mid = (left + (right - left) / 2) >> 0;
        if (target === nums[mid]) {
            return mid;
        } else if (nums[mid] > target) {
            right = mid + 1;
        } else {
            left = mid + 1;
        }
    }
    return -1;
};

146. LRU 缓存

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
    this.capacity = capacity;
    this.map = new Map();
    this.head = null;
    this.tail = null;
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
    if (!this.map.has(key)) return -1;
    const node = this.map.get(key);
    this.moveToHead(node);
    return node.val;
};

/**
 * @param {ListNode} node
 */
LRUCache.prototype.removeNode = function (node) {
    if (node.prev) {
        node.prev.next = node.next;
    } else {
        this.head = node.next;
    }

    if (node.next) {
        node.next.prev = node.prev;
    } else {
        this.tail = node.prev;
    }
};

/**
 * @param {ListNode} node
 */
LRUCache.prototype.addToHead = function (node) {
    node.prev = null;
    node.next = this.head;

    if (this.head) {
        this.head.prev = node;
    } else {
        this.tail = node;
    }
    this.head = node;
};

/**
 * @param {ListNode} node
 */
LRUCache.prototype.moveToHead = function (node) {
    this.removeNode(node);
    this.addToHead(node);
};

LRUCache.prototype.removeTail = function () {
    const node = this.tail;
    this.removeNode(node);
    return node;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
    if (this.map.has(key)) {
        const node = this.map.get(key);
        node.val = value;
        this.moveToHead(node);
    } else {
        const node = new ListNode(key, value);
        this.map.set(key, node);

        this.addToHead(node);

        if (this.map.size > this.capacity) {
            const removed = this.removeTail();
            this.map.delete(removed.key);
        }
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * var obj = new LRUCache(capacity)
 * var param_1 = obj.get(key)
 * obj.put(key,value)
 */

// 双向链表

class ListNode {
    constructor(key, val) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

621. 任务调度器

253 会议室 II

贪心算法

function canAttendMeetings(intervals) {
    intervals.sort((a, b) => a[0] - b[0]);
    let end = 0;
    for (let i = 0; i < intervals.length; i++) {
        if (intervals[i][0] < end) {
            return false;
        }
        end = intervals[i][1];
    }
    return true;
}

1603. 设计停车系统

/**
 * @param {number} big
 * @param {number} medium
 * @param {number} small
 */
var ParkingSystem = function (big, medium, small) {
    const map = new Map();

    [big, medium, small].forEach((limit, i) => {
        map.set(i + 1, {
            limit: limit,
            count: 0,
        });
    });
    this.map = map;
};

/**
 * @param {number} carType
 * @return {boolean}
 */
ParkingSystem.prototype.addCar = function (carType) {
    const data = this.map.get(carType);
    if (data.count === data.limit) return false;
    data.count++;
    return true;
};

/**
 * Your ParkingSystem object will be instantiated and called as such:
 * var obj = new ParkingSystem(big, medium, small)
 * var param_1 = obj.addCar(carType)
 */

1396. 设计地铁系统

var UndergroundSystem = function () {
    // 存储当前进站后 还没出站的信息
    this.map = new Map();
    // 存储平均时间
    this.timerMap = new Map();
};

/**
 * @param {number} id
 * @param {string} stationName
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkIn = function (id, stationName, t) {
    const map = this.map;
    if (!map.has(id)) {
        return map.set(id, { stationName, t });
    }
};

/**
 * @param {number} id
 * @param {string} stationName
 * @param {number} t
 * @return {void}
 */
UndergroundSystem.prototype.checkOut = function (id, stationName, t) {
    const map = this.map,
        timerMap = this.timerMap;

    if (map.has(id)) {
        const { stationName: s1, t: t1 } = map.get(id);
        const key = `${s1}#${stationName}`;
        let { sum = 0, count = 0 } = timerMap.get(key) || {};
        sum += t - t1;
        count += 1;
        timerMap.set(key, { sum, count });
        map.delete(id);
    }
};

/**
 * @param {string} startStation
 * @param {string} endStation
 * @return {number}
 */
UndergroundSystem.prototype.getAverageTime = function (startStation, endStation) {
    const key = `${startStation}#${endStation}`;
    const { sum = 0, count = 0 } = this.timerMap.get(key);
    return sum / count;
};

/**
 * Your UndergroundSystem object will be instantiated and called as such:
 * var obj = new UndergroundSystem()
 * obj.checkIn(id,stationName,t)
 * obj.checkOut(id,stationName,t)
 * var param_3 = obj.getAverageTime(startStation,endStation)
 */

2389. 和有限的最长子序列

排序后从前往后遍历

时间复杂度 O(m*n + nlogN) 空间复杂度 O(n)

这个解法中，每次去有序数组中累积求 从 1......x 的和，存在重复计算。可以把前缀和先求出来。再二分去找。

/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @return {number[]}
 */
var answerQueries = function (nums, queries) {
    // 先排序
    nums.sort((a, b) => a - b);

    let ans = [];
    for (let i = 0; i < queries.length; i++) {
        const max = queries[i];
        let sum = 0,
            j = 0;
        for (; j < nums.length; j++) {
            sum += nums[j];
            if (sum > max) {
                break;
            }
        }
        ans[i] = j;
    }
    return ans;
};

前缀和 + 二分查找

对原始数组排序后，可以求出前缀和。省去了每次都要重复计算 1.....x 的和。 二分搜索过程中，需要查找最右边的值，保证子序列长度最长

/**
 * @param {number[]} nums
 * @param {number[]} queries
 * @return {number[]}
 */
var answerQueries = function (nums, queries) {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    const prefixSum = new Array(n + 1).fill(0);
    for (let i = 1; i <= n; i++) {
        prefixSum[i] = prefixSum[i - 1] + nums[i - 1];
    }
    const m = queries.length;
    const ans = new Array(m).fill(0);

    for (let i = 0; i < m; i++) {
        const q = queries[i];

        // 二分搜索，查找最右边的值
        let left = findRightMost(q);
        ans[i] = left - 1;
    }
    return ans;

    function findRightMost(q) {
        let left = 0,
            right = n + 1;
        while (left < right) {
            const mid = (left + (right - left) / 2) >> 0;
            if (prefixSum[mid] <= q) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
};

1012. 至少有 1 位重复的数字

时间复杂度 O(n*logN)

超时了，没有达到题目时间复杂度要求

/**
 * @param {number} n
 * @return {number}
 */
var numDupDigitsAtMostN = function (n) {
    let count = 0;
    for (let i = 1; i <= n; i++) {
        let digits = String(i).split('');
        let set = new Set(digits);
        if (set.size < digits.length) {
            count++;
        }
    }
    return count;
};

除了暴力解法，其他解法看不懂。搞不定

2488. 统计中位数为 K 的子数组

前缀和

var countSubarrays = function (nums, k) {
    const n = nums.length;
    let kIndex = -1;
    for (let i = 0; i < n; i++) {
        if (nums[i] === k) {
            kIndex = i;
            break;
        }
    }
    let ans = 0;
    const counts = new Map();
    counts.set(0, 1);
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += sign(nums[i] - k);
        if (i < kIndex) {
            counts.set(sum, (counts.get(sum) || 0) + 1);
        } else {
            const prev0 = counts.get(sum) || 0;
            const prev1 = counts.get(sum - 1) || 0;
            ans += prev0 + prev1;
        }
    }
    return ans;

    function sign(num) {
        if (num === 0) {
            return 0;
        }
        return num > 0 ? 1 : -1;
    }
};

剑指 Offer II 109. 开密码锁

BFS

解题思路： 此题可以用 BFS 算法来解决。将初始数字 "0000" 作为 BFS 的起点，然后依次将相邻的数字加入到队列中，并记录这些数字的旋转次数。然后，依次从队列中取出数字，将它们旋转一位上或一位下，并判断它们是否和目标数字相同。如果相同，则返回旋转次数。如果队列为空，说明无法旋转形成目标数字序列，则返回 -1。

/**
 * @param {string[]} deadends
 * @param {string} target
 * @return {number}
 */
var openLock = function (deadends, target) {
    // 将 deadends 转换为 Set
    const deadSet = new Set(deadends);
    // 初始数字 "0000" 入队
    const queue = ['0000'];
    // 记录旋转次数
    let step = 0;
    // 用 Set 来记录已经出现过的数字
    const visited = new Set();
    visited.add('0000');
    while (queue.length > 0) {
        // 当前队列的长度，即当前层的节点个数
        const size = queue.length;
        for (let i = 0; i < size; i++) {
            const current = queue.shift();
            // 如果当前数字是目标数字，则返回旋转次数
            if (current === target) {
                return step;
            }
            // 如果当前数字在 deadends 中出现过，则跳过
            if (deadSet.has(current)) {
                continue;
            }
            // 将相邻的数字加入队列
            for (let j = 0; j < 4; j++) {
                // 旋转一位上或一位下
                const up = plusOne(current, j);
                const down = minusOne(current, j);
                // 如果未出现过，则加入队列
                if (!visited.has(up)) {
                    queue.push(up);
                    visited.add(up);
                }
                if (!visited.has(down)) {
                    queue.push(down);
                    visited.add(down);
                }
            }
        }
        // 每一层结束后，旋转次数加一
        step++;
    }
    // 如果队列为空，说明无法旋转形成目标数字序列
    return -1;

    /**
     * 将数字的第 i 位加一
     * @param {string} s 数字字符串
     * @param {number} i 位数
     * @return {string} 旋转后的数字字符串
     */
    function plusOne(s, i) {
        const char = s.charAt(i);
        let newChar = char === '9' ? '0' : Number(char) + 1;
        return s.slice(0, i) + newChar + s.slice(i + 1);
    }

    /**
     * 将数字的第 i 位减一
     * @param {string} s 数字字符串
     * @param {number} i 位数
     * @return {string} 旋转后的数字字符串
     */
    function minusOne(s, i) {
        const char = s.charAt(i);
        let newChar = char === '0' ? '9' : Number(char) - 1;
        return s.slice(0, i) + newChar + s.slice(i + 1);
    }
};

双向 BFS

2367. 算术三元组的数目

HashSet

/**
 * @param {number[]} nums
 * @param {number} diff
 * @return {number}
 */
var arithmeticTriplets = function (nums, diff) {
    let ans = 0;
    const set = new Set(nums);

    for (let i = 1; i < nums.length - 1; i++) {
        if (set.has(nums[i] - diff) && set.has(nums[i] + diff)) {
            ans++;
        }
    }
    return ans;
};

1637. 两点之间不包含任何点的最宽垂直区域

排序

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxWidthOfVerticalArea = function (points) {
    points.sort((a, b) => a[0] - b[0]);
    let ans = 0;
    for (let i = 1; i < points.length; i++) {
        ans = Math.max(points[i][0] - points[i - 1][0], ans);
    }
    return ans;
};

impl Solution {
    pub fn max_width_of_vertical_area(points: Vec<Vec<i32>>) -> i32 {
        let mut points: Vec<i32> = points.iter().map(|p| p[0]).collect();
        points.sort();

        let mut ans = 0;
        for i in 1..points.len() {
            ans = ans.max(points[i] - points[i - 1])
        }
        ans
    }
}

831. 隐藏个人信息

正则表达式

/**
 * @param {string} s
 * @return {string}
 */
var maskPII = function (s) {
    let isEmail = /@/.test(s) ? true : false;
    if (isEmail) {
        let temp = s.toLocaleLowerCase();
        const regex = /(\w)(\w*)@/;
        const replacement = (match, first, rest) => `${first}*****${rest.slice(-1)}@`;

        return temp.replace(regex, replacement);
    } else {
        let rawStr = s.replace(/\D/g, '');
        const len = rawStr.length;
        if (len === 10) {
            return '***-***-' + rawStr.slice(-4);
        }
        return '+' + '*'.repeat(len - 10) + '-***-***-' + rawStr.slice(-4);
    }
};

impl Solution {
    pub fn mask_pii(s: String) -> String {
        if s.contains('@') {
            let email: String = s.to_lowercase();
            let pos = email.find('@').unwrap();
            let (username, domain) = email.split_at(pos);
            let masked_username = format!(
                "{}*****{}",
                username.chars().next().unwrap(),
                username.chars().last().unwrap(),
            );

            format!("{}{}", masked_username, domain)
        } else {
            //
            let digits: String = s.chars().filter(|c| c.is_ascii_digit()).collect();
            let len = digits.len();
            if len == 10 {
                format!("***-***-{}", &digits[len - 4..])
            } else {
                format!("+{}-***-***-{}", "*".repeat(len - 10), &digits[len - 4..])
            }
        }
    }
}

1053. 交换一次的先前排列

贪心算法

时间复杂度 O(n) 空间复杂度 O(1)

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevPermOpt1 = function (arr) {
    const n = arr.length;
    for (let i = n - 2; i >= 0; i--) {
        if (arr[i] > arr[i + 1]) {
            let j = n - 1;
            while (arr[j] >= arr[i] || arr[j] === arr[j - 1]) {
                j--;
            }
            swap(i, j, arr);
            break;
        }
    }
    return arr;
};

function swap(i, j, arr) {
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

impl Solution {
    pub fn prev_perm_opt1(arr: Vec<i32>) -> Vec<i32> {
        let n = arr.len();
        let mut arr = arr;

        for i in (0..n - 1).rev() {
            if arr[i] > arr[i + 1] {
                let mut j = n - 1;
                while arr[j] >= arr[i] || arr[j] == arr[j - 1] {
                    j -= 1;
                }
                arr.swap(i, j);
                break;
            }
        }
        arr
    }
}

2427. 公因子的数目

暴力解法

/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
/**
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
var commonFactors = function (a, b) {
    let ans = 0;
    for (let x = 1; x <= Math.min(a, b); ++x) {
        if (a % x === 0 && b % x === 0) {
            ++ans;
        }
    }
    return ans;
};

Rust

impl Solution {
    pub fn common_factors(a: i32, b: i32) -> i32 {
      let mut ans = 0;
      for x in 1..=std::cmp::min(a, b) {
          if a % x == 0 && b % x == 0 {
              ans += 1;
          }
      }
      ans

    }
}

1017 负二进制转换

方案一

Javascript

/**
 * @param {number} N
 * @return {string}
 */
var baseNeg2 = function (N) {
    if (N === 0) {
        return '0';
    }
    let res = '';
    while (N !== 0) {
        const r = N % -2;
        N = Math.trunc(N / -2) + (r < 0 ? 1 : 0);
        res = Math.abs(r) + res;
    }
    return res;
};

1040. 移动石子直到连续 II

双指针

Javascript

/**
 * @param {number[]} stones
 * @return {number[]}
 */
var numMovesStonesII = function (stones) {
    let n = stones.length;
    stones.sort((a, b) => a - b);
    if (stones[n - 1] - stones[0] + 1 == n) {
        return [0, 0];
    }
    let ma = Math.max(stones[n - 2] - stones[0] + 1, stones[n - 1] - stones[1] + 1) - (n - 1);
    let mi = n;
    let j = 0;
    for (let i = 0; i < n; i++) {
        while (j + 1 < n && stones[j + 1] - stones[i] + 1 <= n) {
            j++;
        }
        if (j - i + 1 == n - 1 && stones[j] - stones[i] + 1 == n - 1) {
            mi = Math.min(mi, 2);
        } else {
            mi = Math.min(mi, n - (j - i + 1));
        }
    }
    return [mi, ma];
};

2399. 检查相同字母间的距离

字母索引

Javascript

/**
 * @param {string} s
 * @param {number[]} distance
 * @return {boolean}
 */
var checkDistances = function (s, distance) {
    const list = new Array(26).fill(-1);
    for (let i = 0; i < s.length; i++) {
        const index = s[i].charCodeAt(0) - 97;
        list[index] = list[index] === -1 ? i : i - list[index];
    }
    // console.log(list);
    for (let j = 0; j < distance.length; j++) {
        if (list[j] !== -1 && distance[j] !== list[j] - 1) {
            return false;
        }
    }
    return true;
};

1041. 困于环中的机器人

模拟 最后结束位置在原点，或者 dx 或者 dy 中有一个不等于 0 则是圆环

Javascript

/**
 * @param {string} instructions
 * @return {boolean}
 */
var isRobotBounded = function (instructions) {
    let x = 0,
        y = 0,
        dx = 0,
        dy = 1;
    for (let i = 0; i < instructions.length; i++) {
        const instruction = instructions.charAt(i);
        if (instruction === 'G') {
            x += dx;
            y += dy;
        } else if (instruction === 'L') {
            [dx, dy] = [-dy, dx];
        } else {
            [dx, dy] = [dy, -dx];
        }
    }
    return (x === 0 && y === 0) || dx !== 0 || dy !== 1;
};

1147. 段式回文

双指针

Javascript

var longestDecomposition = function (text) {
    let n = text.length;
    let left = '';
    let right = '';
    let count = 0;

    for (let i = 0; i < n; i++) {
        left = left + text[i];
        right = text[n - 1 - i] + right;

        if (left === right) {
            count += 1;
            left = '';
            right = '';
        }
    }

    return count;
};