• 力扣记录:Hot100(10)——461-739


    461 汉明距离

    • Brian Kernighan 算法,参考JZ15 二进制中1的个数,首先计算两数的异或结果,再通过x&(x - 1)计算该结果中1的个数,即为两数的汉明距离
      • 时间复杂度O(log(数据范围)),空间复杂度O(1)
    class Solution {
        public int hammingDistance(int x, int y) {
            int z = x ^ y;
            int res = 0;
            while(z != 0){
                res++;
                z &= (z - 1);
            }
            return res;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    494 目标和

    • 动态规划,01背包,之前做过,假设数组最大和(全为加法)为sum,做加法的和为x,则做减法的和为sum-x,要求x-(sum - x) = target,则x=(target + sum)/2。因此,求加法和为x有几种即为结果
      • 时间复杂度O(n|sum−target|),空间复杂度O(|sum−target|)
    class Solution {
        public int findTargetSumWays(int[] nums, int target) {
            //动态规划,01背包
            //假设数组最大和(全为加法)为sum
            int sum = 0;
            for(int num : nums){
                sum += num;
            }
            if((target + sum) % 2 == 1) return 0;
            int t = (target + sum) / 2;
            if(t < 0) t = -t;   //这里需要将t转为正数
            int[] dp = new int[t + 1];
            dp[0] = 1;  //初始化为1
            //做加法的和为x,则做减法的和为sum-x
            //要求x-(sum - x) = target,则x=(target + sum)/2
            //因此,求加法和为x有几种即为结果
            //一维数组,先物品后背包(大到小)
            for(int i = 0; i < nums.length; i++){
                for(int j = t; j >= nums[i]; j--){
                    dp[j] += dp[j - nums[i]];   //有多少种直接叠加
                }
            }
            return dp[t];
        }
    }
    
    • 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

    538 把二叉搜索树转换为累加树

    • 递归,反向中序遍历(右中左)从后向前累加,之前做过,记录上一个节点值,直接在原树上修改。注意:不使用全局变量
      • 时间复杂度O(n),空间复杂度O(n)
    class Solution {
        public TreeNode convertBST(TreeNode root) {
            //递归
            //记录上一个节点值,直接在原树上修改
            //不使用全局变量
            dfs(0, root);
            return root;
        }
        //递归函数,反向中序遍历(右中左)从后向前累加
        private int dfs(int pre, TreeNode root){
            //终止条件
            if(root == null){
                return pre;
            }
            root.val += dfs(pre, root.right);
            return dfs(root.val, root.left);
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • morris遍历*

    543 二叉树的直径

    • 递归,参考104 二叉树的最大深度,后序遍历,分别计算二叉树中每个节点左右子树的最大深度,经过该节点的最大路径长度为左右子树最大深度之和。
      • 时间复杂度O(n),空间复杂度O(|二叉树高度|)
    class Solution {
        int result;	//定义全局变量记录经过某节点的路径最大长度
        public int diameterOfBinaryTree(TreeNode root) {
            //递归
            result = 0;
            postorder(root);
            return result;
        }
        //递归函数,分别计算二叉树中每个节点左右子树的最大深度,经过该节点的最大路径长度为左右子树最大深度之和
        private int postorder(TreeNode root){
            //终止条件
            if(root == null) return 0;
            //后序遍历
            int left = postorder(root.left);
            int right = postorder(root.right);
            result = Math.max(result, left + right);
            return Math.max(left, right) + 1;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    560 和为 K 的子数组

    • 前缀和+哈希表,参考1 两数之和454 四数相加II,子数组要求连续,将数组第i位之前(不包含i)的和存为前缀和数组sum[i],然后将前缀和出现的次数保存到哈希表中。假设当前位置前缀和为x,则要求x-y=target,即查找哈希表中x-target的个数。
      • 时间复杂度O(n),空间复杂度O(n)
    class Solution {
        public int subarraySum(int[] nums, int k) {
            //前缀和+哈希表
            int sum = 0;
            Map<Integer, Integer> map = new HashMap<>();
            map.put(0, 1);  //注意这里需要初始化,相当于子数组[]
            int result = 0;
            //子数组要求连续,将数组第i位之前(不包含i)的和存为前缀和数组sum[i]
            for(int num : nums){
                sum += num; //更新前缀和
                //假设当前位置前缀和为x,则要求x-y=target,即查找哈希表中x-target的个数
                if(map.containsKey(sum - k)){
                    result += map.get(sum - k);
                }
                //然后将前缀和出现的次数保存到哈希表中
                if(!map.containsKey(sum)){
                    map.put(sum, 0);
                }
                map.put(sum, map.get(sum) + 1);
            }
            return result;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23

    581 最短无序连续子数组

    • 双指针,错误:左右指针分别从首尾出发,找到首尾顺序不对的第一个下标,中间即为最短无序连续子数组子数组(行不通,有重复的数)
    • 正确:左指针从首出发,记录最大值,其正确的位置即右边界;右指针从尾出发,记录最小值,其正确位置即左边界。
      • 时间复杂度O(n),空间复杂度O(1)
    class Solution {
        public int findUnsortedSubarray(int[] nums) {
            //双指针
            int leng = nums.length;
            if(leng == 1) return 0;
            int left = 0;
            int right = 0;
            int max = Integer.MIN_VALUE;
            int min = Integer.MAX_VALUE;
            for(int i = 0; i < leng; i++){
                if(max > nums[i]){
                    right = i;
                }else{
                    max = nums[i];
                }
                if(min < nums[leng - i - 1]){
                    left = leng - i - 1;
                }else{
                    min = nums[leng - i - 1];
                }
            }
            //若left和right在同一位置,说明数组有序,返回0
            return left == right ? 0 : right - left + 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

    617 合并二叉树

    • 递归,之前做过,前序遍历,直接修改其中一棵树的节点。输入两棵树对应位置的节点,若同时为空则返回空,若同时不为空则值相加,否则返回不为空的节点,递归后结果直接赋值为节点的左右孩子
      • 时间复杂度O(n),空间复杂度O(n)
    class Solution {
        public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {
            //递归
            //前序遍历,直接修改其中一棵树的节点
            //输入两棵树对应位置的节点
            if(root1 == null && root2 == null){//若同时为空则返回空
                return null;
            }else if(root1 == null){//否则返回不为空的节点
                return root2;
            }else 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;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    621 任务调度

    • 使用哈希表统计任务及次数,利用二维矩阵进行构造,假设数组中的任务次数最多为x,共有y个,则构造(n+1) * x的二维矩阵,说明至少需要(n+1) * (x-1)+y的时间, 然后将剩下的任务塞进矩阵(最后一行不放),若总列数超出n+1,则过程中不需要待命,结果为任务总数。
      • 时间复杂度O(n+|任务种类|),空间复杂度O(|任务种类|)
    class Solution {
        public int leastInterval(char[] tasks, int n) {
            //使用哈希表统计任务及次数,利用二维矩阵进行构造
            //假设数组中的任务次数最多为x,共有y个,则构造(n+1) * x的二维矩阵
            //说明至少需要(n+1) * (x-1)+y的时间
            Map<Character, Integer> map = new HashMap<>();
            int x = 0;
            int y = 0;
            for(char ch : tasks){
                if(!map.containsKey(ch)){
                    map.put(ch, 0);
                }
                map.put(ch, map.get(ch) + 1);
                x = Math.max(x, map.get(ch));
            }
            //然后将剩下的任务塞进矩阵(最后一行不放)
            for(Map.Entry<Character, Integer> entryset : map.entrySet()){
                if(entryset.getValue() == x){
                    y++;
                }
            }
            //若总列数超出n+1,则过程中不需要待命,结果为任务总数
            return Math.max((n + 1) * (x - 1) + y, tasks.length);
        }
    }
    
    • 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

    647 回文子串

    • 双指针中心扩展,之前做过,遍历字符串,以一个元素后两个元素为中心向两边扩散,左右指针分别向中心两边扩散,每扩散一次若字符相同则回文子串数加1,直到字符不同,返回当前中心的回文子串。
      • 时间复杂度O(n^2),空间复杂度O(1)
    class Solution {
        public int countSubstrings(String s) {
            //双指针中心扩展
            //遍历字符串,以一个元素后两个元素为中心向两边扩散
            int result = 0;
            for(int i = 0; i < s.length(); i++){
                result += count(s, i, i);
                result += count(s, i, i + 1);
            }
            return result;
        }
        //计算当前中心的回文子串个数
        private int count(String s, int i, int j){
            //左右指针分别向中心两边扩散,每扩散一次若字符相同则回文子串数加1
            int result = 0;
            while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
                result++;
                i--;
                j++;
            }
            //直到字符不同,返回当前中心的回文子串个数
            return result;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • Manacher 算法*

    739 每日温度

    • 单调栈,之前做过,栈头值最小,使用单调栈存储下标,遍历数组,如果当前温度大于栈顶下标对应温度,则出栈,并计算栈顶下标的下一次高温(当前下标-栈顶下标),直到当前温度小于栈顶下标对应温度,当前下标入栈。
    • 如果需要找到左边或者右边第一个比当前位置大或者小,则可以考虑使用单调栈
      • 时间复杂度O(n),空间复杂度O(n)
    class Solution {
        public int[] dailyTemperatures(int[] temperatures) {
            //栈头值最小,使用单调栈存储下标
            Deque<Integer> stack = new LinkedList<>();
            int[] result = new int[temperatures.length];
            //遍历数组,如果当前温度大于栈顶下标对应温度,则出栈
            for(int i = 0; i < temperatures.length; i++){
                if(!stack.isEmpty()){
                    while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]){
                        int index = stack.pop();
                        //并计算栈顶下标的下一次高温(当前下标-栈顶下标)
                        result[index] = i - index;
                    }
                    //直到当前温度小于栈顶下标对应温度,当前下标入栈。
                    stack.push(i);
                }else{
                    stack.push(i);
                }
            }
            return result;
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
  • 相关阅读:
    基于枚举实现的观察者模式
    【数字图像处理】直方图均衡化与规定化
    Shaderlab的组成部分SubShader
    VSCode 占用内存过高
    2023秋招感悟
    Segger RTT深度使用说明-移植-Jlink rtt viewer显示-输出到Secure CRT
    YOLO改进系列之注意力机制(GAM Attention模型介绍)
    ios safari 浏览器跳转页面没有自适应
    【Vue3 Antdv】Ant Design Vue文字溢出鼠标滑上显示tooltip。不溢出,鼠标滑上不显示tooltip
    C之fopen/fclose/fread/fwrite/flseek
  • 原文地址:https://blog.csdn.net/Kiwi_fruit/article/details/125752355