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，滑动窗口位于序列的最左侧，窗口大小为零。
窗口的左边界和右边界永远只能向右移动，而不能向左移动。这是为了保证滑动窗口的时间复杂度是 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];
}
