Задача: №16. 3Sum Closest #medium

Условие:

Учитывая целочисленный массив 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.

Задача: №17. Letter Combinations of a Phone Number #medium

Условие:

Учитывая строку, содержащую цифры от 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. Сложность по времени и памяти:
- Временная сложность зависит от количества цифр и максимального числа букв на цифру.
- Пространственная сложность определяется размером списка вывода.

Задача: №18. 4Sum #medium

Условие:

Учитывая массив 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.

Задача: №19. Remove Nth Node From End of List #medium

Условие:

Учитывая заголовок связанного списка, удалите 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, который указывает на начальный узел списка, исключая фиктивный узел.

Задача: №20. Valid Parentheses #easy

Условие:

Учитывая строку s, содержащую только символы '(', ')', '{', '}', '[' и ']', определите, является ли входная строка допустимой. Входная строка действительна, если: Открытые скобки должны закрываться скобками того же типа.
Открытые скобки должны закрываться в правильном порядке.
Каждой закрывающей скобке соответствует открытая скобка того же типа.

Решение:

import (
    GOG "github.com/emirpasic/gods/stacks/arraystack"
)

func isValid(s string) bool {

    var coolStack = GOG.New()

 for _, v := range s {
  stringv := string(v)
  if stringv == "("  stringv == "{"  stringv == "[" {
   coolStack.Push(stringv)
  } else if stringv == ")" {
            tempCoolVal, _ := coolStack.Pop()
   if tempCoolVal == "(" {
                continue
            } else {
                return false
            }
  } else if stringv == "}" {
   tempCoolVal, _ := coolStack.Pop()
   if tempCoolVal == "{" {
                continue
            } else {
                return false
            }
  } else if stringv == "]" {
   tempCoolVal, _ := coolStack.Pop()
   if tempCoolVal == "[" {
                continue
            } else {
                return false
            }
  } else {
            return false
        }
 }

    _, yeahCool := coolStack.Pop()

 return !yeahCool
}

Пояснение:
Инициализация стека:

Функция использует стек coolStack из библиотеки gods. Стек применяется для хранения открывающих скобок.
Проход по строке:

Функция итерирует по каждому символу в строке s. Для каждого символа выполняются следующие действия:
Если символ является открывающей скобкой (, {, или [, он добавляется в стек.
Если символ является закрывающей скобкой ), }, или ], происходит проверка:
Извлекается элемент из стека.
Если извлеченный элемент соответствует соответствующей открывающей скобке, процесс продолжается.
Если извлеченный элемент не соответствует, возвращается false, так как строки не сбалансированы.
Проверка на пустоту стека:

После обработки всех символов в строке, стек должен быть пустым, если все скобки правильно сбалансированы. Если стек не пуст, это означает, что есть открывающие скобки, которые не имеют соответствующих закрывающих скобок, и функция возвращает false.
Возврат результата:

Если стек пуст после всех проверок, это означает, что все скобки были правильно сбалансированы, и функция возвращает true. В противном случае, функция возвращает false.

Задача: 46. Permutations #medium
Условие:

Учитывая массив nums, состоящий из различных целых чисел, верните все возможные перестановки. Вы можете вернуть ответ в любом порядке.

Решение:

func permute(nums []int) [][]int {
  result := make([][]int, 0)

  // define inner function
  var backTracking func(permutation []int)
  backTracking = func(permutation []int) {
    if len(permutation) == len(nums) {
      copyPermutation := make([]int, len(nums))
      copy(copyPermutation, permutation)
      result = append(result, copyPermutation)
      return
    }

    for _, num := range nums {
      isAdded := false
      for _, element := range permutation {
        if num == element {
          isAdded = true
          break
        }
      }

      if !isAdded {
        permutation = append(permutation, num)
        backTracking(permutation)
        permutation = permutation[:len(permutation)-1]
      }
    }
  }

  backTracking(make([]int, 0))
  return result
}

