34. 在排序数组中查找元素的第一个和最后一个位置【中等】
https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/
查找target目标值有关的问题，以及时间复杂度要求O(logn)，首先想到就是二分法。记住！！
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = leftBound(nums, target);
res[1] = rightBound(nums, target);
return res;
}
private int leftBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (nums[mid] == target) {
right = mid - 1;
}
else if (nums[mid] < target) {
left = mid + 1;
}
else if (nums[mid] > target) {
right = mid - 1;
}
}
if (left > nums.length - 1 || nums[left] != target)
return -1;
return left;
}
private int rightBound(int[] nums, int target) {
int left = 0, right = nums.length - 1;
while (left <= right){
int mid = left + (right - left) / 2;
if (nums[mid] == target)
left = mid + 1;
else if (nums[mid] < target)
left = mid + 1;
else if (nums[mid] > target)
right = mid -1;
}
if (right < 0 || nums[right] != target)
return -1;
return right;
}
}
62. 不同路径【中等】
https://leetcode-cn.com/problems/unique-paths/
DFS
一开始想到dfs,把这个路径抽象为一个二叉树，只需要统计全部的叶子节点（也就是终点）的个数，就能得到所有的路径。但是会超时。
class Solution {
public int uniquePaths(int m, int n) {
return dfs(m, n, 0, 0);
}
private int dfs(int m, int n, int i, int j) {
if (i >= m || j >= n) return 0; // 越界
if (i == m -1 && j == n - 1) return 1; // 找到了一种方法
return dfs(m, n, i + 1, j) + dfs(m, n, i, j + 1);
// int right = dfs(m, n, i + 1, j);
// int down = dfs(m, n, i, j + 1);
// int sum = right + down; // 相当于分解问题的思想
}
}
带备忘录的dfs
class Solution {
private int[][] memo;
public int uniquePaths(int m, int n) {
memo = new int[m][n];
return dfs(m, n, 0, 0);
}
private int dfs(int m, int n, int i, int j) {
// base case
if (i == m || j == n) {
return 0;
}
if (i == m -1 && j == n - 1) {
return 1;
}
// 备忘录
if (memo[i][j] != 0) {
return memo[i][j];
}
int sum = 0;
// 向右和向下进行递归
sum += dfs(m, n, i + 1, j);
sum += dfs(m, n, i, j+ 1);
memo[i][j] = sum;
return sum;
}
}
动态规划
class Solution {
public int uniquePaths(int m, int n) {
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
dp[i][0] = 1;
}
for (int i = 0; i < n; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
dp[i][j] = dp[i-1][j] + dp[i][j-1];
}
}
return dp[m-1][n-1];
}
}
https://leetcode-cn.com/problems/unique-paths/solution/bu-tong-lu-jing-java-by-sui-ji-guo-cheng-4g3t/
297. 二叉树的序列化与反序列化【困难】
https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/
