跳转至

算法面试题(山月)

如何实现一个优先级队列

原文:https://q.shanyue.tech/base/algorithm/49.html

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 

如何判断两个链表是否相交

原文:https://q.shanyue.tech/base/algorithm/62.html

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 62(opens new window)

Author

回答者: wython(opens new window)

只判断链表相交,好一点的方式是用双指针+哈希表。 同时遍历 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

原文:https://q.shanyue.tech/base/algorithm/94.html

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 94(opens new window)

Author

回答者: manyyuri(opens new window)

leetcode149

  1. 用双向链表+哈希。
/**
 * @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);
  }
}; 
  1. 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

原文:https://q.shanyue.tech/base/algorithm/177.html

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 177(opens new window)

Author

回答者: HNHED(opens new window)

排序之后使用双指针 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, []));

写一个关于全排列,全组合的函数

原文:https://q.shanyue.tech/base/algorithm/187.html

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;
}; 

大数乘法和大数加法

原文:https://q.shanyue.tech/base/algorithm/189.html

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

原文:https://q.shanyue.tech/base/algorithm/290.html

更多描述

求数组中的前 N 个最大的数

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 290(opens new window)

Author

回答者: shfshanyue(opens new window)

  1. 取数组中前 k 个数做小顶堆,堆化
  2. 数组中的其它数逐一与堆顶元素比较,若大于堆顶元素,则插入该数

时间复杂度 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); 

对以下字符串进行压缩编码

原文:https://q.shanyue.tech/base/algorithm/419.html

更多描述

这是一道大厂常考的代码题

  • 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 实现该功能

代码见 【Q412】对以下字符进行压缩编码 - codepen(opens new window)

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" 

但是面试官往往会继续深入

  1. 如果只出现一次,不编码数字,如 aaab -> a3b
  2. 如果只出现两次,不进行编码,如 aabbb -> aab3
  3. 如果进行解码,碰到数字如何处理?

以下是除数字外的进一步编码

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

回答者: Asarua(opens new window)

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

回答者: 3N26(opens new window)

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 所有可能集合

原文:https://q.shanyue.tech/base/algorithm/692.html

更多描述

求给定数组中 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 的两个数

原文:https://q.shanyue.tech/base/algorithm/700.html

更多描述

//=> [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 层楼,两个玻璃球,求最少多少次测出能摔碎玻璃球的楼层

原文:https://q.shanyue.tech/base/algorithm/701.html

更多描述

给你两个一摸一样的球,这两个球如果从一定的高度掉到地上有可能就会摔碎,当然,如果在这个高度以下往下扔,怎么都不会碎,当然超过这个高度肯定就一定摔碎了。

现在已知这个恰巧摔碎高度范围在一层楼到 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

回答者: 3N26(opens new window)

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?

原文:https://q.shanyue.tech/base/algorithm/711.html

更多描述

已知有一个函数 叫做 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)

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

回答者: 3N26(opens new window)

function rand5() {
  return (Math.random() * 6) | 0;
}

function rand7() {
  return (rand5() & 1) * 4 + (rand5() & 1) * 2 + (rand5() & 1);
} 


回到顶部