第三和第四题都挺有意思, 也有难度
第三题是动态规划, 第四题比较巧妙
/**
* @param {string} s
* @return {number}
*/
var balancedStringSplit = function (s) {
const n = s.length;
if (n < 2) return 0;
let f = s[0] === 'L' ? 1 : -1, r = 0;
for (let i = 1; i < n; i++) {
if (s[i] === 'L')++f;
else --f;
if (f === 0)++r;
}
return r;
};
/**
* @param {number[][]} queens
* @param {number[]} king
* @return {number[][]}
*/
var queensAttacktheKing = function (queens, king) {
const g = new Array(8).fill(0).map(() => new Array(8).fill(0));
g[king[0]][king[1]] = '*';
for (const [x, y] of queens) {
g[x][y] = 1;
}
const res = [];
for (let i = king[0] - 1; i >= 0; i--) if (g[i][king[1]]) { res.push([i, king[1]]); break; }
for (let i = king[0] + 1; i < 8; i++) if (g[i][king[1]]) { res.push([i, king[1]]); break; }
for (let i = king[1] - 1; i >= 0; i--) if (g[king[0]][i]) { res.push([king[0], i]); break; }
for (let i = king[1] + 1; i < 8; i++) if (g[king[0]][i]) { res.push([king[0], i]); break; }
for (let i = king[0] - 1, j = king[1] + 1; i >= 0 && j < 8; i-- , j++) if (g[i][j]) { res.push([i, j]); break; }
for (let i = king[0] + 1, j = king[1] + 1; i < 8 && j < 8; i++ , j++) if (g[i][j]) { res.push([i, j]); break; }
for (let i = king[0] + 1, j = king[1] - 1; i < 8 && j >= 0; i++ , j--) if (g[i][j]) { res.push([i, j]); break; }
for (let i = king[0] - 1, j = king[1] - 1; i >= 0 && j >= 0; i-- , j--) if (g[i][j]) { res.push([i, j]); break; }
return res;
};
/**
* @param {number} n
* @param {number[]} rollMax
* @return {number}
* https://leetcode.com/problems/dice-roll-simulation/discuss/403756/Java-Share-my-DP-solution
*/
var dieSimulator = function (n, rollMax) {
const dp = new Array(7).fill(0).map(() => new Array(n + 1).fill(0));
const d = 10 ** 9 + 7;
for (let i = 0; i < 6; i++) {
dp[i][1] = 1;
}
dp[6][1] = 6;
for (let i = 2; i <= n; i++) {
let sum = 0;
for (let j = 0; j < 6; j++) {
dp[j][i] = dp[6][i - 1];
if (i - rollMax[j] === 1) dp[j][i]--;
if (i - rollMax[j] >= 2) dp[j][i] = (dp[j][i] - (dp[6][i - rollMax[j] - 1] - dp[j][i - rollMax[j] - 1]) + d) % d;
sum = (sum + dp[j][i]) % d;
}
dp[6][i] = sum;
}
return dp[6][n];
};
/**
* @param {number[]} nums
* @return {number}
*/
var maxEqualFreq = function (nums) {
const n = nums.length;
const m = {}; // 记录数字的出现次数
const f = {}; // 记录数字的出现次数的个数
let mf = 0; //记录数字个数的出现次数
let r = 0;
for (let i = 0; i < n; i++) {
if (m[nums[i]])++m[nums[i]];
else m[nums[i]] = 1;
if (!f[m[nums[i]] - 1]) f[m[nums[i]] - 1] = 0;
if (!f[m[nums[i]]]) f[m[nums[i]]] = 0;
--f[m[nums[i]] - 1];
++f[m[nums[i]]];
if (m[nums[i]] > mf) mf = m[nums[i]];
// 三种可能的情况
// 1. 每个数字都只有一个
// 2. 除了一个数字出现一次, 其他数字都出现了 mf 次
// 3. 除了一个数字出现了 mf 次, 其他数字都出现了 mf - 1 次
if (
mf * f[mf] === i || // 情况2
(mf - 1) * (f[mf - 1] + 1) === i || // 情况3
mf === 1 // 情况1
) r = i + 1;
}
return r;
};