Пояснение:
Код выше реализует функцию `permute`, которая принимает массив целых чисел `nums` и возвращает все возможные перестановки этих чисел. Функция использует метод обратного отслеживания (backtracking) для генерации всех возможных перестановок.

Функция `permute` создает пустой результат `result` типа `[][]int`, где каждый элемент представляет собой одну перестановку.

Внутри функции `permute` определена внутренняя функция `backTracking`, которая рекурсивно генерирует все возможные перестановки. Если длина текущей перестановки равна длине исходного массива `nums`, то добавляем эту перестановку в результат.

Затем проходим по каждому элементу из исходного массива `nums`. Если элемент еще не был добавлен в текущую перестановку, то добавляем его, рекурсивно вызываем `backTracking`, а затем удаляем его из текущей перестановки перед продолжением итерации.

В конце вызываем `backTracking` с пустой начальной перестановкой и возвращаем результат.

Этот код позволяет генерировать все возможные перестановки исходного массива.

Задача: 45. Jump Game ll #medium
Условие:

Вам предоставляется массив целых чисел nums с индексом 0 и длиной n. Изначально вы располагаетесь в nums [0].
Каждый элемент nums [i] представляет максимальную длину прямого перехода от индекса i. Другими словами, если вы находитесь в nums [1], вы можете перейти к любому nums [i + j], где:
• <=j<= nums[i] и
• i+j <n
Возвращает минимальное количество переходов для достижения nums [n -
11. Тестовые примеры генерируются таким образом, чтобы вы могли достичь значений [n - 1].

Решение:

func jump(nums []int) int {
  if len(nums) <= 1 {
    return 0
  }

  var maxIdx, i, step int
  for i < len(nums)-1 {
    nextIdx, tmpIdx := 0, 0
    for j := 0; j < nums[i]; j++ {
      tmpIdx = i + j + 1
      if tmpIdx < len(nums) && tmpIdx+nums[tmpIdx] > maxIdx {
        maxIdx = tmpIdx + nums[tmpIdx]
        nextIdx = tmpIdx
      }
      if tmpIdx == len(nums)-1 {
        nextIdx = tmpIdx
      }
    }

    i = nextIdx
    step++
  }

  return step
}

Пояснение:
1. Функция `jump` предназначена для определения минимального количества прыжков, необходимых для достижения последнего элемента в массиве `nums`, если каждый элемент массива представляет максимальное количество индексов, на которое можно прыгнуть.
2. Начнем с проверки базового случая: если длина массива `nums` меньше или равна 1, функция возвращает 0, так как не требуется никаких прыжков.
3. В функции используются переменные `maxIdx` (максимальный индекс, до которого можно прыгнуть), `i` (текущий индекс) и `step` (общее количество прыжков).
4. В цикле `for` мы итерируемся до предпоследнего элемента массива `nums` (так как работаем с парами индексов).
5. Во внутреннем цикле `for` проверяется каждый возможный прыжок из текущего индекса `i`, и определяется следующий индекс `nextIdx`, куда необходимо совершить прыжок. Мы также обновляем `maxIdx`, чтобы выбрать оптимальный путь и уменьшить количество шагов.
6. После обработки всех возможных прыжков обновляем текущий индекс `i` до `nextIdx` и увеличиваем количество шагов `step` на один.
7. Функция продолжает выполнение, пока `i` не достигнет предпоследнего индекса (так как мы всегда делаем прыжок на следующий элемент).
8. Наконец, функция возвращает общее количество прыжков `step`, необходимых для достижения последнего элемента массива `nums`. Данный код реализует жадный алгоритм для нахождения минимального количества прыжков.

Задача: 44. Wildcard Matching
#hard
Условие:

Учитывая входную строку (строки) и шаблон (p), реализуйте сопоставление шаблонов с подстановочными знаками с поддержкой '?' и '*', где:
"?'
Соответствует любому отдельному символу.
'*'
Соответствует любой последовательности символов (включая пустую последовательность).
Соответствие должно охватывать всю входную строку (не частичное).

Решение:

func isMatch(s string, p string) bool {
  var newPattern = []string{}
  for _, c := range p {
    if string(c) == "*" || string(c) == "?" {
      if string(c) == "*" {
        newPattern = append(newPattern, "[[:lower:]]")
      }
      if string(c) == "?" {
        newPattern = append(newPattern, "[[:lower:]]{1}")
      }
      newPattern = append(newPattern, string(c))
      continue
    }
    newPattern = append(newPattern, string(c))
  }
  p = strings.Join(newPattern, "")
  re := regexp.MustCompile(fmt.Sprintf("^%s$", p))
  return re.Match([]byte(s))
}

Пояснение:
Функция `isMatch` используется для сравнения строки `s` с шаблоном `p`, где `p` может содержать специальные символы &#039;*&#039; и &#039;?&#039;. В ней создается новый шаблон `newPattern`, в котором символы &#039;*&#039; заменяются на `[[:lower:]]` (любой символ или пустая строка), а символы &#039;?&#039; заменяются на `[[:lower:]]{1}` (один произвольный символ). Затем строка `p` преобразуется в новый шаблон с использованием `strings.Join`. Создается регулярное выражение `re`, которое соответствует точному совпадению со строкой `s` и обработанному шаблону `p`. Функция возвращает результат сравнения регулярного выражения с исходной строкой `s`. Этот код использует регулярные выражения для проверки совпадения строки `s` с шаблоном, содержащим символы &#039;*&#039; и &#039;?&#039;.

Задача: №21. Merge Two Sorted Lists #easy

Условие:

Вам даны заголовки двух отсортированных связанных списков list1 и list2. Объедините два списка в один отсортированный список. Список должен быть составлен путем сращивания узлов первых двух списков. Возвращает заголовок объединенного связанного списка.

Решение:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
    result := &ListNode{}
    current := result
    
    for list1 != nil && list2 != nil {
        if list1.Val < list2.Val {
            current.Next = list1
            list1 = list1.Next
        } else {
            current.Next = list2
            list2 = list2.Next
        }
        current = current.Next
    }
    
    if list1 == nil {
        current.Next = list2
    } else {
        current.Next = list1
    }
    
    return result.Next
}

