剑指offer（持续更新）

查找

整数中1出现的次数

求出1~ 13的整数中1出现的次数,并算出100~ 1300的整数中1出现的次数？为此他特别数了一下1~ 13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

function NumberOf1Between1AndN_Solution(n){
	let count = 0;
	for (let i = 0; i <= n; i++) {
		i.toString().split('').forEach((item)=>{
            if (item == 1) {
                count++;
            }
		})
	};
	return count;
}

旋转数组的最小数字

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

function minNumberInRotateArray(rotateArray)
{let len = rotateArray.length;
 if(len == 0){return 0;}
 else{
     var low = 0;
     for(let i = 1;i < len; i++){
         if(rotateArray[i]<rotateArray[low]){
             low = i
         }
     }
     return rotateArray[low]
 } 
}

Math.min.apply(null,rotateArray);
apply第一个参数给了一个null,是因为没有对象去调用这个方法,只需要用这个方法计算得到结果，所以直接传递了一个null过去
详情参看：https://blog.csdn.net/qq_27954643/article/details/88861827

二维数组中查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

function Find(target, array){
    var len  = array.length;
    for(var i = 0;i< len; i++){
        for(var j = 0;j<len; j++){
            if(array[i][j] == target){
                return true;
            }
        }
    }
}

数组有序，从左下角开始，
上面的比他小，右侧的比它大；或者从右上角开始

    let row = 0,
        col = array[0].length -1;
    while(row < array.length && col >= 0){
        if(target > array[row][col]){
            row += 1;
        }else if(target < array[row][col]){
            col -= 1;
        }else{
            return true;
        }
    }
    return false;

排序

数据流中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

var arr = [];
function Insert(num)
{
    arr.push(num);
    arr.sort();
    return arr;
}
function GetMedian(){
    var len = arr.length;
    let mid = Math.floor(len/2);
    if(len%2 == 0){ 
        return (arr[mid]+arr[mid-1])/2;
    }
    else{
        return arr[mid];
    }
}

递归

字符串全排

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
思路：

1. str.length == 1;输出 [ str ]
2. 循环str，取出目标字符串放首字符firstNumber，以及剩余字符remainNumber。
   ①. 对剩余字符递归循环得到remainSort
   ② 拼接：首字符+剩余字符的可能排序结果
   3.数组去重

function Permutation(str){
    var res = [];
    if(str.length == 1){
        return [str];
    }
    else{
        for(let i =0; i < str.length; i++){
            var firstNumber = str[i];
            var remainNumber = str.slice(0,i)+str.slice(i+1,str.length);
            var remainSort = Permutation(remainNumber);
            for(let j = 0; j<remainSort.length; j++){
                var tmp = firstNumber + remainSort[j];
                res.push(tmp);
            }   
        }
    }
    return Array.from(new Set(res));
}