《剑指offer》JavaScript版41~46

41.和为s的连续正整数列

题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述：输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。

思路分析：
我们可以使用滑动窗口解决此问题。滑动窗口可以看成数组中框起来的一个部分。在一些数组类题目中，我们可以用滑动窗口来观察可能的候选结果。当滑动窗口从数组的左边滑到了右边，我们就可以从所有的候选结果中找到最优的结果。

对于这道题来说，数组就是正整数序列 [1, 2, 3, ..., n]。我们设滑动窗口的左边界为 i，右边界为 j，则滑动窗口框起来的是一个左闭右开区间 [i, j)。在一开始，i=1, j=1，滑动窗口位于序列的最左侧，窗口大小为零。

image.png

窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 O(n)。当窗口的和大于 target 的时候，窗口的和需要减少，所以要缩小窗口，窗口的左边界向右移动。当窗口的和小于 target 的时候，窗口的和需要增加，所以要扩大窗口，窗口的右边界向右移动。

当滑动窗口的右边界向右移动时，也就是 j = j + 1，窗口中多了一个数字 j，窗口的和也就要加上 j。当滑动窗口的左边界向右移动时，也就是 i = i + 1，窗口中少了一个数字 i，窗口的和也就要减去 i。当窗口的和恰好等于 target 的时候，我们需要记录此时的结果。设此时的窗口为 [i, j)，那么我们已经找到了一个 ii开头的序列，也是唯一一个 i 开头的序列，接下来需要找 i+1开头的序列，所以窗口的左边界要向右移动。

function FindContinuousSequence(sum)
{
    const res = [];
    let i = 1;
    let j = 1;
    let tempSum = 0;
    while (i < sum/2) {
        if (tempSum < sum) {
            tempSum += j;
            j++;
        } else if (tempSum > sum) {
            tempSum -= i;
            i++;
        } else {
            let arr = [];
            for (let n = i; n < j;n++) {
                arr.push(n);
            }
            res.push(arr);
            tempSum -= i;
            i++;
        }
    }
    return res;
}

42.和为s的字符串

题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路分析：由乘积最小可知，两个数分别在数组两头才能满足，于是使用两个指针，一个从头开始，一个从尾开始，不断向中间遍历。循环终止条件为两指针相遇。

function FindNumbersWithSum(array, sum) {
  if (array.length < 2) return [];
  let left = 0,
    right = array.length - 1;
  const res = [];
  while (left < right) {
    if (array[left] + array[right] < sum) {
      left++;
    } else if (array[left] + array[right] > sum) {
      right--;
    } else {
      res.push(array[left], array[right]);
      return res;
    }
  }
  return res;
}

43.左旋字符串

题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路分析：注意n大于字符串长度的情况即可。

function LeftRotateString(str, n) {
  if (str === null || str.length === 0) return '';
  n = n % str.length;
  return str.slice(n) + str.slice(0, n);
}

44.翻转单词顺序

题目描述：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？

function ReverseSentence(str) {
  return str
    .split(' ')
    .reverse()
    .join(' ');
}

45.扑克牌顺子

题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定难度不大，可以将大小王看成数字 0，可以在任何不连续的两个数字之间做填充。

思路分析：首先将原数组排序，然后统计任意数字0的出现次数zeros。再遍历0之后的数字，计算不相邻数字之间有多少个空隙gap。最后比较zeros和gap两者的大小关系即可，若zeros>=gap，则可以组成顺子，返回true。注意，连续两个相同的数字是对子，不符合要求直接返回false。

function IsContinuous(numbers)
{
    if (numbers.length === 0) return false;
    let zeros = 0;
    let gap = 0;
    numbers.sort();
    for (let i = 0; i < numbers.length; i++) {
        if (numbers[i] === 0) {
            zeros++;
        }
    }
    for (let j = zeros; j < numbers.length - 1;j++) {
        if (numbers[j] === numbers[j + 1]) {
            return false;
        }
        gap += numbers[j + 1] - numbers[j] - 1;
    }
    return zeros >= gap;
}

46.孩子们的游戏（圆圈中最后剩下的数）

题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？如果没有小朋友，请返回-1(注：小朋友的编号是从0到n-1)

思路分析：
1.可以构建一个循环链表，将这些节点一一存入，当报数满足了条件时，将当前节点删除即可。注意报数是从0开始，报到m-1为止，然后删除节点。

function LastRemaining_Solution(n, m)
{
    if (n < 1) return -1;
    
    function ListNode(val) {
        this.val = val;
        this.next = null;
    }
    
    //构建循环链表
    let head = new ListNode(0);
    let last = head;
    for (let i = 1; i < n; i++) {
        last.next = new ListNode(i);
        last = last.next;
    }
    last.next = head;
    
    let count = 0;
    while (head.next !== head) {
        count++;
        //此时head指向为下标为m-2的节点，即m-1的前一个节点
        if (count === m - 1){
            //删除下标为m-1的节点
            head.next = head.next.next;
            count = 0;
        }
        head = head.next;
    }
    return head.val;
}

2.也可以用数组存储，不断计数发现符合条件的元素，删除即可，然后进行下一次计数。

function LastRemaining_Solution(n, m)
{
    if (n < 1) return -1;
    //构造模拟数组
    let arr = [];
    for (let i = 0; i < n; i++) {
        arr.push(i);
    }
    let start = 0;
    while (arr.length > 1) {
        //start为开始计数时的下标，注意有循环一遍数组的可能，所以要取余
        start = (start + m - 1)%arr.length;
        //删除下标为m-1的元素
        arr.splice(start, 1);
    }
    return arr[0];
}