算法学习有些时候是枯燥的，坚持学习，一起见证技术er的成长~*
算法题目
算法知识点如下
杨辉三角，类型：数组，动态规划，比较简单。
解数独，类型：数组，回溯，比较难。
跳跃游戏，类型，贪心，数组，中等难度。
算法题目描述
杨辉三角
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 1:
输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
示例 2:
输入: numRows = 1
输出: [[1]]
提示:
1 <= numRows <= 30
java解题代码如下
class Solution {
public List<List<Integer>> generate(int numRows) {
List<List<Integer>> res = new ArrayList<List<Integer>>();
if (numRows == 0) {
return res;
}
for (int i = 0; i < numRows; ++i) {
List<Integer> temp = new ArrayList<Integer>();
for (int j = 0; j <= i; ++j) {
temp.add(numberget(i, j));
}
res.add(temp);
}
return res;
}
public int numberget(int i, int j) {
if (j == 0 || i == j) {
return 1;
} else {
return (numberget(i - 1, j - 1) + numberget(i - 1, j));
}
}
}
算法题目描述
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
示例:
输入: [2,3,1,1,4]
输出: 2
解释: 跳到最后一个位置的最小跳跃数是 2。从下标为 0 跳到下标为 1 的位置，跳 1 步，然后跳 3 步到达数组的最后一个位置。
说明:
假设你总是可以到达数组的最后一个位置。
java解题代码
class Solution {
public int jump(int[] nums) {
int end = 0;
int steps = 0;
int maxPosition = 0;
for (int i = 0; i < nums.length - 1; i++) {
maxPosition = Math.max(maxPosition, i + nums[i]);
if (i == end) {
end = maxPosition;
steps++;
}
}
return steps;
}
}题目描述
编写一个程序，通过填充空格来解决数独问题。
数独的解法需 遵循如下规则：
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
输入：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"]]
输出：
[["5","3","4","6","7","8","9","1","2"],
["6","7","2","1","9","5","3","4","8"],
["1","9","8","3","4","2","5","6","7"],
["8","5","9","7","6","1","4","2","3"],
["4","2","6","8","5","3","7","9","1"],
["7","1","3","9","2","4","8","5","6"],
["9","6","1","5","3","7","2","8","4"],
["2","8","7","4","1","9","6","3","5"],
["3","4","5","2","8","6","1","7","9"]]
解释：输入的数独如上图所示，唯一有效的解决方案如下所示：
提示：
board.length == 9
board[i].length == 9
boardi 是一位数字或者 '.'
题目数据 保证 输入数独仅有一个解
以下程序实现了这一功能，请你填补空白处内容：
class Solution {
boolean row[][] = new boolean[9][9];
boolean col[][] = new boolean[9][9];
boolean cell[][][] = new boolean[3][3][9];
public void solveSudoku(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] != '.') {
int t = board[i][j] - '1';
row[i][t] = col[j][t] = cell[i / 3][j / 3][t] = true;
}
}
}
dfs(board, 0, 0);
}
public boolean dfs(char[][] board, int x, int y) {
if (y == 9) {
x++;
y = 0;
}
if (x == 9)
return true;
____________________;
for (int num = 0; num < 9; num++) {
if (!row[x][num] && !col[y][num] && !cell[x / 3][y / 3][num]) {
board[x][y] = (char) (num + '1');
row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = true;
if (dfs(board, x, y + 1))
return true;
board[x][y] = '.';
row[x][num] = col[y][num] = cell[x / 3][y / 3][num] = false;
}
}
return false;
}
}java在空白处解题代码如下
if (board[x][y] != '.')
return dfs(board, x, y + 1);