贪心 - 计数 - 《算法》

409. 最长回文串

/**
 * @param {string} s
 * @return {number}
 */
var longestPalindrome = function(s) {
  const r = {};
  for (let i = 0; i < s.length; i++) {
    r[s.charAt(i)] = r[s.charAt(i)] || 0;
    r[s.charAt(i)] += 1;
  }
  let ans = 0, hasSingle = false;
  Object.values(r).forEach(v => {
    if (v % 2 === 1) {
      hasSingle = true;
    }
    ans += (v >> 1);
  });
  return ans*2 + (hasSingle ? 1: 0);
};

680. 验证回文字符串 Ⅱ

/**
 * @param {string} s
 * @return {boolean}
 */
var validPalindrome = function(s) {
  let l = 0, r = s.length-1, k = 1;
  while (l < r) {
    if (s.charAt(l) === s.charAt(r)) {
      l++;
      r--;
    } else {
      if (k > 0) {
        k--;
        return check(s, l + 1, r) || check(s, l, r - 1);
      }
      return false;
    }
  }
  return true;
};
function check(s, l, r) {
  while (l < r) {
    if (s.charAt(l) === s.charAt(r)) {
      l++;
      r--;
      continue;
    }
    return false;
  }
  return true;
}

class Solution {
public:
    bool palindrome(const std::string& s, int i, int j)
    {
        for ( ; i < j && s[i] == s[j]; ++i, --j);
        return i >= j;
    }
    bool validPalindrome(string s) {
        int i = 0, j = s.size() - 1;
        for ( ; i < j && s[i] == s[j]; ++i, --j);        
        return palindrome(s, i, j - 1) || palindrome(s, i + 1, j);
    }
};

316. 去除重复字母

思路一：单调递增栈 + 计数保护

要使得字典序最小，则必须单调递增序，所以维护一个单调递增栈，来选择保留哪些字符。
另外，为了防止某些不满足单调性的个别字符被弹出，需要检测弹出的字符是否在后续还有，如果没有，则不弹出，不然找了一个字符

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function(s) {
  const counts = new Array(128).fill(0);
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i);
    counts[c] += 1;
  }
  const r = [], joined = new Set();
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i);
    // joined 用来记录已经添加了哪些字符。
    if (!joined.has(c)) {
      // 当栈顶字符的计数大于1且比当前遍历字符大，才可以弹出，不然留在栈中。
      while (r.length && counts[r[r.length - 1]] > 1 && r[r.length - 1] > c) {
        const t = r.pop();
        // 弹出时要计数减一，且从joined中删除。
        counts[t] -= 1;
        joined.delete(t);
      }
      r.push(c);
      joined.add(c);
    } else {
      // 已经添加了，计数减一
      counts[c] -= 1;
    }
  }
  return r.map(i => String.fromCharCode(i)).join('');
};

765. 情侣牵手

N 对情侣坐在连续排列的 2N 个座位上，想要牵到对方的手。计算最少交换座位的次数，以便每对情侣可以并肩坐在一起。一次交换可选择任意两人，让他们站起来交换座位。

人和座位用 0 到 2N-1 的整数表示，情侣们按顺序编号，第一对是 (0, 1)，第二对是 (2, 3)，以此类推，最后一对是 (2N-2, 2N-1)。

这些情侣的初始座位 row[i] 是由最初始坐在第 i 个座位上的人决定的。

示例 1:

输入: row = [0, 2, 1, 3]
输出: 1
解释: 我们只需要交换row[1]和row[2]的位置即可。
示例 2:

输入: row = [3, 2, 0, 1]
输出: 0
解释: 无需交换座位，所有的情侣都已经可以手牵手了。
说明:

len(row) 是偶数且数值在 [4, 60]范围内。
可以保证row 是序列 0…len(row)-1 的一个全排列。

至少交换的次数 = 所有情侣的对数 - 并查集里连通分量的个数

/**
 * @param {number[]} row
 * @return {number}
 */
var minSwapsCouples = function(row) {
  let len = row.length;
  let N = len >>> 1;
  const unionFind = new UnionFind(N);
  for (let i = 0; i < len; i += 2) {
    unionFind.union(row[i] >>> 1, row[i + 1] >>> 1);
  }
  return N - unionFind.getCount();
};

