剑指 offer 代码+资料 + 具体安排（2022.8.12更）
注意：打卡是在 B 站的每个视频下面打卡！！！另外，这里的代码会给出一些注释
剑指 offer 刷题活动，帅地会把视频发 B 站，不过 B 站放不了代码，所以我把自己视频讲解中的代码放在这篇文章里，并且代码会做相对详细的注释，因为视频需要控制时长，所以就不在视频来花太多的时间在注释上。
并且为了让大家可以更好跳转，我到时候也把每天发布的任务，隔天和代码以及视频也一起同步到这里吧。
PS：帅地也搞了个Java后端训练营：一份带你拿offer的Java训练营
三、每天安排与代码资料
Day22(2022.9.13)
要求：时间O(n)，空间O(1)
Day21(2022.9.12)
视频讲解直达：41. 数据流中的中位数
class MedianFinder {
Queue<Integer> min, max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue<>(); // 小根，保存较大的
max = new PriorityQueue<>((x, y) -> (y - x));// 大根
}
public void addNum(int num) {
// 如果是偶数
if(min.size() == max.size()){
min.add(num);
max.add(min.poll());
} else {
max.add(num);
min.add(max.poll());
}
}
public double findMedian() {
// 如果是偶数
if(min.size() == max.size()){
return (min.peek() + max.peek()) / 2.0;
} else {
return max.peek() * 1.0;
}
}
}
Day20(2022.9.11)
视频讲解直达：【剑指Offer最优解】 40. 最小的k个数 ｜ 字节腾讯问了好几遍。。。。
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || arr.length == 0 || k == 0){
return new int[0];
}
return quickFind(arr, 0, arr.length - 1, k);
}
int[] quickFind(int[] arr, int left, int right, int k){
int i = partition(arr, left, right);
// 之所以需要 i+1，是因为下标从 0 开始，0～i之间一共有 i+1个数
if(i + 1 == k){
return Arrays.copyOf(arr, k);
}
if(i + 1 > k){
return quickFind(arr, 0, i - 1, k);
} else {
return quickFind(arr, i + 1, right, k);
}
}
// 找出pivot的下标以及使小于等于pivot在左边，大于等于的在右边
int partition(int[] arr, int left, int right){
int pivot = arr[left];
int i = left + 1;
int j = right;
while(i < j){
while(i <= j && arr[i] <= pivot) i++;
while(i <= j && arr[j] >= pivot) j--;
if(i >= j){
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
}
Day19(2022.8.9)
视频讲解直达：【剑指Offer最优解】 38. 字符串的排列
class Solution {
List<Character> path;
List<String> res;
boolean[] visited;
public String[] permutation(String s) {
this.path = new ArrayList<>();
this.res = new ArrayList<>();
this.visited = new boolean[s.length()];
char[] arr = s.toCharArray();
Arrays.sort(arr);
dfs(arr, 0);
String[] ss = new String[res.size()];
for(int i = 0; i < res.size(); i++){
ss[i] = res.get(i);
}
return ss;
}
// 时间复杂度：O(n*n!) 空间：N,N,递归调用最大深度也是 N，3n,O(n)
void dfs(char[] arr, int k){
if(arr.length == k){
res.add(listToString(path));
return;
}
//进行N叉树搜索
for(int i = 0; i < arr.length; i++){
// 剪枝 aab
if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
continue;
}
if(visited[i] == false){
// 递归访问
visited[i] = true;
path.add(arr[i]);
dfs(arr, k + 1);
path.remove(path.size() - 1);
visited[i] = false;
}
}
}
String listToString(List<Character> list){
StringBuilder b = new StringBuilder();
for(int i = 0; i < list.size(); i++){
b.append(list.get(i));
}
return b.toString();
}
}
视频讲解直达：剑指Offer 39. 数组中出现次数超过一半的数字
class Solution {
public int majorityElement(int[] nums) {
if(nums.length <= 2){
return nums[0];
}
int x = nums[0];
int sum = 1;
for(int i = 1; i < nums.length; i++){
if(sum == 0){
x = nums[i];
sum = 1;
} else {
if(x == nums[i]){
sum++;
} else {
sum--;
}
}
}
return x;
}
}
Day18(2022.8.8)
视频讲解直达:【剑指Offer最优解】37. 序列化二叉树 ｜ 有点意思
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// 序列化成字符串,1,2,3,null,null,4,5,null...
if(root == null){
return "";
}
StringBuilder build = new StringBuilder();
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
if(t != null){
queue.add(t.left);
queue.add(t.right);
build.append(t.val + ",");
}else{
build.append("null,");
}
}
return build.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// 1,2,3,null,null,4,5,null...
if(data == null || data.length() <= 0){
return null;
}
String[] s = data.split(",");
Queue<TreeNode> queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(s[0]));
queue.add(root);
int i = 1;
while(!queue.isEmpty()){
TreeNode t = queue.poll();
// 构建做左节点
if(!s[i].equals("null")){
TreeNode left = new TreeNode(Integer.parseInt(s[i]));
t.left = left;
queue.add(left);
}
i++;
// 构建右节点
if(!s[i].equals("null")){
TreeNode right = new TreeNode(Integer.parseInt(s[i]));
t.right = right;
queue.add(right);
}
i++;
}
return root;
}
}
Day17(2022.8.7)
视频讲解直达：【剑指Offer最优解】 36. 二叉搜索树与双向链表 ｜ 基础功
class Solution {
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
Queue<Node> queue = new LinkedList<>();
inOrder(root, queue);
Node head = queue.poll();
Node pre = head;
while(!queue.isEmpty()){
Node cur = queue.poll();
pre.right = cur;
cur.left = pre;
pre = cur;
}
pre.right = head;
head.left = pre;
return head;
}
void inOrder(Node root, Queue<Node> queue){
if(root == null){
return;
}
inOrder(root.left, queue);
queue.add(root);
inOrder(root.right, queue);
}
}
视频讲解直达：【剑指Offer最优解】 35. 复杂链表的复制 ｜ 基础功
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
// 复制链表节点
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
// 复制随机节点
cur = head;
while(cur != null){
Node curNew = cur.next;
curNew.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
// 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
Node headNew = head.next;
cur = head;
Node curNew = head.next;
while(cur != null){
cur.next = cur.next.next;
cur = cur.next;
curNew.next = cur == null ? null : cur.next;
curNew = curNew.next;
}
return headNew;
}
}
Day16(2022.8.6)
视频讲解直达：【剑指Offer最优解】 33. 二叉搜索树的后序遍历序列 ｜ 被单调栈虐了
leetcode单调栈题解：leetcode单调栈题解
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder == null){
return true;
}
return f(postorder, 0, postorder.length - 1);
}
boolean f(int[] postorder, int i, int j){
if(i >= j){
return true;
}
int root = postorder[j];
int p = i;
// 获取第一个大于或者等于 root 等元素的位置
while(postorder[p] < root) p++;
// 判断 p ~ j -1 这个范围是否存在小于root的元素
for(int k = p; k < j; k++){
if(postorder[k] < root){
return false;
}
}
return f(postorder, i, p - 1) && f(postorder, p, j - 1);
}
}
视频讲解直达：【剑指Offer最优解】 34. 二叉树中和为某一值的路径
class Solution {
List<List<Integer>> res;
List<Integer> tmp;
public List<List<Integer>> pathSum(TreeNode root, int target) {
res = new ArrayList<>();
tmp = new ArrayList<>();
dsf(root, target);
return res;
}
void dsf(TreeNode root, int target){
if(root == null){
return;
}
tmp.add(root.val);
target = target - root.val;
if(root.left == null && root.right == null && target == 0){
res.add(new ArrayList<>(tmp));
}
dsf(root.left, target);
dsf(root.right, target);
tmp.remove(tmp.size() - 1);
}
}
Day15(2022.8.5)
视频讲解直达：【剑指Offer最优解】 32 – III. 蛇形打印二叉树
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
int sum = 1;
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
LinkedList<Integer> tmp = new LinkedList<>();
for(int i = 0; i < k; i++){
TreeNode t = queue.poll();
if(sum % 2 == 1){
tmp.add(t.val);
} else {
tmp.addFirst(t.val);
}
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(tmp);
sum ++;
}
return res;
}
}
视频讲解直达:【剑指Offer最优解】 32 – II.. 分层打印二叉树
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
List<Integer> tmp = new ArrayList<>();
for(int i = 0; i < k; i++){
TreeNode t = queue.poll();
tmp.add(t.val);
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(tmp);
}
return res;
}
}
视频讲解直达:【剑指Offer最优解】 32 – I. 从上到下打印二叉树
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null){
return new int[0];
}
Queue<TreeNode> queue = new LinkedList<>();
List<Integer> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
res.add(t.val);
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
int[] arr = new int[res.size()];
for(int i = 0; i < res.size(); i++){
arr[i] = res.get(i);
}
return arr;
}
}
评论(2)
打卡
打卡是在 B 站的每个视频下面打卡！！！！！