算法题目

判断一个链表是否有环

1，设置两个指针都指向头，一个每次走一步，一个每次走两步，当链表有环时，两个指针会相遇。

判断一个有环的链表，环长度

环长 = 每一次速度差 ✖️ 前进次数 = 前进次数

如果联表有环，求入环口

首先获取相遇点，p2从相遇点开始，p1从头指针开始，两个指针每次都走一步，此时的相遇点就是入环口

求栈的最小值，最大值，栈有pop，push，getMin，getMax方法

设置3个栈，一个基本栈存储内容、存储最大值栈、存储最小值栈，首先
第一个值入栈，假设是4，三个栈都存储此值
第二个值入栈，假设是3，3比4小，基本栈入栈，存储最小值栈入栈
第三个值入栈，假设是5，5比4大，基本栈入栈，存储最大值栈入栈
出栈5，最大值5与存储最大值栈，栈顶相等，基本栈出栈，存储最大值栈出栈
…

求最大公约数

辗转相除法

a/b的余数c，c与b求最大公约数，一直递归
缺点% 取模运算性能差

function getGreatestCommonDivisor(a, b) {
  let max = a > b ? a : b;
  let min = a < b ? a : b;
  if (max % min === 0) {
    return min;
  }
  return getGreatestCommonDivisor(max % min, min);
}
getGreatestCommonDivisor(10, 25); // 5;

更相减损术

缺点，如果两个术相差较大，会减很多次。

function getGreatestCommonDivisor(a, b) {
    if (a === b) {
    return a
  }
  let max = a > b ? a : b;
  let min = a < b ? a : b;
  return getGreatestCommonDivisor(max - min, min);
}
getGreatestCommonDivisor(10, 25); // 5;

位移加更相减损术

function getGreatestCommonDivisor(a, b) {
    if (a === b) {
    return a
  }
  if (
      (a & 1) === 0 && (b & 1) === 0
  ) {
      return getGreatestCommonDivisor(a >> 1, b >> 1);
  } else if (
      (a & 1) === 0 && (b & 1) !== 0
  ) {
    return getGreatestCommonDivisor(a >> 1, b);
  } else if (
      (a & 1) !== 0 && (b & 1) === 0
  ) {
    return getGreatestCommonDivisor(a, b >> 1);
  } else {
      let max = a > b ? a : b;
      let min = a < b ? a : b;
      return getGreatestCommonDivisor(max - min, min);
  }
}
getGreatestCommonDivisor(10, 25); // 5;

求一个数是否是2的整数次幕

十进制,二进制,原始值-1,是否为2的整数次幕
8,1000B,111B,是
16，10000B,1111B,是
….

function isPowerOf(a) {
  return a & a - 1 === 0;
}

无序数组排序后求最大相临差

function sort(arr) {
  let max = arr[0];
  let min = arr[0];
  for (let i = 0; i < arr.length; i++) {
    if (max < arr[i]) {
       max = arr[i];
    }
    if (min > arr[i]) {
      min = arr[i];
    }
  }
  const d = max - min;
  if (d === 0) {
    return 0;
  }
  const bucketNum = arr.length
  const bucketArr = [];
  for (let i = 0; i < bucketNum; i++)
    bucketArr.push({});
  for (let i = 0; i < arr.length; i++) {
    const index = parseInt((arr[i] - min) * (bucketNum - 1) / d);
    if (!bucketArr[index].min || bucketArr[index].min > arr[i]) {
        bucketArr[index].min = arr[i];
    }
    if (!bucketArr[index].max || bucketArr[index].max < arr[i]) {
        bucketArr[index].max = arr[i];
    }
  }
  const sortArr = [];
  let leftMax = bucketArr[0].max;
  let maxDistance = 0;
  for (let i = 1; i < bucketArr.length; i++) {
    if (!bucketArr[i].min) {
      continue;
    }
    if (bucketArr[i].min - leftMax > maxDistance) {
        maxDistance = bucketArr[i].min - leftMax;
    }
        leftMax = bucketArr[i].max;
  }
  console.log(maxDistance);
  return Number(maxDistance.toFixed(2));
}
var arr = [0.84, 4.5, 2.18, 0.5, 3.25]
sort(arr);

栈实现队列

使用两个栈来实现，让入栈时，入栈到栈A中，当出栈时，检查栈B有没有内容，有的话直接出，没有的话，将栈A全部出栈到栈B中，在从栈B中出栈元素。

输入一个正整数，找出这个正整数所有数字全排列的下一个数。字典序算法解

例如 输入12345，则返回 12354
输入12354，则返回12435
输入12435，则返回 12453

// 从后往前查逆序区域
/*
求那个位置可以交互
*/
function findTransferPoint(arr = []) {
    for (let i = arr.length - 1; i > 0; i--) {
      if (arr[i] > arr[i - 1]) {
      return i;
    }
  }
  return 0;
}
function findNearestNumber(arr = []) {
    const index = findTransferPoint(arr);
  if (index === 0) {
      return false;
  }
  var arrCopy = arr.map(item => item);
  // 逆序区域调整位置
  exchangeHead(index, arr);
  // 将交换位置后的，下标后面的按从小到大排序
  reverse(index, arr);
  return arr;
}
function reverse(index, arr) {
    var i = index;
  var j = arr.length - 1;
  while(i < j) {
    const temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
    i++;
    j--;
  }
  return arr;
}
function exchangeHead(index, arr) {
  const head = arr[index - 1];
  for (let i = arr.length - 1; i > 0; i--) {
      if (head < arr[i]) {
      arr[index - 1] = arr[i];
      arr[i] = head;
      break;
    }
  }
  return arr;
}
var a = [1,2,3,4,5]
for (let i = 0 ; i < 10000; i++) {
  a = findNearestNumber(a);
  console.log(a);
  if (!a) {
    console.log(i + 1);
      break;
  }
}