豆包 LeetCode 3782. 交替删除操作后最后剩下的整数 TypeScript实现

TypeScript / JavaScript 实现 LeetCode 3782 lastInteger题意回顾初始数组 [1,2,3,...,n] 交替执行删除1. 第一轮从左删隔一删一保留奇数位置2. 第二轮从右删隔一删一循环直到只剩一个数返回结果数据极大1e15不能模拟数组用迭代 O(logn) 最优解法迭代 O(logn) 版本无递归大数安全typescriptfunction lastInteger(n: number): number {let start 1;let end n;let step 1;let remain n;while (remain 1) {// 从左侧删除一轮if (remain % 2 1) {end - step;}// 切换为从右侧删翻转区间步长取反翻倍[start, end] [end, start];step * -2;remain Math.floor((remain 1) / 2);}return start;}递归简洁版逻辑直观n极大时栈深很小ACtypescriptfunction lastInteger(n: number): number {if (n 1) return 1;const m Math.floor((n 1) / 2);return 2 * (m 1 - lastInteger(m)) - 1;}JS 原生版本去掉类型标注浏览器/Node直接运行javascriptfunction lastInteger(n) {let start 1, end n, step 1, remain n;while (remain 1) {if (remain % 2 1) end - step;[start, end] [end, start];step * -2;remain (remain 1) 1;}return start;}测试样例typescriptconsole.log(lastInteger(1)); // 1console.log(lastInteger(5)); // 1console.log(lastInteger(8)); // 3复杂度- 时间O(\log n)每次数量折半- 空间迭代版 O(1)递归版 O(\log n)