@Yano
2015-12-30T11:20:27.000000Z
字数 39021
阅读 36543
LeetCode
我的博客:http://blog.csdn.net/yano_nankai
LeetCode题解:https://github.com/LjyYano/LeetCode
LeetCode之Array题目汇总
LeetCode之Hash Table题目汇总
LeetCode之Linked List题目汇总
LeetCode之Math题目汇总
LeetCode之String题目汇总
LeetCode之Binary Search题目汇总
LeetCode之Divide and Conquer题目汇总
LeetCode之Dynamic Programming题目汇总
LeetCode之Backtracing题目汇总
LeetCode之Stack题目汇总
LeetCode之Sort题目汇总
LeetCode之Bit Manipulation题目汇总
LeetCode之Tree题目汇总
LeetCode之Depth-first Search题目汇总
LeetCode之Breadth-first Search题目汇总
LeetCode之Graph题目汇总
LeetCode之Trie题目汇总
LeetCode之Design题目汇总
文章目录:
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
public int[] twoSum(int[] nums, int target) {
if (nums == null || nums.length <= 1) {
return new int[2];
}
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
// key = target - nums[i], just one solution
for (int i = 0; i < nums.length; i++) {
map.put(target - nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
Integer v = map.get(nums[i]);
// can't use itself
if (v != null && v != i) {
return new int[] { i + 1, v + 1 };
}
}
return null;
}
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
For example, given array S = {-1 0 1 2 -1 -4},
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
分析:
去重:
public List<List<Integer>> threeSum(int[] nums) {
if (nums == null || nums.length < 3) {
return new ArrayList<List<Integer>>();
}
Set<List<Integer>> set = new HashSet<List<Integer>>();
Arrays.sort(nums);
for (int start = 0; start < nums.length; start++) {
if (start != 0 && nums[start - 1] == nums[start]) {
continue;
}
int mid = start + 1, end = nums.length - 1;
while (mid < end) {
int sum = nums[start] + nums[mid] + nums[end];
if (sum == 0) {
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(nums[start]);
tmp.add(nums[mid]);
tmp.add(nums[end]);
set.add(tmp);
while (++mid < end && nums[mid - 1] == nums[mid])
;
while (--end > mid && nums[end + 1] == nums[end])
;
}
else if (sum < 0) {
mid++;
}
else {
end--;
}
}
}
return new ArrayList<List<Integer>>(set);
}
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
public int threeSumClosest(int[] nums, int target) {
if (nums == null || nums.length < 3) {
return Integer.MIN_VALUE;
}
Arrays.sort(nums);
int minGap = Integer.MAX_VALUE;
int result = 0;
for (int start = 0; start < nums.length; start++) {
int mid = start + 1, end = nums.length - 1;
while (mid < end) {
int sum = nums[start] + nums[mid] + nums[end];
int gap = Math.abs(sum - target);
if (gap < minGap) {
minGap = gap;
result = sum;
}
if (sum < target) {
mid++;
} else {
end--;
}
}
}
return result;
}
Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.
A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)
public List<List<Integer>> fourSum(int[] nums, int target) {
if (nums == null || nums.length < 4) {
return new ArrayList<List<Integer>>();
}
Arrays.sort(nums);
Set<List<Integer>> set = new HashSet<List<Integer>>();
// 和3Sum一样,只是多了一个循环
for (int a = 0; a < nums.length - 3; a++) {
int target_3Sum = target - nums[a];
for (int b = a + 1; b < nums.length - 2; b++) {
int c = b + 1, d = nums.length - 1;
while (c < d) {
int sum = nums[b] + nums[c] + nums[d];
if (sum == target_3Sum) {
// 将结果加入集合
List<Integer> tmp = new ArrayList<Integer>();
tmp.add(nums[a]);
tmp.add(nums[b]);
tmp.add(nums[c]);
tmp.add(nums[d]);
set.add(tmp);
// 去重
while (++c < d && nums[c - 1] == nums[c])
;
while (--d > c && nums[d + 1] == nums[d])
;
}
else if (sum < target_3Sum) {
c++;
} else {
d--;
}
}
}
}
return new ArrayList<List<Integer>>(set);
}
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
参考:LeetCode 121 Best Time to Buy and Sell Stock
prices | 7 | 2 | 3 | 6 | 1 | 9 |
---|---|---|---|---|---|---|
lowest | 7 | 2 | 2 | 2 | 1 | 1 |
maxProfit | 0 | 0 | 1 | 4 | 4 | 8 |
public int maxProfit(int[] prices) {
if (prices.length <= 1) {
return 0;
}
int maxProfit = 0;
int lowest = Integer.MAX_VALUE;
for (int v : prices) {
lowest = Math.min(v, lowest);
maxProfit = Math.max(maxProfit, v - lowest);
}
return maxProfit;
}
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
参考:LeetCode 122 Best Time to Buy and Sell Stock II
只要有利润就卖,就是最优解。
prices | 7 | 2 | 3 | 6 | 1 | 9 |
---|---|---|---|---|---|---|
profit | 0 | 0 | 1 | 4 | 4 | 12 |
public int maxProfit(int[] prices) {
int profit = 0;
for (int i = 1; i < prices.length; i++) {
if (prices[i - 1] < prices[i]) {
profit += prices[i] - prices[i - 1];
}
}
return profit;
}
Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
The same repeated number may be chosen from C unlimited number of times.
Note:
For example, given candidate set 2,3,6,7
and target 7
,
A solution set is:
[7]
[2, 2, 3]
参考:LeetCode 039 Combination Sum
使用递归,注意保存结果时,应该新建一个ArrayList:result.add(new ArrayList< Integer>(cur))。否则result会指向一直变化的cur。
public List<List<Integer>> combinationSum(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> result = new ArrayList<List<Integer>>();
ArrayList<Integer> cur = new ArrayList<Integer>();
Arrays.sort(candidates);
dfs(0, target, result, cur, candidates);
return result;
}
private void dfs(int start, int target, List<List<Integer>> result,
ArrayList<Integer> cur, int[] candidates) {
if (target == 0) {
result.add(new ArrayList<Integer>(cur));
return;
}
for (int i = start; i < candidates.length; i++) {
// candidates[i] > target,则递归结束,后面不可能是解
if (candidates[i] > target) {
return;
}
cur.add(candidates[i]);
dfs(i, target - candidates[i], result, cur, candidates);
cur.remove(cur.size() - 1);
}
}
Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:
For example, given candidate set 10,1,2,7,6,1,5
and target 8
,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]
参考:LeetCode 040 Combination Sum II
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
if (candidates == null || candidates.length == 0) {
return new ArrayList<List<Integer>>();
}
Set<List<Integer>> rt = new HashSet<List<Integer>>();
ArrayList<Integer> cur = new ArrayList<Integer>();
Arrays.sort(candidates);
dfs(0, target, rt, cur, candidates);
return new ArrayList<List<Integer>>(rt);
}
private void dfs(int start, int target, Set<List<Integer>> rt,
ArrayList<Integer> cur, int[] candidates) {
if (target == 0) {
rt.add(new ArrayList<Integer>(cur));
return;
}
for (int i = start; i < candidates.length; i++) {
// candidates[i] > target,则递归结束,后面不可能是解
if (candidates[i] > target) {
return;
}
cur.add(candidates[i]);
dfs(i + 1, target - candidates[i], rt, cur, candidates);
cur.remove(cur.size() - 1);
}
}
Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers.
Ensure that numbers within the set are sorted in ascending order.
Example 1:
Input: k = 3, n = 7
Output:
[[1,2,4]]
Example 2:
Input: k = 3, n = 9
Output:
[[1,2,6], [1,3,5], [2,3,4]]
Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.
参考:LeetCode 216 Combination Sum III
这次是指定了元素的个数,用一个变量记录即可。
public List<List<Integer>> combinationSum3(int k, int n) {
List<List<Integer>> rt = new ArrayList<List<Integer>>();
if (k < 1 || n < 1) {
return rt;
}
List<Integer> cur = new ArrayList<Integer>();
dfs(rt, cur, 0, k, n, 1);
return rt;
}
private void dfs(List<List<Integer>> rt, List<Integer> cur, int sum, int k,
int n, int level) {
if (sum == n && k == 0) {
rt.add(new ArrayList<Integer>(cur));
return;
} else if (sum > n || k <= 0) {
return;
}
for (int i = level; i <= 9; i++) {
cur.add(i);
dfs(rt, cur, sum + i, k - 1, n, i + 1);
cur.remove(cur.size() - 1);
}
}
Given preorder and inorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
参考:LeetCode 105 Construct Binary Tree from Preorder and Inorder Traversal
题目要求:根据前序遍历和中序遍历序列,构建二叉树。
中序遍历i:4 2 1 5 3 6
1
/ \
2 3
/ / \
4 5 6
前序遍历p[0]是二叉树的根结点,1是i[2],则:
int p = 0;
int[] preorder;
int[] inorder;
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
return buildTree(0, preorder.length);
}
TreeNode buildTree(int start, int end) {
if (start >= end) {
return null;
}
TreeNode root = new TreeNode(preorder[p]);
int i;
for (i = start; i < end && preorder[p] != inorder[i]; i++)
;
p++;
root.left = buildTree(start, i);
root.right = buildTree(i + 1, end);
return root;
}
Given inorder and postorder traversal of a tree, construct the binary tree.
Note:
You may assume that duplicates do not exist in the tree.
参考:LeetCode 106 Construct Binary Tree from Inorder and Postorder Traversal
int p;
int[] postorder;
int[] inorder;
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.p = postorder.length - 1;
this.inorder = inorder;
this.postorder = postorder;
return buildTree(0, postorder.length);
}
TreeNode buildTree(int start, int end) {
if (start >= end) {
return null;
}
TreeNode root = new TreeNode(postorder[p]);
int i;
for (i = start; i < end && postorder[p] != inorder[i]; i++)
;
p--;
root.right = buildTree(i + 1, end);
root.left = buildTree(start, i);
return root;
}
Given an array of integers, find if the array contains any duplicates. Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
参考:LeetCode 217 Contains Duplicate
public boolean containsDuplicate(int[] nums) {
Set<Integer> s = new HashSet<Integer>();
for (int n : nums) {
if (s.contains(n)) {
return true;
}
s.add(n);
}
return false;
}
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the difference between i and j is at most k.
参考:LeetCode 219 Contains Duplicate II
建立一个map,key是出现过的元素,value是该元素的下标。若相同元素距离大于k,则更新下标。
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(nums[i])) {
if (i - map.get(nums[i]) <= k) {
return true;
}
}
map.put(nums[i], i);
}
return false;
}
Given an array of integers, find out whether there are two distinct indices i and j in the array such that the difference between nums[i] and nums[j] is at most t and the difference between i and j is at most k.
参考:LeetCode 220 Contains Duplicate III
对于加入的元素,要能够在O(1)时间内查找,同时还要自动排序,维持一个k个元素的TreeSet。
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0 || nums == null || nums.length < 2) {
return false;
}
SortedSet<Long> set = new TreeSet<Long>();
for (int j = 0; j < nums.length; j++) {
SortedSet<Long> subSet = set.subSet((long) nums[j] - t,
(long) nums[j] + t + 1);
// 集合不为空,则表示找到解
if (!subSet.isEmpty()) {
return true;
}
if (j >= k) {
set.remove((long) nums[j - k]);
}
set.add((long) nums[j]);
}
return false;
}
Suppose a sorted array 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
).
Find the minimum element.
You may assume no duplicate exists in the array.
参考:LeetCode 153 Find Minimum in Rotated Sorted Array
数列基本有序,则使用二分查找。假设数列是n,s是起始下标,e是最后下标,m是中间元素下标。分为三种情况:
情况1:n[s] < n[e]
0 1 2 4 5 6 7
这种情况,直接返回n[s]。因为数列是有序的,或者只是旋转过一次。如果n[s] < n[e],则表明没有旋转。最小元素是n[s]。
情况2:n[m] > n[s] > n[e]
4 5 6 7 0 1 2
只需要满足n[m] > n[s]即可,因为第一种情况排除后,n[s]就一定会 > n[e]。
在本例中:
n[s] = 4
n[m] = 7
n[e] = 2
则最小值肯定在7之后,到2之间,即 [m+1, e]。
情况3:n[m] < n[e] < n[s]
6 7 0 1 2 4 5
n[m] < n[e],在本例中:
n[s] = 6
n[m] = 1
n[e] = 5
则表明,从m到e,数组已经是上升的,所以最小值在[s, m]。
public int findMin(int[] nums) {
if (nums.length == 1) {
return nums[0];
}
if (nums.length == 2) {
return Math.min(nums[0], nums[1]);
}
int s = 0, e = nums.length - 1;
int m = (s + e) / 2;
if (nums[s] < nums[e]) {
return nums[s];
}
if (nums[m] > nums[s]) {
return findMin(Arrays.copyOfRange(nums, m + 1, e + 1));
}
return findMin(Arrays.copyOfRange(nums, s, m + 1));
}
A peak element is an element that is greater than its neighbors.
Given an input array where num[i] ≠ num[i+1]
, find a peak element and return its index.
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.
You may imagine that num[-1] = num[n] = -∞
.
For example, in array [1, 2, 3, 1]
, 3 is a peak element and your function should return the index number 2.
Note:
Your solution should be in logarithmic complexity.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
参考:LeetCode 162 Find Peak Element
public int findPeakElement(int[] nums) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int mid = low + (high - low) / 2;
if (nums[mid] > nums[mid + 1]) {
high = mid;
} else {
low = mid + 1;
}
}
return low;
}
According to the Wikipedia's article: "The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970."
Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article):
Write a function to compute the next state (after one update) of the board given its current state.
Follow up:
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
题目中说最好是in-place,因为board是int型的,所以要区分四种状态(dead是0,live是1):
dead->live 01
dead->dead 00
live->dead 10
live->live 11
或者直接用0,1,2,3四个数字表示四种状态都可以,然后通过移位进行结果的更新。
下面的图片,是一个Game of Life变化图。
public void gameOfLife(int[][] board) {
if (board == null || board.length == 0 || board[0] == null
|| board[0].length == 0)
return;
int m = board.length;
int n = board[0].length;
// 判断每个点,下一时刻的状态
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x = getLiveNum(board, i, j);
if (board[i][j] == 0) {
if (x == 3)
board[i][j] += 10;
} else {
if (x == 2 || x == 3)
board[i][j] += 10;
}
}
}
// 更新每个点的状态
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
board[i][j] /= 10;
}
}
}
// 获取board[x][y]邻居live的数量
private int getLiveNum(int[][] board, int x, int y) {
int c = 0;
for (int i = x - 1; i <= x + 1; i++) {
for (int j = y - 1; j <= y + 1; j++) {
if (i < 0 || j < 0 || i > board.length - 1
|| j > board[0].length - 1 || (i == x && j == y))
continue;
if (board[i][j] % 10 == 1)
c++;
}
}
return c;
}
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4]
, return true
.
A = [3,2,1,0,4]
, return false
.
设变量maxStep为当前能够跳跃的最大步数,超过数组长度,就表示能够跳出;否则不能跳出。
那么maxStep怎么求得呢?nums[i] + i 就代表:从当前位置起跳,所能跳跃的最远位置。
public boolean canJump(int[] nums) {
if (nums == null || nums.length == 0) {
return false;
}
int maxStep = 0;
for (int i = 0; i < nums.length; i++) {
if (maxStep >= nums.length - 1) {
return true;
}
if (nums[i] == 0 && maxStep == i) {
return false;
}
maxStep = Math.max(maxStep, nums[i] + i);
}
return true;
}
Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋
times.
You may assume that the array is non-empty and the majority element always exist in the array.
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
参考:LeetCode 169 Majority Element
A Linear Time Majority Vote Algorithm 一个典型的算法,可以在一次遍历,时间复杂度是O(1),空间复杂度是O(1)的情况下完成。
public int majorityElement(int[] nums) {
int m = nums[0];
int c = 1;
for (int i = 1; i < nums.length; i++) {
if (m == nums[i]) {
c++;
} else if (c > 1) {
c--;
} else {
m = nums[i];
}
}
return m;
}
Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋
times. The algorithm should run in linear time and in O(1) space.
Hint:
参考:LeetCode 229 Majority Element II
因为题目中说是大于⌊ n/3 ⌋次数的元素,这样的元素最多只能有2个。
public List<Integer> majorityElement(int[] nums) {
List<Integer> rt = new ArrayList<Integer>();
if (nums == null || nums.length == 0) {
return rt;
}
int m1 = nums[0];
int m2 = 0;
int c1 = 1;
int c2 = 0;
for (int i = 1; i < nums.length; i++) {
int x = nums[i];
if (x == m1) {
c1++;
} else if (x == m2) {
c2++;
} else if (c1 == 0) {
m1 = x;
c1 = 1;
} else if (c2 == 0) {
m2 = x;
c2 = 1;
} else {
c1--;
c2--;
}
}
c1 = 0;
c2 = 0;
for (int i = 0; i < nums.length; i++) {
if (m1 == nums[i]) {
c1++;
} else if (m2 == nums[i]) {
c2++;
}
}
if (c1 > nums.length / 3) {
rt.add(m1);
}
if (c2 > nums.length / 3) {
rt.add(m2);
}
return rt;
}
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4]
,
the contiguous subarray [4,−1,2,1]
has the largest sum = 6
.
More practice:
If you have figured out the O(n) solution, try coding another solution using the divide and conquer approach, which is more subtle.
参考:LeetCode 053 Maximum Subarray
curSum存储数组当前的和,maxSum存储数组中连续最大的和。
假设数组是[−2,1,−3,4,−1,2,1,−5,4],首先curSum = -2, maxSum = -2。
本题只是返回连续最大和,并没有返回数组,所以没有必要记录下标。curSum和maxSum 的计算公式如下:
public int maxSubArray(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int curSum = nums[0];
int maxSum = nums[0];
for (int i = 1; i < nums.length; i++) {
curSum = Math.max(curSum + nums[i], nums[i]);
maxSum = Math.max(curSum, maxSum);
}
return maxSum;
}
Find the contiguous subarray within an array (containing at least one number) which has the largest product.
For example, given the array [2,3,-2,4]
,
the contiguous subarray [2,3]
has the largest product = 6
.
参考:LeetCode 152 Maximum Product Subarray
LeetCode第53题Maximum Subarray是求连续和最大的子数组,本题是求连续乘积最大的子数组。
在解法上是一样的,只是在求和时,是负就舍弃。但是在乘积中,因为负数*负数=正数,所以连续乘积为负数时,并不能舍弃这个数,因为如果数组的元素是负数,它可能成为乘积最大的数。
所以LeetCode第53题Maximum Subarray,只需要定义一个变量,用来记录和;本题要定义两个变量:positive和negative,分别记录当前乘积最大值和最小值。
public int maxProduct(int[] nums) {
int max = nums[0];
int positive = nums[0];
int negative = nums[0];
for (int i = 1; i < nums.length; i++) {
positive *= nums[i];
negative *= nums[i];
if (positive < negative) {
int t = positive;
positive = negative;
negative = t;
}
positive = Math.max(positive, nums[i]);
negative = Math.min(negative, nums[i]);
max = Math.max(max, positive);
}
return max;
}
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
参考:LeetCode 088 Merge Sorted Array
public int help(int[] nums, int k) {
if (k < 0) {
return Integer.MIN_VALUE;
}
return nums[k];
}
public void merge(int[] nums1, int m, int[] nums2, int n) {
if (nums1 == null || nums2 == null) {
return;
}
int t = m + n - 1;
while (t >= 0) {
int n1 = help(nums1, m - 1);
int n2 = help(nums2, n - 1);
if (n1 > n2) {
nums1[t] = n1;
m--;
} else {
nums1[t] = n2;
n--;
}
t--;
}
}
Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
Note: You can only move either down or right at any point in time.
参考:LeetCode 064 Minimum Path Sum
建立一个背包dp[m][n],其中dp[i][j]表示从grid[0][0]到grid[i][j]的最小和。
public int minPathSum(int[][] grid) {
if (grid == null || grid[0] == null) {
return 0;
}
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int y = 1; y < n; y++) {
dp[0][y] = dp[0][y - 1] + grid[0][y];
}
for (int x = 1; x < m; x++) {
dp[x][0] = dp[x - 1][0] + grid[x][0];
}
for (int y = 1; y < n; y++) {
for (int x = 1; x < m; x++) {
int min = Math.min(dp[x - 1][y], dp[x][y - 1]);
dp[x][y] = min + grid[x][y];
}
}
return dp[m - 1][n - 1];
}
Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.
For example, given the array [2,3,1,2,4,3]
and s = 7
,
the subarray [4,3]
has the minimal length under the problem constraint.
More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
参考:LeetCode 209 Minimum Size Subarray Sum
定义两个指针,st和ed。如果sum>=s,sum从前面元素开始减;如果sum< s,ed++。
public int minSubArrayLen(int s, int[] nums) {
int sum = 0;
int st = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
sum += nums[i];
if (sum >= s) {
while (sum - nums[st] >= s) {
sum -= nums[st++];
}
min = Math.min(min, i - st + 1);
}
}
if (min > nums.length) {
return 0;
}
return min;
}
Given an array containing n distinct numbers taken from 0, 1, 2, ..., n
, find the one that is missing from the array.
For example,
Given nums = [0, 1, 3]
return 2
.
Note:
Your algorithm should run in linear runtime complexity. Could you implement it using only constant extra space complexity?
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
参考:LeetCode 268 Missing Number
既然是0~n只差其中一个数,不如再次加入0~n的序列,这样就和LeetCode 136 Single Number一样了,missing number只出现一次,其余都是出现两次。
public int missingNumber(int[] nums) {
int rt = nums.length;
for (int i = 0; i < nums.length; i++) {
rt = rt ^ nums[i] ^ i;
}
return rt;
}
Given an array nums
, write a function to move all 0
's to the end of it while maintaining the relative order of the non-zero elements.
For example, given nums = [0, 1, 0, 3, 12]
, after calling your function, nums
should be [1, 3, 12, 0, 0]
.
Note:
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
public void moveZeroes(int[] nums) {
int t = 0;
// 把非0元素移到前面
for (int i = 0; i < nums.length; i++) {
if (nums[i] != 0) {
nums[t++] = nums[i];
}
}
// 把后面元素值0
for (int i = t; i < nums.length; i++) {
nums[i] = 0;
}
}
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).
The replacement must be in-place, do not allocate extra memory.
Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.
1,2,3
→ 1,3,2
3,2,1
→ 1,2,3
1,1,5
→ 1,5,1
参考:LeetCode 031 Next Permutation
public void nextPermutation(int[] nums) {
if (nums == null || nums.length < 2) {
return;
}
int p = 0;
for (int i = nums.length - 2; i >= 0; i--) {
if (nums[i] < nums[i + 1]) {
p = i;
break;
}
}
int q = 0;
for (int i = nums.length - 1; i > p; i--) {
if (nums[i] > nums[p]) {
q = i;
break;
}
}
if (p == 0 && q == 0) {
reverse(nums, 0, nums.length - 1);
return;
}
int temp = nums[p];
nums[p] = nums[q];
nums[q] = temp;
if (p < nums.length - 1) {
reverse(nums, p + 1, nums.length - 1);
}
}
private void reverse(int[] nums, int left, int right) {
while (left < right) {
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
left++;
right--;
}
}
Given numRows, generate the first numRows of Pascal's triangle.
For example, given numRows = 5,
Return
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
参考:LeetCode 118 Pascal's Triangle
public List<List<Integer>> generate(int numRows) {
ArrayList<List<Integer>> rt = new ArrayList<List<Integer>>();
Integer[] pre = null;
for (int i = 1; i <= numRows; i++) {
//must be defined as Integer[]
Integer[] row = new Integer[i];
row[0] = 1;
row[i - 1] = 1;
for (int j = 1; j < i - 1; j++) {
row[j] = pre[j] + pre[j - 1];
}
rt.add(new ArrayList<Integer>(Arrays.asList(row)));
pre = row;
}
return rt;
}
Given an index k, return the kth row of the Pascal's triangle.
For example, given k = 3,
Return [1,3,3,1]
.
Note:
Could you optimize your algorithm to use only O(k) extra space?
参考:LeetCode 119 Pascal's Triangle II
public List<Integer> getRow(int rowIndex) {
Integer[] row = new Integer[rowIndex + 1];
Arrays.fill(row, 1);
for (int i = 0; i < rowIndex - 1; i++) {
for (int j = i + 1; j >= 1; j--) {
row[j] = row[j] + row[j - 1];
}
}
return Arrays.asList(row);
}
Given a non-negative number represented as an array of digits, plus one to the number.
The digits are stored such that the most significant digit is at the head of the list.
public int[] plusOne(int[] digits) {
if (digits == null || digits.length == 0) {
return null;
}
int[] rt = new int[digits.length + 1];
digits[digits.length - 1]++;
for (int i = digits.length - 1; i >= 0; i--) {
rt[i + 1] += digits[i];
rt[i] += rt[i + 1] / 10;
rt[i + 1] %= 10;
}
if (rt[0] == 0) {
return Arrays.copyOfRange(rt, 1, rt.length);
} else {
return rt;
}
}
Given an array of n integers where n > 1, nums
, return an array output
such that output[i]
is equal to the product of all the elements of nums
except nums[i]
.
Solve it without division and in O(n).
For example, given [1,2,3,4]
, return [24,12,8,6]
.
Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)
参考:LeetCode 238 Product of Array Except Self
可以定义两个辅助数组,left和right。
left[i]:存放nums[i]之前的乘积
right[i]:存放nums[i]之后的乘积
但是分析一下,空间可以优化,因为我们先从右向左算,再从左向右算,只需要返回的那一个数组就够了。
public int[] productExceptSelf(int[] nums) {
int[] rt = new int[nums.length];
rt[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
rt[i] = rt[i + 1] * nums[i+1];
}
int left = 1;
for (int i = 0; i < nums.length; i++) {
rt[i] *= left;
left *= nums[i];
}
return rt;
}
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array nums = [1,1,2]
,
Your function should return length = 2
, with the first two elements of nums being 1
and 2
respectively. It doesn't matter what you leave beyond the new length.
参考:LeetCode 026 Remove Duplicates from Sorted Array
public int removeDuplicates(int[] nums) {
if (nums == null) {
return -1;
}
if (nums.length < 2) {
return nums.length;
}
int len = 0;
for (int i = 1; i < nums.length; i++) {
if (nums[len] != nums[i]) {
nums[++len] = nums[i];
}
}
return len + 1;
}
Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
For example,
Given sorted array nums = [1,1,1,2,2,3]
,Your function should return length = 5
, with the first five elements of nums being 1
, 1
, 2
, 2
and 3
. It doesn't matter what you leave beyond the new length.
参考:LeetCode 080 Remove Duplicates from Sorted Array II
public int removeDuplicates(int[] nums) {
int cur = 2;
for (int i = cur; i < nums.length; i++) {
// 一个数字,最多出现2次
if (!(nums[i] == nums[cur - 1] && nums[i] == nums[cur - 2])) {
nums[cur++] = nums[i];
}
}
return Math.min(cur, nums.length);
}
Given an array and a value, remove all instances of that value in place and return the new length.
The order of elements can be changed. It doesn't matter what you leave beyond the new length.
参考:LeetCode 027 Remove Element
public int removeElement(int[] nums, int val) {
if (nums == null || nums.length == 0) {
return 0;
}
int len = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] != val) {
nums[len++] = nums[i];
}
}
return len;
}
Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7]
is rotated to [5,6,7,1,2,3,4]
.
Note:
Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Hint:
Could you do it in-place with O(1) extra space?
Related problem: Reverse Words in a String II
Credits:
Special thanks to @Freezen for adding this problem and creating all test cases.
void reverse(int[] nums, int st, int ed) {
while (st < ed) {
int t = nums[st];
nums[st] = nums[ed];
nums[ed] = t;
st++;
ed--;
}
}
public void rotate(int[] nums, int k) {
int length = nums.length;
k = k % length;
if (length == 1 || k == 0)
return;
reverse(nums, 0, length - k - 1);
reverse(nums, length - k, length - 1);
reverse(nums, 0, length - 1);
}
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Follow up:
Could you do this in-place?
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
final int mx = matrix.length;
final int my = matrix[0].length;
int x, y;
int t;
int _my = my - 1;
for (x = 0; x < mx - 1; x++) {
for (y = 0; y < _my; y++) {
int ny = mx - 1 - x;
int nx = my - 1 - y;
t = matrix[y][x];
matrix[y][x] = matrix[ny][nx];
matrix[ny][nx] = t;
}
_my--;
}
for (x = 0; x < mx; x++) {
for (y = 0; y < my / 2; y++) {
int ny = my - 1 - y;
int nx = x;
t = matrix[y][x];
matrix[y][x] = matrix[ny][nx];
matrix[ny][nx] = t;
}
}
}
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
For example,
Consider the following matrix:
[
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
Given target = 3
, return true
.
参考:LeetCode 074 Search a 2D Matrix
public boolean searchMatrix(int[][] matrix, int target) {
int mx = matrix.length;
int my = matrix[0].length;
int l = 0;
int r = mx * my;
while (l < r) {
int m = l + (r - l) / 2;
// 将m转换成x、y
int x = m / my;
int y = m % my;
// 二分查找:matrix[x][y]转换成一维数组,坐标就是m
if (matrix[x][y] == target) {
return true;
} else if (matrix[x][y] < target) {
l = m + 1;
} else {
r = m;
}
}
return false;
}
Given a sorted array of integers, 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]
.
For example,
Given [5, 7, 7, 8, 8, 10]
and target value 8,
return [3, 4]
.
参考:LeetCode 034 Search for a Range
public int[] searchRange(int[] nums, int target) {
int l = 0, r = nums.length;
while (l < r) {
int m = l + (r - l) / 2;
if (nums[m] == target) {
int s = m, e = m;
while (s - 1 >= 0 && nums[s - 1] == target) {
s--;
}
while (e + 1 < nums.length && nums[e + 1] == target) {
e++;
}
return new int[] { s, e };
} else if (nums[m] > target) {
r = m;
} else {
l = m + 1;
}
}
return new int[] { -1, -1 };
}
Suppose a sorted array 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.
参考:LeetCode 033 Search in Rotated Sorted Array
public int search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = (l + r) / 2;
if (nums[m] == target)
return m;
if (nums[l] < nums[m]) {
if (target <= nums[m] && target >= nums[l])
r = m - 1;
else
l = m + 1;
} else if (nums[l] > nums[m]) {
if (target >= nums[l] || target <= nums[m])
r = m - 1;
else
l = m + 1;
} else
l++;
}
return -1;
}
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
参考:LeetCode 081 Search in Rotated Sorted Array II
public boolean search(int[] nums, int target) {
int l = 0, r = nums.length - 1;
while (l <= r) {
int m = (l + r) / 2;
if (nums[m] == target)
return true;
if (nums[l] < nums[m]) {
if (target <= nums[m] && target >= nums[l])
r = m - 1;
else
l = m + 1;
} else if (nums[l] > nums[m]) {
if (target >= nums[l] || target <= nums[m])
r = m - 1;
else
l = m + 1;
} else
l++;
}
return false;
}
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.
Here are few examples.
[1,3,5,6]
, 5 → 2
[1,3,5,6]
, 2 → 1
[1,3,5,6]
, 7 → 4
[1,3,5,6]
, 0 → 0
参考:LeetCode 035 Search Insert Position
public int searchInsert(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return 0;
}
for (int i = 0; i < nums.length; i++) {
if (target <= nums[i]) {
return i;
}
}
return nums.length;
}
Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.
Follow up:
Did you use extra space?
A straight forward solution using O(_m__n_) space is probably a bad idea.
A simple improvement uses O(m + n) space, but still not the best solution.
Could you devise a constant space solution?
参考:LeetCode 073 Set Matrix Zeroes
public void setZeroes(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return;
}
int mx = matrix.length;
int my = matrix[0].length;
// 两个变量,判断第一行和第一列是否有0
boolean xflag = false, yflag = false;
// 判断第一行是否有0
for (int i = 0; i < mx; i++) {
if (matrix[i][0] == 0) {
xflag = true;
break;
}
}
// 判断第一列是否有0
for (int i = 0; i < my; i++) {
if (matrix[0][i] == 0) {
yflag = true;
break;
}
}
// 其它行、列是否有0
for (int i = 1; i < mx; i++) {
for (int j = 1; j < my; j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// 对于第一列,为0,则将所在行变成0
for (int i = 1; i < mx; i++) {
if (matrix[i][0] == 0) {
for (int j = 0; j < my; j++) {
matrix[i][j] = 0;
}
}
}
// 对于第一行,为0,则将所在列变成0
for (int i = 0; i < my; i++) {
if (matrix[0][i] == 0) {
for (int j = 0; j < mx; j++) {
matrix[j][i] = 0;
}
}
}
// 若原来第一行中有0,则将整行置0
if (xflag) {
for (int i = 0; i < mx; i++) {
matrix[i][0] = 0;
}
}
// 若原来第一列中有0,则将整列置0
if (yflag) {
for (int i = 0; i < my; i++) {
matrix[0][i] = 0;
}
}
}
Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?
public void sortColors(int[] nums) {
if (nums == null || nums.length == 0) {
return;
}
// 定义三个变量,存储三种颜色出现次数
int red = 0;
int white = 0;
int blue = 0;
// 循环一次,记录每种颜色出现次数
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
red++;
} else if (nums[i] == 1) {
white++;
} else {
blue++;
}
}
// 对nums数组重新赋值
int i = 0;
while (red-- > 0) {
nums[i++] = 0;
}
while (white-- > 0) {
nums[i++] = 1;
}
while (blue-- > 0) {
nums[i++] = 2;
}
}
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
You should return [1,2,3,6,9,8,7,4,5]
.
public List<Integer> spiralOrder(int[][] matrix) {
List<Integer> rt = new ArrayList<Integer>();
if (matrix == null || matrix.length == 0) {
return rt;
}
int startx = 0, endx = matrix.length - 1;
int starty = 0, endy = matrix[0].length - 1;
while (startx <= endx && starty <= endy) {
// 上边的行,从左向右
for (int y = starty; y <= endy; y++) {
rt.add(matrix[startx][y]);
}
// 右边的列,从上到下
for (int x = startx + 1; x <= endx; x++) {
rt.add(matrix[x][endy]);
}
// 如果行或列遍历完,则退出循环
if (startx == endx || starty == endy) {
break;
}
// 下边的行,从右向左
for (int y = endy - 1; y >= starty; y--) {
rt.add(matrix[endx][y]);
}
// 左边的列,从下到上
for (int x = endx - 1; x >= startx + 1; x--) {
rt.add(matrix[x][starty]);
}
startx++;
starty++;
endx--;
endy--;
}
return rt;
}
Given an integer n, generate a square matrix filled with elements from 1 to n2 in spiral order.
For example,
Given n = 3
,
You should return the following matrix:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
参考:LeetCode 059 Spiral Matrix II
public int[][] generateMatrix(int n) {
if (n <= 0) {
return new int[0][0];
}
int[][] matrix = new int[n][n];
int num = 1;
int startx = 0, endx = n - 1;
int starty = 0, endy = n - 1;
while (startx <= endx && starty <= endy) {
// 上边的行,从左向右
for (int y = starty; y <= endy; y++) {
matrix[startx][y] = num++;
}
// 右边的列,从上到下
for (int x = startx + 1; x <= endx; x++) {
matrix[x][endy] = num++;
}
// 如果行或列遍历完,则退出循环
if (startx == endx || starty == endy) {
break;
}
// 下边的行,从右向左
for (int y = endy - 1; y >= starty; y--) {
matrix[endx][y] = num++;
}
// 左边的列,从下到上
for (int x = endx - 1; x >= startx + 1; x--) {
matrix[x][starty] = num++;
}
startx++;
starty++;
endx--;
endy--;
}
return matrix;
}
Given a set of distinct integers, nums, return all possible subsets.
Note:
For example,
If nums = [1,2,3]
, a solution is:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
int target;// 次数
Integer[] stack;// 存储每次排列
List<List<Integer>> rt;// 存储结果
public void search(int p, int[] nums) {
// 若长度为k,则stack是其中一个结果,保存结果
if (p == target) {
rt.add(new ArrayList<Integer>(Arrays.asList(stack)));
return;
}
for (int i = 0; i < nums.length; i++) {
if (p > 0 && nums[i] <= stack[p - 1]) {
continue;
}
stack[p] = nums[i];
search(p + 1, nums);
}
}
public List<List<Integer>> subsets(int[] nums) {
Arrays.sort(nums);
rt = new ArrayList<List<Integer>>();
// 分别做0~num.length长度的组合
for (int i = 0; i <= nums.length; i++) {
target = i;
stack = new Integer[i];
search(0, nums);
}
return rt;
}
Given a collection of integers that might contain duplicates, nums, return all possible subsets.
Note:
For example,
If nums = [1,2,2]
, a solution is:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]
使用二进制,不需要递归。对于二进制中的每一位,0表示不选择,1表示选择。则有2^n种情况。
使用HashSet,能够直接过滤重复情况(先对数组排序,题目中也要求每个list非降序排列)。
public List<List<Integer>> subsetsWithDup(int[] nums) {
if (nums == null) {
return null;
}
if (nums.length == 0) {
return new ArrayList<List<Integer>>();
}
Set<List<Integer>> set = new HashSet<List<Integer>>();
// 题目中要求每个list是非降序,所以要先从小到大排序
Arrays.sort(nums);
// 对于n位,有2^n种情况
for (int i = 0; i < Math.pow(2, nums.length); i++) {
List<Integer> list = new ArrayList<Integer>();
int tmp = i;
// 对于每种情况,分别求得二进制中1的个数
// 0代表不选择,1代表选择
for (int j = 0; j < nums.length; j++) {
int bit = tmp & 1;
tmp >>= 1;
if (bit == 1) {
list.add(nums[j]);
}
}
set.add(list);
}
return new ArrayList<List<Integer>>(set);
}
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7]
, return ["0->2","4->5","7"].
Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.
参考:LeetCode 228 Summary Ranges
public List<String> summaryRanges(int[] nums) {
List<String> rt = new ArrayList<String>();
if (nums == null || nums.length == 0) {
return rt;
}
for (int i = 0; i < nums.length; i++) {
int st = nums[i];
int ed = st;
while (i + 1 < nums.length && nums[i + 1] - ed == 1) {
i++;
ed++;
}
if (ed == st) {
rt.add(st + "");
} else {
rt.add(st + "->" + ed);
}
}
return rt;
}
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
构造二维数组dp[m][n],其中:
public int uniquePaths(int m, int n) {
if (m <= 0 || n <= 0) {
return 0;
}
int[][] dp = new int[m][n];
for (int y = 1; y < n; y++) {
dp[0][y] = 1;
}
for (int x = 1; x < m; x++) {
dp[x][0] = 1;
}
for (int y = 1; y < n; y++) {
for (int x = 1; x < m; x++) {
dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
}
}
return dp[m - 1][n - 1];
}
Follow up for "Unique Paths":
Now consider if some obstacles are added to the grids. How many unique paths would there be?
An obstacle and empty space is marked as 1
and 0
respectively in the grid.
For example,
There is one obstacle in the middle of a 3x3 grid as illustrated below.
[
[0,0,0],
[0,1,0],
[0,0,0]
]
The total number of unique paths is 2
.
Note: m and n will be at most 100.
参考:LeetCode 063 Unique Paths II
和上一题一样,只是有障碍物的时候(obstacleGrid[i][j]==1),将对应的dp置0(dp[i][j]=0)
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
if (obstacleGrid == null || obstacleGrid[0] == null) {
return 0;
}
if (obstacleGrid[0][0] == 1) {
return 0;
}
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
for (int y = 1; y < n; y++) {
if (obstacleGrid[0][y] == 0) {
dp[0][y] = 1;
} else {
break;
}
}
for (int x = 1; x < m; x++) {
if (obstacleGrid[x][0] == 0) {
dp[x][0] = 1;
} else {
break;
}
}
for (int y = 1; y < n; y++) {
for (int x = 1; x < m; x++) {
if (obstacleGrid[x][y] == 1) {
dp[x][y] = 0;
} else {
dp[x][y] = dp[x - 1][y] + dp[x][y - 1];
}
}
}
return dp[m - 1][n - 1];
}