贪心 - 规划 - 《算法》

502. IPO

思路：大堆，维护一个收益最大堆

前置条件：
1、合并项目和收益数组，以启动资本降序，收益升序排列项目和启动资本的合并数组；
2、构建一个大堆，队中的排序规则是，收益降序，自动资本升序。
过程：

1、获取不高于当前资本的所有项目入堆；
2、从堆中选择一个项目，k—，并计算资本；
3、返回最终结果。

/**
 * @param {number} k
 * @param {number} w
 * @param {number[]} profits
 * @param {number[]} capital
 * @return {number}
 */
var findMaximizedCapital = function(k, w, profits, capital) {
  const projects = new Array(profits.length);
  for (let i = 0; i < profits.length; i++) {
    projects[i] = {
      profit: profits[i],
      capital: capital[i]
    };
  }
  projects.sort((a, b) => {
    if (a.capital === b.capital) {
      return a.profit - b.profit;
    }
    return b.capital - a.capital;
  });
  const hp = new Heap((a, b) => {
    if (a.profit === b.profit) {
      return a.capital - b.capital;
    }
    return b.profit - a.profit;
  });
  let ans = w;
  while (k) {
    while (projects.length && projects[projects.length - 1] && projects[projects.length - 1].capital <= ans) {
      hp.push(projects.pop());
    }
    let p;
    if (!hp.isEmpty())  {
      p = hp.pop();
    }
    if (!p) {
        // 已有资金不够启动新项目
      break;
    }
    ans += p.profit;
    k--;
  }
  return ans;
};
function swap(d, i, j) {
  [d[i], d[j]] = [d[j], d[i]];
}
function toUpper(d, i, comp) {
  while (i > 0) {
    let p =  ((i - 1) >>> 1);
    if (comp(d[p], d[i]) > 0) {
      swap(d, p, i);
    }
    i = p;
  }
}
function toBottom(d, i, len, comp) {
  while (i < len) {
    let l = 1 + (i << 1);
    let r = 2 + (i << 1);
    let m = i;
    if (l < len && comp(d[l], d[m]) < 0) {
      m = l;
    }
    if (r < len && comp(d[r], d[m]) < 0) {
      m = r;
    }
    if (m === i) {
      break;
    }
    swap(d, m, i);
    i = m;
  }
}
class Heap {
  constructor(comp) {
    this.d = [];
    this.comp = comp;
  }
  push(t) {
    this.d.push(t);
    toUpper(this.d, this.d.length - 1, this.comp);
  }
  pop() {
    if (this.d.length <= 1) {
      return this.d.pop();
    }
    const r = this.d[0];
    this.d[0] = this.d.pop();
    toBottom(this.d, 0, this.d.length, this.comp);
    return r;
  }
  peek() {
    return this.d[0];
  }
  isEmpty() {
    return this.d.length === 0;
  }
}

881. 救生艇

/**
 * @param {number[]} people
 * @param {number} limit
 * @return {number}
 */
var numRescueBoats = function(people, limit) {
   people.sort((a, b) => a- b);
   let ans = 0, left = 0, right = people.length - 1;
   while (left <= right) {
     ans += 1;
     if (people[right] + people[left] <= limit) {
      left ++;
     }
     right --;
   }
   return ans;
};

1011. 在 D 天内送达包裹的能力

/**
 * @param {number[]} weights
 * @param {number} days
 * @return {number}
 */
var shipWithinDays = function(weights, days) {
  let bounds = weights.reduce((r, i) => {
    r.min = i > r.min ? i : r.min;
    r.max += i;
    return r;
  }, {
    min: Number.MIN_SAFE_INTEGER,
    max: 0
  });
  let {min: left, max: right } = bounds;
  let ans = right;
  while (left < right) {
    const mid = left + ((right - left) >> 1);

    let r = 1;
    let sum = 0;
    for (let i = 0; i < weights.length; i++) {
      if (sum + weights[i] > mid) {
        r += 1;
        sum = 0;
      }
      sum += weights[i];
    }

    if (r > days) {
      left = mid + 1;
    } else if (r <= days) {
      right = mid;
      ans = Math.min(ans, mid);
    }
  }
  return ans;
};

1382. 将二叉搜索树变平衡

/**
 * 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 {TreeNode}
 */
