[数据结构与算法]LeetCode高频200题练习记录

LeetCode必刷200题练习记录

一、数据结构相关

1. 链表

• 1.相交链表

给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。
如果两个链表没有交点，返回 null 。

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        //处理特殊输入
        if(headA == null || headB == null)
            return null;
        //双指针遍历
        ListNode pA = headA;
        ListNode pB = headB;
        
        while(pA != pB){
            pA = pA == null ? headB : pA.next;
            pB = pB == null ? headA : pB.next;
        }

        return pA;
    }
}

思路：

假设链表A的长度为a，链表B的长度为b，公共部分长度为c，相交节点为Node。指针pA先遍历完A链再遍历B链，走到Node时，走过的长度为a+(b-c)。同理对于pB的话就是b+(a-c)。对于a+(b-c)=b+(a-c)，若有相交节点Node，则c>0，pA和pB会指向同一个节点Node；若Node不存在，则c=0，两个指针都会指向null，循环也会结束。

• 2.翻转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-nuahBuWW-1629641726838)(C:\Users\11482\Desktop\找工作相关\LeetCode必刷200题练习记录.assets\1479f99ec2d8583971cc3dfb0c59e0cb.png)]

//迭代法
class Solution {
    public ListNode reverseList(ListNode head) {
        //处理特殊输入
        //head为空或者head.next为空直接返回 无需翻转
        if(head == null || head.next == null)
            return head;
        
        //指针定义在外部 避免频繁创建 对内存空间的占用    
        ListNode pre = null;
        ListNode nxt = null;
        ListNode cur = head;
        while(cur != null){
            nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

//递归法
class Solution {
    public ListNode reverseList(ListNode head) {
        //处理特殊输入
        //head为空或者head.next为空直接返回 无需翻转
        if(head == null || head.next == null)
            return head;
        
        ListNode newHead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

• 3.合并两个有序链表

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        //处理特殊输入
        if(l1 == null) return l2;
        if(l2 == null) return l1;

        ListNode dummyHead = new ListNode(0);
        ListNode p1 = l1;
        ListNode p2 = l2;
        int val = 0;
        ListNode cur = dummyHead;
        while(p1 != null && p2 != null){
            if(p1.val < p2.val){
                val = p1.val;
                p1 = p1.next;
            } else {
                val = p2.val;
                p2 = p2.next;
            }
            cur.next = new ListNode(val);
            cur = cur.next;
        }
        while(p1 != null){
            cur.next = new ListNode(p1.val);
            cur = cur.next;
            p1 = p1.next;
        }
        while(p2 != null){
            cur.next = new ListNode(p2.val);
            cur = cur.next;
            p2 = p2.next;
        }
        return dummyHead.next;
    }
}

• 4.删除排序链表中的重复元素

存在一个按升序排列的链表，给你这个链表的头节点 head ，请你删除所有重复的元素，使每个元素 只出现一次 。

返回同样按升序排列的结果链表。

class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode cur = head;
        while(cur.next != null){
            if(cur.next.val == cur.val){
                cur.next = cur.next.next;
            } else {
                cur = cur.next;
            }
        }
        return head;
    }
}

• 5.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

进阶：你能尝试使用一趟扫描实现吗？

class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //处理特殊输入 暂时没想到

        //快慢指针
        ListNode fast = head;
        ListNode slow = head;

        while(n > 0){
            fast = fast.next;
            n--;
        }
        // n 大于等于 链表长了
        if(fast == null){
            return head.next;
        }

        while(fast.next != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return head;
    }
}

• 6.两两交换链表中的节点

给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。

你不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。

//迭代
class Solution {
    public ListNode swapPairs(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode dummyhead = new ListNode(-1);
        dummyhead.next = head;
        ListNode cur = dummyhead;
        while(cur.next != null && cur.next.next != null){
            ListNode first = cur.next;
            ListNode last = cur.next.next;
            first.next = last.next;
            cur.next = last;
            last.next = first;
            cur = cur.next.next;
        }
        return dummyhead.next;
    }
}

//递归
//还没有理解  先空着

• 7.两数相加II

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<Integer> q1 = new ArrayDeque<>();
        Deque<Integer> q2 = new ArrayDeque<>();
        
        while(l1 != null){
            q1.push(l1.val);
            l1 = l1.next;
        }

        while(l2 != null){
            q2.push(l2.val);
            l2 = l2.next;
        }

        ListNode res = null;
        int num1 = 0;
        int num2 = 0;
        int temp = 0;
        int flag = 0;
        while(!q1.isEmpty() || !q2.isEmpty() || flag != 0){
            num1 = q1.isEmpty() ? 0 : q1.pop();
            num2 = q2.isEmpty() ? 0 : q2.pop();
            temp = num1 + num2 + flag;
            ListNode node = new ListNode(temp % 10);
            node.next = res;
            res = node;
            flag = temp / 10;
        }
        return res;
    }
}

