LeetCode刷题11-20

①二叉树的最大深度

题目：给定一个二叉树 root ，返回其最大深度。
二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。

思考：递归实现

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

②108.将有序数组转换为二叉搜索树BST

Binary search tree

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树结构，其中每个节点都满足以下条件：

1. 左子树上的所有节点的值小于该节点的值；
2. 右子树上的所有节点的值大于该节点的值；
3. 左子树和右子树也分别是二叉搜索树。
   由于这种结构的特点，二叉搜索树具有以下性质：
4. 二叉搜索树中的元素是可以比较大小的，因此可以进行快速的搜索、插入和删除操作；
5. 中序遍历二叉搜索树会得到一个有序的元素序列。

高度平衡二叉搜索树（Balanced Binary Search Tree）是二叉搜索树的一种特殊形式，给定其中任意节点，其左子树和右子树的高度差不超过 1 。换句话说，高度平衡二叉搜索树是一棵相对平衡的二叉搜索树。
高度平衡二叉搜索树的优点在于，它可以保证搜索、插入和删除操作的时间复杂度为 O(log n)，其中 n 是树中节点的数量。这是因为树的高度保持在较小的范围内，使得操作的时间复杂度相对较低。
常见的高度平衡二叉搜索树有红黑树、AVL树等，它们通过自平衡的方式保持树的相对平衡性，从而保证了高效的操作效果。

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

    public TreeNode helper(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        // 总是选择中间位置左边的数字作为根节点
        int mid = (left + right) / 2;

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

思考：选取有序数组的中间值作为根节点，左边小于根，右边大于根

③110.平衡二叉树

题目：给定一个二叉树，判断它是否是高度平衡的二叉树。
本题中，一棵高度平衡二叉树定义为：一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1 。

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

    }

    //得到树的高度的函数
    public int height(TreeNode root){
        if(root == null){
            return 0;
        }else{
            return Math.max(height(root.left),height(root.right)) + 1;
        }
    }
}

④111.二叉树的最小深度

题目：给定一个二叉树，找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明：叶子节点是指没有子节点的节点。

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

        int min = Integer.MAX_VALUE;
        if(root.left != null){
            min = Math.min(minDepth(root.left),min);
        }
        if(root.right != null){
            min = Math.min(minDepth(root.right),min);
        }
        return min + 1;

    }
}

思考：
到达叶子节点的条件：该节点无左右孩子
root左右孩子都为null，return 1
root左右孩子不都为null，return 较小深度的结点

⑤112.路径总和

题目：给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。
判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。
如果存在，返回 true ；否则，返回 false 。
叶子节点 是指没有子节点的节点。

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;
        }
        boolean left = hasPathSum(root.left,targetSum - root.val);
        boolean right = hasPathSum(root.right,targetSum - root.val);

        return left || right;
    }
}

⑥118.杨辉三角

题目：
给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。

递归
递归的终止条件是numRows==1
每一层的第一个数字and最后一个数字是1
其他数字是上一层 当前位置数字 + 前一个数字

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = new ArrayList<>();

        if(numRows == 0) return null;
        if(numRows == 1){
            result.add(new ArrayList<>());
            //得到第一个位置的列表，给第一个位置的列表+1
            result.get(0).add(1);
            return result;
        }
        //递归的终止条件是numRows==1
        result = generate(numRows-1);

        List<Integer> row = new ArrayList<>();
        row.add(1);
        for(int i = 1; i<numRows -1 ;i++){
            //result.get(numRows-2)得到上一层
            row.add(result.get(numRows-2).get(i-1) + result.get(numRows-2).get(i));
        }
        row.add(1);
        result.add(row);
        return result;
    }

动态规划

public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> result = 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(result.get(i-1).get(j-1) + result.get(i-1).get(j));
                }
            }
            result.add(row);
        }
        return result;
    }

⑦119.杨辉三角Ⅱ

题目：给定一个非负索引 rowIndex，返回「杨辉三角」的第 rowIndex 行。
在「杨辉三角」中，每个数是它左上方和右上方的数的和。
和上一道题没有太大区别，且要求：
输入: rowIndex = 3
输出: [1,3,3,1]

public List<Integer> getRow(int rowIndex) {
       List<List<Integer>> result = 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(result.get(i-1).get(j-1) + result.get(i-1).get(j));
               }
           }
           result.add(row);
       }
       return result.get(rowIndex);  
   }

⑧121.买卖股票的最佳时机

题目：给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。
你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。
返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。
暴力解法(超时)

public int maxProfit(int[] prices) {
    int maxPrice = 0 ;
    for(int i = 0; i < prices.length - 1; i++){
        for(int j = i + 1; j<prices.length; j++){
            int profit = prices[j] - prices[i];
            if(profit > maxPrice){
                maxPrice = profit;
            }
        }

    }
    return maxPrice;
}

一次遍历

