Каталог

  • 34. Найдите первую и последнюю позицию элемента в отсортированном массиве
  • 35. Поиск позиции вставки
  • 36. Действительные судоку

исходный код | Github

34. Найдите первую и последнюю позицию элемента в отсортированном массиве

Литкод | задача 34

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

Если target не найдено в массиве, вернуть [-1, -1].

Вы должны написать алгоритм со сложностью выполнения O(log n).

Пример 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Пример 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

Пример 3:

Input: nums = [], target = 0
Output: [-1,-1]

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

  • 0 <= nums.length <= 105
  • -109 <= nums[i] <= 109
  • nums — неубывающий массив.
  • -109 <= target <= 109

35. Поиск позиции вставки

Литкод | Проблема 35

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

Вы должны написать алгоритм со сложностью выполнения O(log n).

Пример 1:

Input: nums = [1,3,5,6], target = 5
Output: 2

Пример 2:

Input: nums = [1,3,5,6], target = 2
Output: 1

Пример 3:

Input: nums = [1,3,5,6], target = 7
Output: 4

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

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums содержит разные значения, отсортированные в возрастающем порядке.
  • -104 <= target <= 104

36. Действительные судоку

Литкод | Проблема 36

Определите, действительна ли доска 9 x 9 судоку. Только заполненные ячейки должны быть проверены в соответствии со следующими правилами:

  1. Каждая строка должна содержать цифры 1-9 без повторения.
  2. Каждый столбец должен содержать цифры 1-9 без повторения.
  3. Каждый из девяти подблоков 3 x 3 сетки должен содержать цифры 1-9 без повторения.

Примечание.

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

Пример 1:

Input: board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: true

Пример 2:

Input: board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
Output: false
Explanation: Same as Example 1, except with the 5 in the top left corner being modified to 8. Since there are two 8's in the top left 3x3 sub-box, it is invalid.

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

  • board.length == 9
  • board[i].length == 9
  • board[i][j] — это цифра 1-9 или '.'.