Пояснение:
Инициализация:

Создается новый узел result, который служит заглушкой (dummy node) для начала нового отсортированного списка.
Указатель current инициализируется на этот заглушечный узел, чтобы начать строить новый список с его использованием.
Цикл слияния:

Цикл продолжается, пока оба входных списка list1 и list2 не достигнут конца:
Сравниваются значения текущих узлов list1 и list2.
Если значение в list1 меньше значения в list2, то узел list1 добавляется к текущему узлу current. Указатель current перемещается на следующий узел в list1.
В противном случае узел list2 добавляется к текущему узлу current. Указатель current перемещается на следующий узел в list2.
Окончание одного списка:

После завершения цикла один из списков (list1 или list2) может быть непустым. Если list1 закончилось, указывает на оставшийся список list2. Если list2 закончилось, указывает на оставшийся список list1.
current.Next указывает на начало оставшегося списка, что обеспечивает правильное соединение всех элементов двух исходных списков.
Возврат результата:

Возвращается result.Next, так как result был начальным заглушечным узлом. result.Next указывает на начало нового отсортированного списка, который состоит из элементов обоих входных списков.

Задача: 22. Generate Parentheses #medium
Условие:

Учитывая n пар круглых скобок, напишите функцию, которая генерирует все комбинации правильных круглых скобок.

Решение:

func generateParenthesis(n int) []string {
    res := make([]string, 0)
    backtrack(&res,n,0,0,"")
    return res
}

func backtrack(res *[]string, n, openN, closedN int, val string) {
    if openN == closedN && openN == n {
        *res = append(*res, val)
        return
    }
    if openN < n {
        backtrack(res, n, openN + 1, closedN, val + "(")
    }
    if closedN < openN {
        backtrack(res, n, openN, closedN + 1, val + ")")
    }
}