class UnionFind {
  constructor(n) {
    this.count = n;
    this.parent = new Array(n).fill(-1);
    for (let i = 0; i < n; i++) {
      this.parent[i] = i;
    }
  }
  getCount() {
    return this.count;
  }

  find(x) {
    while (x != this.parent[x]) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }

  union(x, y) {
    let rootX = this.find(x);
    let rootY = this.find(y);
    if (rootX == rootY) {
      return;
    }

    this.parent[rootX] = rootY;
    this.count--;
  }
}

1217. 玩筹码

难度简单94收藏分享切换为英文接收动态反馈
数轴上放置了一些筹码，每个筹码的位置存在数组 chips 当中。
你可以对 任何筹码 执行下面两种操作之一（不限操作次数，0 次也可以）：

将第 i 个筹码向左或者右移动 2 个单位，代价为 0。
将第 i 个筹码向左或者右移动 1 个单位，代价为 1。

最开始的时候，同一位置上也可能放着两个或者更多的筹码。
返回将所有筹码移动到同一位置（任意位置）上所需要的最小代价。

示例 1：
输入：chips = [1,2,3] 输出：1 解释：第二个筹码移动到位置三的代价是 1，第一个筹码移动到位置三的代价是 0，总代价为 1。
示例 2：
输入：chips = [2,2,2,3,3] 输出：2 解释：第四和第五个筹码移动到位置二的代价都是 1，所以最小总代价为 2。

提示：

1 <= chips.length <= 100
1 <= chips[i] <= 10^9

思路：由题意可知，移动偶数个位置代价为0，奇数个位置代价为1，所以可以
1、将所有的奇数位置筹码移动到 1处。
2、将所有的偶数位置筹码移动到0处。
3、然后比较两者的数量，那个少移动那个。

/**
 * @param {number[]} position
 * @return {number}
 */
var minCostToMoveChips = function(position) {
  const len = position.length;
  let count = 0;
  for (let i = 0; i < len; i++) {
    if (position[i] % 2 === 0) {
      count += 1;
    }
  }
  return Math.min(count, len - count);
};

难度中等45收藏分享切换为英文接收动态反馈
有两个长度相同的字符串 s1 和 s2，且它们其中 只含有 字符 “x” 和 “y”，你需要通过「交换字符」的方式使这两个字符串相同。
每次「交换字符」的时候，你都可以在两个字符串中各选一个字符进行交换。
交换只能发生在两个不同的字符串之间，绝对不能发生在同一个字符串内部。也就是说，我们可以交换 s1[i] 和 s2[j]，但不能交换 s1[i] 和 s1[j]。
最后，请你返回使 s1 和 s2 相同的最小交换次数，如果没有方法能够使得这两个字符串相同，则返回 -1 。

示例 1：
输入：s1 = “xx”, s2 = “yy”
输出：1
解释： 交换 s1[0] 和 s2[1]，得到 s1 = “yx”，s2 = “yx”。
示例 2：
输入：s1 = “xy”, s2 = “yx”
输出：2
解释： 交换 s1[0] 和 s2[0]，得到 s1 = “yy”，s2 = “xx” 。交换 s1[0] 和 s2[1]，得到 s1 = “xy”，s2 = “xy” 。注意，你不能交换 s1[0] 和 s1[1] 使得 s1 变成 “yx”，因为我们只能交换属于两个不同字符串的字符。
示例 3：
输入：s1 = “xx”, s2 = “xy”
输出：-1
示例 4：
输入：s1 = “xxyyxyxyxx”, s2 = “xyyxyxxxyx”
输出：4

提示：

1 <= s1.length, s2.length <= 1000
s1, s2 只包含 ‘x’ 或 ‘y’。

思路：

字符不相等分为两种情况讨论：

情况	S1	S2	交换次数
一	xy	yx	2
二	xx	yy	1

因此在遍历时分别统计这两种情况的数量，最后再统一计算需要交换的次数。
第二步：得出结论，假设最终有M对xy，N对yx
1、计数 - 图1
2、
若M为偶数，则N也为偶数，则全部为(a)类交换。总匹配数为：计数 - 图2
若M为奇数，则N也为奇数，则各拿一组进行(b)类交换，其余(a)类交换。总匹配数为：计数 - 图3
两者均可写作：计数 - 图4

