Description

Write a program to solve a Sudoku puzzle by filling the empty cells.

A sudoku solution must satisfy all of the following rules:

1. Each of the digits 1-9 must occur exactly once in each row.
2. Each of the digits 1-9 must occur exactly once in each column.
3. Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

Empty cells are indicated by the character ‘.’.

A sudoku puzzle…

…and its solution numbers marked in red.

Note:

• The given board contain only digits 1-9 and the character ‘.’.
• You may assume that the given Sudoku puzzle will have a single unique solution.
• The given board size is always 9x9.

Difficulty: Hard

Code:

1
2
3
4
5

class Solution {
    public void solveSudoku(char[][] board) {
        
    }
}

题意

将数独中的空白按规则正确填充，假设有且仅有唯一解。

Description

Determine if a 9x9 Sudoku board is valid. Only the filled cells need to be validated according to the following rules:

1. Each row must contain the digits 1-9 without repetition.
2. Each column must contain the digits 1-9 without repetition.
3. Each of the 9 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

A partially filled sudoku which is valid.

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13

Input:
[
  ["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

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

Input:
[
  ["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.

Note:

• A Sudoku board (partially filled) could be valid but is not necessarily solvable.
• Only the filled cells need to be validated according to the mentioned rules.
• The given board contain only digits 1-9 and the character ‘.’.
• The given board size is always 9x9.

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public boolean isValidSudoku(char[][] board) {
        
    }
}

题意

判断9x9的数独棋盘是否有效，要求满足以下条件：

1. 每一行必须包含1-9，不能重复
2. 每一列必须包含1-9，不能重复
3. 每个3x3的格子必须包含1-9，不能重复

另外请注意

1. 数独棋盘已经填充的部分要求有效但不要求能解出来
2. 只有已经填充的格子才需要验证是否符合上述条件
3. 棋盘只包含1-9和字符.
4. 棋盘大小是9x9

Description

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Example 1:

1
2

Input: [1,3,5,6], 5
Output: 2

Example 2:

1
2

Input: [1,3,5,6], 2
Output: 1

Example 3:

1
2

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

Example 4:

1
2

Input: [1,3,5,6], 0
Output: 0

Difficulty: Easy

Code:

1
2
3
4
5

class Solution {
    public int searchInsert(int[] nums, int target) {
        
    }
}

题意

给定一个有序数组nums和一个目标值target，若数组中nums能找到target则返回下标，否则返回它应该放入的位置。数组中没有重复元素。

Description

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

1
2

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

Example 2:

1
2

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

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public int[] searchRange(int[] nums, int target) {
        
    }
}

题意

给定一个整数数组nums，按升序排列，元素可以重复，找出目标数target出现的起始和结束位置。时间复杂度要求O(log n)，若没找到，返回[-1, -1]。

Description

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.

(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

Your algorithm’s runtime complexity must be in the order of O(log n).

Example 1:

1
2

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

Example 2:

1
2

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

Difficulty: Medium

Code:

1
2
3
4
5

class Solution {
    public int search(int[] nums, int target) {
        
    }
}

题意

有一个数组，其原本按升序排列，但后来在某个轴被旋转。给定一个目标数字，在数组中查找其下标，若不存在则返回-1。

数组中的元素不重复，算法时间复杂度必须是O(log n)。