Пояснение:
Этот код решает задачу генерации правильных комбинаций скобок для данного числа пар N. Мы используем рекурсивный подход, где backtrack функция добавляет открывающие и закрывающие скобки, если это возможно.

Функция generateparenthesis создает пустой список res, вызывает функцию backtrack и возвращает результат.

backtrack функция принимает указатель на список res, число N, текущее количество открывающих и закрывающих скобок, и текущую строку val.

Если количество открывающих и закрывающих скобок равно N, то мы добавляем текущую строку val в список res и возвращаемся.

Если количество открывающих скобок меньше N, мы вызываем backtrack с увеличенным количеством открывающих скобок.

Если количество закрывающих скобок меньше открывающих, мы вызываем backtrack с увеличенным количеством закрывающих скобок.

Таким образом, рекурсивно перебираются все возможные комбинации скобок, пока не будет достигнуто необходимое количество открывающих и закрывающих скобок.

Задача: 23. Merge k Sorted Lists #hard
Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.

Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

import "container/heap"

type PQueue []*ListNode

func (pq PQueue) Len() int {
    return len(pq)
}

func (pq PQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PQueue) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PQueue) Push(x interface{}) {
  item := x.(*ListNode)
  *pq = append(*pq, item)
}

func (pq *PQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  old[n-1] = nil
  *pq = old[0 : n-1]
  return item
}

func (pq *PQueue) Peek(x interface{}) *ListNode {
    return (*pq)[len(*pq)-1]
}

func mergeKLists(lists []*ListNode) *ListNode {
    top := &ListNode{
        Val: -1,
    }
    merged := top
    pq := PQueue{}
    for _, l := range lists {
        if l != nil {
            pq = append(pq, l)
        }
    }
    heap.Init(&pq)
    for len(pq) > 0 {
        merged.Next = heap.Pop(&pq).(*ListNode)
        merged = merged.Next
        if merged.Next != nil {
            heap.Push(&pq, merged.Next)
        }
    }
    return top.Next
}

Пояснение:
Этот код реализует алгоритм слияния k отсортированных связанных списков.

В этом коде определен тип pqueue, который представляет очередь с приоритетами, основанную на куче. Каждый элемент в очереди представляет узел списка и содержит значение этого узла.

Методы len, less, swap определены для работы с очередью. Методы push и pop добавляют и удаляют элементы из очереди соответственно. Метод peek возвращает элемент с наивысшим приоритетом (с наименьшим значением) в очереди.

Функция mergeklists принимает массив lists содержащий указатели на начало каждого отсортированного связанного списка. Алгоритм начинает слияние, добавляя все не пустые списки в приоритетную очередь. Затем в цикле извлекается узел с наименьшим значением из очереди и добавляется к результату слияния. Если узел имеет следующий элемент, он добавляется обратно в очередь. Этот процесс продолжается, пока очередь не станет пустой.

В конце функция возвращает указатель на первый элемент нового отсортированного связанного списка.

Использование стратегии слияния списков с помощью приоритетной очереди позволяет эффективно объединять множество уже отсортированных списков в один отсортированный список.

Задача: 23. Merge k Sorted Lists #hard
Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.

Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

import "container/heap"

type PQueue []*ListNode

func (pq PQueue) Len() int {
    return len(pq)
}

func (pq PQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PQueue) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PQueue) Push(x interface{}) {
  item := x.(*ListNode)
  *pq = append(*pq, item)
}

func (pq *PQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  old[n-1] = nil
  *pq = old[0 : n-1]
  return item
}

func (pq *PQueue) Peek(x interface{}) *ListNode {
    return (*pq)[len(*pq)-1]
}

func mergeKLists(lists []*ListNode) *ListNode {
    top := &ListNode{
        Val: -1,
    }
    merged := top
    pq := PQueue{}
    for _, l := range lists {
        if l != nil {
            pq = append(pq, l)
        }
    }
    heap.Init(&pq)
    for len(pq) > 0 {
        merged.Next = heap.Pop(&pq).(*ListNode)
        merged = merged.Next
        if merged.Next != nil {
            heap.Push(&pq, merged.Next)
        }
    }
    return top.Next
}

