5774. 使用服务器处理任务

https://leetcode-cn.com/problems/process-tasks-using-servers/

/*
由于在JS中没有自带的优先队列，因此这里手写堆
堆的起始数组坐标是0
*/
class Heap {
    /**
     * 构造器
     * @param {Number} data 数据
     * @param {Function} compare 比较函数
     */
    constructor(data, compare) {
        this.data = data;
        this.compare = compare;
        // 建立堆
        for (let i = (data.length >> 1) - 1; i >= 0; i--) {
            this.heapify(i);
        }
    }
    /**
     * 构建堆
     * @param {Number} index 索引
     */
    heapify(index) {
        let target = index;
        // 左子树
        let left = index * 2 + 1;
        // 右子树
        let right = index * 2 + 2;
        if (left < this.data.length && this.compare(this.data[left], this.data[target])) {
            target = left;
        }
        if (right < this.data.length && this.compare(this.data[right], this.data[target])) {
            target = right;
        }
        if (target !== index) {
            this.swap(target, index);
            this.heapify(target);
        }
    }
    /**
     * 交互函数，交互数组坐标l和r处的元素
     * @param {Number} l 左坐标
     * @param {Number} r 右坐标
     */
    swap(l, r) {
        let data = this.data;
        [data[l], data[r]] = [data[r], data[l]];
    }
    /**
     * 入队
     * @param {*} item 放入的值
     */
    push(item) {
        this.data.push(item);
        let index = this.data.length - 1;
        // 父节点
        let father = ((index + 1) >> 1) - 1;
        while (father >= 0) {
            if (this.compare(this.data[index], this.data[father])) {
                this.swap(index, father);
                index = father;
                father = ((index + 1) >> 1) - 1;
            } else {
                break;
            }
        }
    }
    /**
     * 出队
     * @returns 出队的值
     */
    pop() {
        this.swap(0, this.data.length - 1);
        let ret = this.data.pop();
        this.heapify(0);
        return ret;
    }
}
/**
 * @param {number[]} servers 服务权重
 * @param {number[]} tasks 任务时间
 * @return {number[]}
 */
var assignTasks = function (servers, tasks) {
    let data = [];
    // 根据服务权重和索引存放数据到data中
    for (let i = 0; i < servers.length; i++) {
        data.push({
            prioity: servers[i],
            index: i,
        });
    }
    console.log(data);
    // 新建heap队列，按照优先级递增的顺序排列
    this.heap = new Heap(data, (lower, higher) => {
        if (lower.prioity < higher.prioity) {
            return true;
        } else if (lower.prioity == higher.prioity && lower.index <= higher.index) {
            return true;
        } else {
            return false;
        }
    });
    // 新建idle队列，按照任务时间顺序排列
    this.idle = new Heap([], (lower, higher) => {
        if (lower.time <= higher.time) {
            return true;
        } else {
            return false;
        }
    });
    console.log(this.heap);
    console.log(this.idle);
    let ret = [];
    let index = 0;
    let time = 0;
    // 只要任务还有就不停止
    while (tasks.length !== 0) {
        while (this.idle.data.length && this.idle.data[0].time == time) {
            this.heap.push(this.idle.pop().handle);
        }
        while (this.heap.data.length && index <= time && tasks.length !== 0) {
            let tmp = tasks.shift();
            let item = this.heap.pop();
            this.idle.push({
                time: time + tmp,
                handle: item,
            })
            index++;
            ret.push(item.index);
        }
        if (this.heap.data.length) {
            time++;
        } else {
            time = this.idle.data[0].time;
        }
    }
    return ret;
};
let servers = [4,3,2], tasks = [1,2,3,2,1,2];
let res = assignTasks(servers,tasks);
console.log(res);

牛妹的LIS

class Solution{
public:
    int val(string s){
        int ans=0;
        for(char c:s){
            ans=ans*10+c-'0';
        }
        return ans;
    }
    int NS_LIS(string n){
        int L=(int)n.length();
        if(L==1){
            return val(n);
        }
        int ans=0;
        int a=n[0]-'0';
        ans=max(ans,(a-1)+(L-1)*9);
        int s=0;
        for(char c:n){
            s+=c-'0';
        }
        ans=max(ans,s);
        return ans;
    }
};

魔法师牛牛

bool cmp(pair<int,int> a,pair<int,int> b){
    return a.first<b.first;
}
class Solution{
public:
    vector<int> Magical_NN(vector<int> h){
        int n=(int)h.size();
        vector<pair<int,int>> a(n+1);
        vector<int> pre(n+2,0);
        for(int i=1;i<=n;i++){
            a[i].first=h[i-1];
            a[i].second=i-1;            
        } 
        sort(a.begin()+1,a.end(),cmp);
        for(int i=1;i<=n;i++){
            pre[i]=pre[i-1]+a[i].first;
        }
        vector<int> ans(n);
        for(int i=1;i<=n;i++){
            int Lned=(i-1)*a[i].first-pre[i-1];
            int Rned=(pre[n]-pre[i])-(n-i)*a[i].first;
            ans[a[i].second]=Lned+Rned;
        }
        return ans;
    }
};

149. 直线上最多的点数

/**
 * @param {number[][]} points
 * @return {number}
 */
var maxPoints = function (points) {
    let n = points.length;
    let ans = 1;
    for (let i = 0; i < n; i++) {
        const map = new Map();
        let maxPointsNum = 0;
        for (let j = i + 1; j < n; j++) {
            const x1 = points[i][0], y1 = points[i][1];
            const x2 = points[j][0], y2 = points[j][1];
            const a = x1 - x2, b = y1 - y2;
            const k = gcd(a, b);
            let key = (a / k) + "_" + (b / k);
            // 对某一点，计算在某条直线上最多的点上数量，保存到maxPointsNum中
            map.set(key, (map.get(key) || 0) + 1);
            maxPointsNum = Math.max(maxPointsNum, map.get(key));
        }
        // 所有点的最大值就是结果
        ans = Math.max(ans, maxPointsNum + 1);
    }
    return ans;

    /**
     * @param {Number} a 
     * @param {Number} b 
     * @returns 最大公约数
     */
    function gcd(a, b) {
        return b === 0 ? a : acd(b, a % b);
    }
};