乐趣区

关于kotlin:算法-Notes|LeetCode-14-最长公共前缀-easy

前言

对于算法,集体感觉,有的只是本人辛苦,私下多思考,多画图,多了解。

没有最好的形式,也没有最快捷的法子,有的只是本人摸索中一直前行,附上之前刷题笔记:

  • 算法 Notes|LeetCode 349. 两个数组的交加 – easy

多想,多画,多练,多思考,多了解,多分享,莫慌,莫怕,一步一足迹前行。

加油~

GitHub 地址如下:

  • https://github.com/HLQ-Strugg…

14. 最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀,返回空字符串 “”。

示例 1:

 输出: ["flower","flow","flight"]
输入: "fl"

示例 2:

 输出: ["dog","racecar","car"]
输入: ""
解释: 输出不存在公共前缀。

阐明:

  • 所有输出只蕴含小写字母 a-z。

暴力解法一

入上草图,说思路:

  • 根本校验,输出数组为空间接 return,输出数组只有一个时,同理间接 return;
  • 取数组中第一个为基数,顺次判断数组中 char 是否相等,同时更新数组比对后果,也就是基数内容;当基数为空时,间接 return。

这里首要明确,最长公共,也就是从数组中的每一个开始比对,如果呈现不一样则进行比对。当初我就是这里犯了嘀咕。

这里附上代码:

fun longestCommonPrefix(strs: Array<String>): String {
    var resultStr = ""
    if (strs.isEmpty()) {return resultStr}
    if (strs.size == 1) {return strs[0]
    }
    resultStr = strs[0]
    for(str in strs){
        var j = 0
        while (j < resultStr.length && j < str.length){if(str.toCharArray()[j] != resultStr.toCharArray()[j]){break}
            j++
        }
        resultStr = resultStr.substring(0,j)
        if(resultStr.isEmpty()){break}
    }
    return resultStr
}

耗费状况:

暴力解法二

在 Debug 过程中,忽然发现第一种解法的循环比对是从头开始的。这块其实应该是从数组第一位开始,因为一开始就选取了数组第 0 位作为基数进行比照,这里革新下代码,缩小一层循环:

fun longestCommonPrefix2(strs: Array<String>): String {
    var resultStr = ""
    if (strs.isEmpty()) {return resultStr}
    if (strs.size == 1) {return strs[0]
    }
    resultStr = strs[0]
    for(i in 1 until strs.size){
        var j = 0
        while (j < resultStr.length && j < strs[i].length){if(strs[i].toCharArray()[j] != resultStr.toCharArray()[j]){break}
            j++
        }
        resultStr = resultStr.substring(0,j)
        if(resultStr.isEmpty()){break}
    }
    return resultStr
}

耗费状况:

暴力解法三

忽然想到为什么每次都要 toCharArray() 呢?我间接取对应的值不好么?

再次革新下代码:

class Solution {fun longestCommonPrefix(strs: Array<String>): String {
        var resultStr = ""
        if (strs.isEmpty()) {return resultStr}
        if (strs.size == 1) {return strs[0]
        }
        var len = strs.size
        Arrays.sort(strs)
        for (i in strs[0].indices){if(strs[len-1][i] == strs[0][i]){resultStr += strs[0][i]
            }else{break}
        }
        return resultStr
    }
}

耗费状况:

学习下大佬解法 – 排序法

思考以及通过 Debug 后得出思路如下:

  • 根本校验同上,不再累述;
  • 对数组进行排序,比照第一个和最初一个。复杂度我猜想应该基于数组的排序这块。

简略举个例子:

现提供数组如下:

  • {“flower”, “flow”, “flight”}

通过排序后,变成:

  • {“flight”, “flow”, “flower”}

随后间接比照数组第一个和最初一个即可。

最终得出最长公共前缀为:

  • fl

贴一下代码局部:

fun longestCommonPrefix3(strs: Array<String>): String {
    var resultStr = ""
    if (strs.isEmpty()) {return resultStr}
    if (strs.size == 1) {return strs[0]
    }
    val len = strs.size
    Arrays.sort(strs)
    for (i in strs[0].indices){if(strs[len-1][i] == strs[0][i]){resultStr += strs[0][i]
        }else{break}
    }
    return resultStr
}

耗费状况:

这种解法有点纳闷

在 LeetCode 中,最优解提醒我是如下这种计划。然而理论提交后,并没有发现哪儿最优。

而且 LeetCode 雷同的代码段提交两次,工夫以及耗费并不一样,很奇怪。

简略说下这种解法吧。

  • 同样的校验,只是另外对数组一个元素进行了判空;
  • 首先获取数组中最短的长度;
  • 随后获取到雷同索引;
  • 最初截取返回

简略举个例子:

给定数组如下:

  • {“flower”, “flow”, “flight”}

此处疏忽后期根本校验。

获取提供数组中最短长度,也就是 flow 4 位。而后按照数组第一个进行比对,三者雷同内容的索引为 1,也就是 fl。最初间接 return 裁剪此索引即可。

以下附上代码:

fun longestCommonPrefix4(strs: Array<String>): String {if (strs.isEmpty()) {return ""}
    if (strs.size == 1) {return if(strs[0].isEmpty()) "" else strs[0]
    }
    // 获取输出数组中最短长度
    var min = Int.MAX_VALUE
    for(str in strs){if(min > str.length){min = str.length}
    }
    // 获取最初一次雷同的地位
    var isl = true
    var index = 0
    while (index < min){for(i in strs.indices){if(strs[0][index] != strs[i][index]){
                isl = false
                break
            }
        }
        if(!isl){break}
        index++
    }
    return strs[0].substring(0,index)
}

耗费工夫:

为了防止大佬喷我,此处放出此解法地址:

End

算法这货色,真是的,多练习,多画图,多 Debug,缓缓转化本人的货色。

这个思维真的蛮不错的,至多目前的本人仿佛是感触到了那么一丝丝。

另外有点本人的小心得就是:

  • 不要上来就求最优解。这个货色没有肯定的积攒是不可能的,哪儿有那么多的蠢才。先从暴力开始,缓缓优化。多看看前辈的代码,多学学,了解人的思维。

另外就是,技术提高的实质就是分享,思维的交换能够衍生出多种微妙的想法。

一起加油呀~

欢送大佬指导~

参考资料

  • 最长公共前缀 (14)
  • 离奇的排序算法
退出移动版