/**
 * @param {string} s1
 * @param {string} s2
 * @return {number}
 */
var minimumSwap = function(s1, s2) {
  let xy = 0; yx = 0;
  for (let i = 0; i < s1.length; i++) {
    if (s1.charAt(i) === s2.charAt(i)) continue;
    if (s1.charAt(i) === 'x') xy += 1;
    if (s1.charAt(i) === 'y') yx += 1;
  }

  if ((xy + yx) % 2 !== 0) {
    return -1;
  }
  return (( 1 + xy) >>> 1) + ((yx + 1) >>> 1);
};

1400. 构造 K 个回文字符串

难度中等28收藏分享切换为英文接收动态反馈
给你一个字符串 s 和一个整数 k 。请你用 s 字符串中 所有字符 构造 k 个非空 回文串 。
如果你可以用 s 中所有字符构造 k 个回文字符串，那么请你返回 True ，否则返回 False 。

示例 1：
输入：s = “annabelle”, k = 2
输出：true
解释：可以用 s 中所有字符构造 2 个回文字符串。一些可行的构造方案包括：”anna” + “elble”，”anbna” + “elle”，”anellena” + “b”
示例 2：
输入：s = “leetcode”, k = 3
输出：false
解释：无法用 s 中所有字符构造 3 个回文串。
示例 3：
输入：s = “true”, k = 4
输出：true
解释：唯一可行的方案是让 s 中每个字符单独构成一个字符串。
示例 4：
输入：s = “yzyzyzyzyzyzyzy”, k = 2
输出：true
解释：你只需要将所有的 z 放在一个字符串中，所有的 y 放在另一个字符串中。那么两个字符串都是回文串。
示例 5：
输入：s = “cr”, k = 7
输出：false
解释：我们没有足够的字符去构造 7 个回文串。

提示：

1 <= s.length <= 10^5
s 中所有字符都是小写英文字母。

1 <= k <= 10^5

/**
* @param {string} s
* @param {number} k
* @return {boolean}
*/
var canConstruct = function(s, k) {
const len = s.length;
if (len < k) return false;
const cmaps = new Array(26).fill(0);
const base = 'a'.charCodeAt(0);
let left = 0;
for (let i = 0; i < len; i++) {
  let char = s.charCodeAt(i) - base;
  cmaps[char] ^= 1;  // 计算奇偶性
  left += cmaps[char] === 1 ? 1 : -1; // 计算奇数数量
}
return k >= left && k <= len; // k 在最小（左边界）和最大（右边界）之间即可
};

921. 使括号有效的最少添加

难度中等97收藏分享切换为英文接收动态反馈
给定一个由 ‘(‘ 和 ‘)’ 括号组成的字符串 S，我们需要添加最少的括号（ ‘(‘ 或是 ‘)’，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：

它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。

给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。

