最长公共前缀
本帖最后由 wwwwwllllk 于 2022-11-13 17:01 编辑这篇文章本来是为了最长公共前缀解决问题遇到的情况，但是提交的代码发现自己题意理解错了。前缀就是从头开始就叫前缀，这样一下就排除了好多情况。
https://bbs.tampermonkey.net.cn/thread-3616-1-1.html
下面的代码通过了，但是肯定是可以优化的，但是今天早上提了不下10次了，实在不想改了。但是思路是没问题的。哥哥们有好的思路可以评论下面说一下，dd学习一下.
```
var longestCommonPrefix = function(strs) {
// 最上面直接考虑一下数组中只有一个元素的情况吧
if(strs.length == 1) {
return strs
}
// 获取最小值有多少个连续的组合
function getMinValueCollection(str){
let left = 0
let right = 1
// 计算执行了几个来回，刚开始是0来回
let count = 0
// 01 12 2302 13 03
let list = []
while(count !== str.length) {
if(right == str.length) {
count += 1
list.push(str.slice(left,right))
left = 0
right = 1 + count
} else {
list.push(str.slice(left,right))
left++
right++
}
}
// 使用new Set去重
list = new Set(list)
return list
}
// 找出最小的字符串
let minValue = null
// 公共的值的组合
let commonList = {}
strs.map((item,index) => {
if(minValue && minValue.length < item.length){
}else {
minValue = item
}
})
let minValueCollection = getMinValueCollection(minValue)
debugger
// 把最小的字符串过滤出来
newStrs = strs.filter((item) => item!== minValue)
// 为了解决["flower","flower","flower","flower"] 这种情况
if(strs.length > 0 && newStrs.length == 0) {
return strs
}
for(let val of minValueCollection) {
newStrs.map((item) => {
// 这样写直接就是前缀的情况下进行的操作["abca","aba","aaab"]解决这个问题
if(item.indexOf(val) == 0){
// 加这个if是为了防止出现["dog","racecar","car"]，如果有一个元素都有的时候我们应该设置为false
if(commonList == false) {
} else {
commonList = true
}
} else {
commonList = false
}
})
}
if(JSON.stringify(commonList) == '{}') {
return ''
} else {
// 过滤出为true的
let result = []
result = Object.entries(commonList).filter(item =>item )
console.log(result)
// 最长前缀
let maxQianZhui = ''
result.map((item) => {
// 这里就需要判断是不是公共前缀了
strs.map((item1) => {
if(item1.indexOf(item) !== 0){
} else {
if(item.length > maxQianZhui.length) {
maxQianZhui = item
}
}
})
})
console.log('maxQianZhui',maxQianZhui)
// 判断是不是公共前缀(这里也得加一下)
// 前缀没理解到位，写复杂了，但是不想改了，我最后for循环判断一下了
strs.map((item) => {
if(item.indexOf(maxQianZhui) !== 0){
maxQianZhui = ''
}
})
return maxQianZhui
}
};
console.log(longestCommonPrefix(["abca","aba","aaab"]))
``` 本帖最后由 steven026 于 2022-11-13 14:33 编辑
如果只是为了找最长公共前缀，为什么要写的那么复杂
先把数组按长度排序，找出最短的字符串，然后遍历最短字符串的所有前缀，如果每个数组元素都以这个前缀开头说明这个就是公共前缀
function longestCommonPrefix(arr) {
if (arr.length < 2) return
let shortest = arr.sort((a, b) => a.length - b.length)
let result = null
for (let i = 1; i < shortest.length; i++) {
const prefix = shortest.slice(0, i)
if (arr.findIndex(item => !item.startsWith(prefix)) > -1) break
result = prefix
}
return result
} steven026 发表于 2022-11-13 14:31
如果只是为了找最长公共前缀，为什么要写的那么复杂
先把数组按长度排序，找出最短的字符串，然后遍历最短 ...
确实，刚开始漏掉了前缀的理解了。 哥哥开始搞算法了？ 王一之 发表于 2022-11-13 16:41
哥哥开始搞算法了？
没办法，小公司面试都要考算法了
页:
[1]