public int maxProfit(int[] prices) {
       int minPrice = Integer.MAX_VALUE;
       int maxProfit = 0;
       for(int i = 0; i < prices.length; i++){
           if(prices[i] < minPrice){
               minPrice = prices[i];
           }
           if(prices[i] - minPrice > maxProfit){
               maxProfit = prices[i] - minPrice;
           }
       }
       return maxProfit;
   }

⑨125.验证回文串

题目：如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 s，如果它是 回文串 ，返回 true ；否则，返回 false 。

Character类是Java中用于表示和操作字符的类，提供了许多实用的方法。以下是Character类中一些常用的方法总结：

1. 字符判断方法：

   • isLetter(char ch)：判断字符是否为字母。
   • isDigit(char ch)：判断字符是否为数字。
   • **isLetterOrDigit(char ch)**：判断字符是否为字母或数字。
   • isLowerCase(char ch)：判断字符是否为小写字母。
   • isUpperCase(char ch)：判断字符是否为大写字母。
   • isWhitespace(char ch)：判断字符是否为空白字符（包括空格、制表符、换行符等）。

2. 字符转换方法：

   • **toLowerCase(char ch)**：将字符转换为小写形式。
   • toUpperCase(char ch)：将字符转换为大写形式。

3. 字符比较方法：

   • equals(char ch1, char ch2)：比较两个字符是否相等。
   • compareTo(char ch1, char ch2)：按照字符的顺序比较两个字符。

4. 字符类型方法：

   • getType(char ch)：返回字符的类型。
   • getNumericValue(char ch)：返回字符的数值。

这些方法可以帮助我们进行字符的判断、转换、比较和查询等操作，方便处理字符相关的需求。

筛选 + 判断 ： 使用reverse

public boolean isPalindrome(String s) {
       StringBuilder sb = new StringBuilder();
       for(int i = 0; i < s.length(); i++){
           char little = s.charAt(i);
           if(Character.isLetterOrDigit(little)){
               sb.append(Character.toLowerCase(little));
           }
       }
       StringBuilder sb_re = new StringBuilder(sb).reverse();
       return sb.toString().equals(sb_re.toString());
   }

筛选 + 判断：不用reverse，使用双指针

public boolean isPalindrome(String s) {
        //使用双指针，不用reverse
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < s.length(); i++){
            char little = s.charAt(i);
            if(Character.isLetterOrDigit(little)){
                sb.append(Character.toLowerCase(little));
            }
        }

        //双指针
        int n = sb.length();
        int left = 0;
        int right = n - 1;
        while(left < right){
            if(sb.charAt(left) != sb.charAt(right)){
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }

直接在原字符串上用双指针
不用StringBuilder产生新的字符串
指针移动到字母/数字上时再进行判断
当不是字母/数字时就自动跳过，指向下一个位置
在 while 循环内部，有两个嵌套的 while 循环。它们的作用是将 left 指针从左向右移动，直到找到一个字母或数字字符；将 right 指针从右向左移动，直到找到一个字母或数字字符。

public boolean isPalindrome(String s) {
        //直接在原有字符串上使用双指针，不产生新的字符串
        int n = s.length();
        int left = 0;
        int right = n-1;
        while(left < right){
            while(left < right && !Character.isLetterOrDigit(s.charAt(left))){
                ++left;
            }
            while(left < right && !Character.isLetterOrDigit(s.charAt(right))){
                --right;
            }
            if(left<right){
                if(Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))){
                    return false;
                }
                ++left;
                --right;
            }
        }
        return true;
    }

⑩136.只出现一次的数字

题目：给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

线性时间复杂度（Linear Time Complexity）是指算法的执行时间与问题规模 n 呈线性关系的情况，即时间复杂度**O(n)**。

异或运算有以下三个性质。

1. 任何数和 0 做异或运算，结果仍然是原来的数，即 a^0=a
2. 任何数和其自身做异或运算，结果是 0，即 a^a=0
3. 异或运算满足交换律和结合律，即 a^b^a = b
   a^b^a
   =b^a^a
   =b^(a^a)
   =b^0
   =b

异或运算的规则是，如果两个操作数的对应位相同，则结果为 0；如果两个操作数的对应位不同，则结果为 1。

int a = 5;  // 二进制表示为 0101
int b = 3;  // 二进制表示为 0011

int result = a ^ b;  // 二进制表示为 0110，十进制表示为 6

运用了异或运算符的性质
a^a^b^b^c^c^e^e^f = f

public int singleNumber(int[] nums) {
        int single = 0;
        for(int num : nums){
            single = single ^ num;
        }
        return single;
    }

若不考虑空间复杂度 可以用HashSet

public int singleNumber(int[] nums) {
       //若不考虑空间复杂度，可以使用哈希表
       Set<Integer> set = new HashSet<Integer>();

       for(int num:nums){
           if(!set.remove(num)){
               //没有此元素
               //若该元素已经存在则会将该元素移除 且不会进入if
               set.add(num);
           }
       }
       return set.iterator().next();
   }

Donate