Golang вопросы собеседований

👣 Решаем задачи. Реализуем алгоритм «Посмотри-и-скажи» (Count and Say).



«Посмотри-и-скажи» — это последовательность чисел, начинающаяся следующим образом:



1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211,… (последовательность A005150 в OEIS).



Каждое последующее число генерируется из предыдущего путём конкатенации цифры, из которой состоит группа одинаковых цифр и количества цифр в этой группе, для каждой группы одинаковых цифр в числе.



Решим задачу с leetcode: https://leetcode.com/problems/count-and-say



Пример1:

Input: n = 1

Output: '1'



Пример2:

Input: n = 4

Output: '1211'

Explanation:

countAndSay(1) = '1'

countAndSay(2) = say '1' = one 1 = '11'

countAndSay(3) = say '11' = two 1's = '21'

countAndSay(4) = say '21' = one 2 + one 1 = '12' + '11' = '1211'



Ограничения:



- 1 <= n <= 30



Решение:



func countAndSay(n int) string {

dp := make([]string, n + 1)

dp[1] = '1'

var current, next string

counter := 1



for i := 2; i <= n; i++ {

current = dp[i - 1]

next = ''



counter = 1



for j := 1; j < len(current); j++ {

if current[j - 1] == current[j] {

counter++

} else {

next += strconv.Itoa(counter) + string(current[j - 1])

counter = 1

}

}



next += strconv.Itoa(counter) + current[len(current) - 1:]



dp[i] = next

}



return dp[n]

}



👉 Пишите свое решение в комментариях👇



@golang_interview