Задача: №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
Задача: №18. 4Sum #medium
Условие:
Решение:
Пояснение:
Сортировка массива:
Сначала массив nums сортируется, чтобы облегчить работу с индексами и избежать повторений в комбинациях. Сортировка также упрощает использование двухсвязных указателей для поиска.
Внешний цикл для первой вершины:
Внешний цикл итерирует по элементам массива, рассматривая каждый элемент как первую вершину (a) в наборе из четырех чисел.
Удаление дубликатов:
Если текущий элемент такой же, как предыдущий, он пропускается, чтобы избежать дублирующихся комбинаций.
Второй цикл для второй вершины:
Второй цикл начинается с элемента сразу после текущего элемента внешнего цикла и рассматривает его как вторую вершину (b).
Удаление дубликатов для второй вершины:
Аналогично, если элемент второй вершины совпадает с предыдущим элементом, он пропускается.
Инициализация двухсвязных указателей:
start и end устанавливаются на следующий элемент после второго элемента и на последний элемент массива соответственно.
Тройное соединение:
Используются два указателя (start и end) для перебора оставшихся двух чисел, чтобы сформировать набор из четырех чисел (a, b, nums[start], nums[end]).
Если сумма этих четырех чисел меньше target, указатель start сдвигается вправо, чтобы увеличить сумму.
Если сумма больше target, указатель end сдвигается влево, чтобы уменьшить сумму.
Если сумма равна target, комбинация добавляется в результат, и оба указателя сдвигаются для поиска следующей комбинации.
Удаление дубликатов после обработки:
После добавления комбинации проверяются и, если необходимо, пропускаются все дубликаты, чтобы убедиться, что каждая комбинация в результатах уникальна.
Возврат результата:
После завершения всех итераций возвращается список всех уникальных наборов четырех чисел, сумма которых равна target.
Условие:
Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:
0 <= a, b, c, d < n
a, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цель
Вы можете вернуть ответ в любом порядке.
Решение:
func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
res := [][]int{}
for i:=0; i<len(nums)-3; i++ {
for i>0 && i<len(nums) && nums[i]==nums[i-1] {
i++
}
for j:=i+1; j<len(nums); j++ {
for j>i+1 && j<len(nums) && nums[j]==nums[j-1] {
j++
}
start:=j+1
end:=len(nums)-1
for start<end {
if (nums[start]+nums[end]+nums[i]+nums[j])<target {
start++
for start< len(nums) && nums[start]==nums[start-1] {
start++
}
} else if (nums[start]+nums[end]+nums[i]+nums[j])>target {
end--
for end>0 && nums[end]==nums[end+1] {
end--
}
} else {
res = append(res, []int{nums[i], nums[j], nums[start], nums[end]})
start++
end--
for start<len(nums) && nums[start]==nums[start-1] {
start++
}
for end>0 && nums[end]==nums[end+1] {
end--
}
}
}
}
}
return res
}Пояснение:
Сортировка массива:
Сначала массив nums сортируется, чтобы облегчить работу с индексами и избежать повторений в комбинациях. Сортировка также упрощает использование двухсвязных указателей для поиска.
Внешний цикл для первой вершины:
Внешний цикл итерирует по элементам массива, рассматривая каждый элемент как первую вершину (a) в наборе из четырех чисел.
Удаление дубликатов:
Если текущий элемент такой же, как предыдущий, он пропускается, чтобы избежать дублирующихся комбинаций.
Второй цикл для второй вершины:
Второй цикл начинается с элемента сразу после текущего элемента внешнего цикла и рассматривает его как вторую вершину (b).
Удаление дубликатов для второй вершины:
Аналогично, если элемент второй вершины совпадает с предыдущим элементом, он пропускается.
Инициализация двухсвязных указателей:
start и end устанавливаются на следующий элемент после второго элемента и на последний элемент массива соответственно.
Тройное соединение:
Используются два указателя (start и end) для перебора оставшихся двух чисел, чтобы сформировать набор из четырех чисел (a, b, nums[start], nums[end]).
Если сумма этих четырех чисел меньше target, указатель start сдвигается вправо, чтобы увеличить сумму.
Если сумма больше target, указатель end сдвигается влево, чтобы уменьшить сумму.
Если сумма равна target, комбинация добавляется в результат, и оба указателя сдвигаются для поиска следующей комбинации.
Удаление дубликатов после обработки:
После добавления комбинации проверяются и, если необходимо, пропускаются все дубликаты, чтобы убедиться, что каждая комбинация в результатах уникальна.
Возврат результата:
После завершения всех итераций возвращается список всех уникальных наборов четырех чисел, сумма которых равна target.
👍1🤔1
Задача: №19. Remove Nth Node From End of List #medium
Условие:
Решение:
Пояснение:
Создание фиктивного узла:
В начале создается фиктивный узел (res) с значением 0, и его следующим элементом становится head. Это помогает упростить управление крайними случаями, такими как удаление первого узла списка.
Указатель вперед:
Указатель lead инициализируется на res. Целью этого указателя является перемещение на n+1 узел вперед, чтобы создать "разрыв" между двумя указателями: lead и cur.
Перемещение указателя lead вперед:
Цикл сдвигает указатель lead вперед на n+1 шагов. Таким образом, после завершения цикла lead окажется на (n+1)-ом узле от начала списка.
Перемещение указателей lead и cur до конца списка:
Далее, перемещая оба указателя (lead и cur) одновременно, пока lead не достигнет конца списка (nil). Указатель cur будет находиться на узле перед тем, который нужно удалить.
Удаление узла:
Когда lead достигает конца, cur указывает на узел перед узлом, который нужно удалить. Чтобы удалить этот узел, просто переопределяется указатель cur.Next на cur.Next.Next. Это effectively убирает узел, который находится на n-ом месте с конца.
Возврат нового списка:
Возвращается res.Next, который указывает на начальный узел списка, исключая фиктивный узел.
Условие:
Учитывая заголовок связанного списка, удалите n-й узел из конца списка и верните его заголовок.
Решение:
func removeNthFromEnd(head *ListNode, n int) *ListNode {
res := &ListNode{0, head}
lead := res
for i := 0; i <= n; i++ {
lead = lead.Next
}
cur := res
for lead != nil {
cur = cur.Next
lead = lead.Next
}
cur.Next = cur.Next.Next
return res.Next
}Пояснение:
Создание фиктивного узла:
В начале создается фиктивный узел (res) с значением 0, и его следующим элементом становится head. Это помогает упростить управление крайними случаями, такими как удаление первого узла списка.
Указатель вперед:
Указатель lead инициализируется на res. Целью этого указателя является перемещение на n+1 узел вперед, чтобы создать "разрыв" между двумя указателями: lead и cur.
Перемещение указателя lead вперед:
Цикл сдвигает указатель lead вперед на n+1 шагов. Таким образом, после завершения цикла lead окажется на (n+1)-ом узле от начала списка.
Перемещение указателей lead и cur до конца списка:
Далее, перемещая оба указателя (lead и cur) одновременно, пока lead не достигнет конца списка (nil). Указатель cur будет находиться на узле перед тем, который нужно удалить.
Удаление узла:
Когда lead достигает конца, cur указывает на узел перед узлом, который нужно удалить. Чтобы удалить этот узел, просто переопределяется указатель cur.Next на cur.Next.Next. Это effectively убирает узел, который находится на n-ом месте с конца.
Возврат нового списка:
Возвращается res.Next, который указывает на начальный узел списка, исключая фиктивный узел.
👍1🤔1