算法面试题（山月）
如何实现一个优先级队列
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 49(opens new window)
Author
回答者: hx-code(opens new window)
// 封装优先级队列 function PriorityQueue() { // 在 PriorityQueue 中重新创建一个类，和 java 中的内部类很相似 function QueueElement(element, priority) { this.element = element; this.priority = priority; } // 封装属性，用数组来存储队列 this.items = [];
// 入队
PriorityQueue.prototype.enQueue = function (element, priority) {
// 1.创建对象
var queueElement = new QueueElement(element, priority);
// 2.判断队列是否为空
if(this.items.length == 0)
this.items.push(queueElement);
else {
var flag = false;
for(var i = 0; i< this.items.length; i++){
if(queueElement.priority < this.items[i].priority){
this.items.splice(i,0,queueElement);
flag = true;
break;
}
}
if(!flag)
this.items.push(queueElement);
}
}
// 2.出队
PriorityQueue.prototype.deQueue = function () {
return this.items.shift();
}
// 3.查看队头元素
PriorityQueue.prototype.front = function() {
return this.items[0];
}
// 4.判断队列是否为空
PriorityQueue.prototype.isEmpty = function() {
return this.items.length == 0;
}
// 5.查看队列中元素的个数
PriorityQueue.prototype.size = function() {
return this.items.length;
}
// 6.将队列元素按字符串格式输出
PriorityQueue.prototype.toString = function() {
var result = "";
for(var i = 0; i < this.items.length; i++)
result += this.items[i].element + " ";
return result;
}
}
Author
回答者: someGenki(opens new window)
基于最大堆实现优先队列
class MaxHeap {
constructor(arr = []) {
this.heap = []; // 用数组表示堆结构
arr.forEach((item) => this.add(item));
}
add(value) {
// O(logK) 插入节点值: 放入数组末尾并上浮到合适位置
this.heap.push(value);
this.shiftUp(this.heap.length - 1);
}
pop() {
// O(logK) 提取最大值/堆顶: 提取 heap[0] 并用 heap[-1] 进行代替，然后从顶部开始下沉到合适位置
const max = this.heap[0];
this.swap(0, this.size() - 1);
this.heap.pop();
this.shiftDown(0);
return max;
}
peek() {
// 获取最值/堆顶
return this.heap[0];
}
size() {
// 获取当前堆大小
return this.heap.length;
}
// ↓私有属性↓
swap(index1, index2) {
// 交换节点位置
const temp = this.heap[index1];
this.heap[index1] = this.heap[index2];
this.heap[index2] = temp;
}
parentIndex(index) {
// 获取父节点的位置 (index - 1) / 2 向下取整
return (index - 1) >> 1;
}
leftChildIndex(index) {
// 获取左子节点
return index * 2 + 1;
}
rightChildIndex(index) {
// 获取右子节点
return index * 2 + 2;
}
shiftUp(index) {
// 上浮节点，当前值小于父节点值时停止，使当前堆保持最大堆的性质
let parentIndex = this.parentIndex(index);
while (index > 0 && this.heap[parentIndex] < this.heap[index]) {
this.swap(index, parentIndex);
parentIndex = this.parentIndex((index = parentIndex));
}
}
shiftDown(index) {
// 下沉节点，当前值大于子节点值时停止，使当前堆保持最大堆的性质
const leftIndex = this.leftChildIndex(index);
const rightIndex = this.rightChildIndex(index);
// 先比较左子节点值，当前值小于左子节点，则交换,并递归进行下沉
if (this.heap[index] < this.heap[leftIndex]) {
this.swap(leftIndex, index);
this.shiftDown(leftIndex);
}
if (this.heap[index] < this.heap[rightIndex]) {
this.swap(rightIndex, index);
this.shiftDown(rightIndex);
}
}
}
// ==TEST==
const priorityQueue = new MaxHeap([2, 5, 3]);
console.log(priorityQueue.peek()); // 5
priorityQueue.add(7);
console.log(priorityQueue.peek()); // 7
priorityQueue.pop();
priorityQueue.add(1);
console.log(priorityQueue.peek()); // 5
如何判断两个链表是否相交
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 62(opens new window)
Author
只判断链表相交，好一点的方式是用双指针+哈希表。 同时遍历 a，b 链表，如果当前 a 和 b 所在元素不在哈希表，则将元素加入哈希表。知道找到哈希表里面重复元素则算相交。时间复杂度 o(max(a, b))是 a，b 不想交部分的较大值。空间复杂度是 o(a + b)，a 和 b 不想交部分。
第二种是遍历 a 和 b，判断尾指针是否相等。时间复杂度 o(a + b)，空间复杂度 o(1)。
进阶问题是，找到相交链表的第一个相交点
Author
回答者: shfshanyue(opens new window)
TODO
如何实现一个 LRU
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 94(opens new window)
Author
回答者: manyyuri(opens new window)
leetcode149
- 用双向链表+哈希。
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.map = new Map();
this.cache = new DoubleList();
};
class Node {
constructor(k, val) {
this.k = k;
this.val = val;
this.pre = null;
this.next = null;
}
}
class DoubleList {
constructor() {
this.size = 0;
this.head = new Node(0, 0);
this.tail = new Node(0, 0);
this.head.next = this.tail;
this.tail.pre = this.head;
}
addLast(x) {
const { head, tail } = this;
x.pre = tail.pre;
x.next = tail;
tail.pre.next = x;
tail.pre = x;
this.size++;
}
remove(x) {
x.pre.next = x.next;
x.next.pre = x.pre;
this.size--;
}
removeFirst() {
const { head, tail } = this;
if (head.next === tail) return null;
let first = head.next;
this.remove(first);
return first;
}
}
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
const { cache, map } = this;
if (map.has(key)) {
let x = map.get(key);
cache.remove(x);
cache.addLast(x);
return map.get(key).val;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
const { cache, map, size } = this;
const addRecently = function (key, value) {
let x = new Node(key, value);
cache.addLast(x);
map.set(key, x);
};
if (map.has(key)) {
let x = map.get(key);
cache.remove(x);
map.delete(key);
addRecently(key, value);
} else {
if (cache.size === this.capacity) {
let x = cache.removeFirst();
map.delete(x.k);
}
addRecently(key, value);
}
};
- Map 的巧妙使用 map 放入数据是按顺序的，最新放入的数据在迭代器最后 而且 map 的 entries 方法，还有 keys 方法，会返回一个迭代器，迭代器调用 next 也是顺序返回，所以返回第一个的值就是最老的，找到并删除即可
/**
* @param {number} capacity
*/
var LRUCache = function (capacity) {
this.capacity = capacity;
this.map = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function (key) {
const map = this.map;
let val = map.get(key);
if (val !== undefined) {
map.delete(key);
map.set(key, val);
return val;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function (key, value) {
const { map, capacity } = this;
if (map.has(key)) map.delete(key);
map.set(key, value);
if (map.size > capacity) {
map.delete(map.entries().next().value[0]);
}
};
如何在数组中找出三个数之和为 N
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 177(opens new window)
Author
排序之后使用双指针 let ar = [5, 12, 6, 3, 9, 2, 1, 7];
function getthreenum(arr, target, result = []) { arr = arr.sort((a, b) => a - b) const len = arr.length; for (let i = 0; i < len; i++) { let j = i + 1; let k = len - 1; while (j < k) { if (arr[j] + arr[k] > target - arr[i]) { k--; } else if (arr[j] + arr[k] < target - arr[i]) { j++; } else { result.push([arr[i], arr[j], arr[k]]); j++; } } } return result; } console.log(getthreenum(ar, 13, []));
写一个关于全排列，全组合的函数
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 187(opens new window)
Author
回答者: shfshanyue(opens new window)
Arragement
Combination
Author
回答者: haotie1990(opens new window)
全排列
/**
* @param {number[]} nums
* @return {number[][]}
*/
var permute = function (nums) {
let result = [];
let used = Array.from({ length: nums.length }).fill(false);
function search(collection, used) {
if (collection.length === nums.length) {
result.push(collection);
return;
}
for (let i = 0; i < nums.length; i++) {
if (used[i] === false) {
used[i] = true;
search(collection.concat(nums[i]), used.slice(0));
used[i] = false; // 重置状态
}
}
collection = null;
used = null;
}
search([], used);
return result;
};
Author
回答者: haotie1990(opens new window)
全组合: 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
var combine = function (n, k) {
let result = [];
function find(collection, from) {
if (collection.length === k) {
result.push(collection);
return;
}
for (let i = from; i <= n; i++) {
find(collection.concat(i), i + 1);
}
}
find([], 1);
return result;
};
大数乘法和大数加法
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 189(opens new window)
Author
回答者: shfshanyue(opens new window)
TODO
Author
回答者: haotie1990(opens new window)
var multiply = function (num1, num2) {
if (num1 === "0" || num2 === "0") {
return "0";
}
let num1s = num1.split("");
let num2s = num2.split("");
num1s.reverse();
num2s.reverse();
function add(a, b) {
a = a.split("").reverse();
b = b.split("").reverse();
let len = Math.max(a.length, b.length);
let c = 0;
let r = [];
for (let i = 0; i < len; i++) {
let d = Number(a[i] || 0) + Number(b[i] || 0) + c;
let e = 0;
if (d >= 10) {
e = d - 10;
c = 1;
} else {
e = d;
c = 0;
}
r[i] = e;
}
if (c === 1) {
r[r.length] = 1;
}
return r.reverse().join("");
}
let results = [];
for (let i = 0; i < num1s.length; i++) {
for (let j = 0; j < num2s.length; j++) {
let zero = Array.from({ length: i + j })
.fill(0)
.join("");
results.push(Number(num1s[i]) * Number(num2s[j]) + zero);
}
}
return results.reduce((acc, c) => {
return add(acc, c);
});
};
如何求数组中的 TOP k
更多描述
求数组中的前 N 个最大的数
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 290(opens new window)
Author
回答者: shfshanyue(opens new window)
- 取数组中前 k 个数做小顶堆，堆化
- 数组中的其它数逐一与堆顶元素比较，若大于堆顶元素，则插入该数
时间复杂度 O(nlg(k))
Author
回答者: manyyuri(opens new window)
实现一个优先队列类，默认大顶堆，传入(x,y)=>x>y 比较函数则为小顶堆。 首先将前 k 个数 insert，之后的数字如果大于栈顶元素（栈顶元素为堆中最小值），delTop 删除栈顶元素，然后 insert 该数。 维护一个 size 为 k 的小顶堆。 最后堆中元素即为数组中最大的 k 个元素。
class PriorityQueue {
constructor(
// 默认大顶堆
cmp = (x, y) => {
return x < y;
}
) {
this.queue = [];
this.N = 0;
this.cmp = (i, j) => {
return cmp(this.queue[i], this.queue[j]);
};
this.parent = function (x) {
return Math.floor(x / 2);
};
this.left = function (x) {
return x * 2;
};
this.right = function (x) {
return x * 2 + 1;
};
this.exch = (x, y) => {
let temp = this.queue[x];
this.queue[x] = this.queue[y];
this.queue[y] = temp;
};
}
swim(k) {
const { cmp, parent, exch } = this;
while (k > 1 && cmp(parent(k), k)) {
exch(parent(k), k);
k = parent(k);
}
}
sink(k) {
const { left, right, exch, N, cmp } = this;
while (left(k) <= N) {
let older = left(k);
if (right(k) <= N && cmp(older, right(k))) {
older = right(k);
}
if (cmp(older, k)) break;
exch(older, k);
k = older;
}
}
top() {
return this.queue[1];
}
delTop() {
const { queue, exch } = this;
let top = queue[1];
exch(1, this.N);
queue.pop();
this.N--;
this.sink(1);
return top;
}
insert(x) {
this.N++;
this.queue[this.N] = x;
this.swim(this.N);
}
size() {
return this.N;
}
}
function TopK(arr, k) {
// 传入cmp，设置为小顶堆
let pq = new PriorityQueue((x, y) => x > y);
let i = 0;
for (i = 0; i < k; i++) {
pq.insert(arr[i]);
}
for (; i < arr.length; i++) {
if (arr[i] > pq.top()) {
pq.delTop();
pq.insert(arr[i]);
}
}
console.log("TOP K应为：", arr.sort((a, b) => b - a).splice(0, k));
console.log("求出的TOP k：");
// 排序，整理，方便对照
pq.queue.sort((a, b) => b - a).pop();
console.log(pq.queue);
}
let arr = [10, 15, 2, 6, 4, 5, 7, 3, 6, 14, 3, 12, 14, 13, 16, 1, 8];
TopK(arr, 10);
对以下字符串进行压缩编码
更多描述
这是一道大厂常考的代码题
- Input: 'aaaabbbccd'
- Output: 'a4b3c2d1'，代表 a 连续出现四次，b 连续出现三次，c 连续出现两次，d 连续出现一次
有以下测试用例
//=> a4b3c2
encode("aaaabbbcc");
//=> a4b3a4
encode("aaaabbbaaaa");
//=> a2b2c2
encode("aabbcc");
如果代码编写正确，则可继续深入：
- 如果只出现一次，不编码数字，如 aaab -> a3b
- 如果只出现两次，不进行编码，如 aabbb -> aab3
- 如果进行解码数字冲突如何解决
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 419(opens new window)
Author
回答者: shfshanyue(opens new window)
编写函数 encode 实现该功能
function encode(str) {
const l = [];
let i = 0;
for (const s of str) {
const len = l.length;
const lastChar = len > 0 ? l[len - 1][0] : undefined;
if (lastChar === s) {
l[len - 1][1]++;
} else {
l.push([s, 1]);
}
}
return l.map((x) => x.join("")).join("");
}
// 另外一种思路的解法
function encode(str) {
const l = [];
let i = -1;
let lastChar;
for (const char of str) {
if (char !== lastChar) {
lastChar = char;
i++;
l[i] = [char, 1];
} else {
l[i][1]++;
}
}
return l.flat().join("");
}
测试通过
> encode('aaab')
< "a3b1"
但是面试官往往会继续深入
- 如果只出现一次，不编码数字，如
aaab -> a3b - 如果只出现两次，不进行编码，如
aabbb -> aab3 - 如果进行解码，碰到数字如何处理？
以下是除数字外的进一步编码
function encode(str) {
const l = [];
let i = -1;
let lastChar;
for (const char of str) {
if (char !== lastChar) {
lastChar = char;
i++;
l[i] = [char, 1];
} else {
l[i][1]++;
}
}
return l
.map(([x, y]) => {
if (y === 1) {
return x;
}
if (y === 2) {
return x + x;
}
return x + y;
})
.join("");
}
Author
回答者: LiJinWD(opens new window)
const encode = function(input) { let obj = {} for(const key of input) { if(obj[key]) { obj[key]++ } else { obj[key] = 1 } } return Object.entries(obj).flat().join('') }
Author
回答者: LiJinWD(opens new window)
const encode = function(input, n) { let obj = {} for(const key of input) { if(obj[key]) { obj[key]++ } else { obj[key] = 1 } } return Object.entries(obj).flat().join('') // 如果只出现一次，不编码数字 // return Object.entries(obj).flat().join('').replace(/1/gi, '') // 如果只出现 N 次，不进行编码, N 是参数 / let objArr = Object.entries(obj); objArr.forEach(item => { if(item[1] == n) { item[1] = (new Array(n - 1)).fill(item[0]).join('') } }) return objArr.flat().join('') / }
encode('aaaabbbccd', 2)
Author
回答者: haiifeng(opens new window)
var doEncode = (str, nums = 0) => {
const res = str.split("").reduce((sum, cur) => {
sum[cur] ? sum[cur]++ : (sum[cur] = 1);
return sum;
}, {});
const filteredArr = Object.entries(res).filter((item) => item[1] > nums);
//const filteredArr= Object.entries(res).map(item=>{item[1]=item[1]>nums?item[1]:'';return item});
return filteredArr.flat().join("");
};
doEncode("aaaabbbccd"); //"a4b3c2d1"
doEncode("aaaabbbccd", 1); //"a4b3c2"
doEncode("aaaabbbccd", 2); //"a4b3"
Author
回答者: shfshanyue(opens new window)
@haiifeng 注意标记下 js 的语法高亮
Author
回答者: haotie1990(opens new window)
function encodeString(string) {
let result = "";
let stack = [];
if (!string || !string.length) {
return result;
}
const strArray = string.split("");
const pick = () => stack[stack.length - 1];
const concat = () =>
(result = result + pick() + (stack.length > 1 ? stack.length : ""));
stack.push(strArray.shift());
while (strArray.length) {
const letter = strArray.shift();
if (pick() !== letter) {
concat();
stack.length = 0;
}
stack.push(letter);
}
if (stack.length) {
concat();
}
return result;
}
console.log(encodeString("aaaabbbccd"));
console.log(encodeString("aaaabbbcc"));
console.log(encodeString("aaaabbbaaaa"));
console.log(encodeString("aabbcc"));
exercism(opens new window) 上出现了这个题目
export default class RunLengthEncoding {
static encode(input: string): string {
if (input === "") {
return input;
}
const encoding: string[] = [];
for (let i = 0; i < input.length; i++) {
let charCount = 1;
while (input[i] === input[i + 1]) {
charCount++;
i++;
}
if (charCount === 1) {
// 出现一次不编码数字
encoding.push(input[i]);
} else {
encoding.push(input[i] + charCount);
}
}
return encoding.join("");
}
static decode(input: string): string {
if (input === "") {
return input;
}
const decoding: string[] = [];
for (let i = 0; i < input.length; i++) {
let charCode = input.charCodeAt(i);
let charCount: string | number = "";
while (charCode > 47 && charCode < 58) {
// 0 ~ 9
charCount += input[i];
i++;
charCode = input.charCodeAt(i);
}
if (charCount === "") {
charCount += "1";
}
charCount = Number(charCount);
while (charCount) {
decoding.push(input[i]);
charCount--;
}
}
return decoding.join("");
}
}
Author
function encode(str, ignore) {
const container = new Map();
for (const s of str) {
container.set(s, (container.get(s) ?? 0) + 1);
}
return Array.from(container.entries()).reduce((ret, [char, num]) => {
if (num === ignore) {
ret += char.repeat(num);
} else {
ret += char + num;
}
return ret;
}, "");
}
Author
回答者: hwb2017(opens new window)
最基础功能的实现:
const encode = (str) => {
const encodedArray = Array.from(str).reduce((a, b) => {
if (a.length === 0) {
a.push(b, 1);
return a;
}
let lastChar = a[a.length - 2];
if (lastChar === b) {
a[a.length - 1] += 1;
} else {
a.push(b, 1);
}
return a;
}, []);
return encodedArray.join("");
};
Author
function solution(s, limit) {
const n = s.length;
let res = "";
for (let i = 0, cnt = 0; i < n; i += cnt) {
cnt = 1;
while (s[i] === s[i + cnt]) cnt++;
res += cnt > limit ? s[i] + cnt : s[i].repeat(cnt);
}
return res;
}
Author
回答者: LiJinWD(opens new window)
const encode = word => { if(!word) return ""; let ary = word.split(''); let group = {} let result = "" group[ary[0]] = 1 for(let i = 1, j = ary.length; i <= j; i++) { if(ary[i - 1] != ary[i]) { result += Object.entries(group).flat().join('') group = {} group[ary[i]] = 1 } else { group[ary[i]]++ } } return result
}
const encode1 = word => { return word.replace(/1/gi, '') }
const encode2 = word => { let one = word.substring(0, 1) let newWord = '' for(item of word) { newWord += item == 2 ? one : item one = item } return newWord }
Author
回答者: yuli-lovely(opens new window)
function encode(str) {
let prefix = ""; //初识节点
let num = 0; //计数器
let result = ""; //结果
for (let i = 0; i < str.length; i++) {
if (i == 0) {
prefix = str[i];
}
if (prefix != str[i] || i == str.length - 1) {
if (i == str.length - 1) {
num++;
}
if (num == 1 || num == 2) {
result = result + prefix.repeat(num);
} else {
result = result + prefix + num;
}
prefix = str[i];
num = 0;
}
num++;
}
return result;
}
Author
回答者: yuli-lovely(opens new window)
// number<10--适用下面
function decode(str) {
let result = "";
for (let i = 1; i <= str.length; i++) {
console.log();
if (typeof parseInt(str[i]) === "number") {
result = result + str[i - 1].repeat(parseInt(str[i]));
}
}
return result;
}
//全场景适用
function decode2(str) {
let datas = Array.from(str.matchAll(/[a-z][0-9]*/g));
let result = "";
for (elem of datas) {
elem = elem[0];
result = result + elem[0];
if (elem.length > 1) {
result = result + elem[0].repeat(parseInt(elem.substr(1)) - 1);
}
}
return result;
}
Author
回答者: JiangHuanLH(opens new window)
好像没看到用正则的解法，我来补充一下😗 感觉用正则来实现，修改编码条件也挺简单的
function encode(str) {
let res = "";
const reg = /(\w)\1*/g;
const matchs = str.match(reg);
matchs.forEach((item) => {
if (item.length > 1) {
res += item[0] + item.length;
} else {
res += item[0];
}
});
return res;
}
Author
回答者: fanfankill(opens new window)
function encode(str) {
//
let index = 0;
let result = "";
while (index < str.length) {
let count = 1;
result += str[index];
while (str[index] == str[index + 1]) {
index++;
count++;
}
index++;
result += count;
}
console.log(result);
return result;
}
求给定数组中 N 个数相加之和为 sum 所有可能集合
更多描述
求给定数组中 N 个数相加之和为 sum 所有可能集合，请补充以下代码
function fn(arr, n, sum) {}
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 692(opens new window)
Author
回答者: shfshanyue(opens new window)
TODO
Author
回答者: heretic-G(opens new window)
function fun(arr, n, sum) {
let result = [];
if (arr.length < n) return -1;
arr.sort((prev, next) => {
return prev - next;
});
function getSum(arr, n, currSum, index, incArr = []) {
for (let i = index; i < arr.length; i++) {
let temp = currSum + arr[i];
if (temp > sum) break;
if (n > 1) {
getSum(arr, n - 1, temp, i + 1, [arr[i], ...incArr]);
}
if (n === 1 && temp === sum) {
result.push([arr[i], ...incArr]);
}
}
}
getSum(arr, n, 0, 0);
return result;
}
Author
回答者: haotie1990(opens new window)
function findSumNumbers(array, n, sum) {
// 枚举所有n个数的组合，判断组合的和等于sum
let result = [];
const generateAll = function (index, collection, arr) {
if (collection.length === n) {
const s = collection.reduce((acc, c) => (acc += c), 0);
if (s === sum) {
result.push(collection);
}
return;
}
for (let i = 0; i < arr.length; i++) {
generateAll(index + 1, collection.concat(arr[i]), arr.slice(i + 1));
}
};
generateAll(0, [], array.slice(0));
return result;
}
findSumNumbers([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 2, 10);
findSumNumbers([1, 0, -1, 0, -2, 2], 4, 0);
求正序增长的正整数数组中，其和为 N 的两个数
更多描述
//=> [5, 10]
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15);
//=> null
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 150);
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 700(opens new window)
Author
回答者: shfshanyue(opens new window)
TODO
Author
回答者: hengistchan(opens new window)
const twoSum = (arr, sum) => {
if (arr.length < 2 || arr[arr.length - 1] + arr[arr.length - 2] < sum) {
return null;
}
const sumList = {},
res = [];
for (let i = 0; i < arr.length; i++) {
let val = arr[i];
if (sumList[val]) {
res.push([Math.min(val, sumList[val]), Math.max(val, sumList[val])]);
} else {
sumList[sum - val] = val;
}
}
return res.length === 0 ? null : res;
};
twoSum([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 15); // [[7, 8], [6, 9], [5, 10]]
返回的数组不唯一
Author
回答者: AaronKwong929(opens new window)
一，常规两数之和
var twoSum = function (nums, target) {
const hash = new Map();
for (let i = 0; i < nums.length; i++) {
if (hash.has(target - nums[i])) return [nums[i], nums[target - i]];
hash.set(nums[i], i);
}
return null;
};
二，双指针 利用题目的提示 “正序增长的正整数数组” 而且例 1 的提示很明显了，左右两个指针 当前和大于目标值，右指针左移 当前和小于目标值，左指针右移 左指针等于右指针，循环中断，返回 null
const twoSum = (number, target) => {
let left = 0,
right = number.length - 1;
while (left < right) {
const sum = number[left] + number[right];
if (sum === target) return [number[left], number[right]];
// 等于目标值，返回对应值
else if (sum < target) left++;
// 小于目标值，左指针向右移动
else right--; // 大于目标值，右指针向左移动
}
return null;
};
Author
回答者: JoeWrights(opens new window)
一、获取其中某一种组合
function twoSum(arr, target) {
let first;
let second;
arr.forEach((element) => {
if (arr.includes(target - element)) {
first = element;
}
});
second = arr.find((ele) => ele === target - first);
if (!first || !second) return null;
return [first, second];
}
二、获取所有组合
function twoSum(arr, target) {
let firstArr = [];
let secondArr = [];
let result = [];
arr.forEach((ele) => {
if (arr.includes(target - ele)) {
firstArr.push(ele);
}
});
firstArr.forEach((ele) => {
secondArr.push(target - ele);
});
firstArr.forEach((firstEle, i) => {
secondArr.forEach((secondEle, j) => {
if (i === j) {
result.push([firstEle, secondEle]);
}
});
});
return result.length > 0 ? result : null;
}
Author
回答者: hwb2017(opens new window)
双指针法获取所有组合
const twoSum = (arr, sum) => {
if (arr.length <= 1) return [];
let len = arr.length;
let left = 0;
let right = len - 1;
let result = [];
while (left < right) {
let _sum = arr[left] + arr[right];
if (_sum === sum) {
result.push([arr[left], arr[right]]);
left++;
right--;
} else if (_sum > sum) {
right--;
} else {
left++;
}
}
return result;
};
100 层楼，两个玻璃球，求最少多少次测出能摔碎玻璃球的楼层
更多描述
给你两个一摸一样的球，这两个球如果从一定的高度掉到地上有可能就会摔碎，当然，如果在这个高度以下往下扔，怎么都不会碎，当然超过这个高度肯定就一定摔碎了。
现在已知这个恰巧摔碎高度范围在一层楼到 100 层楼之间。
如何用最少的试验次数，用这两个玻璃球测试出摔碎的楼高
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 701(opens new window)
Author
回答者: heretic-G(opens new window)
假设最少次数是 x 次 那么第一个我们从哪里扔呢 ？从 x 因为如果碎了 另一个球从 1 到 x 正好就是 x 如果没碎这时候我们第一个球第二次只剩 x-1 次 所以我们从 x+x-1 层扔 碎了从 x+1 到 x + x-2 遍历 后面逻辑一样 减 1 去扔第一个球 没碎下次再减 1 碎了从上一次的没碎的上一层遍历就好了
所以可以一共层数等于 x + (x-1) + (x-2) + ... + 1 = 100
下面我们来解这个这个方程:
(x+1)*x/2 = 100
最终 x 向上取整,得到 x=14
因此，最优解在最坏情况的尝试次数是 14 次，第一次扔鸡蛋的楼层也是 14 层。
最后，让我们把第一个鸡蛋没碎的情况下，所尝试的楼层数完整列举出来：
14，27， 39， 50， 60， 69， 77， 84， 90， 95， 99， 100
Author
function solution(n) {
const dp = Array.from({ length: 2 }, () => new Array(n + 1).fill(0));
for (let i = 1; i <= n; i++) {
dp[0][i] = i;
dp[1][i] = n;
for (let j = 1; j <= i; j++) {
dp[1][i] = Math.min(dp[1][i], Math.max(dp[0][j - 1], dp[1][i - j]) + 1);
}
}
return dp[1][n - 1];
}
如何根据 random5 随机生成 [0, 5]，生成一个函数 random7？
更多描述
已知有一个函数 叫做 random5，执行这个函数会随机返回 0-5 之间任意一个数，概率相同。
根据这个 random5，实现一个 random7，要求执行这个函数后随机返回 0-7 之间任意一个数，概率相同。
这是一道群友分享的百度面经中的问题。
Issue
欢迎在 Gtihub Issue 中回答此问题: Issue 711(opens new window)
Author
回答者: AaronKwong929(opens new window)
https://www.growingwiththeweb.com/2014/03/given-random5-implement-random7.html 看到一题近似的，不过 random5 和 random7 是返回[0, 5]和[0, 7]
Author
回答者: Camliar(opens new window)
- 参考 leetcode 470. 用 Rand7() 实现 Rand10()(opens new window)-
- 方法：拒绝采样
- 思路：
random5生成[0, 5]每个数的概率是 $ \frac {1}{6} $， 使用两次random函数，相乘，找到等概率出现的 8 个数就可以，不满足的数据排除掉
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 | 4 | 5 |
| 2 | 0 | 2 | 4 | 6 | 8 | 10 |
| 3 | 0 | 3 | 6 | 9 | 12 | 15 |
| 4 | 0 | 4 | 8 | 12 | 16 | 20 |
| 5 | 0 | 5 | 10 | 15 | 20 | 25 |
| 0 | 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|---|
| P | \(\frac{11}{36}\) | \(\frac{1}{36}\) | \(\frac{2}{36}\) | \(\frac{2}{36}\) | \(\frac{3}{36}\) | \(\frac{2}{36}\) |
| 6 | 8 | 9 | 10 | 12 | 15 | |
| P | \(\frac{2}{36}\) | \(\frac{2}{36}\) | \(\frac{1}{36}\) | \(\frac{2}{36}\) | \(\frac{2}{36}\) | \(\frac{2}{36}\) |
| 16 | 20 | 25 | ||||
| P | \(\frac{1}{36}\) | \(\frac{2}{36}\) | \(\frac{1}{36}\) |
根据上图可知，我们只需要取 [1, 2, 3, 5, 6, 8, 9, 12, 15],这几个数，对 8 取余后可得到：
| 1 | 2 | 3 | 4 | 5 | 6 | 0 | 1 | 7 |
|---|---|---|---|---|---|---|---|---|
| \(\frac{1}{36}\) | \(\frac{2}{36}\) | \(\frac{3}{36}\) | \(\frac{2}{36}\) | \(\frac{2}{36}\) | \(\frac{2}{36}\) | \(\frac{2}{36}\) | \(\frac{1}{36}\) | \(\frac{2}{36}\) |
至此，我们可以得到等概率的[0, 7] 之间的数，每个数出现的概率为 \(\frac{2}{36}\)
故，简单粗暴的方式可用以下方式实现：
def random5(self):
return randint(0, 5)
def random7(self):
picked = [1, 2, 3, 5, 6, 8, 9, 12, 15]
while True:
rd1 = self.random5()
rd2 = self.random5()
if (rd1 * rd2) in picked:
return (rd1 * rd2) % 8
rd1 = self.random5()
rd2 = self.random5()
如果要更进一步优化，减少random5 函数的调用，我们就需要优化，如果随机出现的值不在我们采样的范围中时，怎么去减少对函数 random5 的调用，具体操作可看到官方题解
Author
回答者: heretic-G(opens new window)
function rand5() {
return (Math.random() * 6) | 0;
}
function rand7() {
while (true) {
let num = rand5() * 6 + rand5();
if (num < 32) {
return num % 8;
}
}
}
Author
function rand5() {
return (Math.random() * 6) | 0;
}
function rand7() {
return (rand5() & 1) * 4 + (rand5() & 1) * 2 + (rand5() & 1);
}
