Ищу работу пол года

Практически под каждым постом в этом канале я вижу комментарии от людей, которые ищут работу по полгода. Это перерастает в обсуждение того, как нужно (или не нужно) искать работу, почему процесс найма сломан и как они откликались на фейковые вакансии.

Честно говоря, искать работу полгода — это нонсенс. Очевидно, что человек делает что-то не так. Главная ошибка, которую совершают многие, — это создание иллюзии поиска работы.

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

➖ Просматривает вакансии перед откликом.
➖ Пытается понять, подходит ли он под вакансию. Если считает, что не подходит — не откликается.
➖ Пишет сопроводительные письма (иногда даже уникальные под каждую вакансию).
➖ Заполняет анкеты, проходит тесты.

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

Почему это не работает?

HR-менеджер не может вручную отсмотреть 2000 откликов, оценить каждое резюме и прочитать сопроводительные письма. Поэтому компании используют ATS-системы (системы автоматического подбора), которые анализируют резюме и определяют процент его соответствия вакансии.

Что делать, чтобы повысить шансы?

1️⃣ Добавить ключевые навыки в резюме — и в основной текст, и в теги. Возьмите их с easyoffer.ru

2️⃣ Убрать нерелевантный опыт, оставить только подходящий.

3️⃣ Оформить опыт так, чтобы он выглядел релевантным. Если у вас его нет, укажите проекты, стажировки или другой опыт, который можно представить как работу от 1 года. Если опыт слишком большой, сузьте его до 6 лет.

4️⃣ Откликаться на все вакансии без разбору. Если вы Junior, не ищите только стажер или Junior-вакансии — пробуйте везде. Не отказывайте себе сами, пусть это решит HR

5️⃣ Сделать резюме публичным, потому что HR-менеджеры часто ищут кандидатов не только среди откликов, но и в базе резюме.

6️⃣ Используйте ИИ по минимуму – ATS-системы считывают это и помечают "сгенерировано ИИ"

‼️ Главное правило: чем больше откликов — тем выше шанс получить оффер. Делайте резюме удобным для ATS-систем, и вас заметят.

1. Посмотрите видео о том как я вывел свою резюме в Топ1 на HH
2. Посмотрите видео как я нашел первую работу
3. Прочитайте этот кейс про оптимизацию резюме

Если прям вообще тяжело.

Создайте несколько разных резюме. Создайте 2, 3 да хоть 10 резюме. Настройте авто-отлики и ждите приглашения на собесы.

Не нужно создавать иллюзию поиска работы, сделайте несколько простых и актуальных действий.

#medium
Задача: 1514. Path with Maximum Probability

Вам дан неориентированный взвешенный граф из n узлов (индексация с нуля), представленный списком ребер, где edges[i] = [a, b] является неориентированным ребром, соединяющим узлы a и b с вероятностью успешного прохождения этого ребра succProb[i].

Даны два узла start и end, найдите путь с максимальной вероятностью успеха, чтобы перейти от start к end, и верните его вероятность успеха.

Если пути от start до end не существует, верните 0. Ваш ответ будет принят, если он отличается от правильного ответа не более чем на 1e-5.

Пример:

Input: n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
Output: 0.25000
Explanation: There are two paths from start to end, one having a probability of success = 0.2 and the other has 0.5 * 0.5 = 0.25.

👨‍💻 Алгоритм:

1⃣Инициализируйте массив maxProb как максимальную вероятность достижения каждого узла из начального узла, установите maxProb[start] равным 1.

2⃣Расслабьте все ребра: для каждого ребра (u, v), если найдена более высокая вероятность достижения u через это ребро, обновите max_prob[u] как max_prob[u] = max_prob[v] * path_prob. Если найдена более высокая вероятность достижения v через это ребро, обновите max_prob[v].

3⃣Если нам не удается обновить какой-либо узел с более высокой вероятностью, мы можем остановить итерацию, перейдя к шагу 4. В противном случае повторяйте шаг 2, пока все ребра не будут расслаблены n - 1 раз. Верните max_prob[end].

😎 Решение🐍

