美文网首页Web前端之路让前端飞前端开发
js刷林扣 lintcode(2017年1月)

js刷林扣 lintcode(2017年1月)

作者: mytac | 来源:发表于2017-02-03 17:55 被阅读144次

    题目前的数字是对应的lintcode的题目序号

    14.二分查找

    给定一个排序的整数数组(升序)和一个要查找的整数target,用O(logn)的时间查找到target第一次出现的下标(从0开始),如果target不存在于数组中,返回-1。

    样例
    在数组 [1, 2, 3, 3, 4, 5, 10] 中二分查找3,返回2。

            function binarySearch(arr,num,start,end){
                if(!arr.length) return 'no data'
                if(arr.length==1&&arr[0]==num) return 0
                if(num<arr[0]||num>arr[arr.length-1]) return 'not found'
                var end=end||arr.length-1,
                    start=start||0,
                    m=Math.floor((end+start)/2)
                    if(arr[m]==num&&arr[m]!=arr[m-1]) return m
                    if(arr[m]<num){
                        return binarySearch(arr,num,m+1,end)
                    }else{
                        return binarySearch(arr,num,start,m-1)
    
                    }
                    return 'not found'
    
            }
        console.log(binarySearch([1,2,3,3,4,5,10],3))
    

    22.平面列表(01-06)

    给定一个列表,该列表中的每个要素要么是个列表,要么是整数。将其变成一个只包含整数的简单列表。

    样例
    给定 [1,2,[1,2]],返回 [1,2,1,2]。

    给定 [4,[3,[2,[1]]]],返回 [4,3,2,1]。

            var list=[1,2,[3,4,[5,6],7],8]
            var result=[]
            function fuc(list){
                for(var i=0;i<list.length;i++){
                    if(list[i][0]){
                        var arr=list[i]
                         fuc(arr)
                    }else{
                        result.push(list[i])
                    }
                }
            }
            fuc(list)
            console.log(result)
    

    28.搜索二维矩阵(01-07)

    写出一个高效的算法来搜索 m × n矩阵中的值。

    这个矩阵具有以下特性:

    每行中的整数从左到右是排序的。
    每行的第一个数大于上一行的最后一个整数。

    样例
    考虑下列矩阵:

    [
    [1, 3, 5, 7],
    [10, 11, 16, 20],
    [23, 30, 34, 50]
    ]
    给出 target = 3,返回 true

    function searchMatrix(matrix,target){
                var result=false
                if(target<matrix[0][0]||target>matrix[matrix.length-1][matrix[matrix.length-1].length-1]) return result
                for(var i=0;i<matrix.length;i++){
                    if(target>matrix[i][0]&&target<matrix[i+1][0]){
                        var arr=matrix[i]
                        arr.forEach(function(a){
                            if(a==target){result=true}
                        })
                    }
                }
                return result
            }
    

    插入区间(01-08)

    给出一个无重叠的按照区间起始端点排序的区间列表。

    在列表中插入一个新的区间,你要确保列表中的区间仍然有序且不重叠(如果有必要的话,可以合并区间)。

    样例

    插入区间[2, 5] 到 [[1,2], [5,9]],我们得到 [[1,9]]。

    插入区间[3, 4] 到 [[1,2], [5,9]],我们得到 [[1,2], [3,4], [5,9]]。

            function insertDistance(matrix,target){
                for(var i=0;i<matrix.length-1;i++){
                    if((target[0]>=matrix[i][0])&&(target[1]<=matrix[i+1][1])){
                        debugger
                        if(target[0]==matrix[i][1]&&target[1]==matrix[i+1][1]){
                            matrix[i][1]=matrix[i+1][1]
                            delete(matrix[i+1])
                        }else if(target[0]==matrix[i][0]&&target[1]==matrix[i+1][1]){
                            matrix[i]=target
                            delete(matrix[i+1])
                        }else{
                            matrix.splice(i+1,0,target)
                        }
                        
                    }
                }
            }
    

    39.恢复旋转排序数组(01-09)

    给定一个旋转排序数组,在原地恢复其排序。

    比如,原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

    function recoverRotatedSortedArray(arr) {
        var len=arr.length
        if(len<1) return '数组为空'
        if(arr[0]<arr[len-1]||len==1) return arr
        if(arr[0]>arr[len-1]||(arr[0]==arr[len-1]&&len>1)){
            var temp=arr[0]
            for(var i=0;i<len;i++){
                arr[i]=arr[i+1]
            }
            arr[len-1]=temp
            return recoverRotatedSortedArray(arr)
        }
    }
    

    41.最大子数组(01-10)

    给定一个整数数组,找到一个具有最大和的子数组,返回其最大和。

    注意事项 子数组最少包含一个数

    样例
    给出数组[−2,2,−3,4,−1,2,1,−5,3],符合要求的子数组为[4,−1,2,1],其最大和为6

    function maxSubArray(arr) {
        var max=0
        var sum=0
        var maxNum=0//数组中最大数
        var fushu=0
        for(var i=0;i<arr.length;i++){      
    
            if(a[i]<0){
                fushu++
            }
            if(maxNum<arr[i]){
                maxNum=arr[i]
            }
            sum+=arr[i]
            if(sum>max){
                max=sum
            }else if(sum<0){
                sum=0
            }
        }
            if(fushu==arr.length){//全为负数的情况,就选一个最大值
                arr.sort()
                max=arr[0]
            }
        
            return max
    }
    

    42.最小子数组(01-11)

    给定一个整数数组,找到一个具有最小和的子数组。返回其最小和。
    样例
    给出数组[1, -1, -2, 1],返回 -3

    function minSubArray(arr) {
        var min=0
        var sum=0
        var minNum=0
        var zhengshu=0
        for(var i=0;i<arr.length;i++){      
    
            if(a[i]>0){
                zhengshu++
            }
            if(minNum>arr[i]){
                minNum=arr[i]
            }
            sum+=arr[i]
            if(sum<min){
                min=sum
            }else if(sum>0){
                sum=0
            }
        }
            if(zhengshu==arr.length){
                arr.sort()
                min=arr[arr.length-1]
            }
        
            return min
    }
    

    46.主元素【01-12】

    给定一个整型数组,找出主元素,它在数组中的出现次数严格大于数组元素个数的二分之一。

    样例

    给出数组[1,1,1,1,2,2,2],返回 1

    挑战

    要求时间复杂度为O(n),空间复杂度为O(1)

    function majorityNumber(arr) {
        var halfLen=arr.length/2
        arr.sort()
    for(var i= 0;i<arr.length;i++){
        if(i<halfLen){
            if (arr[i]==arr[Math.floor(halfLen)]) {
                return arr[i]
            }
    }
    }
    return '没有主元素'
    }
    

    50.数组剔除元素后的乘积【01-16】

    给定一个整数数组A。

    定义B[i] = A[0] * ... * A[i-1] * A[i+1] * ... * A[n-1], 计算B的时候请不要使用除法。

    样例
    给出A=[1, 2, 3],返回 B为[6, 3, 2]

    function productExcludeItself(arr) {
        var arrB=[]
        for(var i=0,len=arr.length;i<len;i++){
            var sum=1
            var left=1,right=1
            for(var j=0;j<i;j++){
                left*=arr[j]
            }
            for(var k=i+1;k<len;k++){
                right*=arr[k]
            }
            sum=left*right
            arrB.push(sum)
        }
        return arrB
    }
    

    53. 翻转字符串【01-18】

    给定一个字符串,逐个翻转字符串中的每个单词。

    单词的构成:无空格字母构成一个单词

    输入字符串是否包括前导或者尾随空格?可以包括,但是反转后的字符不能包括
    如何处理两个单词间的多个空格?在反转字符串中间空格减少到只含一个
    样例:
    给出s = "the sky is blue",返回"blue is sky the"

    //使用现有方法实现
    function reverseWords(str){
    var arr=str.split(' ').reverse()
    return arr.join(' ')
    }
    

    55.比较字符串【01-19】

    比较两个字符串A和B,确定A中是否包含B中所有的字符。字符串A和B中的字符都是 大写字母
    样例
    给出 A = "ABCD" B = "ACD",返回 true

    给出 A = "ABCD" B = "AABC", 返回 false

    function compareStrings(str1,str2,pos){
        if(!str1||!str2||pos>str2.length) return false
        if(str1==str2||pos==str2.length) return true
        var target=str2.charAt(pos)
        var len1=str1.split(target).length
        var len2=str2.split(target).length
        if(len1>=len2){
            pos++
            return compareStrings(str1,str2,pos++)
        }
        return false
    }
    

    60.搜索插入位置 【01-20】 今天是偶滴生日~~~吼吼吼

    给定一个排序数组和一个目标值,如果在数组中找到目标值则返回索引。如果没有,返回到它将会被按顺序插入的位置。

    你可以假设在数组中无重复元素。
    样例
    [1,3,5,6],5 → 2

    [1,3,5,6],2 → 1

    [1,3,5,6], 7 → 4

    [1,3,5,6],0 → 0

    function searchInsert(arr,index){
        var res = arr.indexOf(index)
    if(res<0){
        arr.push(index)
        arr.sort()
        return arr.indexOf(index)
    }else
        return res
    }
    

    64.合并排序数组 II【01-22】

    合并两个排序的整数数组A和B变成一个新的数组。
    样例
    给出 A = [1, 2, 3, empty, empty], B = [4, 5]
    合并之后 A 将变成 [1,2,3,4,5]

    function mergeSortedArray(arr1,arr2){
        arr2.forEach(function(a2){
            arr1.push(a2)
        })
        return arr1.sort()
    }
    

    相关文章

      网友评论

        本文标题:js刷林扣 lintcode(2017年1月)

        本文链接:https://www.haomeiwen.com/subject/ckbdittx.html