我正在嘗試提高個人技能以解決黑客等級挑戰：有一串小寫英文字母 s 被無限次重復。給定一個整數 n，找出并打印無限字符串的前 n 個字母中字母 a 的個數。1<=s<=100 && 1<=n<=10^12非常天真，我雖然這段代碼會很好：fs := strings.Repeat(s, int(n)) // full stringss := fs[:n] // sub stringfmt.Println(strings.Count(ss, "a"))顯然我爆炸了內存并得到了一個：“內存不足”。我從來沒有遇到過這種問題，而且我對如何處理它一無所知。如何操作很長的字符串以避免內存不足？
2 回答
慕后森
TA貢獻1802條經驗 獲得超5個贊
我希望這會有所幫助，您不必通過遍歷字符串來實際計數。這是天真的做法。你需要使用一些基本的算法來得到答案而不會耗盡內存，我希望這些評論對你有所幫助。
var answer int64
// 1st figure out how many a's are present in s.
aCount := int64(strings.Count(s, "a"))
// How many times will s repeat in its entirety if it had to be of length n
repeats := n / int64(len(s))
remainder := n % int64(len(s))
// If n/len(s) is not perfectly divisible, it means there has to be a remainder, check if that's the case.
// If s is of length 5 and the value of n = 22, then the first 2 characters of s would repeat an extra time.
if remainder > 0{
aCountInRemainder := strings.Count(s[:remainder], "a")
answer = int64((aCount * repeats) + int64(aCountInRemainder))
} else{
answer = int64((aCount * repeats))
}
return answer
可能還有其他方法，但這就是我想到的。
有只小跳蛙
TA貢獻1824條經驗 獲得超8個贊
正如您所發現的，如果您實際生成字符串，您最終將在 RAM 中擁有巨大的內存塊。
表示“傳入字節的大序列”的一種常見方法是將其實現為io.Reader（您可以將其視為字節流），并讓您的代碼運行一個r.Read(buff)循環。
鑒于您提到的練習的具體情況（固定字符串重復n次數），特定字母的出現次數也可以直接根據該字母在 中出現的次數s以及更多內容（我會讓您弄清楚應該做哪些乘法和計數）。
如何實現一個重復字符串而不分配 10^12 倍字符串的閱讀器？
請注意，在實現該.Read()方法時，調用者已經分配了他的緩沖區。您不需要在內存中重復您的字符串，您只需要用正確的值填充緩沖區——例如，將數據逐字節復制到緩沖區中。
這是一種方法：
type RepeatReader struct {
str string
count int
}
func (r *RepeatReader) Read(p []byte) (int, error) {
if r.count == 0 {
return 0, io.EOF
}
// at each iteration, pos will hold the number of bytes copied so far
var pos = 0
for r.count > 0 && pos < len(p) {
// to copy slices over, you can use the built-in 'copy' method
// at each iteration, you need to write bytes *after* the ones you have already copied,
// hence the "p[pos:]"
n := copy(p[pos:], r.str)
// update the amount of copied bytes
pos += n
// bad computation for this first example :
// I decrement one complete count, even if str was only partially copied
r.count--
}
return pos, nil
}
https://go.dev/play/p/QyFQ-3NzUDV
要獲得完整、正確的實施，您還需要跟蹤下次.Read()調用時需要開始的偏移量：
type RepeatReader struct {
str string
count int
offset int
}
func (r *RepeatReader) Read(p []byte) (int, error) {
if r.count == 0 {
return 0, io.EOF
}
var pos = 0
for r.count > 0 && pos < len(p) {
// when copying over to p, you should start at r.offset :
n := copy(p[pos:], r.str[r.offset:])
pos += n
// update r.offset :
r.offset += n
// if one full copy of str has been issued, decrement 'count' and reset 'offset' to 0
if r.offset == len(r.str) {
r.count--
r.offset = 0
}
}
return pos, nil
}
https://go.dev/play/p/YapRuioQcOz
您現在可以a在遍歷此 Reader 時計算 s。
- 2 回答
- 0 關注
- 136 瀏覽
添加回答
舉報
0/150
提交
取消