我正在處理一項任務，我必須接受用戶輸入的字串并搜索它以找到其中最長的非重復字串。例如：
如果字串是：
"abcabcabcdef"
我的輸出需要是：
"abcdef是 6 個字符的最長子字串"
這是我做的不好的代碼：
class Homework_4
puts "Enter any string of alphabetical characters: "
user_input = gets
longest_str = 0
empty_string = ""
map = {}
i = 0
j = 0
def long_substr()
while j < str_len
if map.key?(user_input[j])
i = [map[user_input[j]], i].max
end
longest_str = [longest_str, j - i 1].max
map[user_input[j]] = j 1
j = 1
end
longest_str
end
long_substr(user_input)
end
我今天已經為此作業了 6 個多小時，但我就是想不通。似乎互聯網有很多方法可以做到這一點。幾乎所有這些都讓我非常困惑，并沒有真正解釋他們在做什么。我不理解他們使用的語法或任何變數或條件。
All I understand is that I need to create two indicators that go through the inputted string searching for a non-repeating substring (sliding window method). I don't understand how to create them, what to make them do or even how to make them find and build the longest substring. It is very confusing to try and read the code that is full of random letters, symbols, and conditions. I'm sure my code is all sorts of messed up but any help or tips that could point me in the right direction would be greatly appreciated!
uj5u.com熱心網友回復：
def uniq?(s)
# All letters of s uniq?
return s.chars.uniq == s.chars
end
def subs(s)
# Return all substrings in s.
(0..s.length).inject([]){|ai,i|
(i..s.length - i).inject(ai){|aj,j|
aj << s[i,j]
}
}.uniq
end
def longest_usub(s)
# Return first longest substring of s.
substrings(s).inject{|res, s| (uniq?(s) and s.length > res.length) ? s : res}
end
ruby'sinject實際上是一個reduce函式，其中inject(optional_start_value){<lambda expression>}- 與lambda expressionPython 類似，lambda x, y: <return expression using x and y>只是 lambda 運算式在 Ruby 中奇怪地寫成{|x, y| <return expression using x and y>}.
Pythonrange(i, y)是 Ruby 的i..y.
Python 的切片s[i:j]使用 Rubys[i..j]或s[i,j].
<<表示添加到陣列的末尾。
第二種解決方案（受@Rajagopalan 的回答啟發）
def usub(s)
# Return first chunk of uniq substring in s
arr = []
s.chars do |char|
break if arr.include? char
arr << char
end
arr.join
end
def usubs(s)
# Return each position's usub() in s
(0..s.length).to_a.map{|i| usub(s[i,s.length])}
end
def longest_usub(s)
# return the longest one of the usubs() over s
usubs(s).max_by(&:length)
end
那么你可以這樣做：
longest_usub("abcabcabcdef")
## "abcdef"
uj5u.com熱心網友回復：
我假設一個字串被定義為重復，如果它包含s一個或一個以上字符的子字串，后跟相同的子字串s，并且如果字串不重復，則字串是不重復的。
當且僅當字串與正則運算式匹配時，才會看到字串重復
R = /([a-z] )\1/
演示
正則運算式為“匹配一個或多個保存到捕獲組 1 的字母，然后匹配捕獲組 1 的內容”。
為方便起見，我們可以構造一個簡單的輔助方法。
def nonrepeating?(str)
!str.match? R
end
我將執行二進制搜索以找到最長的非重復字串。首先，我需要第二個輔助方法：
def find_nonrepeating(str, len)
0.upto(str.size-len) do |i|
s = str[i,len]
return s if nonrepeating?(s)
end
nil
end
find_nonrepeating("abababc", 7) #=> nil
find_nonrepeating("abababc", 6) #=> nil
find_nonrepeating("abababc", 5) #=> nil
find_nonrepeating("abababc", 4) #=> "babc"
find_nonrepeating("abababc", 3) #=> "aba"
find_nonrepeating("abababc", 2) #=> "ab"
find_nonrepeating("abababc", 1) #=> "a"
我們現在可以實作二分查找。
def longest(str)
longest = ''
low = 0
high = str.size - 1
while low < high
mid = (low high)/2
s = find_nonrepeating(str, mid)
if s
longest = s
low = mid 1
else
high = mid - 1
end
end
longest
end
longest("dabcabcdef")
#=> "bcabcdef"
uj5u.com熱心網友回復：
a = "abcabcabcdef"
arr = []
words = []
b=a
a.length.times do
b.chars.each do |char|
break if arr.include? char
arr << char
end
words << arr.join
arr.clear
b=b.chars.drop(1).join
end
p words.map(&:chars).max_by(&:length).join
輸出
"abcdef"
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/445698.html
標籤：ruby