Пояснение:
Этот код реализует алгоритм слияния k отсортированных связанных списков.

В этом коде определен тип pqueue, который представляет очередь с приоритетами, основанную на куче. Каждый элемент в очереди представляет узел списка и содержит значение этого узла.

Методы len, less, swap определены для работы с очередью. Методы push и pop добавляют и удаляют элементы из очереди соответственно. Метод peek возвращает элемент с наивысшим приоритетом (с наименьшим значением) в очереди.

Функция mergeklists принимает массив lists содержащий указатели на начало каждого отсортированного связанного списка. Алгоритм начинает слияние, добавляя все не пустые списки в приоритетную очередь. Затем в цикле извлекается узел с наименьшим значением из очереди и добавляется к результату слияния. Если узел имеет следующий элемент, он добавляется обратно в очередь. Этот процесс продолжается, пока очередь не станет пустой.

В конце функция возвращает указатель на первый элемент нового отсортированного связанного списка.

Использование стратегии слияния списков с помощью приоритетной очереди позволяет эффективно объединять множество уже отсортированных списков в один отсортированный список.

Задача: 23. Merge k Sorted Lists #hard
Условие:

Вам дан массив из k списков связанных списков, каждый связанный список отсортирован в порядке возрастания.

Объедините все связанные списки в один отсортированный связанный список и верните его.

Решение:

import "container/heap"

type PQueue []*ListNode

func (pq PQueue) Len() int {
    return len(pq)
}

func (pq PQueue) Less(i, j int) bool {
    return pq[i].Val < pq[j].Val
}

func (pq PQueue) Swap(i, j int) {
  pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PQueue) Push(x interface{}) {
  item := x.(*ListNode)
  *pq = append(*pq, item)
}

func (pq *PQueue) Pop() interface{} {
  old := *pq
  n := len(old)
  item := old[n-1]
  old[n-1] = nil
  *pq = old[0 : n-1]
  return item
}

func (pq *PQueue) Peek(x interface{}) *ListNode {
    return (*pq)[len(*pq)-1]
}

func mergeKLists(lists []*ListNode) *ListNode {
    top := &ListNode{
        Val: -1,
    }
    merged := top
    pq := PQueue{}
    for _, l := range lists {
        if l != nil {
            pq = append(pq, l)
        }
    }
    heap.Init(&pq)
    for len(pq) > 0 {
        merged.Next = heap.Pop(&pq).(*ListNode)
        merged = merged.Next
        if merged.Next != nil {
            heap.Push(&pq, merged.Next)
        }
    }
    return top.Next
}

Пояснение:
Этот код реализует алгоритм слияния k отсортированных связанных списков.

В этом коде определен тип pqueue, который представляет очередь с приоритетами, основанную на куче. Каждый элемент в очереди представляет узел списка и содержит значение этого узла.

Методы len, less, swap определены для работы с очередью. Методы push и pop добавляют и удаляют элементы из очереди соответственно. Метод peek возвращает элемент с наивысшим приоритетом (с наименьшим значением) в очереди.

Функция mergeklists принимает массив lists содержащий указатели на начало каждого отсортированного связанного списка. Алгоритм начинает слияние, добавляя все не пустые списки в приоритетную очередь. Затем в цикле извлекается узел с наименьшим значением из очереди и добавляется к результату слияния. Если узел имеет следующий элемент, он добавляется обратно в очередь. Этот процесс продолжается, пока очередь не станет пустой.

В конце функция возвращает указатель на первый элемент нового отсортированного связанного списка.

Использование стратегии слияния списков с помощью приоритетной очереди позволяет эффективно объединять множество уже отсортированных списков в один отсортированный список.

Задача: 24. Swap Nodes in Pairs
#medium
Условие:

Учитывая связанный список, поменяйте местами каждые два соседних узла и верните его голову. Вы должны решить проблему, не изменяя значения в узлах списка (т. е. изменять можно только сами узлы).

Решение:

