您的位置:js12345金沙官网登入 > 网络编程 > 每周一道算法题(四十二)

每周一道算法题(四十二)

2019-10-02 10:00

本周题目难度级别'Medium',使用语言'C'

前言

在很多算法题中,要求查找一个特定的内容,可能是一个数字,也有可能是一个子串,或者是题目定义的一个满足某个性质的元素...这种题如果使用暴力搜索或者嵌套循环,往往会超时,所以我们需要一种更好的方法来降低时间复杂度:双索引技术。

题目:给你一组非负数组成的集合,然后从第一个索引中的数开始往下‘跳’,看能否‘跳’到最后一个数。eg:[2,3,1,1,4],第一个索引是2,所以从第一个索引开始‘跳’两步,当‘跳’到第二个索引3的时候又能跳‘3’步,很显然能够跳完。再eg:[3,2,1,0,4],第一个索引是3,从第一个索引开始‘跳’3步,当跳到0的时候,前面的3,2,1,0都已经跳完,就不能跳了,所以返回false。

思路:就是跳一跳么,一个索引一个索引的走,第一个索引能跳几步就往下继续跳,跳到下一个索引的时候更新所能够跳的步数,看最后能否跳完。不难,看代码吧:

bool canJump(int* nums, int numsSize) { //如果只有一个数,直接返回true if (numsSize == 1) return true; //获取能够跳的步数 int temp = nums[0]; //从第一个索引开始遍历 int i = 0; //能跳的步数不为0就继续跳 while (temp != 0) { //当跳完了集合返回true if (nums[i] +i >= numsSize - 1) return true; //步数减一 temp--; //跳到下一个索引 i++; //更新能跳的步数 if (temp < nums[i]) temp = nums[i]; } return false;}

效率还行吧,while可以换成for,for一般用于已知遍历次数的,while一般用于未知遍历次数的,这个题明显的知道最大遍历次数不超过numsSize,所以用for更好些,我就不改了。另外这个题用到了“贪心算法”也叫“贪婪算法”,有兴趣的小伙伴可以自己了解下。。。

起源之二分法

这种查找方法的老祖宗,就是我们高中就学习过的二分法了。当然,在大学的数据结构和算法的课程里,它的地位也非常重要,只因为它是一个O(logn)的算法。
那它的双索引是什么呢?
开始索引和结束索引。即查找范围的始索引和终索引。
上代码:

function binarySearch(arr, target) {
    var len = arr.length;
    // 在arr[l...r]之中查找target
    var l = 0,
        r = len - 1;
    while (l <= r) {
        //防止大数溢出,所以mid不是~~(l+r)/2
        var mid = l + ~~((r - l) / 2);
        if (arr[mid] == target)
            return mid;

        if (arr[mid] > target)
            r = mid - 1;
        else
            l = mid + 1;
    }

    return -1;
}

// 递归方式实现二分查找法

function __binarySearch2(arr, l,  r, target){

    if( l > r )
        return -1;

    var mid = l + ~~((r - l) / 2);

    if( arr[mid] === target )
        return mid;
    else if( arr[mid] > target )
        return __binarySearch2(arr, l, mid-1, target);
    else
        return __binarySearch2(arr, mid+1, r, target);

}

function binarySearch2(arr,target){
    var len = arr.length;
    return __binarySearch2( arr , 0 , len-1, target);
}

版权声明:本文为 Crazy Steven 原创出品,欢迎转载,转载时请注明出处!

对撞指针

这是双索引的一种特殊情况:即第一个索引在前,第二个索引在后,在程序运行的过程中两者不断靠近,最后达到一个临界范围,程序结束。
以leetcode的167题为例:题目要求我们找出一个数组中相加为target的两个数,并返回他们的次序。
因为输入的数组是已经排序好的,所以双索引的最初指向分别为首和尾。
我们假设两个指针为i和j,[i...j]范围内就是我们关注的,如果numbers[i]js12345金沙官网登入,+numbers[j]等于target返回结果,小了就让i右移,大了就让j左移

var twoSum = function (numbers, target) {
    let i = 0, j = numbers.length - 1;
    while (i < j) {
        if (numbers[i] + numbers[j] === target) return [i + 1, j + 1]
        else if (numbers[i] + numbers[j] < target) i++
        else j--
    }
    return []
};

本文由js12345金沙官网登入发布于网络编程,转载请注明出处:每周一道算法题(四十二)

关键词: