每日两题 T7
算法
LeetCode T914. 卡牌分组[1]
描述
给定一副牌，每张牌上都写着一个整数。
此时，你需要选定一个数字 X，使我们可以将整副牌按下述规则分成 1 组或更多组：
•每组都有 X 张牌。
•组内所有的牌上都写着相同的整数。
仅当你可选的 X >= 2 时返回 true。
示例 1：
输入：[1,2,3,4,4,3,2,1]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[3,3]，[4,4]示例 2：
输入：[1,1,1,2,2,2,3,3]
输出：false
解释：没有满足要求的分组。示例 3：
输入：[1]
输出：false
解释：没有满足要求的分组。示例 4：
输入：[1,1]
输出：true
解释：可行的分组是 [1,1]示例 5：
输入：[1,1,2,2,2,2]
输出：true
解释：可行的分组是 [1,1]，[2,2]，[2,2]提示：
•1 <= deck.length <= 10000•0 <= deck[i] < 10000
分析
我们发现每个数组必须满足以下条件：
•相同牌的个数必须大于2•不同牌个数可以拆分为相同个数的小组，这点非常关键
为了好记录每张牌的张数，使用 Map 来存放数据。然后获取到存放张数的数组，保证每一项与前一项的最大公约数都大于1。
代码
/**
* @param {number[]} deck
* @return {boolean}
*/
var hasGroupsSizeX = function (deck) {
let m = new Map()
for(let n of deck){
m.set(n,m.has(n)?m.get(n)+1:1)
}
const vals = [...m.values()]
let res = vals[0]
return vals.every(val => (res = calcGcd(res, val)) > 1)
};
function calcGcd(a, b) {
return b === 0 ? a : calcGcd(b, a % b);
}JavaScript
说说setTimeout、Promise、Async/Await 的区别
考虑这个问题，我们首先回顾一个概念：事件循环中的宏任务队列和微任务队列。
•setTimeout的回调函数放到宏任务队列里，等到执行栈清空以后执行•promise.then里的回调函数会放到相应宏任务的微任务队列里，等宏任务里面的同步代码执行完再执行•async函数表示函数里面可能会有异步方法，await后面跟一个表达式，async方法执行时，遇到await会立即执行表达式，然后把表达式后面的代码放到微任务队列里，让出执行栈让同步代码先执行
我们通过简单代码来理解一下
setTimeout
console.log('start')
setTimeout(function(){
console.log('settimeout')
})
console.log('end')
// 输出顺序：start->end->settimeoutPromise
Promise本身是同步的立即执行函数， 当在executor中执行resolve或者reject的时候, 此时是异步操作， 会先执行then/catch等，当主栈完成后，才会去调用resolve/reject中存放的方法执行，打印p的时候，是打印的返回结果，一个Promise实例。
console.log('script start')
let promise1 = new Promise(function (resolve) {
console.log('promise1')
resolve()
console.log('promise1 end')
}).then(function () {
console.log('promise2')
})
setTimeout(function(){
console.log('settimeout')
})
console.log('script end')
// 输出顺序: script start->promise1->promise1 end->script end->promise2->settimeout当JS主线程执行到Promise对象时，
•promise1.then() 的回调就是一个 task•promise1 是 resolved或rejected: 那这个 task 就会放入当前事件循环回合的 microtask queue•promise1 是 pending: 这个 task 就会放入 事件循环的未来的某个(可能下一个)回合的 microtask queue 中•setTimeout 的回调也是个 task ，它会被放入 macrotask queue 即使是 0ms 的情况
async/await
async function async1(){
console.log('async1 start');
await async2();
console.log('async1 end')
}
async function async2(){
console.log('async2')
}
console.log('script start');
async1();
console.log('script end')
// 输出顺序：script start->async1 start->async2->script end->async1 endasync 函数返回一个 Promise 对象，当函数执行的时候，一旦遇到 await 就会先返回，等到触发的异步操作完成，再执行函数体内后面的语句。可以理解为，是让出了线程，跳出了 async 函数体。
最后看看 babel es8 编译 async/await 的结果
async function asyncTest() {
const ret = await asyncFunction();
}转化为
function asyncGeneratorStep(gen, resolve, reject, _next, _throw, key, arg) {
try {
var info = gen[key](arg);
var value = info.value;
} catch (error) {
reject(error);
return;
}
if (info.done) {
resolve(value);
} else {
Promise.resolve(value).then(_next, _throw);
}
}
function _asyncToGenerator(fn) {
return function() {
var self = this,
args = arguments;
return new Promise(function(resolve, reject) {
var gen = fn.apply(self, args);
function _next(value) {
asyncGeneratorStep(gen, resolve, reject, _next, _throw, "next", value);
}
function _throw(err) {
asyncGeneratorStep(gen, resolve, reject, _next, _throw, "throw", err);
}
_next(undefined);
});
};
}
function asyncTest() {
return _asyncTest.apply(this, arguments);
}
function _asyncTest() {
_asyncTest = _asyncToGenerator(function*() {
const ret = yield asyncFunction();
});
return _asyncTest.apply(this, arguments);
}References
[1] 914. 卡牌分组: https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/