剑指 offer 代码+资料 + 具体安排(2022.8.12更)

注意:打卡是在 B 站的每个视频下面打卡!!!另外,这里的代码会给出一些注释

剑指 offer 刷题活动,帅地会把视频发 B 站,不过 B 站放不了代码,所以我把自己视频讲解中的代码放在这篇文章里,并且代码会做相对详细的注释,因为视频需要控制时长,所以就不在视频来花太多的时间在注释上。

并且为了让大家可以更好跳转,我到时候也把每天发布的任务,隔天和代码以及视频也一起同步到这里吧。

PS:帅地也搞了个Java后端训练营一份带你拿offer的Java训练营

三、每天安排与代码资料

Day22(2022.9.13)

剑指 Offer 42. 连续子数组的最大和

要求:时间O(n),空间O(1)

Day21(2022.9.12)

剑指 Offer 41. 数据流中的中位数

视频讲解直达: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个数

视频讲解直达:【剑指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. 字符串的排列

视频讲解直达:【剑指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. 数组中出现次数超过一半的数字

视频讲解直达:剑指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. 序列化二叉树

视频讲解直达:【剑指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. 二叉搜索树与双向链表

视频讲解直达:【剑指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. 复杂链表的复制

视频讲解直达:【剑指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. 二叉搜索树的后序遍历序列

视频讲解直达:【剑指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. 二叉树中和为某一值的路径

视频讲解直达:【剑指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. 从上到下打印二叉树

视频讲解直达:【剑指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. 从上到下打印二叉树

视频讲解直达:【剑指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. 从上到下打印二叉树

视频讲解直达:【剑指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)