func swapPairs(head *ListNode) *ListNode {
    newHead := &ListNode{
        Next: head,
    }
    prev := newHead
    i := head
    if i == nil {
        return head
    }
    j := head.Next
    for i != nil && j != nil {
        prev.Next = j
        i.Next = j.Next
        j.Next = i
        if i.Next == nil {
            break
        }
        prev, i, j = i, i.Next, i.Next.Next
    }
    return newHead.Next
}

Пояснение:
Конечно! Давайте разберем этот код подробнее:


Этот код представляет собой функцию `swapPairs`, которая меняет местами каждую пару соседних элементов в связанном списке.

1. Создается новый узел `newHead`, который инициализируется как исходный головной узел списка.

2. Устанавливается указатель `prev` на `newHead`, который будет использоваться для обновления связей между узлами списка.

3. Устанавливаются указатели `i` и `j` на начальный и следующий после него узлы соответственно.

4. Происходит проверка, если начальный узел `i` равен `nil` (конец списка), то возвращается исходный головной узел.

5. В цикле происходит обмен значениями между узлами:
- `prev.Next` указывает на `j` (следующий после `i`)
- `i.Next` указывает на `j.Next` (следующий после `j`)
- `j.Next` указывает на `i`
- Если `i.Next` равен `nil`, то прерывается цикл
- Обновляются указатели `prev`, `i`, `j` на следующие узлы
6. После завершения цикла возвращается головной узел списка, указываемый `newHead.Next`, который стал новым первым элементом после обмена.


Таким образом, функция `swapPairs` меняет местами каждую пару соседних узлов в связанном списке, используя указатели для изменения связей между узлами.

Задача: 25. Reverse Nodes in k-Group #hard
Условие:

Учитывая заголовок связанного списка, поменяйте местами узлы списка k за раз и верните измененный список.

k — целое положительное число, меньшее или равное длине связанного списка. Если количество узлов не кратно k, то пропущенные узлы в конечном итоге должны остаться такими, какие они есть.

Вы не можете изменять значения в узлах списка, можно изменять только сами узлы

Решение:

func reverseKGroup(head *ListNode, k int) *ListNode {
    top := &ListNode{
        Next: head,
    }
    track := top
    for track.Next != nil {
        last, after := reverse(track.Next, k)
        if last == nil {
            return top.Next
        }
        track.Next.Next = after
        track.Next, track = last, track.Next
    }
    return top.Next
}

func reverse(n *ListNode, remaining int) (last, after *ListNode) {
    if remaining == 1 {
        return n, n.Next
    }
    if n.Next == nil {
        return nil, nil
    }
    last, after = reverse(n.Next, remaining-1)
    if last == nil {
        return nil, nil
    }
    n.Next.Next = n
    return
}

Пояснение:
Функция `reverseKGroup`:
1. Создается новый узел `top`, который инициализируется как исходный головной узел списка.
2. Устанавливается указатель `track` на `top`, который используется для отслеживания текущего положения в списке.
3. В цикле выполняется следующие действия для каждой группы из k элементов:
- Вызывается функция `reverse`, которая возвращает последний узел (`last`) и узел, следующий за группой (`after`).
- Если возвращенный `last` равен `nil`, значит достигнут конец списка и происходит возврат нового головного узла `top.Next`.
- В противном случае, устанавливаются связи между узлами в группе.
- Обновляется указатель `track` на последний узел текущей группы, и продолжается обход списка.
4. По завершении обхода списка возвращается новый головной узел `top.Next`.

Функция `reverse`:
1. Функция рекурсивно меняет порядок следования узлов в группе размером `k`.
2. Если остался один элемент в группе (remaining == 1), то возвращается последний узел и узел, следующий за ним.
3. Если узел `n` является последним в списке, то возвращаются `nil` значения.
4. Иначе, функция вызывается рекурсивно с узлом следующим за `n` и уменьшением оставшегося количества элементов.
5. После рекурсивного вызова меняется порядок следования узлов в группе.
6. Возвращаются узлы `last` (последний элемент в группе) и `after` (узел, следующий за группой).

