• Java练习 day2(LeetCode简单题15道）

    一、删除排序链表中的重复元素

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * 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 deleteDuplicates(ListNode head) {
        ListNode curNode = head;
        while(curNode != null && curNode.next != null){
            if(curNode.next.val == curNode.val){
                curNode.next = curNode.next.next;
            } else{
                curNode = curNode.next; 
            }
        }
    return head;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    3、知识点

    (1) 链表

    二、合并两个有序数组

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int[] sorted = new int[m + n];
        int i = 0;
        int j = 0;
        int index = 0;
        while(i < m && j < n){
            if(nums1[i] <= nums2[j]){
                sorted[index++] = nums1[i++];
            } else{
                sorted[index++] = nums2[j++];
            }
        }
        while(i < m){
            sorted[index++] = nums1[i++];
        }
        while(j < n){
            sorted[index++] = nums2[j++];
        }
        for(i = 0; i < m + n; ++i){
            nums1[i] = sorted[i];
        } 
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24

    3、知识点

    (1) 线性枚举，两个顺序表合并。

    三、二叉树的中序遍历

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public void inorder(TreeNode root, List<Integer> res){
        if(root == null){
            return ;
        }
        inorder(root.left, res);
        res.add(root.val);
        inorder(root.right, res);
    }


    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        inorder(root, res);
        return res;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    3.知识点

    (1) 树的中序遍历。

    四、相同的树

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        } else if(p == null || q == null){
            return false;
        } else if(p.val != q.val){
            return false;
        }
    return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27

    3.知识点

    (1) 树中用递归解决问题。

    五、对称二叉树

    1、题目链接

    点击跳转到题目位置

    2、代码

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

class Solution {
    public boolean judge(TreeNode root1, TreeNode root2){
        if(root1 == null && root2 == null){
            return true;
        } else if(root1 == null || root2 == null){
            return false;
        } else if(root1.val != root2.val){
            return false;
        }
    return judge(root1.left, root2.right) && judge(root1.right, root2.left);
    }

    public boolean isSymmetric(TreeNode root) {
        return judge(root.left, root.right);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    3.知识点

    (1) 树中递归

    六、二叉树的最大深度

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left_length = maxDepth(root.left);
        int right_length = maxDepth(root.right);
    return Math.max(left_length, right_length) + 1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25

    3.知识点

    (1) 树中递归。

    七、将有序数组转换为二叉搜索树

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode Build(int[] nums, int left, int right){
        if(left > right){
            return null;
        }

        int mid = ((right - left) >> 1) + left;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = Build(nums, left, mid - 1);
        root.right = Build(nums, mid + 1, right);
    return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return Build(nums, 0, nums.length - 1);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    3.知识点

    (1) 树中递归。

    八、将有序数组转换为二叉搜索树

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode Build(int[] nums, int left, int right){
        if(left > right){
            return null;
        }

        int mid = ((right - left) >> 1) + left;

        TreeNode root = new TreeNode(nums[mid]);
        root.left = Build(nums, left, mid - 1);
        root.right = Build(nums, mid + 1, right);
    return root;
    }

    public TreeNode sortedArrayToBST(int[] nums) {
        return Build(nums, 0, nums.length - 1);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33

    3.知识点

    (1) 树中分治（实际上是递归）

    九、平衡二叉树

    1、题目链接

    点击跳转到题目位置

    2、代码

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

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

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    3.知识点

    (1) 树中递归

    十、二叉树的最小深度

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDepth(TreeNode root) {
        if(root == null){
            return 0;
        }
        int left_length = minDepth(root.left);
        int right_length = minDepth(root.right);
        if(left_length == 0){
            return right_length + 1;
        } 
        if(right_length == 0){
            return left_length + 1;
        }
    return Math.min(left_length, right_length) + 1;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31

    3.知识点

    (1) 树中递归。

    十一、路径总和

    1、题目链接

    点击跳转到题目位置

    2、代码

    /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public boolean Sum(TreeNode root,int num,int targetSum){
        if(root == null){
            return false;
        }
        num += root.val;
        if(root.left == null && root.right == null){
            if(num == targetSum){
                return true;
            } 
        return false;
        }
    return Sum(root.left, num, targetSum) || Sum(root.right, num, targetSum);
    }
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if(root == null){
            return false;
        }
        return Sum(root, 0, targetSum);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    3.知识点

    (1) 树中递归。

    十二、杨辉三角

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for(int i = 0; i < numRows; ++i){
            List<Integer> row = new ArrayList<Integer>();
            for(int j = 0; j <= i; ++j){
                if(j == 0 || j == i){
                    row.add(1);
                } else{
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
    return ret;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    3.知识点

    (1) 动态规划（二维）。

    十三、杨辉三角 II

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public List<Integer> getRow(int rowIndex) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        for(int i = 0; i <= rowIndex; ++i){
            List<Integer> row = new ArrayList<Integer>();
            for(int j = 0; j <= i; ++j){
                if(j == 0 || j == i){
                    row.add(1);
                } else{
                    row.add(ret.get(i - 1).get(j - 1) + ret.get(i - 1).get(j));
                }
            }
            ret.add(row);
        }
    return ret.get(rowIndex);
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17

    3.知识点

    (1) 动态规划（二维）。

    十四、 买卖股票的最佳时机

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] dp = new int[n+1];
        int max_price = 0;
        for(int i = 0; i < n; ++i){
            if(i == 0){
                dp[i] = prices[i];
            } else{
                dp[i] = Math.min(dp[i - 1], prices[i]);
                max_price = Math.max(max_price, prices[i] - dp[i-1]);
            }
        }
    return max_price;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16

    3.知识点

    (1) 动态规划(一维）

    十五、只出现一次的数字

    1、题目链接

    点击跳转到题目位置

    2、代码

    class Solution {
    public int singleNumber(int[] nums) {
        int num = 0;
        for(int i = 0; i < nums.length; ++i){
            num ^= nums[i];
        }
    return num;
    }
}

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    3、知识点

    (1) 使用位运算的性质来解决问题。

  • 相关阅读:
    【力扣算法简单五十题】08.删除排序链表中的重复元素
    Redis之发布订阅
    ubuntu18安装coova chilli精简
    图论篇--代码随想录算法训练营第五十六天打卡| 108. 冗余连接，109. 冗余连接II
    【BSC】使用Python玩转PancakeSwap（入门篇）
    【蓝桥每日一题]-前缀和与差分（保姆级教程 篇2）#差分序列
    关于父母离婚后子女姓名变更有关问题的批复
    @Autowired注解在spring中的用法
    URDMA跑起来
    DAB DETR 论文精度，并解析其模型结构
  • 原文地址：https://blog.csdn.net/qq_56086076/article/details/133482848