package class033;
// 不用任何算术运算，只用位运算实现加减乘除
// 代码实现中你找不到任何一个算术运算符
// 测试链接 : https://leetcode.cn/problems/divide-two-integers/
public class BitOperationAddMinusMultiplyDivide {
public static int MIN = Integer.MIN_VALUE;
public static int divide(int a, int b) {
if (a == MIN && b == MIN) {
// a和b都是整数最小
return 1;
}
if (a != MIN && b != MIN) {
// a和b都不是整数最小，那么正常去除
return div(a, b);
}
if (b == MIN) {
// a不是整数最小，b是整数最小
return 0;
}
// a是整数最小，b是-1，返回整数最大，因为题目里明确这么说了
if (b == neg(1)) {
return Integer.MAX_VALUE;
}
// a是整数最小，b不是整数最小，b也不是-1
a = add(a, b > 0 ? b : neg(b));
int ans = div(a, b);
int offset = b > 0 ? neg(1) : 1;
return add(ans, offset);
}
// 必须保证a和b都不是整数最小值，返回a除以b的结果
public static int div(int a, int b) {
int x = a < 0 ? neg(a) : a;
int y = b < 0 ? neg(b) : b;
int ans = 0;
for (int i = 30; i >= 0; i = minus(i, 1)) {
if ((x >> i) >= y) {
ans |= (1 << i);
x = minus(x, y << i);
}
}
return a < 0 ^ b < 0 ? neg(ans) : ans;
}
public static int add(int a, int b) {
int ans = a;
while (b != 0) {
// ans : a和b无进位相加的结果
ans = a ^ b;
// b : a和b相加时的进位信息
b = (a & b) << 1;
a = ans;
}
return ans;
}
public static int minus(int a, int b) {
return add(a, neg(b));
}
public static int neg(int n) {
return add(~n, 1);
}
public static int multiply(int a, int b) {
int ans = 0;
while (b != 0) {
if ((b & 1) != 0) {
// 考察b当前最右的状态！
ans = add(ans, a);
}
a <<= 1;
b >>>= 1;
}
return ans;
}
}
package class034;
// 返回两个无环链表相交的第一个节点
// 测试链接 : https://leetcode.cn/problems/intersection-of-two-linked-lists/
public class Code01_IntersectionOfTwoLinkedLists {
// 提交时不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
}
// 提交如下的方法
public static ListNode getIntersectionNode(ListNode h1, ListNode h2) {
if (h1 == null || h2 == null) {
return null;
}
ListNode a = h1, b = h2;
int diff = 0;
while (a.next != null) {
a = a.next;
diff++;
}
while (b.next != null) {
b = b.next;
diff--;
}
if (a != b) {
return null;
}
if (diff >= 0) {
a = h1;
b = h2;
} else {
a = h2;
b = h1;
}
diff = Math.abs(diff);
while (diff-- != 0) {
a = a.next;
}
while (a != b) {
a = a.next;
b = b.next;
}
return a;
}
}
package class034;
// 每k个节点一组翻转链表
// 测试链接：https://leetcode.cn/problems/reverse-nodes-in-k-group/
public class Code02_ReverseNodesInkGroup {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
}
// 提交如下的方法
public static ListNode reverseKGroup(ListNode head, int k) {
ListNode start = head;
ListNode end = teamEnd(start, k);
if (end == null) {
return head;
}
// 第一组很特殊因为牵扯到换头的问题
head = end;
reverse(start, end);
// 翻转之后start变成了上一组的结尾节点
ListNode lastTeamEnd = start;
while (lastTeamEnd.next != null) {
start = lastTeamEnd.next;
end = teamEnd(start, k);
if (end == null) {
return head;
}
reverse(start, end);
lastTeamEnd.next = end;
lastTeamEnd = start;
}
return head;
}
// 当前组的开始节点是s，往下数k个找到当前组的结束节点返回
public static ListNode teamEnd(ListNode s, int k) {
while (--k != 0 && s != null) {
s = s.next;
}
return s;
}
// s -> a -> b -> c -> e -> 下一组的开始节点
// 上面的链表通过如下的reverse方法调整成 : e -> c -> b -> a -> s -> 下一组的开始节点
public static void reverse(ListNode s, ListNode e) {
e = e.next;
ListNode pre = null, cur = s, next = null;
while (cur != e) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
s.next = e;
}
}
package class034;
// 复制带随机指针的链表
// 测试链接 : https://leetcode.cn/problems/copy-list-with-random-pointer/
public class Code03_CopyListWithRandomPointer {
// 不要提交这个类
public static class Node {
public int val;
public Node next;
public Node random;
public Node(int v) {
val = v;
}
}
// 提交如下的方法
public static Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Node cur = head;
Node next = null;
// 1 -> 2 -> 3 -> ...
// 变成 : 1 -> 1' -> 2 -> 2' -> 3 -> 3' -> ...
while (cur != null) {
next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
cur = head;
Node copy = null;
// 利用上面新老节点的结构关系，设置每一个新节点的random指针
while (cur != null) {
next = cur.next.next;
copy = cur.next;
copy.random = cur.random != null ? cur.random.next : null;
cur = next;
}
Node ans = head.next;
cur = head;
// 新老链表分离 : 老链表重新连在一起，新链表重新连在一起
while (cur != null) {
next = cur.next.next;
copy = cur.next;
cur.next = next;
copy.next = next != null ? next.next : null;
cur = next;
}
// 返回新链表的头节点
return ans;
}
}
package class034;
// 判断链表是否是回文结构
// 测试链接 : https://leetcode.cn/problems/palindrome-linked-list/
public class Code04_PalindromeLinkedList {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
}
// 提交如下的方法
public static boolean isPalindrome(ListNode head) {
if (head == null || head.next == null) {
return true;
}
ListNode slow = head, fast = head;
// 找中点
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// 现在中点就是slow，从中点开始往后的节点逆序
ListNode pre = slow;
ListNode cur = pre.next;
ListNode next = null;
pre.next = null;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
// 上面的过程已经把链表调整成从左右两侧往中间指
// head -> ... -> slow <- ... <- pre
boolean ans = true;
ListNode left = head;
ListNode right = pre;
// left往右、right往左，每一步比对值是否一样，如果某一步不一样答案就是false
while (left != null && right != null) {
if (left.val != right.val) {
ans = false;
break;
}
left = left.next;
right = right.next;
}
// 本着不坑的原则，把链表调整回原来的样子再返回判断结果
cur = pre.next;
pre.next = null;
next = null;
while (cur != null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return ans;
}
}
package class034;
// 返回链表的第一个入环节点
// 测试链接 : https://leetcode.cn/problems/linked-list-cycle-ii/
public class Code05_LinkedListCycleII {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
}
// 提交如下的方法
public static ListNode detectCycle(ListNode head) {
if (head == null || head.next == null || head.next.next == null) {
return null;
}
ListNode slow = head.next;
ListNode fast = head.next.next;
while (slow != fast) {
if (fast.next == null || fast.next.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
fast = head;
while (slow != fast) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
package class034;
// 排序链表
// 要求时间复杂度O(n*logn)，额外空间复杂度O(1)，还要求稳定性
// 数组排序做不到，链表排序可以
// 测试链接 : https://leetcode.cn/problems/sort-list/
public class Code06_SortList {
// 不要提交这个类
public static class ListNode {
public int val;
public ListNode next;
}
// 提交如下的方法
// 时间复杂度O(n*logn)，额外空间复杂度O(1)，有稳定性
// 注意为了额外空间复杂度O(1)，所以不能使用递归
// 因为mergeSort递归需要O(log n)的额外空间
public static ListNode sortList(ListNode head) {
int n = 0;
ListNode cur = head;
while (cur != null) {
n++;
cur = cur.next;
}
// l1...r1 每组的左部分
// l2...r2 每组的右部分
// next 下一组的开头
// lastTeamEnd 上一组的结尾
ListNode l1, r1, l2, r2, next, lastTeamEnd;
for (int step = 1; step < n; step <<= 1) {
// 第一组很特殊，因为要决定整个链表的头，所以单独处理
l1 = head;
r1 = findEnd(l1, step);
l2 = r1.next;
r2 = findEnd(l2, step);
next = r2.next;
r1.next = null;
r2.next = null;
merge(l1, r1, l2, r2);
head = start;
lastTeamEnd = end;
while (next != null) {
l1 = next;
r1 = findEnd(l1, step);
l2 = r1.next;
if (l2 == null) {
lastTeamEnd.next = l1;
break;
}
r2 = findEnd(l2, step);
next = r2.next;
r1.next = null;
r2.next = null;
merge(l1, r1, l2, r2);
lastTeamEnd.next = start;
lastTeamEnd = end;
}
}
return head;
}
// 包括s在内，往下数k个节点返回
// 如果不够，返回最后一个数到的非空节点
public static ListNode findEnd(ListNode s, int k) {
while (s.next != null && --k != 0) {
s = s.next;
}
return s;
}
public static ListNode start;
public static ListNode end;
// l1...r1 -> null : 有序的左部分
// l2...r2 -> null : 有序的右部分
// 整体merge在一起，保证有序
// 并且把全局变量start设置为整体的头，全局变量end设置为整体的尾
public static void merge(ListNode l1, ListNode r1, ListNode l2, ListNode r2) {
ListNode pre;
if (l1.val <= l2.val) {
start = l1;
pre = l1;
l1 = l1.next;
} else {
start = l2;
pre = l2;
l2 = l2.next;
}
while (l1 != null && l2 != null) {
if (l1.val <= l2.val) {
pre.next = l1;
pre = l1;
l1 = l1.next;
} else {
pre.next = l2;
pre = l2;
l2 = l2.next;
}
}
if (l1 != null) {
pre.next = l1;
end = r1;
} else {
pre.next = l2;
end = r2;
}
}
}
package class036;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
// 二叉树的层序遍历
// 测试链接 : https://leetcode.cn/problems/binary-tree-level-order-traversal/
public class Code01_LevelOrderTraversal {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 提交时把方法名改为levelOrder，此方法为普通bfs，此题不推荐
public static List<List<Integer>> levelOrder1(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
Queue<TreeNode> queue = new LinkedList<>();
HashMap<TreeNode, Integer> levels = new HashMap<>();
queue.add(root);
levels.put(root, 0);
while (!queue.isEmpty()) {
TreeNode cur = queue.poll();
int level = levels.get(cur);
if (ans.size() == level) {
ans.add(new ArrayList<>());
}
ans.get(level).add(cur.val);
if (cur.left != null) {
queue.add(cur.left);
levels.put(cur.left, level + 1);
}
if (cur.right != null) {
queue.add(cur.right);
levels.put(cur.right, level + 1);
}
}
}
return ans;
}
// 如果测试数据量变大了就修改这个值
public static int MAXN = 2001;
public static TreeNode[] queue = new TreeNode[MAXN];
public static int l, r;
// 提交时把方法名改为levelOrder，此方法为每次处理一层的优化bfs，此题推荐
public static List<List<Integer>> levelOrder2(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if (root != null) {
l = r = 0;
queue[r++] = root;
while (l < r) { // 队列里还有东西
int size = r - l;
ArrayList<Integer> list = new ArrayList<Integer>();
for (int i = 0; i < size; i++) {
TreeNode cur = queue[l++];
list.add(cur.val);
if (cur.left != null) {
queue[r++] = cur.left;
}
if (cur.right != null) {
queue[r++] = cur.right;
}
}
ans.add(list);
}
}
return ans;
}
}
package class036;
// 求二叉树的最大、最小深度
public class Code04_DepthOfBinaryTree {
// 不提交这个类
public static class TreeNode {
public int val;
public TreeNode left;
public TreeNode right;
}
// 测试链接 : https://leetcode.cn/problems/maximum-depth-of-binary-tree/
public static int maxDepth(TreeNode root) {
return root == null ? 0 : Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
}
// 测试链接 : https://leetcode.cn/problems/minimum-depth-of-binary-tree/
public int minDepth(TreeNode root) {
if (root == null) {
// 当前的树是空树
return 0;
}
if (root.left == null && root.right == null) {
// 当前root是叶节点
return 1;
}
int ldeep = Integer.MAX_VALUE;
int rdeep = Integer.MAX_VALUE;
if (root.left != null) {
ldeep = minDepth(root.left);
}
if (root.right != null) {
rdeep = minDepth(root.right);
}
return Math.min(ldeep, rdeep) + 1;
}
}
package class038;
import java.util.Stack;
// 用递归函数排序栈
// 栈只提供push、pop、isEmpty三个方法
// 请完成无序栈的排序，要求排完序之后，从栈顶到栈底从小到大
// 只能使用栈提供的push、pop、isEmpty三个方法、以及递归函数
// 除此之外不能使用任何的容器，数组也不行
// 就是排序过程中只能用：
// 1) 栈提供的push、pop、isEmpty三个方法
// 2) 递归函数，并且返回值最多为单个整数
public class Code06_SortStackWithRecursive {
public static void sort(Stack<Integer> stack) {
int deep = deep(stack);
while (deep > 0) {
int max = max(stack, deep);
int k = times(stack, deep, max);
down(stack, deep, max, k);
deep -= k;
}
}
// 返回栈的深度
// 不改变栈的数据状况
public static int deep(Stack<Integer> stack) {
if (stack.isEmpty()) {
return 0;
}
int num = stack.pop();
int deep = deep(stack) + 1;
stack.push(num);
return deep;
}
// 从栈当前的顶部开始，往下数deep层
// 返回这deep层里的最大值
public static int max(Stack<Integer> stack, int deep) {
if (deep == 0) {
return Integer.MIN_VALUE;
}
int num = stack.pop();
int restMax = max(stack, deep - 1);
int max = Math.max(num, restMax);
stack.push(num);
return max;
}
// 从栈当前的顶部开始，往下数deep层，已知最大值是max了
// 返回，max出现了几次，不改变栈的数据状况
public static int times(Stack<Integer> stack, int deep, int max) {
if (deep == 0) {
return 0;
}
int num = stack.pop();
int restTimes = times(stack, deep - 1, max);
int times = restTimes + (num == max ? 1 : 0);
stack.push(num);
return times;
}
// 从栈当前的顶部开始，往下数deep层，已知最大值是max，出现了k次
// 请把这k个最大值沉底，剩下的数据状况不变
public static void down(Stack<Integer> stack, int deep, int max, int k) {
if (deep == 0) {
for (int i = 0; i < k; i++) {
stack.push(max);
}
} else {
int num = stack.pop();
down(stack, deep - 1, max, k);
if (num != max) {
stack.push(num);
}
}
}
// 为了测试
// 生成随机栈
public static Stack<Integer> randomStack(int n, int v) {
Stack<Integer> ans = new Stack<Integer>();
for (int i = 0; i < n; i++) {
ans.add((int) (Math.random() * v));
}
return ans;
}
// 为了测试
// 检测栈是不是从顶到底依次有序
public static boolean isSorted(Stack<Integer> stack) {
int step = Integer.MIN_VALUE;
while (!stack.isEmpty()) {
if (step > stack.peek()) {
return false;
}
step = stack.pop();
}
return true;
}
// 为了测试
public static void main(String[] args) {
Stack<Integer> test = new Stack<Integer>();
test.add(1);
test.add(5);
test.add(4);
test.add(5);
test.add(3);
test.add(2);
test.add(3);
test.add(1);
test.add(4);
test.add(2);
sort(test);
while (!test.isEmpty()) {
System.out.println(test.pop());
}
// 随机测试
int N = 20;
int V = 20;
int testTimes = 20000;
System.out.println("测试开始");
for (int i = 0; i < testTimes; i++) {
int n = (int) (Math.random() * N);
Stack<Integer> stack = randomStack(n, V);
sort(stack);
if (!isSorted(stack)) {
System.out.println("出错了!");
break;
}
}
System.out.println("测试结束");
}
}
评论区