- 142. 环形链表 II
/**
* Definition for singly-linked list.
* class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode detectCycle(ListNode head) {
if (head == null) return null;
ListNode fast = head, slow = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (fast == slow) {
break;
}
}
// 上面的代码类似 hasCycle 函数
if (fast == null || fast.next == null) {
// fast 遇到空指针说明没有环
return null;
}
// 将快指针置回头部,慢指针每次走一步,快指针也每次走一步,直到相遇
fast = head;
// 快慢指针同步前进，相交点就是环起点
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return fast;
}
}
- 146. LRU 缓存
class LRUCache {
LinkedHashMap<Integer, Integer> cache;
int capacity;
public LRUCache(int capacity) {
// 按照访问顺序存放
cache = new LinkedHashMap<>(capacity + 1, 0.75f, true);
this.capacity = capacity;
}
public int get(int key) {
if (!cache.containsKey(key)) {
return -1;
}
return cache.get(key);
}
public void put(int key, int value) {
// 修改 key 的值
cache.put(key, value);
if (cache.size() > capacity) {
// 链表头部就是最久未使用的 key
int oldestKey = cache.keySet().iterator().next();
cache.remove(oldestKey);
}
}
}
- 148. 排序链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
/**
* 归并排序:
* 先分解到最小单元，然后逐个进行合并并排序，这样在合并的时候，
* 其实两个链表本身就是有序的，那么当有一个全部取完后，另一个可以直接拼接在最后面
*/
public ListNode sortList(ListNode head) {
// 链表为空或者只有一个节点的时候
if (head == null || head.next == null) return head;
// 查找出后半部分的链表
ListNode lastNode = getLastNode(head);
// 递归 *** 作
ListNode l1 = sortList(head);
ListNode l2 = sortList(lastNode);
// 合并
return merge(l1, l2);
}
private ListNode merge(ListNode l1, ListNode l2) {
if (l1 == null) return l2;
if (l2 == null) return l1;
if (l1.val < l2.val) {
l1.next = merge(l1.next, l2);
return l1;
} else {
l2.next = merge(l2.next, l1);;
return l2;
}
}
private ListNode getLastNode(ListNode node) {
if (node == null) return null;
// 快慢指针寻找到中间节点
ListNode fast = node, slow = node;
// 划分节点
ListNode breakNode = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
breakNode = slow;
slow = slow.next;
}
breakNode.next = null;
return slow;
}
}
- 152. 乘积最大子数组
class Solution {
/**
* 2,3,-2,4
* 如果是正整数可以如下做法
* dp[0] = 2
* dp[1] = Math.max(3, 3 * dp[0]) = 6
* dp[i] = Math( nums[i], nums[i] * dp[i-1] ) 其中 i >=1
*
*
* 但是这里不能这么做,需要两个dp
*/
public int maxProduct(int[] nums) {
int n = nums.length;
// 乘积最大子数组的乘积值
int[] dpMax = new int[n];
// 乘积最小子数组的乘积值
int[] dpMin = new int[n];
dpMax[0] = nums[0];
dpMin[0] = nums[0];
int max = nums[0];
for (int i = 1; i < n; i++) {
// 当前位置的值 max( 最小的dpMin的前一个位置 * 当前位置的值 和 dpMax的前一个位置 * 当前位置的值 )
dpMax[i] = Math.max(nums[i], Math.max(dpMin[i - 1] * nums[i], dpMax[i - 1] * nums[i]));
dpMin[i] = Math.min(nums[i], Math.min(dpMax[i - 1] * nums[i], dpMin[i - 1] * nums[i]));
if (max < dpMax[i]) {
max = dpMax[i];
}
}
return max;
}
}
- 155. 最小栈
class MinStack {
Stack<Integer> stack;
Stack<Integer> minStack;
public MinStack() {
stack = new Stack<>();
minStack = new Stack<>();
}
public void push(int val) {
stack.push(val);
if (minStack.isEmpty() || minStack.peek() >= val) {
minStack.push(val);
} else {
minStack.push(Math.min(val, minStack.peek()));
}
}
public void pop() {
if (minStack.isEmpty()) {
return;
}
minStack.pop();
stack.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return minStack.peek();
}
}
- 160. 相交链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode A = headA, B = headB;
while (A != B) {
A = A == null ? headB : A.next;
B = B == null ? headA : B.next;
}
return A;
}
}
- 169. 多数元素
class Solution {
/**
* 摩尔投票:
* 选出投票数最多的
*/
public int majorityElement(int[] nums) {
int candidate = 0, count = 0, n = nums.length;
for (int num : nums) {
if (count == 0) {
candidate = num;
count = 1;
} else {
count += (num == candidate) ? 1 : -1;
}
}
return candidate;
}
}
- 198. 打家劫舍
class Solution {
/**
* 动态规划
*/
public int rob(int[] nums) {
int n = nums.length;
if (n == 1) return nums[0];
// dp[][0] 没有偷第i个
// dp[][1] 偷了第i个
int[][] dp = new int[n][2];
// dp[i][0] 从 0~i不偷第i个房屋获得的最高金额
// dp[i][1] 偷第i个房屋获得的最高金额
dp[0][0] = 0;
dp[0][1] = nums[0];
for (int i = 1; i < n; i++) {
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1]);
dp[i][1] = dp[i - 1][0] + nums[i];
}
return Math.max(dp[n - 1][0], dp[n - 1][1]);
}
}
- 200. 岛屿数量
class Solution {
/**
* DFS
* 将周围的1变成0,直到找不到为之 然后位置移动到下一次找到1为止然后重复进行
*/
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) return 0;
int res = 0;
int row = grid.length;
int col = grid[0].length;
// 遍历 grid
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
// 每发现一个岛屿，岛屿数量加一
if (grid[i][j] == '1') {
res += 1;
// 然后使用 DFS 将岛屿淹了
dfs(grid, i, j, row, col);
}
}
}
return res;
}
// 从 (i, j) 开始，将与之相邻的陆地都变成海水
private void dfs(char[][] grid, int x, int y, int row, int col) {
if (x < 0 || y < 0 || x >= row || y >= col || grid[x][y] == '0') {
return;
}
grid[x][y] = '0';
// 淹没上下左右的陆地
dfs(grid, x + 1, y, row, col);
dfs(grid, x - 1, y, row, col);
dfs(grid, x, y - 1, row, col);
dfs(grid, x, y + 1, row, col);
}
}
- 206. 反转链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
return reverse(null, head);
}
private ListNode reverse(ListNode pre, ListNode cur) {
if (cur == null) return pre;
ListNode next = cur.next;
cur.next = pre;
return reverse(cur, next);
}
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）