5197. 最小绝对差
给你个整数数组 arr，其中每个元素都 不相同。
请你找到所有具有最小绝对差的元素对，并且按升序的顺序返回。
示例 1：
输入：arr = [4,2,1,3] 输出：[[1,2],[2,3],[3,4]]
示例 2：
输入：arr = [1,3,6,10,15] 输出：[[1,3]]
示例 3：
输入：arr = [3,8,-10,23,19,-4,-14,27] 输出：[[-14,-10],[19,23],[23,27]]
提示：
2 <= arr.length <= 10^5-10^6 <= arr[i] <= 10^6
/** * @param {number[]} arr * @return {number[][]} */ var minimumAbsDifference = function(arr) { let res = []; arr.sort((a, b)=>a-b); let c = Infinity; for(let i=0; i<arr.length-1; i++){ let val = arr[i+1]-arr[i]; if(val<c) { c = val res.length = 0; } if(val === c){ let temp = []; temp.push(arr[i], arr[i+1]); res.push(temp) } } return res } /* var minimumAbsDifference = function(arr) { arr.sort((a, b)=>a-b); let map = new Map(); let c = Infinity; for(let i=0; i<arr.length-1; i++){ let val = arr[i+1]-arr[i]; if(val<c) c = val if(map.has(val)){ let v = map.get(val); v.push([arr[i], arr[i+1]]) map.set(val, v) }else{ map.set(val, [[arr[i], arr[i+1]]]) } } for(let [key, val] of map.entries()){ if(key ===c){ return val } } }; */
未解决：
https://leetcode-cn.com/contest/weekly-contest-155
https://coding.imooc.com/lesson/315.html#mid=22379
5198. 丑数 III
请你帮忙设计一个程序，用来找出第 n 个丑数。
丑数是可以被 a 或 b 或 c 整除的正整数。
示例 1：
输入：n = 3, a = 2, b = 3, c = 5 输出：4 解释：The ugly numbers are 2, 3, 4, 5, 6, 8, 9, 10... The 3rd is 4.
示例 2：
输入：n = 4, a = 2, b = 3, c = 4 输出：6 解释：丑数序列为 2, 3, 4, 6, 8, 9, 12... 其中第 4 个是 6。
示例 3：
输入：n = 5, a = 2, b = 11, c = 13 输出：10 解释：丑数序列为 2, 4, 6, 8, 10, 11, 12, 13... 其中第 5 个是 10。
示例 4：
输入：n = 1000000000, a = 2, b = 217983653, c = 336916467 输出：1999999984
提示：
1 <= n, a, b, c <= 10^91 <= a * b * c <= 10^18- 本题结果在
[1, 2 * 10^9]的范围内
/** * @param {number} n * @param {number} a * @param {number} b * @param {number} c * @return {number} */ // class Solution { // long gcd(long a, long b) { // if (b == 0) return a; // return gcd(b, a%b); // } // public int nthUglyNumber(int n, int a, int b, int c) { // long l = 0; // long r = Integer.MAX_VALUE; // while (l + 1 < r) { // long m = (l + r) / 2; // long cnt = m / a; // cnt += m / b; // cnt += m / c; // cnt -= m / ((long)a * b / gcd(a, b)); // cnt -= m / ((long)a * c / gcd(a, c)); // cnt -= m / ((long)b * c / gcd(b, c)); // long tmp = (long)a * b / gcd(a, b); // cnt += m / (tmp*c / gcd(c, tmp)); // if (cnt < n) { // l = m; // } else { // r = m; // } // } // return (int)r; // } // } // 最小公倍数 var gcd=function(a, b) { if (b == 0) return a; return gcd(b, a%b); } var nthUglyNumber = function(n, a, b, c) { let l=0; let r = Infinity; while(l + 1 < r){ let m = parseInt((l+r)/2); let cnt = parseInt(m / a); cnt += m / b; cnt += m / c; cnt -= m / (a * b / gcd(a, b)); cnt -= m / (a * c / gcd(a, c)); cnt -= m / (b * c / gcd(b, c)); let tmp = a * b / gcd(a, b); cnt += m / (tmp*c / gcd(c, tmp)); if (cnt < n) { l = m; } else { r = m; } } return r } /* var nthUglyNumber = function(n, a, b, c) { let s = Math.min(a, b, c) let res = [1]; let i2=0,i3=0,i5=0,i=0; while(i++<n){ let tmp=Math.min(a*res[i2],Math.min(b*res[i3],c*res[i5])); res.push(tmp); if(tmp==a*res[i2]) i2++; if(tmp==b*res[i3]) i3++; if(tmp==c*res[i5]) i5++; } return res.pop() // 超出时间限制 // let s = Math.min(a, b, c), count=0; // while(true){ // if(s%a===0 || s%b===0 || s%c===0) count++; // if(count === n) return s // s++ // } }; */
玩筹码
数轴上放置了一些筹码，每个筹码的位置存在数组 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 <= 1001 <= chips[i] <= 10^9
/**
* @param {number[]} chips
* @return {number}
*/
// 所有的奇数都能在代价0的情况下移动到一个点
// 所有的偶都能在代价0的情况下移动到一个点
// 那下面就比较的是 奇数往偶数移动 还是 偶数往奇数移动
var minCostToMoveChips = function(chips) {
let j = 0, o=0;
chips.forEach(c=>{
if(c%2) {o++;}
else {j++}
})
return j>o? o : j;
};
找出给定方程的正整数解
给出一个函数 f(x, y) 和一个目标结果 z，请你计算方程 f(x,y) == z 所有可能的正整数 数对 x 和 y。
给定函数是严格单调的，也就是说：
f(x, y) < f(x + 1, y)f(x, y) < f(x, y + 1)
函数接口定义如下：
interface CustomFunction {
public:
// Returns positive integer f(x, y) for any given positive integer x and y.
int f(int x, int y);
};
如果你想自定义测试，你可以输入整数 function_id 和一个目标结果 z 作为输入，其中 function_id 表示一个隐藏函数列表中的一个函数编号，题目只会告诉你列表中的 2 个函数。
你可以将满足条件的 结果数对 按任意顺序返回。
示例 1：
输入：function_id = 1, z = 5 输出：[[1,4],[2,3],[3,2],[4,1]] 解释：function_id = 1 表示 f(x, y) = x + y
示例 2：
输入：function_id = 2, z = 5 输出：[[1,5],[5,1]] 解释：function_id = 2 表示 f(x, y) = x * y
提示：
1 <= function_id <= 91 <= z <= 100- 题目保证
f(x, y) == z的解处于1 <= x, y <= 1000的范围内。 - 在
1 <= x, y <= 1000的前提下，题目保证f(x, y)是一个 32 位有符号整数。
/**
* // This is the CustomFunction's API interface.
* // You should not implement it, or speculate about its implementation
* function CustomFunction() {
*
* @param {integer, integer} x, y
* @return {integer}
* this.f = function(x, y) {
* ...
* };
*
* };
*/
/**
* @param {CustomFunction} customfunction
* @param {integer} z
* @return {integer[][]}
*/
var findSolution = function(customfunction, z) {
// const result = [];
// let cY = 1000;
// for (let i = 1; i < 1000; i++) {
// let cZ = customfunction.f(i, cY);
// while (cZ > z && cY > 1) {
// cY--;
// cZ = customfunction.f(i, cY);
// }
// if (cZ === z) {
// result.push([i, cY]);
// }
// }
// return result;
// 下面的超出事件限制
let res = [];
let x = 1;
let flag = true;
for(let y=1; y<=1000; y++){
if(flag){
// 题中 1 <= x, y <= 1000，意思是x 和 y 都是这个范围，我开始以为y<=1000,x>=1,它们又都是正整数，所以 1<=y<=1000
// 导致某种情况，y=xxx, x 就是没有匹配的，x会一直jia,完了就死循环了！！！！！所以才必须加上 cz > z这种情况
while(x>=1){
let cz = customfunction.f(x, y);
if(z===cz){
res.push([x, y]);
flag = false;
break;
// 加上下面代码就测试通过了，其实我感觉最大的问题是x你没上限
} else if(cz>z){
flag = false;
break;
}
x++;
}
} else {
let x0=x;
//fnid=2 y =1, x=5 => x=4, y=2 ; x=3, y=2; x=2,y=2 ; x=1, y=2(这个可以通过条件毙掉)
while(--x0 >=1){
let cz = customfunction.f(x0, y);
if(z===cz){
res.push([x0, y]);
x=x0;
break;
} else if(cz<z) {
break;
}
}
}
}
return res
};
这个题之所以没整出来，
1.理解错题中“处于 1 <= x, y <= 1000 的范围内。”， 写代码的时候，没又把 “
(cz>z)
”
加上，导致可能有某个测试用例的死循环。
// 下面这个还没搞懂
循环码排列
给你两个整数 n 和 start。你的任务是返回任意 (0,1,2,,...,2^n-1) 的排列 p，并且满足：
p[0] = startp[i]和p[i+1]的二进制表示形式只有一位不同p[0]和p[2^n -1]的二进制表示形式也只有一位不同
示例 1：
输入：n = 2, start = 3
输出：[3,2,0,1]
解释：这个排列的二进制表示是 (11,10,00,01)
所有的相邻元素都有一位是不同的，另一个有效的排列是 [3,1,0,2]
示例 2：
输出：n = 3, start = 2 输出：[2,6,7,5,4,0,1,3] 解释：这个排列的二进制表示是 (010,110,111,101,100,000,001,011)
提示：
1 <= n <= 160 <= start < 2^n
/**
* @param {number} n
* @param {number} start
* @return {number[]}
*/
// var replace = function(str, index, replacement){
// return str.substr(0, index) + replacement+ str.substr(index + replacement.length);
// }
var circularPermutation = function(n, start) {
const m = Math.pow(2, n);
const t = [];
for (let i = 0; i < n; i++) {
t.push(Math.pow(2, i));
}
const c = [];
for (let i = 0; i < m; i++) {
c.push(0);
}
const result = [ start ];
c[start] = 1;
for (let i = 1; i < m; i++) {
let j = 0;
while (c[result[i - 1] ^ t[j]]) {
j++;
}
result.push(result[i - 1] ^ t[j]);
c[result[i - 1] ^ t[j]] = 1;
}
return result;
// let res =[];
// let start = String(start).toString(2);
// let arr = start.split('');
// let end = start;
// for(let i=0; i<arr.length; i++){
// if(arr[i]==='0'){
// end = replace(start, i, '1');
// replacefn(end,)
// } else {
// end=replace(start, i, '0')
// }
// }
};
// 其实我的思路是画多叉树，然后递归，感觉是可行的。这个里面他用了二进制异或
替换子串得到平衡字符串
有一个只含有 'Q', 'W', 'E', 'R' 四种字符，且长度为 n 的字符串。
假如在该字符串中，这四个字符都恰好出现 n/4 次，那么它就是一个「平衡字符串」。
给你一个这样的字符串 s，请通过「替换一个子串」的方式，使原字符串 s 变成一个「平衡字符串」。
你可以用和「待替换子串」长度相同的 任何 其他字符串来完成替换。
请返回待替换子串的最小可能长度。
如果原字符串自身就是一个平衡字符串，则返回 0。
示例 1：
输入：s = "QWER" 输出：0 解释：s 已经是平衡的了。
示例 2：
输入：s = "QQWE" 输出：1 解释：我们需要把一个 'Q' 替换成 'R'，这样得到的 "RQWE" (或 "QRWE") 是平衡的。
示例 3：
输入：s = "QQQW" 输出：2 解释：我们可以把前面的 "QQ" 替换成 "ER"。
示例 4：
输入：s = "QQQQ" 输出：3 解释：我们可以替换后 3 个 'Q'，使 s = "QWER"。
提示：
1 <= s.length <= 10^5s.length是4的倍数s中只含有'Q','W','E','R'四种字符
/**
* @param {string} s
* @return {number}
*/
var balancedString = function(s) {
// let s1 = {
// 'Q': 0,
// 'W':0,
// 'E':0,
// 'R':0
// };
// s.split('').forEach(item=>s1[item]++);
// let n = s.length/4;
// let res=0;
// Object.keys(s1).forEach(item=>{
// console.log('item: ',item,' ',s1[item])
// if(s1[item]<n){
// res+=(n-s1[item])
// }
// });
// return res
// 待替换子串 不是单纯的统计
const r = [0 , 0, 0, 0];
const a = {Q : 0, W: 1, E: 2, R: 3};
for (let i = 0; i < s.length; i++) {
r[a[s[i]]]++;
}
const n = s.length / 4;
if (r[0] === r[1] && r[1] === r[2] && r[2] === r[3]) return 0;
let l = 0;
let m = 100001;
for (let i = 0; i < s.length; i++) {
r[a[s[i]]]--;
while (r[0] <= n && r[1] <=n && r[2] <=n && r[3] <= n) {
m = Math.min(m, i + 1 - l);
r[a[s[l]]]++;
l++;
}
}
return m;
};
交换字符使得字符串相同
有两个长度相同的字符串 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 <= 1000s1, s2只包含'x'或'y'。
/**
* @param {string} s1
* @param {string} s2
* @return {number}
*/
var minimumSwap = function(s1, s2) {
let l = 0;
let r = 0;
for (let i = 0; i < s1.length; i++) {
if (s1[i] !== s2[i]) {
if (s1[i] === 'x') {
l++;
} else {
r++;
}
}
}
if ((l + r) % 2 === 1) return -1;
return (l + r) / 2 + (l % 2);
};
if(s1.length != s2.length) return -1; let x=0,y=0; for(let i=0;i<s1.length;++i) if(s1[i]=='x') x++;else y++; for(let i=0;i<s2.length;++i) if(s2[i]=='x') x++;else y++; if(x%2 || y%2) return -1; let cnt1=0,cnt2=0; for(let i=0;i<s1.length;++i) { if(s1[i] != s2[i]) { if(s1[i]=='x') cnt1++; else cnt2++; } } return parseInt((cnt1+1)/2)+parseInt((cnt2+1)/2);
var minimumSwap = function(s, t) {
let n = s.length;
let x = 0, y = 0;
for (let i = 0; i < n; ++ i)
{
if (s[i] == t[i]) continue;
if (s[i] == 'x') ++ x; else ++ y;
}
if ((x+y)%2 == 1) return -1;
let ret = parseInt(x/2)+ parseInt(y/2);
x %= 2;
y %= 2;
if (x || y) ret += 2;
return ret;
xy yy xy
yx xx xy
xxy yxy(yy) xxy(xy)
yxx xxx(xx) xxy(xy)
xyxy yyxy yxxy
yxyx yxxx yxxy
这个我当时也在尽力找规律，找了1个半小时也没找到点决定性的规律
var minimumSwap = function(s1, s2) { let s = s1+s2; let map = new Map(); let x=0, y=0; for(let i=0; i<s.length; i++){ if('x'===s[i]){ map.set('x',++x) }else { map.set('y',++y) } } // 个数必须是偶数个 if(map.get('x')%2 !==0 || map.get('y')%2!==0){ return -1 } let first=s1[0], flag = true; for(let i=1; i<s1.length; i++){ if(s[i]!==first){ flag = false } } // 都相同的情况，交换次数是len/2 if(flag) return s1/2; let count=0 if(s1.length) };
统计「优美子数组」
给你一个整数数组 nums 和一个整数 k。
如果某个子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。
请返回这个数组中「优美子数组」的数目。
示例 1：
输入：nums = [1,1,2,1,1], k = 3 输出：2 解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：
输入：nums = [2,4,6], k = 1 输出：0 解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：
输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2 输出：16
提示：
1 <= nums.length <= 500001 <= nums[i] <= 10^51 <= k <= nums.length
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var numberOfSubarrays = function(nums, k) {
let result = 0;
let odd = [ -1 ];
for (let i = 0; i < nums.length; i++) {
if (nums[i] % 2 === 1) {
odd.push(i);
if (odd.length > k + 1) {
result += (odd[odd.length - 1] - odd[odd.length - 2]) * (odd[odd.length - 1 - k] - odd[odd.length - 2 - k]);
}
}
}
if (odd.length > k) {
result += (nums.length - odd[odd.length - 1]) * (odd[odd.length - k] - odd[odd.length -1 - k]);
}
return result;
};
给你一个 n 行 m 列的矩阵，最开始的时候，每个单元格中的值都是 0。
另有一个索引数组 indices，indices[i] = [ri, ci] 中的 ri 和 ci 分别表示指定的行和列（从 0 开始编号）。
你需要将每对 [ri, ci] 指定的行和列上的所有单元格的值加 1。
请你在执行完所有 indices 指定的增量操作后，返回矩阵中 「奇数值单元格」 的数目。
示例 1：
输入：n = 2, m = 3, indices = [[0,1],[1,1]] 输出：6 解释：最开始的矩阵是 [[0,0,0],[0,0,0]]。 第一次增量操作后得到 [[1,2,1],[0,1,0]]。 最后的矩阵是 [[1,3,1],[1,3,1]]，里面有 6 个奇数。
示例 2：
输入：n = 2, m = 2, indices = [[1,1],[0,0]] 输出：0 解释：最后的矩阵是 [[2,2],[2,2]]，里面没有奇数。
提示：
1 <= n <= 501 <= m <= 501 <= indices.length <= 1000 <= indices[i][0] < n0 <= indices[i][1] < m
/** * @param {number} n * @param {number} m * @param {number[][]} indices * @return {number} */ const flatten = arr => arr.reduce( (acc,val) => acc.concat(Array.isArray(val)? flatten(val):val),[] ) var oddCells = function(n, m, indices) { let arr = []; let m0=m; while(n--){ let a = []; while(m0--){ a.push(0) } m0=m; arr.push(a) }; indices.forEach(d=>{ let [r, c] = d; /*为什么在控制台操作就可以,因为这里是给数据直接赋值。而下面map是返回新数组，forEach虽是循环但你的操作是仅仅是+1的话， 就好比 arr[1] + 1,这个只会返回一个新值，必须重新赋值 arr[1] = arr[1] + 1；类似var a = 1; a+1 与 a = a+1 不同 let a = [[1,2,3],2,3]; a[0][1]=100 100 let arr = [1,2,3]; arr[0]=100 100 */ arr[r] = arr[r].map(a=>a+1); arr.forEach(a=>a[c] = a[c]+1) }) // return arr.flat().filter(f=>f%2===1).length return flatten(arr).filter(f=>f%2===1).length };