Эти две функции совместно образуют реализацию обращения каждой группы из `k` элементов в списке, используя рекурсию и обновление связей между узлами.
https://leetcode.com/problems/reverse-nodes-in-k-group

Задача: 26. Remove Duplicates from Sorted Array #easy
Условие:

Учитывая целочисленный массив чисел, отсортированный в неубывающем порядке, удалите дубликаты на месте так, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен оставаться неизменным. Затем верните количество уникальных элементов в числах.

Считайте, что количество уникальных элементов чисел равно k. Чтобы вас приняли, вам нужно сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали уникальные элементы в том порядке, в котором они присутствовали в nums изначально. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

func removeDuplicates(nums []int) int {
    if len(nums) <= 1 {
        return len(nums)
    }
    i, j := 0, 1
    for j < len(nums) {
        if nums[i] == nums[j] {
            j++
        } else {
            nums[i+1] = nums[j]
            i++
            j++
        }
    }
    return i+1
}

Пояснение:
Функция `removeDuplicates` принимает на вход срез целых чисел `nums` и выполняет удаление дубликатов из него. Она возвращает количество уникальных элементов и обновляет исходный срез, удаляя дубликаты.

1. Сначала проверяется длина среза `nums`. Если он меньше или равен 1, то функция мгновенно возвращает длину среза (т.е. в таком случае нет дубликатов).
2. Инициализируются два указателя `i` и `j`, где `i` указывает на начало уникальной части массива, а `j` на следующий за `i` элемент.
3. Запускается цикл, который проходит по элементам массива, начиная с элемента под индексом `1`.
4. На каждой итерации проверяется, равны ли элементы под индексами `i` и `j`.
- Если элементы равны, инкрементируется `j`, чтобы пропустить дубликат.
- В противном случае элемент под индексом `j` копируется на позицию `i+1`, увеличивается `i` и `j` на 1.
5. Процесс продолжается до тех пор, пока `j` не достигнет конца массива.
6. Функция возвращает `i+1`, что соответствует количеству уникальных элементов в массиве.

Таким образом, данная функция эффективно удаляет дубликаты из среза, меняя элементы на месте и возвращая количество уникальных элементов.

Задача: 27. Remove Element #easy
Условие:

Учитывая целочисленный массив nums и целочисленное значение, удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в виде чисел, которые не равны val.

Учитывайте количество элементов в nums, которые не равны val be k. Чтобы вас приняли, вам необходимо сделать следующее:

Измените массив nums так, чтобы первые k элементов nums содержали элементы, не равные val. Остальные элементы nums не важны, как и размер nums.
Вернуть К.

Решение:

func removeElement(a []int, val int) int {
    n := len(a)
    j := 0
    for i := 0; i<n; i++ {
        if a[i] != val {
            a[j] = a[i]
            j++
        }
    } 
    return j
}

Пояснение:
Функция `removeElement` принимает на вход срез целых чисел `a` и значение `val`, которое нужно удалить из среза. Функция возвращает количество элементов в срезе после удаления указанного значения.

1. Длина среза `a` сохраняется в переменной `n`.
2. Инициализируется переменная `j`, которая будет использоваться для обновления индексов в срезе.
3. В цикле `for` проходятся все элементы среза от `0` до `n-1` индекса.
4. На каждой итерации проверяется, равен ли элемент `a[i]` значению `val`.
- Если элемент не равен заданному значению `val`, то он копируется на позицию `a[j]` и значение переменной `j` увеличивается на `1`.
- Это позволяет обновить срез таким образом, чтобы значения, отличные от `val`, были скопированы в начало среза.
5. После завершения цикла возвращается значение `j`, которое является количеством элементов в срезе после удаления всех элементов со значением `val`.

Таким образом, данная функция эффективно удаляет все встречающиеся значения `val` из среза, сдвигая оставшиеся элементы в начало и возвращая количество оставшихся элементов.

Задача: 28. Find the Index of the First Occurrence in a String #easy
Условие:

