Каталог
- 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-9
без повторения. - Каждый столбец должен содержать цифры
1-9
без повторения. - Каждый из девяти подблоков
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
или'.'
.