Задача: №16. 3Sum Closest #medium
Условие:
Решение:
Пояснение:
Сортировка массива:
Сначала функция сортирует массив nums. Сортировка упрощает задачу поиска трех чисел, сумма которых близка к заданному значению, поскольку позволяет эффективно использовать двухсвязный указатель для поиска.
Инициализация переменных:
ans используется для хранения ответа — суммы трех чисел, наиболее близкой к target.
diff хранит минимальное различие между суммой трех чисел и target. Изначально оно установлено в math.MaxInt для обеспечения того, что любая первая сумма будет меньше этого значения.
Основной цикл:
Внешний цикл итерирует по элементам массива nums, рассматривая каждый элемент как первую вершину трех чисел.
Внутренний цикл использует двухсвязный указатель (low и high) для перебора оставшихся двух элементов массива, начиная с элементов, находящихся сразу после текущего элемента внешнего цикла и до конца массива.
Проверка сумм и обновление ответа:
Для каждого сочетания трех чисел (nums[i], nums[low], nums[high]) проверяется их сумма:
Если сумма равна target, возвращается target сразу, так как это идеальное совпадение.
В противном случае, если текущая сумма ближе к target, чем предыдущие, обновляется переменная diff и ans.
Если сумма больше target, указатель high сдвигается влево, чтобы уменьшить сумму.
Если сумма меньше target, указатель low сдвигается вправо, чтобы увеличить сумму.
Возврат результата:
После завершения всех итераций возвращается значение ans, которое представляет собой сумму трех чисел, наиболее близкую к target.
Условие:
Учитывая целочисленный массив nums длины n и целочисленную цель, найдите три целых числа в nums, сумма которых наиболее близка к цели. Возвращает сумму трех целых чисел. Вы можете предположить, что каждый вход будет иметь ровно одно решение.
Решение:
func threeSumClosest(nums []int, target int) int {
sort.Ints(nums)
var ans int
diff:=math.MaxInt
for i:=0;i<len(nums)-2;i++{
low:=i+1
high:=len(nums)-1
for low<high{
if nums[i]+nums[low]+nums[high]==target{
ans=target
return ans
}else if int(math.Abs(float64(nums[i]+nums[low]+nums[high]-target)))<diff{
diff=int(math.Abs(float64(nums[i]+nums[low]+nums[high]-target)))
ans=nums[i]+nums[low]+nums[high]
}
if nums[i]+nums[low]+nums[high]>target{
high--
}else{
low++
}
}
}
return ans
}Пояснение:
Сортировка массива:
Сначала функция сортирует массив nums. Сортировка упрощает задачу поиска трех чисел, сумма которых близка к заданному значению, поскольку позволяет эффективно использовать двухсвязный указатель для поиска.
Инициализация переменных:
ans используется для хранения ответа — суммы трех чисел, наиболее близкой к target.
diff хранит минимальное различие между суммой трех чисел и target. Изначально оно установлено в math.MaxInt для обеспечения того, что любая первая сумма будет меньше этого значения.
Основной цикл:
Внешний цикл итерирует по элементам массива nums, рассматривая каждый элемент как первую вершину трех чисел.
Внутренний цикл использует двухсвязный указатель (low и high) для перебора оставшихся двух элементов массива, начиная с элементов, находящихся сразу после текущего элемента внешнего цикла и до конца массива.
Проверка сумм и обновление ответа:
Для каждого сочетания трех чисел (nums[i], nums[low], nums[high]) проверяется их сумма:
Если сумма равна target, возвращается target сразу, так как это идеальное совпадение.
В противном случае, если текущая сумма ближе к target, чем предыдущие, обновляется переменная diff и ans.
Если сумма больше target, указатель high сдвигается влево, чтобы уменьшить сумму.
Если сумма меньше target, указатель low сдвигается вправо, чтобы увеличить сумму.
Возврат результата:
После завершения всех итераций возвращается значение ans, которое представляет собой сумму трех чисел, наиболее близкую к target.
🤔3👍1
Задача: №17. Letter Combinations of a Phone Number #medium
Условие:
Решение:
Пояснение:
1. Сопоставление цифр с буквами:
- Задача заключается в генерации всех возможных комбинаций букв, которые могут представлять данную строку цифр (от 2 до 9).
- Мы начинаем с создания хэш-таблицы, которая сопоставляет каждую цифру соответствующим буквам на телефонной клавиатуре. Например:
2. Итерация по цифрам:
- Внешний цикл проходит по входной строке digits справа налево (начиная с последней цифры).
- Для каждой цифры мы извлекаем соответствующие буквы из хэш-таблицы.
3. Комбинирование существующих комбинаций:
- Внутри цикла мы поддерживаем список res_comb (изначально пустой) для хранения результирующих комбинаций.
- Если res_comb не пуст (т.е. мы обработали хотя бы одну цифру), мы комбинируем текущие буквы с существующими комбинациями:
- Для каждой буквы в буквах текущей цифры:
- Для каждой существующей комбинации в res_comb:
- Добавляем текущую букву к существующей комбинации.
- Добавляем модифицированную комбинацию в new_comb.
- Если res_comb пуст (т.е. это первая цифра), мы напрямую добавляем буквы из текущей цифры в new_comb.
4. Обновление результата:
- После обработки всех цифр мы обновляем res_comb содержимым new_comb.
5. Итоговый результат:
- Итоговый результат хранится в res_comb, содержащем все возможные комбинации букв.
6. Сложность по времени и памяти:
- Временная сложность зависит от количества цифр и максимального числа букв на цифру.
- Пространственная сложность определяется размером списка вывода.
Условие:
Учитывая строку, содержащую цифры от 2 до 9 включительно, верните все возможные комбинации букв, которые может представлять число. Верните ответ в любом порядке. Соответствие цифр буквам (как на кнопках телефона) приведено ниже. Обратите внимание, что 1 не соответствует никаким буквам.
Решение:
func letterCombinations(digits string) []string {
hash_table := map[byte][]byte{'2': []byte{'a', 'b', 'c'},
'3': []byte{'d', 'e', 'f'},
'4': []byte{'g', 'h', 'i'},
'5': []byte{'j', 'k', 'l'},
'6': []byte{'m', 'n', 'o'},
'7': []byte{'p', 'q', 'r', 's'},
'8': []byte{'t', 'u', 'v'},
'9': []byte{'w', 'x', 'y', 'z'}}
res_comb := []string{}
for len(digits) > 0 {
cur := hash_table[digits[len(digits)-1]]
digits = digits[:len(digits)-1]
new_comb := []string{}
if len(res_comb) > 0 {
for i := 0; i < len(cur); i++ {
for j := 0; j < len(res_comb); j++ {
new_comb = append(new_comb, string(cur[i]) + res_comb[j])
}
}
}else{
for _, val := range cur {
new_comb = append(new_comb, string(val))
}
}
res_comb = make([]string, len(new_comb))
copy(res_comb, new_comb)
}
return res_comb
}Пояснение:
1. Сопоставление цифр с буквами:
- Задача заключается в генерации всех возможных комбинаций букв, которые могут представлять данную строку цифр (от 2 до 9).
- Мы начинаем с создания хэш-таблицы, которая сопоставляет каждую цифру соответствующим буквам на телефонной клавиатуре. Например:
2. Итерация по цифрам:
- Внешний цикл проходит по входной строке digits справа налево (начиная с последней цифры).
- Для каждой цифры мы извлекаем соответствующие буквы из хэш-таблицы.
3. Комбинирование существующих комбинаций:
- Внутри цикла мы поддерживаем список res_comb (изначально пустой) для хранения результирующих комбинаций.
- Если res_comb не пуст (т.е. мы обработали хотя бы одну цифру), мы комбинируем текущие буквы с существующими комбинациями:
- Для каждой буквы в буквах текущей цифры:
- Для каждой существующей комбинации в res_comb:
- Добавляем текущую букву к существующей комбинации.
- Добавляем модифицированную комбинацию в new_comb.
- Если res_comb пуст (т.е. это первая цифра), мы напрямую добавляем буквы из текущей цифры в new_comb.
4. Обновление результата:
- После обработки всех цифр мы обновляем res_comb содержимым new_comb.
5. Итоговый результат:
- Итоговый результат хранится в res_comb, содержащем все возможные комбинации букв.
6. Сложность по времени и памяти:
- Временная сложность зависит от количества цифр и максимального числа букв на цифру.
- Пространственная сложность определяется размером списка вывода.
🤔3