我正在嘗試提高個(gè)人技能以解決黑客等級(jí)挑戰(zhàn)：有一串小寫(xiě)英文字母 s 被無(wú)限次重復(fù)。給定一個(gè)整數(shù) n，找出并打印無(wú)限字符串的前 n 個(gè)字母中字母 a 的個(gè)數(shù)。1<=s<=100 && 1<=n<=10^12非常天真，我雖然這段代碼會(huì)很好：fs := strings.Repeat(s, int(n)) // full stringss := fs[:n] // sub stringfmt.Println(strings.Count(ss, "a"))顯然我爆炸了內(nèi)存并得到了一個(gè)：“內(nèi)存不足”。我從來(lái)沒(méi)有遇到過(guò)這種問(wèn)題，而且我對(duì)如何處理它一無(wú)所知。如何操作很長(zhǎng)的字符串以避免內(nèi)存不足？
2 回答
慕后森
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超5個(gè)贊
我希望這會(huì)有所幫助，您不必通過(guò)遍歷字符串來(lái)實(shí)際計(jì)數(shù)。這是天真的做法。你需要使用一些基本的算法來(lái)得到答案而不會(huì)耗盡內(nèi)存，我希望這些評(píng)論對(duì)你有所幫助。
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貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超8個(gè)贊
正如您所發(fā)現(xiàn)的，如果您實(shí)際生成字符串，您最終將在 RAM 中擁有巨大的內(nèi)存塊。
表示“傳入字節(jié)的大序列”的一種常見(jiàn)方法是將其實(shí)現(xiàn)為io.Reader（您可以將其視為字節(jié)流），并讓您的代碼運(yùn)行一個(gè)r.Read(buff)循環(huán)。
鑒于您提到的練習(xí)的具體情況（固定字符串重復(fù)n次數(shù)），特定字母的出現(xiàn)次數(shù)也可以直接根據(jù)該字母在 中出現(xiàn)的次數(shù)s以及更多內(nèi)容（我會(huì)讓您弄清楚應(yīng)該做哪些乘法和計(jì)數(shù)）。
如何實(shí)現(xiàn)一個(gè)重復(fù)字符串而不分配 10^12 倍字符串的閱讀器？
請(qǐng)注意，在實(shí)現(xiàn)該.Read()方法時(shí)，調(diào)用者已經(jīng)分配了他的緩沖區(qū)。您不需要在內(nèi)存中重復(fù)您的字符串，您只需要用正確的值填充緩沖區(qū)——例如，將數(shù)據(jù)逐字節(jié)復(fù)制到緩沖區(qū)中。
這是一種方法：
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
要獲得完整、正確的實(shí)施，您還需要跟蹤下次.Read()調(diào)用時(shí)需要開(kāi)始的偏移量：
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
您現(xiàn)在可以a在遍歷此 Reader 時(shí)計(jì)算 s。
- 2 回答
- 0 關(guān)注
- 149 瀏覽
添加回答
舉報(bào)
0/150
提交
取消