func maxProbability(n int, edges [][]int, succProb []float64, start int, end int) float64 {
    maxProb := make([]float64, n)
    maxProb[start] = 1.0

    for i := 0; i < n-1; i++ {
        hasUpdate := false
        for j := 0; j < len(edges); j++ {
            u, v := edges[j][0], edges[j][1]
            pathProb := succProb[j]
            if maxProb[u]*pathProb > maxProb[v] {
                maxProb[v] = maxProb[u] * pathProb
                hasUpdate = true
            }
            if maxProb[v]*pathProb > maxProb[u] {
                maxProb[u] = maxProb[v] * pathProb
                hasUpdate = true
            }
        }
        if !hasUpdate {
            break
        }
    }

    return maxProb[end]
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 710. Random Pick with Blacklist

Вам дано целое число n и массив уникальных целых чисел blacklist. Разработайте алгоритм выбора случайного целого числа из диапазона [0, n - 1], не входящего в черный список. Любое целое число, находящееся в указанном диапазоне и не входящее в черный список, должно с равной вероятностью быть возвращено. Оптимизируйте алгоритм так, чтобы он минимизировал количество обращений к встроенной функции random вашего языка. Реализуйте класс Solution: Solution(int n, int[] blacklist) Инициализирует объект целым числом n и целым числом из черного списка blacklist. int pick() Возвращает случайное целое число в диапазоне [0, n - 1] и не входящее в черный список.

Пример:

Input
["Solution", "pick", "pick", "pick", "pick", "pick", "pick", "pick"]
[[7, [2, 3, 5]], [], [], [], [], [], [], []]
Output
[null, 0, 4, 1, 6, 1, 0, 4]

👨‍💻 Алгоритм:

1⃣Создайте маппинг для чисел, входящих в черный список, чтобы сопоставить их с числами из диапазона [n - len(blacklist), n - 1], которые не входят в черный список.

2⃣Создайте массив для хранения возможных чисел для выбора, исключая числа из черного списка.

3⃣При каждом вызове функции pick() используйте встроенную функцию random для выбора случайного индекса из массива возможных чисел и возвращайте соответствующее значение.

😎 Решение:

package main

import (
  "math/rand"
  "time"
)

type Solution struct {
  mapping map[int]int
  bound   int
}

func Constructor(n int, blacklist []int) Solution {
  mapping := make(map[int]int)
  bound := n - len(blacklist)
  blackset := make(map[int]struct{})
  for _, b := range blacklist {
    blackset[b] = struct{}{}
  }
  whitelist := bound
  for _, b := range blacklist {
    if b < bound {
      for {
        if _, exists := blackset[whitelist]; !exists {
          break
        }
        whitelist++
      }
      mapping[b] = whitelist
      whitelist++
    }
  }
  return Solution{mapping: mapping, bound: bound}
}

func (this *Solution) Pick() int {
  r := rand.Intn(this.bound)
  if mapped, exists := this.mapping[r]; exists {
    return mapped
  }
  return r
}

func main() {
  rand.Seed(time.Now().UnixNano())
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 765. Couples Holding Hands

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

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

Пример:

Input: row = [0,2,1,3]
Output: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

👨‍💻 Алгоритм:

1⃣Мы могли бы предположить без доказательства, что решение, при котором мы делаем людей на каждом диване счастливыми по порядку, является оптимальным. Это предположение сильнее, чем гипотеза о жадном подходе, но кажется разумным, поскольку при каждом ходе мы делаем хотя бы одну пару счастливой.

2⃣При таком предположении, для какого-то дивана с несчастливыми людьми X и Y, мы либо заменяем Y на партнера X, либо заменяем X на партнера Y. Для каждой из двух возможностей мы можем попробовать оба варианта, используя подход с возвратом.

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

😎 Решение:

type Solution struct {
    N     int
    pairs [][]int
}

func (s *Solution) minSwapsCouples(row []int) int {
    s.N = len(row) / 2
    s.pairs = make([][]int, s.N)
    for i := 0; i < s.N; i++ {
        s.pairs[i] = []int{row[2*i] / 2, row[2*i+1] / 2}
    }
    return s.solve(0)
}

func (s *Solution) swap(a, b, c, d int) {
    t := s.pairs[a][b]
    s.pairs[a][b] = s.pairs[c][d]
    s.pairs[c][d] = t
}

func (s *Solution) solve(i int) int {
    if i == s.N {
        return 0
    }
    x, y := s.pairs[i][0], s.pairs[i][1]
    if x == y {
        return s.solve(i + 1)
    }

    var jx, kx, jy, ky int
    for j := i + 1; j < s.N; j++ {
        for k := 0; k <= 1; k++ {
            if s.pairs[j][k] == x {
                jx, kx = j, k
            }
            if s.pairs[j][k] == y {
                jy, ky = j, k
            }
        }
    }

    s.swap(i, 1, jx, kx)
    ans1 := 1 + s.solve(i+1)
    s.swap(i, 1, jx, kx)

    s.swap(i, 0, jy, ky)
    ans2 := 1 + s.solve(i+1)
    s.swap(i, 0, jy, ky)

    if ans1 < ans2 {
        return ans1
    }
    return ans2
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 711. Number of Distinct Islands II

Вам дана двоичная матричная сетка m x n. Остров - это группа 1 (представляющая сушу), соединенных в четырех направлениях (горизонтальном или вертикальном). Можно предположить, что все четыре края сетки окружены водой. Остров считается одинаковым с другим, если они имеют одинаковую форму, или имеют одинаковую форму после поворота (только на 90, 180 или 270 градусов) или отражения (влево/вправо или вверх/вниз). Верните количество разных островов.

Пример:

Input: grid = [[1,1,0,0,0],[1,0,0,0,0],[0,0,0,0,1],[0,0,0,1,1]]
Output: 1

👨‍💻 Алгоритм:

1⃣Пройдите по каждому элементу матрицы, если найдена земля (1), выполните DFS для обнаружения всех связанных с этим островом земель и сохраните форму острова.

2⃣Нормализуйте форму острова, применив все возможные повороты и отражения, чтобы найти каноническую форму.

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

😎 Решение:

package main

import (
  "sort"
  "strconv"
  "strings"
)

func numDistinctIslands2(grid [][]int) int {
  uniqueIslands := make(map[string]struct{})

  for i := 0; i < len(grid); i++ {
    for j := 0; j < len(grid[0]); j++ {
      if grid[i][j] == 1 {
        shape := [][]int{}
        dfs(grid, i, j, i, j, &shape)
        uniqueIslands[normalize(shape)] = struct{}{}
      }
    }
  }

  return len(uniqueIslands)
}

func dfs(grid [][]int, i, j, baseI, baseJ int, shape *[][]int) {
  if i < 0 || i >= len(grid) || j < 0 || j >= len(grid[0]) || grid[i][j] == 0 {
    return
  }
  grid[i][j] = 0
  *shape = append(*shape, []int{i - baseI, j - baseJ})
  dfs(grid, i+1, j, baseI, baseJ, shape)
  dfs(grid, i-1, j, baseI, baseJ, shape)
  dfs(grid, i, j+1, baseI, baseJ, shape)
  dfs(grid, i, j-1, baseI, baseJ, shape)
}

func normalize(shape [][]int) string {
  shapes := make([][][]int, 8)
  for i := range shapes {
    shapes[i] = [][]int{}
  }

  for _, p := range shape {
    x, y := p[0], p[1]
    shapes[0] = append(shapes[0], []int{x, y})
    shapes[1] = append(shapes[1], []int{x, -y})
    shapes[2] = append(shapes[2], []int{-x, y})
    shapes[3] = append(shapes[3], []int{-x, -y})
    shapes[4] = append(shapes[4], []int{y, x})
    shapes[5] = append(shapes[5], []int{y, -x})
    shapes[6] = append(shapes[6], []int{-y, x})
    shapes[7] = append(shapes[7], []int{-y, -x})
  }

  for i := range shapes {
    sort.Slice(shapes[i], func(a, b int) bool {
      if shapes[i][a][0] == shapes[i][b][0] {
        return shapes[i][a][1] < shapes[i][b][1]
      }
      return shapes[i][a][0] < shapes[i][b][0]
    })
  }

  minShape := shapeToString(shapes[0])
  for _, s := range shapes {
    shapeStr := shapeToString(s)
    if shapeStr < minShape {
      minShape = shapeStr
    }
  }

  return minShape
}

func shapeToString(shape [][]int) string {
  var sb strings.Builder
  for _, p := range shape {
    sb.WriteString(strconv.Itoa(p[0]))
    sb.WriteString(",")
    sb.WriteString(strconv.Itoa(p[1]))
    sb.WriteString(";")
  }
  return sb.String()
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 766. Toeplitz Matrix

Дана матрица размером m x n. Вернуть true, если матрица является Тёплицевой. В противном случае вернуть false.

Матрица является Тёплицевой, если все диагонали, идущие от верхнего левого к нижнему правому углу, содержат одинаковые элементы.

Пример:

Input: matrix = [[1,2,3,4],[5,1,2,3],[9,5,1,2]]
Output: true
Explanation:
In the above grid, the diagonals are:
"[9]", "[5, 5]", "[1, 1, 1]", "[2, 2, 2]", "[3, 3]", "[4]".
In each diagonal all elements are the same, so the answer is True.

👨‍💻 Алгоритм:

1⃣Что отличает две координаты (r1, c1) и (r2, c2) на одной диагонали? Оказывается, две координаты находятся на одной диагонали тогда и только тогда, когда r1 - c1 == r2 - c2.м

2⃣Это приводит к следующей идее: запоминайте значение этой диагонали как groups[r - c]. Если обнаружено несоответствие, то матрица не является Тёплицевой; в противном случае, она является таковой.

3⃣Таким образом, для каждой ячейки матрицы сохраняйте значение диагонали в словаре groups с ключом r - c. Проходите по всем ячейкам матрицы и проверяйте, совпадает ли текущее значение с сохранённым в groups. Если где-то обнаруживается несоответствие, верните false. Если все элементы соответствуют, верните true.

😎 Решение:

func isToeplitzMatrix(matrix [][]int) bool {
    groups := make(map[int]int)
    for r := 0; r < len(matrix); r++ {
        for c := 0; c < len(matrix[0]); c++ {
            if _, ok := groups[r-c]; !ok {
                groups[r-c] = matrix[r][c]
            } else if groups[r-c] != matrix[r][c] {
                return false
            }
        }
    }
    return true
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 712. Minimum ASCII Delete Sum for Two Strings

Если даны две строки s1 и s2, верните наименьшую ASCII-сумму удаленных символов, чтобы сделать две строки равными.

Пример:

Input: s1 = "sea", s2 = "eat"
Output: 231

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив dp размером (len(s1) + 1) x (len(s2) + 1), где dp[i][j] будет хранить наименьшую ASCII-сумму удаленных символов для первых i символов s1 и первых j символов s2.

2⃣Заполните первую строку и первый столбец массива dp суммами ASCII значений символов, которые необходимо удалить для достижения пустой строки.

3⃣Заполните оставшуюся часть массива dp следующим образом: Если символы s1[i-1] и s2[j-1] равны, dp[i][j] = dp[i-1][j-1]. Иначе, dp[i][j] = min(dp[i-1][j] + ord(s1[i-1]), dp[i][j-1] + ord(s2[j-1])).

😎 Решение:

package main

func minimumDeleteSum(s1 string, s2 string) int {
    dp := make([][]int, len(s1) + 1)
    for i := range dp {
        dp[i] = make([]int, len(s2) + 1)
    }
    for i := 1; i <= len(s1); i++ {
        dp[i][0] = dp[i - 1][0] + int(s1[i - 1])
    }
    for j := 1; j <= len(s2); j++ {
        dp[0][j] = dp[0][j - 1] + int(s2[j - 1])
    }
    for i := 1; i <= len(s1); i++ {
        for j := 1; j <= len(s2); j++ {
            if s1[i - 1] == s2[j - 1] {
                dp[i][j] = dp[i - 1][j - 1]
            } else {
                dp[i][j] = min(dp[i - 1][j] + int(s1[i - 1]), dp[i][j - 1] + int(s2[j - 1]))
            }
        }
    }
    return dp[len(s1)][len(s2)]
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 767. Reorganize String

Дана строка s, переставьте символы строки s так, чтобы любые два соседних символа не были одинаковыми.

Верните любую возможную перестановку строки s или верните "", если это невозможно.

Пример:

Input: s = "aab"
Output: "aba"

👨‍💻 Алгоритм:

1⃣Инициализируйте пустой список ans для хранения переставленных символов. Создайте приоритетную очередь pq, используя структуру данных кучи. Каждый элемент в pq — это кортеж, содержащий количество символов и сам символ. Приоритетная очередь упорядочена так, что элементы с большим количеством имеют более высокий приоритет.

2⃣Извлеките элемент с наивысшим приоритетом из pq. Присвойте его количество и символ переменным count_first и char_first соответственно. Если ans пуст или текущий символ char_first отличается от последнего символа в ans, добавьте char_first в ans. Если количество char_first не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Перейдите к следующей итерации.

3⃣В противном случае, если char_first совпадает с последним символом в ans, нужно выбрать другой символ. Если pq пуста, верните пустую строку, так как переставить символы невозможно. Извлеките следующий элемент из pq, присвоив его количество и символ переменным count_second и char_second соответственно. Добавьте char_second в ans. Если количество char_second не равно нулю, уменьшите его на один. Если обновленное количество больше нуля, поместите его обратно в pq. Наконец, поместите оригинальный char_first обратно в pq. Верните переставленные символы как строку, объединив элементы в ans.

😎 Решение:

import (
    "container/heap"
)

type Element struct {
    count int
    char  byte
}

type PriorityQueue []*Element

func (pq PriorityQueue) Len() int { return len(pq) }
func (pq PriorityQueue) Less(i, j int) bool { return pq[i].count > pq[j].count }
func (pq PriorityQueue) Swap(i, j int) { pq[i], pq[j] = pq[j], pq[i] }

func (pq *PriorityQueue) Push(x interface{}) { *pq = append(*pq, x.(*Element)) }
func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    x := old[n-1]
    *pq = old[0 : n-1]
    return x
}

func reorganizeString(s string) string {
    charCounts := make([]int, 26)
    for _, c := range s {
        charCounts[c-'a']++
    }

    pq := &PriorityQueue{}
    heap.Init(pq)
    for i := 0; i < 26; i++ {
        if charCounts[i] > 0 {
            heap.Push(pq, &Element{charCounts[i], byte(i + 'a')})
        }
    }

    result := []byte{}
    for pq.Len() > 0 {
        first := heap.Pop(pq).(*Element)
        if len(result) == 0 || first.char != result[len(result)-1] {
            result = append(result, first.char)
            if first.count > 1 {
                first.count--
                heap.Push(pq, first)
            }
        } else {
            if pq.Len() == 0 {
                return ""
            }
            second := heap.Pop(pq).(*Element)
            result = append(result, second.char)
            if second.count > 1 {
                second.count--
                heap.Push(pq, second)
            }
            heap.Push(pq, first)
        }
    }

    return string(result)
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 713. Subarray Product Less Than K

Если задан массив целых чисел nums и целое число k, верните количество смежных подмассивов, в которых произведение всех элементов в подмассиве строго меньше k.

Пример:

Input: nums = [10,5,2,6], k = 100
Output: 8

👨‍💻 Алгоритм:

1⃣Инициализируйте переменные для отслеживания текущего произведения и количества допустимых подмассивов. Используйте два указателя для границ подмассива.

2⃣Перемещайте правый указатель по массиву и умножайте текущий элемент на текущее произведение. Если произведение становится больше или равно k, перемещайте левый указатель, уменьшая произведение до тех пор, пока оно снова не станет меньше k.

3⃣Подсчитайте количество подмассивов с текущим правым указателем, добавив к общему количеству допустимых подмассивов разницу между правым и левым указателями.

😎 Решение:

package main

func numSubarrayProductLessThanK(nums []int, k int) int {
    if k <= 1 {
        return 0
    }
    product, count, left := 1, 0, 0
    for right := 0; right < len(nums); right++ {
        product *= nums[right]
        for product >= k {
            product /= nums[left]
            left++
        }
        count += right - left + 1
    }
    return count
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 771. Jewels and Stones

Вам даны строки jewels, представляющие типы камней, которые являются драгоценностями, и stones, представляющие камни, которые у вас есть. Каждый символ в stones является типом камня, который у вас есть. Вы хотите узнать, сколько из камней, которые у вас есть, также являются драгоценностями.

Буквы чувствительны к регистру, поэтому "a" считается другим типом камня, чем "A".

Пример:

Input: jewels = "aA", stones = "aAAbbbb"
Output: 3

👨‍💻 Алгоритм:

1⃣Создайте множество из строки jewels для быстрой проверки, является ли камень драгоценностью. Это позволит эффективно проверять принадлежность каждого камня к драгоценностям.

2⃣Инициализируйте счетчик для подсчета количества камней, которые являются драгоценностями. Пройдите по каждому символу в строке stones и проверьте, содержится ли этот символ в множестве jewels.

3⃣Если символ содержится в множестве, увеличьте счетчик. В конце верните значение счетчика, которое будет количеством камней, являющихся драгоценностями.

😎 Решение:

func numJewelsInStones(J string, S string) int {
    ans := 0
    for _, s := range S {
        for _, j := range J {
            if j == s {
                ans++
                break
            }
        }
    }
    return ans
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 487. Max Consecutive Ones II

Дан бинарный массив nums, верните максимальное количество последовательных единиц в массиве, если можно перевернуть не более одного нуля.

Пример:

Input: nums = [1,0,1,1,0]
Output: 4
Explanation: 
- If we flip the first zero, nums becomes [1,1,1,1,0] and we have 4 consecutive ones.
- If we flip the second zero, nums becomes [1,0,1,1,1] and we have 3 consecutive ones.
The max number of consecutive ones is 4.

👨‍💻 Алгоритм:

1⃣Для каждого возможного начала последовательности в массиве nums начните считать количество нулей.

2⃣Для каждой последовательности проверяйте, сколько нулей содержится в ней. Если количество нулей не превышает одного, обновите максимальную длину последовательности единиц.

3⃣Продолжайте проверять все возможные последовательности в массиве, и верните максимальную длину последовательности единиц, удовлетворяющую условию.

😎 Решение:

func findMaxConsecutiveOnes(nums []int) int {
    longestSequence := 0
    for left := 0; left < len(nums); left++ {
        numZeroes := 0
        for right := left; right < len(nums); right++ {
            if nums[right] == 0 {
                numZeroes++
            }
            if numZeroes <= 1 {
                longestSequence = max(longestSequence, right - left + 1)
            }
        }
    }
    return longestSequence
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 714. Best Time to Buy and Sell Stock with Transaction Fee

Вам дан массив prices, где prices[i] - это цена данной акции в i-й день, и целое число fee, представляющее собой комиссию за сделку. Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить сколько угодно сделок, но за каждую сделку вам придется заплатить комиссию. Примечание: Вы не можете совершать несколько сделок одновременно (то есть вы должны продать акции, прежде чем купить их снова). Комиссия за сделку взимается только один раз за каждую покупку и продажу акций.

Пример:

Input: prices = [1,3,2,8,4,9], fee = 2
Output: 8

👨‍💻 Алгоритм:

1⃣Инициализируйте две переменные: cash, представляющую максимальную прибыль без наличия акций, и hold, представляющую максимальную прибыль с наличием акций.

2⃣Пройдите по каждому элементу массива prices и обновите значения cash и hold, используя текущую цену и комиссию.

3⃣Верните значение cash, которое будет максимальной прибылью без наличия акций.

😎 Решение:

package main

func maxProfit(prices []int, fee int) int {
    cash, hold := 0, -prices[0]
    for _, price := range prices {
        cash = max(cash, hold + price - fee)
        hold = max(hold, cash - price)
    }
    return cash
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 772. Basic Calculator III

Реализуйте базовый калькулятор для вычисления простого строкового выражения.

Строка выражения содержит только неотрицательные целые числа, операторы '+', '-', '*', '/' и открывающие '(' и закрывающие скобки ')'. Целочисленное деление должно округляться к нулю.

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

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

Пример:

Input: s = "1+1"
Output: 2

👨‍💻 Алгоритм:

1⃣Определите вспомогательную функцию evaluate, которая принимает оператор и числовые аргументы. Заметьте, что эта функция идентична той, что представлена в подходе "Basic Calculator II". Инициализируйте несколько переменных: стек для хранения промежуточных результатов, curr для отслеживания текущего числа, которое мы строим, и previousOperator для отслеживания предыдущего оператора. Добавьте в строку s случайный символ, который не будет появляться во входных данных, например "@".

2⃣Итерация по входным данным. Для каждого символа c: если c является цифрой, добавьте его к curr. В противном случае, если c == '(', мы начинаем вычисление нового изолированного выражения. В этом случае сохраните previousOperator в стек и установите previousOperator = "+".

3⃣Если c является оператором, то необходимо вычислить значение curr. Используйте функцию evaluate, чтобы применить previousOperator к curr, и добавьте результат в стек. Затем сбросьте curr до нуля и обновите previousOperator = c. Если c == ')', это означает, что мы находимся в конце изолированного выражения и должны полностью его вычислить. Извлекайте из стека до тех пор, пока не достигнете оператора, суммируя все извлеченные числа в curr. Как только достигнете оператора, обновите previousOperator = stack.pop(). Верните сумму всех чисел в стеке.

😎 Решение:

package main

import (
    "strconv"
)

type Solution struct{}

func (sol *Solution) evaluate(operator byte, first, second string) string {
    x, _ := strconv.Atoi(first)
    y, _ := strconv.Atoi(second)
    res := 0

    if operator == '+' {
        res = x
    } else if operator == '-' {
        res = -x
    } else if operator == '*' {
        res = x * y
    } else {
        res = x / y
    }

    return strconv.Itoa(res)
}

func (sol *Solution) calculate(s string) int {
    stack := []string{}
    curr := ""
    previousOperator := byte('+')
    s += "@"
    operators := map[string]struct{}{"+": {}, "-": {}, "*": {}, "/": {}}

    for i := 0; i < len(s); i++ {
        c := s[i]
        if c >= '0' && c <= '9' {
            curr += string(c)
        } else if c == '(' {
            stack = append(stack, string(previousOperator))
            previousOperator = '+'
        } else {
            if previousOperator == '*' || previousOperator == '/' {
                top := stack[len(stack)-1]
                stack = stack[:len(stack)-1]
                stack = append(stack, sol.evaluate(previousOperator, top, curr))
            } else {
                stack = append(stack, sol.evaluate(previousOperator, curr, "0"))
            }

            curr = ""
            previousOperator = c
            if c == ')' {
                currentTerm := 0
                for len(stack) > 0 {
                    top := stack[len(stack)-1]
                    if _, ok := operators[top]; ok {
                        break
                    }
                    stack = stack[:len(stack)-1]
                    val, _ := strconv.Atoi(top)
                    currentTerm += val
                }
                curr = strconv.Itoa(currentTerm)
                previousOperator = stack[len(stack)-1][0]
                stack = stack[:len(stack)-1]
            }
        }
    }

    ans := 0
    for _, num := range stack {
        val, _ := strconv.Atoi(num)
        ans += val
    }

    return ans
}

func main() {}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 774. Minimize Max Distance to Gas Station

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

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

Определим penalty() как максимальное расстояние между соседними автозаправочными станциями после добавления k новых станций.

Верните наименьшее возможное значение penalty(). Ответы, отличающиеся от фактического ответа не более чем на 10^-6, будут приняты.

Пример:

Input: stations = [1,2,3,4,5,6,7,8,9,10], k = 9
Output: 0.50000

👨‍💻 Алгоритм:

1⃣Пусть i-й интервал равен deltas[i] = stations[i+1] - stations[i]. Мы хотим найти dp[n+1][k] как рекурсию. Мы можем поставить x автозаправочных станций в интервал n+1 с наилучшим расстоянием deltas[n+1] / (x+1), затем оставшиеся интервалы можно решить с ответом dp[n][k-x]. Ответ — это минимум среди всех x.

2⃣Из этой рекурсии мы можем разработать решение с использованием динамического программирования. Инициализируем двумерный массив dp, где dp[i][j] будет хранить минимальное возможное значение penalty при добавлении j автозаправочных станций на первые i интервалов.

3⃣Заполняем dp таблицу начиная с базового случая, когда нет добавленных станций. Затем для каждого интервала и количества добавленных станций вычисляем минимальное значение penalty, используя вышеописанную рекурсию. Итоговый ответ будет находиться в dp[n][k], где n — количество интервалов, а k — количество добавляемых станций.

😎 Решение:

func minmaxGasDist(stations []int, K int) float64 {
    N := len(stations)
    deltas := make([]float64, N-1)
    for i := 0; i < N-1; i++ {
        deltas[i] = float64(stations[i+1] - stations[i])
    }

    dp := make([][]float64, N-1)
    for i := range dp {
        dp[i] = make([]float64, K+1)
    }
    for i := 0; i <= K; i++ {
        dp[0][i] = deltas[0] / float64(i+1)
    }

    for p := 1; p < N-1; p++ {
        for k := 0; k <= K; k++ {
            bns := 1e9
            for x := 0; x <= k; x++ {
                bns = math.Min(bns, math.Max(deltas[p] / float64(x+1), dp[p-1][k-x]))
            }
            dp[p][k] = bns
        }
    }

    return dp[N-2][K]
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 775. Global and Local Inversions

Дан массив целых чисел nums длиной n, который представляет собой перестановку всех чисел в диапазоне [0, n - 1].

Число глобальных инверсий — это количество различных пар (i, j), где:

0 <= i < j < n
nums[i] > nums[j]
Число локальных инверсий — это количество индексов i, где:

0 <= i < n - 1
nums[i] > nums[i + 1]
Верните true, если количество глобальных инверсий равно количеству локальных инверсий.

Пример:

Input: nums = [1,0,2]
Output: true
Explanation: There is 1 global inversion and 1 local inversion.

👨‍💻 Алгоритм:

1⃣Локальная инверсия также является глобальной инверсией. Таким образом, нам нужно проверить, есть ли в нашей перестановке какие-либо нелокальные инверсии (A[i] > A[j], i < j) с j - i > 1.

2⃣Для этого мы можем перебрать каждый индекс i и проверить, есть ли индекс j, такой что j > i + 1 и nums[i] > nums[j]. Если такой индекс найден, это будет означать наличие нелокальной инверсии.

3⃣Если для всех индексов i условие выше не выполняется, это значит, что количество глобальных инверсий равно количеству локальных инверсий, и мы возвращаем true. В противном случае, если хотя бы одна нелокальная инверсия найдена, мы возвращаем false.

😎 Решение:

func isIdealPermutation(A []int) bool {
    N := len(A)
    for i := 0; i < N; i++ {
        for j := i + 2; j < N; j++ {
            if A[i] > A[j] {
                return false
            }
        }
    }
    return true
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 716. Max Stack

Разработайте структуру данных max-стека, поддерживающую операции со стеком и поиск максимального элемента стека. Реализуйте класс MaxStack: MaxStack() Инициализирует объект стека. void push(int x) Вставляет элемент x в стек. int pop() Удаляет элемент на вершине стека и возвращает его. int top() Получает элемент на вершине стека без его удаления. int peekMax() Получает максимальный элемент в стеке без его удаления. int popMax() Получает максимальный элемент в стеке и удаляет его. Если максимальных элементов несколько, удалите только самый верхний. Вы должны придумать решение, которое поддерживает O(1) для каждого вызова вершины и O(logn) для каждого другого вызова.

Пример:

Input
["MaxStack", "push", "push", "push", "top", "popMax", "top", "peekMax", "pop", "top"]
[[], [5], [1], [5], [], [], [], [], [], []]
Output
[null, null, null, null, 5, 5, 1, 5, 1, 5]

👨‍💻 Алгоритм:

1⃣Инициализируйте MaxStack с двумя стеками: один для хранения всех элементов, другой для отслеживания максимальных элементов.

2⃣Для операции push(x) добавьте элемент в оба стека: в основной стек и, если это необходимо, в стек максимумов. Для операции pop() удалите элемент из основного стека и, если этот элемент является текущим максимальным, удалите его и из стека максимумов. Для операции top() верните верхний элемент основного стека.

3⃣Для операции peekMax() верните верхний элемент стека максимумов. Для операции popMax() удалите и верните верхний элемент стека максимумов. Для этого временно извлеките элементы из основного стека до тех пор, пока не будет найден максимальный элемент, затем верните остальные элементы обратно.

😎 Решение:

package main

type MaxStack struct {
    stack    []int
    maxStack []int
}

func Constructor() MaxStack {
    return MaxStack{}
}

func (this *MaxStack) Push(x int) {
    this.stack = append(this.stack, x)
    if len(this.maxStack) == 0 || x >= this.maxStack[len(this.maxStack)-1] {
        this.maxStack = append(this.maxStack, x)
    }
}

func (this *MaxStack) Pop() int {
    x := this.stack[len(this.stack)-1]
    this.stack = this.stack[:len(this.stack)-1]
    if x == this.maxStack[len(this.maxStack)-1] {
        this.maxStack = this.maxStack[:len(this.maxStack)-1]
    }
    return x
}

func (this *MaxStack) Top() int {
    return this.stack[len(this.stack)-1]
}

func (this *MaxStack) PeekMax() int {
    return this.maxStack[len(this.maxStack)-1]
}

func (this *MaxStack) PopMax() int {
    maxVal := this.maxStack[len(this.maxStack)-1]
    this.maxStack = this.maxStack[:len(this.maxStack)-1]
    buffer := []int{}
    for this.stack[len(this.stack)-1] != maxVal {
        buffer = append(buffer, this.stack[len(this.stack)-1])
        this.stack = this.stack[:len(this.stack)-1]
    }
    this.stack = this.stack[:len(this.stack)-1]
    for len(buffer) > 0 {
        this.Push(buffer[len(buffer)-1])
        buffer = buffer[:len(buffer)-1]
    }
    return maxVal
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 776. Split BST

Дан корень бинарного дерева поиска (BST) и целое число target, разделите дерево на два поддерева, где первое поддерево содержит узлы, которые меньше или равны значению target, а второе поддерево содержит узлы, которые больше значения target. Не обязательно, чтобы дерево содержало узел со значением target.

Кроме того, большая часть структуры исходного дерева должна сохраниться. Формально, для любого потомка c с родителем p в исходном дереве, если они оба находятся в одном поддереве после разделения, то узел c все еще должен иметь родителя p.

Верните массив из двух корней двух поддеревьев в порядке.

Пример:

Input: root = [4,2,6,1,3,5,7], target = 2
Output: [[2,1],[4,3,6,null,null,5,7]]

👨‍💻 Алгоритм:

1⃣Базовый случай: Если корень равен null, верните массив, содержащий два указателя null. Это необходимо для обработки случая, когда дерево пустое.

2⃣Проверьте, больше ли значение корня целевого значения. Если да, рекурсивно разделите левое поддерево, вызвав splitBST(root->left, target). Прикрепите правую часть разделенного к левому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

3⃣Если значение корня меньше или равно целевому значению, рекурсивно разделите правое поддерево, вызвав splitBST(root->right, target). Прикрепите левую часть разделенного к правому поддереву корня. Верните массив, содержащий левую часть разделенного и текущий корень.

😎 Решение:

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func splitBST(root *TreeNode, target int) []*TreeNode {
    if root == nil {
        return []*TreeNode{nil, nil}
    }

    if root.Val > target {
        left := splitBST(root.Left, target)
        root.Left = left[1]
        return []*TreeNode{left[0], root}
    } else {
        right := splitBST(root.Right, target)
        root.Right = right[0]
        return []*TreeNode{root, right[1]}
    }
}

Ставь 👍 и забирай 📚 Базу знаний

#easy
Задача: 717. 1-bit and 2-bit Characters

У нас есть два специальных символа: первый символ может быть представлен одним битом 0. Второй символ может быть представлен двумя битами (10 или 11). Если задан двоичный массив bits, который заканчивается 0, верните true, если последний символ должен быть однобитным.

Пример:

Input: bits = [1,0,0]
Output: true

👨‍💻 Алгоритм:

1⃣Инициализируйте индекс для итерации по массиву.

2⃣Пройдите по массиву, увеличивая индекс на 1, если текущий бит равен 0, и на 2, если текущий бит равен 1.

3⃣Проверьте, достиг ли индекс последнего элемента массива, и верните результат.

😎 Решение:

package main

func isOneBitCharacter(bits []int) bool {
    i := 0
    for i < len(bits) - 1 {
        i += bits[i] + 1
    }
    return i == len(bits) - 1
}

Ставь 👍 и забирай 📚 Базу знаний

#medium
Задача: 718. Maximum Length of Repeated Subarray

Если даны два целочисленных массива nums1 и nums2, верните максимальную длину подмассива, который встречается в обоих массивах.

Пример:

Input: nums1 = [1,2,3,2,1], nums2 = [3,2,1,4,7]
Output: 3

👨‍💻 Алгоритм:

1⃣Создайте двумерный массив для хранения длин общих подмассивов.

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

3⃣Итеративно обновляйте массив, сравнивая элементы обоих массивов и обновляя максимальную длину подмассива.

😎 Решение:

package main

func findLength(nums1 []int, nums2 []int) int {
    dp := make([][]int, len(nums1) + 1)
    for i := range dp {
        dp[i] = make([]int, len(nums2) + 1)
    }
    maxLength := 0
    for i := len(nums1) - 1; i >= 0; i-- {
        for j := len(nums2) - 1; j >= 0; j-- {
            if nums1[i] == nums2[j] {
                dp[i][j] = dp[i + 1][j + 1] + 1
                if dp[i][j] > maxLength {
                    maxLength = dp[i][j]
                }
            }
        }
    }
    return maxLength
}

Ставь 👍 и забирай 📚 Базу знаний

#hard
Задача: 719. Find K-th Smallest Pair Distance

Расстояние между парой целых чисел a и b определяется как абсолютная разность между a и b. Учитывая целочисленный массив nums и целое число k, верните k-е наименьшее расстояние среди всех пар nums[i] и nums[j], где 0 <= i < j < nums.length.

Пример:

Input: nums = [1,3,1], k = 1
Output: 0

👨‍💻 Алгоритм:

1⃣Отсортируйте массив nums.

2⃣Определите минимальное и максимальное возможные расстояния.

3⃣Используйте бинарный поиск, чтобы найти k-е наименьшее расстояние, проверяя количество пар с расстоянием меньше или равно текущему среднему значению.

😎 Решение:

package main

import (
    "sort"
)

func countPairs(nums []int, mid int) int {
    count := 0
    j := 0
    for i := 0; i < len(nums); i++ {
        for j < len(nums) && nums[j] - nums[i] <= mid {
            j++
        }
        count += j - i - 1
    }
    return count
}

func smallestDistancePair(nums []int, k int) int {
    sort.Ints(nums)
    left, right := 0, nums[len(nums) - 1] - nums[0]
    for left < right {
        mid := (left + right) / 2
        if countPairs(nums, mid) < k {
            left = mid + 1
        } else {
            right = mid
        }
    }
    return left
}

Ставь 👍 и забирай 📚 Базу знаний