示例 1：
输入：“())” 输出：1
示例 2：
输入：“(((“ 输出：3
示例 3：
输入：“()” 输出：0
示例 4：
输入：“()))((“ 输出：4

提示：

S.length <= 1000
S 只包含 ‘(‘ 和 ‘)’ 字符。

/**
 * @param {string} s
 * @return {number}
 */
var minAddToMakeValid = function(s) {
  let sum = 0, ans = 0;
  for (let i = 0; i < s.length; i++) {
    sum += s[i] === ')' ? -1 : 1;
    if (sum === -1) {
      sum += 1;
      ans += 1;
    }
  }
  return ans + sum;
};

678. 有效的括号字符串

思路一：栈，对号单独见栈，在匹配时根据情况从栈中弹出。

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  const check = (str) => {
    const t = [], star = [];
    for (let i = 0; i < str.length; i++) {
      const current = str.charAt(i);
      if (current === '(') {
        t.push(i);
      }
      if (current === '*') {
        star.push(i);
      }
      if (current === ')') {
        if (t.length) {
          t.pop();
        } else if (star.length) {
          // case 1, 前面已经没有左括号了，需要消耗*栈
          star.pop();
        } else {
          return false;
        }
      }
    }
    // case 2: 左括号比剩余的*栈数量多，多余的左括号无法匹配
    if (t.length > star.length) {
      return false;
    }
    // case 3: 检查每个左括号和*号的消耗的先后顺序，*号需要在左括号后面，如果不是，则说明不匹配。
    while (t.length && star.length) {
      if (star[star.length - 1] < t[t.length - 1]) {
        return false;
      }
      star.pop();
      t.pop();
    }

    return true;
  };
  return check(s);
};

思路二：插旗法

统计两个计数，分别时左括号和右括号，
left：从左向右检查第i个字符，遇到右括号减一，否则加一，
right：从右向左检查第 len - 1 - i个字符，遇到左括号减一，否则加一

/**
 * @param {string} s
 * @return {boolean}
 */
var checkValidString = function(s) {
  let left = 0, right = 0, len = s.length;
  for (let i = 0; i < s.length; i++) {
    left += s.charAt(i) === ')' ? -1: 1;
    right +=  s.charAt(len - 1 - i) === '(' ? -1 : 1;
    if (left < 0 || right < 0) {
      return false;
    }
  }
  return true;
};

1221. 分割平衡字符串

/**
 * @param {string} s
 * @return {number}
 */
var balancedStringSplit = function(s) {
  let c = 0, ans = 0;
  for (let i = 0; i < s.length; i++) {
    const ch = s.charAt(i);
    c += (ch === 'L' ? 1 : -1);
    if (c === 0) {
      ans++;
    }
  }
  return ans;
};

611. 有效三角形的个数

思路一：暴力搜索，三层循环

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
  let ans = 0;
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length; k++) {
        if (nums[i] + nums[j] > nums[k] && nums[i] + nums[k] > nums[j] && nums[j] + nums[k] > nums[i]) {
          ans += 1;
        }
      }
    }
  }
  return ans;
};

思路一：暴力搜索 + 剪枝

考虑固定两条边，第三边需要小于前两边之和，减小第三层循环的数量，另外由于已经排序，所以最内层的if条件已经不需要了。

更近一步的优化是，第三层循环使用二分法查找第三边的上界。

/**
 * @param {number[]} nums
 * @return {number}
 */
var triangleNumber = function(nums) {
  let ans = 0;
  nums.sort((a, b) => a-b);
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      for (let k = j + 1; k < nums.length && (nums[k] < (nums[i] + nums[j])); k++) {
        ans += 1;
      }
    }
  }
  return ans;
};

781. 森林中的兔子

如果有 xx 只兔子都回答 yy，则至少有计数 - 图5 种不同的颜色，且每种颜色有 y+1只兔子，因此兔子数至少为计数 - 图6 ，我们可以用哈希表统计answers中各个元素的出现次数，对每个元素套用上述公式计算，并将计算结果累加，即为最终答案。

/**
 * @param {number[]} answers
 * @return {number}
 */
var numRabbits = function(answers) {
  if (!answers.length) {
    return 0;
  }
  const r = new Array(1001).fill(0);
  for (let i = 0; i < answers.length; i++) {
    r[answers[i]] += 1;
  }

  let ans = 0;
  for (let i = 0; i < r.length; i++) {
    if (r[i] !== 0 ) {
      ans += Math.ceil(r[i]/(i+1)) * (i+1);
    }
  }
  return ans;
};

861. 翻转矩阵后的得分

/**
 * @param {number[][]} grid
 * @return {number}
 */
var matrixScore = function(grid) {
  let m = grid.length;
  let n = grid[0].length;

  let ans = m * (1 << (n - 1) );
  for (let i = 1; i < n; i++) {
    let one = 0;
    for(let r = 0; r < m; r++) {
      if (grid[r][0] === 0) {
        one += (1 - grid[r][i]);
      } else {
        one += grid[r][i];
      }
    }
    ans += Math.max(one, m - one) * (1 << (n - i - 1) );
  }
  return ans;
};

954. 二倍数对数组

/**
 * @param {number[]} arr
 * @return {boolean}
 */
var canReorderDoubled = function(arr) {
  let maps = new Map(), sum = arr.length;
  for (let i = 0; i < arr.length; i++) {
    maps.set(arr[i], (maps.get(arr[i]) || 0) + 1);
  }
  const values = arr.sort((a, b) => Math.abs(a) - Math.abs(b));
  for (let i = 0; i < values.length && maps.size; i++) {
    let n = values[i], target = 2 * n;
    if (maps.get(n) === 0) {
      continue;
    };
    if (!maps.has(target)) return false;
    maps.set(n, maps.get(n) - 1);
    maps.set(target, maps.get(target) - 1);
    sum -= 2;
  }
  return sum === 0;
};