var balanceBST = function(root) {
  const r = [];
  const traverse = (node) => {
    if (node.left) {traverse(node.left); }
    r.push(node.val);
    if (node.right){traverse(node.right);}
  };
  traverse(root);

  const makeTree = (left, right) => {
    if (left > right) return null;
    if (left === right) {
      return new TreeNode(r[left]);
    }
    let mid = left + Math.floor((right - left)/2);
    const nroot = makeTree(mid, mid);
    nroot.left = makeTree(left, mid - 1);
    nroot.right = makeTree(mid + 1, right);
    return nroot;
  };

  return makeTree(0, r.length - 1);
};

1386. 安排电影院座位

/**
 * @param {number} n
 * @param {number[][]} reservedSeats
 * @return {number}
 */
var maxNumberOfFamilies = function(n, reservedSeats) {
  const rs = new Map();
  reservedSeats.reduce((r, item) => {
    const [row, c] = item;
    // 限定预定的座位在【2，9】之间，确保只会可以安排一个4口之家。
    // 在1，10位置预定的，不影响结果计算判断。
    if (c >= 2 && c <= 9) { 
      r.set(row, (r.get(row) || 0) + (1 << (c - 2)));
    }
    return r;
  }, rs);
  // left: 2345, right: 4567, mid: 2345
  const left = 0b11110000, right = 0b00001111, mid = 0b11000011;

  // 不在预定里面的行可以安排两个结果，所以要乘以2；
  let ans = (n - rs.size) * 2;

  for (let value of rs.values()) {
    // 利用或的性质，检测每个家庭的位置是否被占用，如果没有被占用，则这个位置可以安排
    if ((value | left) === left || (value | mid) === mid || (value | right) === right) {
      ans += 1;
    }
  }
  return ans;
};

1663. 具有给定数值的最小字符串

/**
 * @param {number} n
 * @param {number} k
 * @return {string}
 */
var getSmallestString = function(n, k) {
  // 先给每个位置默认填充'a'，然后计算剩余的数值的分配
  let q = new Array(n).fill('a'), remain = k - n, i = n - 1;
  while (remain) {
    if (remain > 25) {
      remain -= 25;
      q[i] = 'z';
      i--;
    } else {
      q[i] = String.fromCharCode(97 + remain);
      remain = 0;
    }
  }
  return q.join('');
};

1792. 最大平均通过率

/**
 * @param {number[][]} classes
 * @param {number} extraStudents
 * @return {number}
 */
var maxAverageRatio = function(classes, extraStudents) {

  const heap = new MaxPriorityQueue({ priority: (bid) => bid.delta });
  classes.forEach(([p, t], index) => {
    heap.enqueue({
      delta: (p+1)/(t+1) - p/t,
      index
    });
  });

  while (extraStudents) {
    const top = heap.dequeue().element;
    classes[top.index][0]++;
    classes[top.index][1]++;
    let [p, t] = classes[top.index];
    heap.enqueue({
      delta: (p + 1)/(t+1) - p/t,
      index: top.index
    });
    extraStudents--;
  }
  let ans = 0;
  for (let i = 0; i < classes.length; i++) {
    ans += (classes[i][0]/classes[i][1]);
  }
  return ans/classes.length;
};

1846. 减小和重新排列数组后的最大元素

/**
 * @param {number[]} arr
 * @return {number}
 */
var maximumElementAfterDecrementingAndRearranging = function(arr) {
  arr.sort((a, b) => a - b);
  arr[0] = 1;
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] - arr[i-1] > 1) {
      arr[i] = arr[i-1] + 1;
    }
  }
  return arr[arr.length - 1];
};

1877. 数组中最大数对和的最小值

/**
 * @param {number[]} nums
 * @return {number}
 */
var minPairSum = function(nums) {
  nums.sort((a, b) => a - b);
  let l = 0, r = nums.length - 1;
  let ans = 0;
  while (l < r) {
    ans = Math.max(ans, nums[l++] + nums[r--]);
  }
  return ans;
};

剑指 Offer 45. 把数组排成最小的数

/**
 * @param {number[]} nums
 * @return {string}
 */
var minNumber = function(nums) {
  return nums.sort((a, b) => Number(a + '' + b) -  Number(b + '' + a)).join('');
};

面试题 10.11. 峰与谷

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var wiggleSort = function(nums) {
  let cmp = [
    (a, b) => a > b,
    (a, b) => a < b
  ];
  for (let i = 0; i < nums.length; i ++) {
    let limit = i;
    for (let j = i + 1; j < nums.length; j++) {
      if (cmp[i%2](nums[j], nums[limit])){
        limit = j;
      }
    }
    const t = nums[i];
    nums[i] = nums[limit];
    nums[limit] = t;
  }
  return nums;
};