• 8.回文链表

请判断一个链表是否为回文链表。

class Solution {
    ListNode temp = null;
    public boolean isPalindrome(ListNode head) {
        //如果回文 则链表长一定是偶数 嘛?  - 不一定
        //1 2 3 2 1
        //1 2 3 3 2 1
        
        temp = head;
        return check(head);
    }

    public boolean check(ListNode node){
        if(node == null)
            return true;
        boolean res = check(node.next) && (temp.val == node.val);
        temp = temp.next;
        return res;
    }
}

• 9.奇偶链表

给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。

请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。

class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode end = even;
        while(odd.next != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
        }
        odd.next = end;
        return head;
    }
}

• 10.K个一组反转链表

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。

k 是一个正整数，它的值小于或等于链表的长度。

如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

/**
 * 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 reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null){
            return head;
        }
        ListNode tail = head;
        for(int i = 0; i < k; i++){
            if(tail == null){
                return head;
            }
            tail = tail.next;
        }
        ListNode newHead = reverse(head, tail);
        head.next = reverseKGroup(tail, k);
        return newHead;
    }

    public ListNode reverse(ListNode head, ListNode tail){
        ListNode pre = null;
        ListNode nxt = null;
        while(head != tail){
            nxt = head.next;
            head.next = pre;
            pre = head;
            head = nxt;
        }
        return pre;
    }
}

2. 树

• 1、前序遍历

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> preorderTraversal(TreeNode root) {
        preOrder(root);
        return res;
    }
    public void preOrder(TreeNode node){
        if(node != null){
            res.add(node.val);
            preOrder(node.left);
            preOrder(node.right);
        }
    }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        preOrder(root, res);
        return res;
    }
    public void preOrder(TreeNode root, List<Integer> res){
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                res.add(root.val);
                stack.add(root);
                root = root.left;
            }
            root = stack.pop().right;
        }
    }
}

• 2、中序遍历

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> inorderTraversal(TreeNode root) {
        //inorder1(root);
        inorder2(root);
        return res;
    }

    //递归法
    public void inorder1(TreeNode root){
        //递归终止条件
        if(root == null) return;
        inorder1(root.left);
        res.add(root.val);
        inorder1(root.right);
    }

    //迭代法
    public void inorder2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode t = stack.pop();
            res.add(t.val);
            root = t.right;
        }
    }
}

• 3、后序遍历

class Solution {
    
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        postOrder(root, res);
        Collections.reverse(res);
        return res;
    }
    public void postOrder(TreeNode root, List<Integer> res){
        Stack<TreeNode> stack = new Stack<>();
        while(root != null || ! stack.isEmpty()){
            while(root != null){
                res.add(root.val);
                stack.push(root);
                root = root.right;
            }
            root = stack.pop().left;
        }
    }
}

class Solution {
    List<Integer> res = new ArrayList<>();
    public List<Integer> postorderTraversal(TreeNode root) {
        help(root);
        return res;
    }
    public void help(TreeNode node){
        if(node == null)
            return;
        help(node.left);
        help(node.right);

        res.add(node.val);
    }
}

• 4、层序遍历

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        if(root == null)
            return new ArrayList<>();

        List<List<Integer>> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();

        q.offer(root);
        int size = 0;
        List<Integer> list;
        while(!q.isEmpty()){
            list = new ArrayList<>();
            size = q.size();
            while(size > 0){
                TreeNode node = q.poll();
                list.add(node.val);
                if(node.left != null)
                    q.offer(node.left);
                if(node.right != null)
                    q.offer(node.right);
                size--;
            }
            res.add(list);
        }
        return res;
    }
}

• 5.验证二叉搜索树

给定一个二叉树，判断其是否是一个有效的二叉搜索树。

假设一个二叉搜索树具有如下特征：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

class Solution {
    public boolean isValidBST(TreeNode root) {
        return cheak(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean cheak(TreeNode root, long min, long max){
        if(root == null)
            return true;
        if(root.val <= min || root.val >= max)
            return false;
        return cheak(root.left, min, root.val) && cheak(root.right, root.val, max);
    }
}

• 6.恢复二叉搜索时

给你二叉搜索树的根节点 root ，该树中的两个节点被错误地交换。请在不改变其结构的情况下，恢复这棵树。

class Solution {
    TreeNode t1, t2, pre;
    public void recoverTree(TreeNode root) {
        inorder(root);
        int temp = t1.val;
        t1.val = t2.val;
        t2.val = temp;
    }

    public void inorder(TreeNode root){
        if(root == null) return;
        inorder(root.left);
        if(pre != null && pre.val > root.val){
            if(t1 == null) t1 = pre;
            t2 = root;
        }
        pre = root;
        inorder(root.right);
    }
    
}

• 7.相同的树

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        if(p == null || q == null)
            return false;
        if(p.val != q.val)
            return false;
        return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

• 8.对称二叉树

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if(root == null)
            return true;
        return cheak(root.left, root.right);
    }

    public boolean cheak(TreeNode node1, TreeNode node2){
        if(node1 == null && node2 == null)
            return true;
        if(node1 == null || node2 == null)
            return false;
        if(node1.val != node2.val)
            return false;
        return cheak(node1.left, node2.right) && cheak(node1.right, node2.left);
    }
}

• 9.二叉树的最大深度

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null)
            return 0;
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
    }
}

• 10.从前序与中序遍历序列构造二叉树

class Solution {
    int[] arr;
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        arr = preorder;
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return build(0, 0, preorder.length - 1);
        
    }

    public TreeNode build(int rootIndex, int left, int right){
        if(left > right) return null;
        TreeNode root = new TreeNode(arr[rootIndex]);
        int index = map.get(arr[rootIndex]);
        root.left = build(rootIndex + 1, left, index - 1);
        root.right = build(rootIndex + index - left + 1, index + 1, right);
        return root;
    }
}

• 11.从后序与中序遍历序列构造二叉树

class Solution {
    int[] arr;
    Map<Integer, Integer> map = new HashMap<>();
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        arr = postorder;
        for(int i = 0; i < inorder.length; i++){
            map.put(inorder[i], i);
        }
        return build(postorder.length - 1, 0, inorder.length - 1);
    }

    public TreeNode build(int rootIndex, int left, int right){
        if(left > right) return null;
        TreeNode root = new TreeNode(arr[rootIndex]);
        int index = map.get(arr[rootIndex]);
        root.left = build(rootIndex - (right - index) - 1, left, index - 1);
        root.right = build(rootIndex - 1, index + 1, right);
        return root;
    }
}

• 12.将有序数组转化为二叉搜索树

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        return build(nums, left, right);
    }

    public TreeNode build(int[] nums, int left, int right){
        if(left > right) return null;
        int mid = (left + right) >> 1;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);
        return root;
    }
}

• 13.有序链表转换二叉搜索树

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        if(head == null) return null;
        if(head.next == null) return new TreeNode(head.val);
        //先找中间节点
        ListNode fast = head;
        ListNode slow = head;
        ListNode pre = null;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            pre = slow;
            slow = slow.next;
        }
        pre.next = null;
        TreeNode root = new TreeNode(slow.val);
        root.left = sortedListToBST(head);
        root.right = sortedListToBST(slow.next);

        return root;
    }
}

• 14.平衡二叉树

class Solution {
    public boolean isBalanced(TreeNode root) {
        if(root == null)
            return true;
        if(Math.abs(depth(root.left) - depth(root.right)) > 1)
            return false;
        return isBalanced(root.left) && isBalanced(root.right);
    }

    public int depth(TreeNode root){
        if(root == null)
            return 0;
        return Math.max(depth(root.left), depth(root.right)) + 1;
    }
}

• 15.二叉树的最小深度

class Solution {
    public int minDepth(TreeNode root) {
        if(root == null)
            return 0;
        int left = minDepth(root.left);
        int right = minDepth(root.right);

        if(left == 0) return right + 1;
        if(right == 0) return left + 1;

        return Math.min(left, right) + 1;
    } 
}

• 16.路径总和

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。

叶子节点 是指没有子节点的节点。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null) 
            return false;
        if(root.left == null && root.right == null)
            return targetSum - root.val == 0;
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

• 17.路径总和II

class Solution {
    List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum, new ArrayList<>());
        return res;
    }

    public void dfs(TreeNode root, int targetSum, List<Integer> list){
        if(root == null) return;
        list.add(root.val);
        if(root.left == null && root.right == null){
            if(targetSum == root.val){
                res.add(new ArrayList<>(list));
            }
        }
        if(root.left != null){
            dfs(root.left, targetSum - root.val, list);
        }
        if(root.right != null){
            dfs(root.right, targetSum - root.val, list);
        }
        list.remove(list.size() - 1);
    }
}

• 18.二叉树展开为链表

class Solution {
    public void flatten(TreeNode root) {
        if(root == null) return ;
        //左右子树拉直
        flatten(root.left);
        flatten(root.right);
        //左子树
        TreeNode left = root.left;
        //右子树
        TreeNode right = root.right;

        root.right = left;
        root.left = null;
        while(root.right != null){
            root = root.right;
        }
        root.right = right;
    }
}

• 19.求根节点到叶节点数字之和

class Solution {
    int res = 0;
    public int sumNumbers(TreeNode root) {
        dfs(root, 0);
        return res;
    }

    public void dfs(TreeNode root, int sum){
        if(root == null) return;
        int k = (sum * 10 + root.val);
        if(root.left == null && root.right == null){
            res += k;
        }
        dfs(root.left, k);
        dfs(root.right, k);
    }
}

• 20.二叉树的所有路径

class Solution {
    List<String> res = new ArrayList<>();
    public List<String> binaryTreePaths(TreeNode root) {
        dfs(root,"");
        return res;
    }
    public void dfs(TreeNode root, String s){
        if(root == null) return;        
        s += root.val;
        if(root.left == null && root.right == null){
            res.add(s);
        }
        dfs(root.left, s + "->");
        dfs(root.right, s + "->");
    }
}

• 21.二叉树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null || p == root || q == root){
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if(left != null && right != null){
            return root;
        }
        return left == null ? right : left;
    }
}

• 22.二叉搜索树的最近公共祖先

• 23.翻转二叉树

class Solution {
    public TreeNode invertTree(TreeNode root) {
        if(root == null) return null;
        invertTree(root.left);
        invertTree(root.right);
        TreeNode right = root.right;
        TreeNode left = root.left;
        root.left = right;
        root.right = left;
        return root;
    }
}

• 24.合并二叉树

class Solution {
    public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
        if(root1 == null)
            return root2;
        if(root2 == null)
            return root1;
        root1.val += root2.val;
        root1.left = mergeTrees(root1.left, root2.left);
        root1.right = mergeTrees(root1.right, root2.right);
        return root1;
    }
}

• 25.二叉树的直径***

class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        dfs(root);
        return max;
    }

    public int dfs(TreeNode root){
        int left = root.left == null ? 0 : dfs(root.left) + 1;
        int right = root.right == null ? 0 : dfs(root.right) + 1;
        max = Math.max(max, left + right);
        return Math.max(left, right);
    }
}

• 26.二叉树中最大的路径和***

class Solution {
    int max = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        if(root == null)
            return 0;
        dfs(root);
        return max;
    }
    public int dfs(TreeNode root){
        if(root == null) return 0;
        int left = Math.max(0, dfs(root.left));
        int right = Math.max(0, dfs(root.right));
        max = Math.max(max, left + right + root.val);
        return Math.max(left, right) + root.val;
    }
}

• 27.二叉树的序列化与反序列化

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        //bfs 层序
        StringBuilder builder = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        if(root == null){
            return "null";
        }
        q.offer(root);
        builder.append(root.val).append(",");
        while(!q.isEmpty()){
            TreeNode node = q.poll();
            if(node.left != null){
                q.offer(node.left);
                builder.append(node.left.val).append(",");
            } else {
                builder.append("null").append(",");
            }
            if(node.right != null){
                q.offer(node.right);
                builder.append(node.right.val).append(",");
            } else {
                builder.append("null").append(",");
            }
        }
        builder.deleteCharAt(builder.length() - 1);
        return builder.toString();
    }
    //suppose to be [1, 2, 3, null, null, 4, 5];

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] nodes = data.split(",");
        TreeNode root = nodes[0].equals("null") ? null : new TreeNode(Integer.parseInt(nodes[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        int i = 1;
        while(i < nodes.length){
            TreeNode node = q.poll();
            if(nodes[i].equals("null")){
                node.left = null;
            } else {
                node.left = new TreeNode(Integer.parseInt(nodes[i]));
                q.offer(node.left);
            }
            i++;
            if(nodes[i].equals("null")){
                node.right = null;
            } else {
                node.right = new TreeNode(Integer.parseInt(nodes[i]));
                q.offer(node.right);
            }
            i++;

        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));