Учитывая две строки, игла и стог сена, верните индекс первого вхождения иглы в стоге сена или -1, если игла не является частью стога сена

Решение:

func strStr(haystack string, needle string) int {
    n := len(needle)
    if n==0 {
        return 0
    }
    for i:=0; i<len(haystack)-n+1; i++ {
        if haystack[i:i+n] == needle {
            return i
        }
    }
    return -1
}

Пояснение:
Функция `strStr` принимает две строки `haystack` и `needle` и ищет первое вхождение подстроки `needle` в строку `haystack`. Если подстрока не найдена, функция возвращает -1, иначе возвращает индекс, с которого начинается найденная подстрока.

1. Получаем длину строки `needle` и сохраняем ее в переменную `n`.
2. Проверяем, если длина `needle` равна нулю, то сразу возвращаем индекс 0, так как пустая подстрока считается встроенной в любую строку.
3. В цикле `for` перебираем индексы от 0 до `len(haystack)-n+1`, чтобы не выходить за пределы строки `haystack` в попытке сравнения подстроки.
4. На каждой итерации сравниваем подстроку `haystack[i:i+n]` с подстрокой `needle`.
- Если они равны, возвращаем индекс `i`, который указывает на начало вхождения подстроки.
5. Если цикл завершается и ни одно вхождение не было найдено, функция возвращает -1.

Таким образом, данная функция выполняет поиск первого вхождения подстроки `needle` в строку `haystack`, путем сравнения подстрок на каждой позиции.

Задача: 29. Divide Two Integers #medium
Условие:

Учитывая два целых числа: делимое и делитель, разделите два целых числа, не используя операторы умножения, деления и модификатора.

Целочисленное деление должно сокращаться до нуля, что означает потерю дробной части. Например, 8,345 будет сокращено до 8, а -2,7335 будет сокращено до -2.

Возвращает частное после деления делимого на делитель.

Примечание. Предположим, мы имеем дело со средой, которая может хранить целые числа только в пределах 32-битного целого диапазона со знаком: [−2^31, 2^31 − 1]. В этой задаче, если частное строго больше 2^31 - 1, верните 2^31 - 1, а если частное строго меньше -2^31, верните -2^31.

Решение:

func divide(dividend int, divisor int) int {
    c := 0
    dividendS, r := SplitSignAndNum(dividend)
    divisorS, d := SplitSignAndNum(divisor)
    for r >= d {
        r = r - d
        c++
    }
    
    result := c
    
    if dividendS < 0 || divisorS < 0 {
        if !(dividendS < 0 && divisorS < 0) {
            result = -c
        }
    }
    
    if result < -2147483648 {
        return -2147483648
    } else if result > 2147483647 {
        return 2147483647
    }
    
    return result
}

func SplitSignAndNum(i int) (int,int) {
    if i < 0 {
        return -1, -i
    }
    return 1, i
}

Пояснение:
Функция `divide` выполняет деление двух целых чисел `dividend` на `divisor`. Если результат деления выходит за пределы 32-битного целого числа, возвращает максимально возможное целое число (INT_MAX или INT_MIN).

1. Инициализируется переменная `c` для хранения результата деления.
2. `dividend` и `divisor` обрабатываются функцией `SplitSignAndNum`, которая возвращает знак (1 или -1) и абсолютное значение числа.
3. В цикле вычитаем из `r` (абсолютное значение делимого) `d` (абсолютное значение делителя) и увеличиваем счетчик `c`, пока `r >= d`.
4. Результат деления сохраняется в переменной `result`.
5. Если исходные числа были отрицательными, результат деления корректируется со знаком.
6. Проверяется переполнение результата по условиям INT_MIN и INT_MAX.
7. Возвращается результат.

Функция `SplitSignAndNum` просто возвращает знак числа и его абсолютное значение. Если число меньше 0, знак будет -1, иначе 1.

Этот код эмулирует деление целых чисел без использования встроенного оператора деления, обрабатывает знаки чисел и контролирует переполнение результата.