991. 坏了的计算器

/**
 * @param {number} x
 * @param {number} y
 * @return {number}
 */
var brokenCalc = function(x, y) {
  if (x > y) return x - y;
  let ans = 0;
  while (y > x) {
    ans++;
    if (y % 2 === 1 ) {
      y ++;
      ans ++;
    }
    y /= 2;
  }
  return ans + x - y;
};

1005. K 次取反后最大化的数组和

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function(nums, k) {
  nums.sort((a, b) => Math.abs(b) - Math.abs(a));
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] < 0 && k) {
      k--;
      nums[i] *= -1;
    }
  }
  if (k % 2 === 1) {
    nums[nums.length - 1] *= -1;
  }
  return nums.reduce((r, e) => r + e, 0);
};

1262. 可被三整除的最大和

/**
 * @param {number[]} nums
 * @return {number}
 */
var maxSumDivThree = function(nums) {
  let dp = [0, Number.NEGATIVE_INFINITY, Number.NEGATIVE_INFINITY];
  let first = dp[0], secod = dp[1], third = dp[2], k = nums[0];
  for (let i = 1; i <= nums.length; i++) {
    k = nums[i - 1];
    first = k + dp[(3 - (k % 3)) % 3];
    secod = k + dp[(3 - (k % 3) + 1) % 3];
    third = k + dp [(3 - (k % 3) + 2) % 3];
    if (first > dp[0]) {
      dp[0] = first;
    }
    if (secod > dp[1]) {
      dp[1] = secod;
    }
    if (third > dp[2]) {
      dp[2] = third;
    }
  }
  return dp[0];
};

1488. 避免洪水泛滥

/**
 * @param {number[]} rains
 * @return {number[]}
 */
var avoidFlood = function(rains) {
  const water = new Map(), zero = new Set();
  const ans = new Array(rains.length).fill(1);

  const findWaterDay = (left) => {
    for (let d of zero) {
      if (d > left) {
        return d;
      }
    }
    return -1;
  };

  for (let i = 0; i < rains.length; i++) {
    const lakeNo = rains[i];
    if (lakeNo === 0) {
      zero.add(i);
      continue;
    }
    if (water.has(lakeNo)) {
      let zeroDay = findWaterDay(water.get(lakeNo));
      if (zeroDay === -1) {
        return [];
      }
      ans[zeroDay] = lakeNo;
      zero.delete(zeroDay);
    }
    water.set(lakeNo, i);
    ans[i] = -1;
  }
  return ans;
};

1647. 字符频次唯一的最小删除次数

/**
 * @param {string} s
 * @return {number}
 */
var minDeletions = function(s) {
  let maps = new Array(26).fill(0), base = 'a'.charCodeAt(0);
  for (let i = 0; i < s.length; i++) {
    maps[s.charCodeAt(i) - base]++;
  }
  const sorts = maps.sort((a, b) => b - a);
  let ans = 0, top = sorts[0];
  for (let i = 1; i < sorts.length; i++) {
    if (sorts[i] >= top) {
      // 从最多到最少，依次删除一个。
      ans += sorts[i] - Math.max(0, top - 1);
      top --;
    } else {
      top = sorts[i];
    }
  }
  return ans;
};

1689. 十-二进制数的最少数目

/**
 * @param {string} n
 * @return {number}
 */
var minPartitions = function(n) {
  let base = 48, ans = 0;
  for (let i = 0; i < n.length; i++) {
    ans = Math.max(n.charCodeAt(i) - base, ans);
  }
  return ans;
};

1996. 游戏中弱角色的数量

/**
 * @param {number[][]} properties
 * @return {number}
 */
var numberOfWeakCharacters = function(properties) {
  properties.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    }
    return b[0] - a[0];
  });

  let max = Number.MIN_SAFE_INTEGER, r = 0, ans = 0;
  while (r < properties.length) {
    if (max > properties[r][1]) {
      ans ++;
    }
    max = Math.max(max, properties[r][1]);
    r++;
  }
  return ans;
};