刷题2 剑指 Offer — 数组和字符串

剑指 Offer 04. 二维数组中的查找

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz2hh7/

var findNumberIn2DArray = function(matrix, target) {
    let col = matrix.length;
    if(!col) return false
    let row = matrix[0].length;
    let i=col-1, j=0;
    while(i>=0 && j<row){
        if(matrix[i][j] == target){
               return true;
           }else if(matrix[i][j] > target){
              i--;
           }else{
              j++;
         }
    }
    return false;
};

剑指 Offer 05. 替换空格

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz2cf5/

var replaceSpace = function(s) {
 return s.split(' ').join('%20')
};

//数组
var replaceSpace = function(s) {
    var res ='';
    for(i = 0; i<s.length; i++){
        if(s[i] == " "){
            res += '%20';
        } else{
            res += s[i]
        }
    }
    return res
};

剑指 Offer 17. 打印从 1 到最大的 n 位数

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzvgc2/

var printNumbers = function(n) {
    if(n==0){
        return false;
    }
    let all = Math.pow(10,n);
    // let all=1
    // for(var i=0;i<n;i++){
    //    all = 10*all   
    // }
    let arr = [];
    for(var i=1;i<all;i++){
        arr.push(i)
    }
return arr;
};

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面

var exchange = function(nums) {
  var a = [];
    var b = [];
    for(var i=0;i<nums.length;i++){
        if (nums[i]%2==1){
            a.push(nums[i])
        }else{
            b.push(nums[i])
        }
    }
    return a.concat(b)
};

双指针

var exchange = function(nums) {
    let right = nums.length-1;
    let left = 0;
    let tmp;
    while(left<right){
       if(left<right &&(nums[right]%2)  == 0 ){
            right--;
        }
       if(left<right &&(nums[left]%2) == 1){
            left++;
        }
    tmp = nums[left]
    nums[left] = nums[right]
    nums[right] = tmp 
    }
  return nums  
};

剑指 Offer 39. 数组中出现次数超过一半的数字

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xz7dgg/

方法一：数组排序：首先将 nums 排序，由于该数字超过数组长度的一半，所以数组的中间元素就是答案，时间复杂度为 O(nlogn)

var majorityElement = function(nums) {
    nums.sort((a,b) => a-b)
    return nums[parseInt(nums.length / 2 )]  
}

方法：哈希计数：遍历 nums 数组，将数字存在 HashMap 中，统计数字出现次数，统计完成后再遍历一次 HashMap，找到超过一半计数的数字，时间复杂度为 O(n)

方法 摩尔投票：遍历 nums 数组，使用 count 进行计数，记录当前出现的数字为 cur，如果遍历到的 num 与 cur 相等，则 count 自增，否则自减，当其减为 0 时则将 cur 修改为当前遍历的 num，通过增减抵消的方式，最终达到剩下的数字是结果的效果，时间复杂度为 O(n)

• 摩尔投票是最优解法，时间复杂度：O(n)，空间复杂度：O(1)

var majorityElement = function(nums) {
    let cur ,count=0;
    for(let i = 0; i<nums.length; i++){
        if(count == 0){
            cur = nums[i];  
        }
        if(nums[i]  == cur){
            count++;
        }else{
            count--
        }
    }
    return cur
}

剑指 Offer 57. 和为 s 的两个数字

https://leetcode-cn.com/leetbook/read/illustrate-lcof/xzimqj/
输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。
思路：有序数组，双指针

var twoSum = function(nums, target) {
    var len = nums.length;
    var left = 0;
    var right = len-1;
    var arr = []
    for(var i = 0; i<len ;i++){
        if(nums[left]+nums[right] == target){
            //  arr.push(nums[left]);
            // arr.push(nums[right]) 
            return  [nums[left],nums[right]]
        };
        if(nums[left]+nums[right] > target){
            right--
        }
        if(nums[left]+nums[right] < target){
            left++
        }
    }
};