45.跳跃游戏 II
class Solution {
public int jump(int[] nums) {
int position = nums.length - 1, result = 0;
while (position != 0) {
for (int i = 0; i < position; i++) {
if (nums[i] + i >= position) {
position = i;
result++;
break;
}
}
}
return result;
}
}
84.柱状图中最大的矩形
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stack = new Stack<>();
int result = 0;
for (int i = 0; i <= heights.length; i++) {
while (!stack.isEmpty() && (i == heights.length || heights[i] < heights[stack.peek()])) {
int index = stack.pop();
int lastIndex = stack.isEmpty() ? -1 : stack.peek();
result = Math.max(result, heights[index] * (i - lastIndex - 1));
}
if (i < heights.length) {
stack.push(i);
}
}
return result;
}
}
85.最大矩形
class Solution {
public int maximalRectangle(char[][] matrix) {
if (matrix.length == 0) return 0;
Stack<Integer> stack = new Stack<>();
int result = 0;
int[] height = new int[matrix[0].length];
for (int i = 0; i < height.length; i++) {
height[i] = 0;
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == '1') height[j]++;
else height[j] = 0;
}
for (int k = 0; k <= height.length; k++) {
while (!stack.isEmpty() && (k == height.length || height[k] < height[stack.peek()])) {
int index = stack.pop();
int lastIndex = stack.isEmpty() ? -1 : stack.peek();
result = Math.max(result, height[index] * (k - lastIndex - 1));
}
if (k < height.length) stack.push(k);
}
}
return result;
}
}
一层一层看就是84题
88.合并两个有序数组
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index1 = m - 1, index2 = n - 1, index3 = m + n - 1;
while (index2 >= 0) {
if (index1 < 0) {
nums1[index3] = nums2[index2];
index2--;
} else if (nums1[index1] > nums2[index2]) {
nums1[index3] = nums1[index1];
index1--;
} else {
nums1[index3] = nums2[index2];
index2--;
}
index3--;
}
}
}
92.反转链表 II
class Solution {
ListNode successor = null;
public ListNode reverseBetween(ListNode head, int left, int right) {
if (left == 1) {
return reverseN(head, right);
}
head.next = reverseBetween(head.next, left-1, right-1);
return head;
}
private ListNode reverseN(ListNode head, int n) {
if (n == 1) {
successor = head.next;
return head;
}
ListNode newHead = reverseN(head.next, n - 1);
head.next.next = head;
head.next = successor;
return newHead;
}
}
141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
}
ListNode fast = head.next, slow = head;
while (fast != null && fast.next != null) {
if (fast == slow) {
return true;
}
fast = fast.next.next;
slow = slow.next;
}
return false;
}
}
200. 岛屿数量
DFS
class Solution {
public int numIslands(char[][] grid) {
int result = 0;
for (int i = 0; i < grid.length; i++) {
for (int j = 0; j < grid[0].length; j++) {
if (grid[i][j] == '1') {
result++;
mark(i, j, grid);
}
}
}
return result;
}
public void mark(int i, int j, char[][] grid) {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] == '0') return;
if (grid[i][j] == '1') grid[i][j] = '0';
mark(i + 1, j, grid);
mark(i - 1, j, grid);
mark(i, j + 1, grid);
mark(i, j - 1, grid);
return;
}
}
并查集
class Solution {
private int rows, cols;
public int numIslands(char[][] grid) {
rows = grid.length;
if (rows == 0) return 0;
cols = grid[0].length;
int zeors = 0;
UnionFind unionFind = new UnionFind(rows * cols);
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
if (grid[i][j] == '0') zeors++;
else {
if ((i + 1) < rows && grid[i + 1][j] == '1')
unionFind.union(getIndex(i, j), getIndex(i + 1, j));
if ((j + 1) < cols && grid[i][j + 1] == '1')
unionFind.union(getIndex(i, j), getIndex(i, j + 1));
}
}
}
return unionFind.getCount() - zeors;
}
public int getIndex(int i, int j) {
return i * cols + j;
}
public class UnionFind {
private int count;
private int[] parent;
public int getCount() {
return count;
}
public UnionFind(int num) {
count = num;
parent = new int[num];
for (int i = 0; i < parent.length; i++) {
parent[i] = i;
}
}
public int find(int index) {
int result = index;
while (result != parent[result]) {
result = parent[result];
}
return result;
}
public void union(int pre, int cur) {
int preRoot = find(pre);
int curRoot = find(cur);
if (preRoot == curRoot) return;
else {
parent[curRoot] = preRoot;
count--;
}
}
}
}
206.反转链表
class Solution {
public ListNode reverseList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode newHead = reverseList(head.next);
head.next.next = head;
head.next = null;
return newHead;
}
}
322. 零钱兑换
class Solution {
public int coinChange(int[] coins, int amount) {
int[] need = new int[amount + 1];
need[0] = 0;
for (int i = 1; i < need.length; i++) {
need[i] = amount + 1;
}
for (int coin : coins) {
for (int i = coin; i <= amount; i++) {
need[i] = Math.min(need[i], need[i - coin] + 1);
}
}
return need[amount] == amount + 1 ? -1 : need[amount];
}
}
Loading Comments...