力扣每日练习-java版（三）

最新推荐文章于 2024-07-19 16:35:49 发布
最新推荐文章于 2024-07-19 16:35:49 发布
阅读量714 收藏
点赞数
分类专栏： 算法 文章标签： leetcode java 算法
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/sinat_20568267/article/details/122804854
版权

力扣每日练习-java版（三）

208. 实现 Trie (前缀树)

208. 实现 Trie (前缀树)
在这里插入图片描述

思路

Trie 树又叫字典树、前缀树、单词查找树，是一种二叉树衍生出来的高级数据结构，主要应用场景是处理字符串前缀相关的操作。
其每个节点包含以下字段：

  • 指向子节点的指针数组children。对于本题而言，数组长度为 226，即小写英文字母的数量。此时children[0] 对应小写字母 a，children[1] 对应小写字母 b，…，children[25] 对应小写字母 z。
  • 布尔字段isEnd，表示该节点是否为字符串的结尾。

    插入字符串
    我们从字典树的根开始，插入字符串。对于当前字符对应的子节点，有两种情况：
    • 子节点存在。沿着指针移动到子节点，继续处理下一个字符。
    • 子节点不存在。创建一个新的子节点，记录在children 数组的对应位置上，然后沿着指针移动到子节点，继续搜索下一个字符。
      重复以上步骤，直到处理字符串的最后一个字符，然后将当前节点标记为字符串的结尾。
      查找前缀
      我们从字典树的根开始，查找前缀。对于当前字符对应的子节点，有两种情况：
    • 子节点存在。沿着指针移动到子节点，继续搜索下一个字符。
    • 子节点不存在。说明字典树中不包含该前缀，返回空指针。
      重复以上步骤，直到返回空指针或搜索完前缀的最后一个字符。
      若搜索到了前缀的末尾，就说明字典树中存在该前缀。此外，若前缀末尾对应节点的isEnd 为真，则说明字典树中存在该字符串。

代码

class Trie {
    private Trie[] children;
    private boolean isEnd;

    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }
    
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); i++) {
            char ch = word.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                node.children[index] = new Trie();
            }
            node = node.children[index];
        }
        node.isEnd = true;
    }
    
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }
    
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;
    }

    private Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); i++) {
            char ch = prefix.charAt(i);
            int index = ch - 'a';
            if (node.children[index] == null) {
                return null;
            }
            node = node.children[index];
        }
        return node;
    }
}

时空复杂度

在这里插入图片描述

备注

198. 打家劫舍

198. 打家劫舍
在这里插入图片描述

思路

动态规划。

  1. 自顶向下
    状态： 当前房子索引。
    选择： 抢or不抢。抢就不能再选相邻房间，要从下下个房间开始选择；不抢就放弃当前，从下一个房子开始选择。
    base case： 走过了最后一间房。
    优化重复子问题： 使用备忘录记录抢过的房间。
  2. 自底向上
    状态： 当前房子索引。
    选择： 抢or不抢。抢就不能再选相邻房间，要从下下个房间开始选择；不抢就放弃当前，从下一个房子开始选择。
    base case： 从结果往回推，走过了第一间房结束。
    优化重复子问题： 只维护走一步、走两步的最大值

代码

  1. 自顶向下
class Solution {
    // 备忘录
    private int[] memo;
    // 主函数
    public int rob(int[] nums) {
        // 初始化备忘录
        memo = new int[nums.length];
        Arrays.fill(memo, -1);
        // 强盗从第 0 间房子开始抢劫
        return dp(nums, 0);
    }

    // 返回 dp[start..] 能抢到的最大值
    private int dp(int[] nums, int start) {
        if (start >= nums.length) {
            return 0;
        }
        // 避免重复计算
        if (memo[start] != -1) return memo[start];

        int res = Math.max(dp(nums, start + 1),
                nums[start] + dp(nums, start + 2));
        // 记入备忘录
        memo[start] = res;
        return res;
    }
}
  1. 自底向上
class Solution {
    public int rob(int[] nums) {
         int n = nums.length;
        // 记录 dp[i+1] 和 dp[i+2]
        int dp_i_1 = 0, dp_i_2 = 0;
        // 记录 dp[i]
        int dp_i = 0; 
        for (int i = n - 1; i >= 0; i--) {
            dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
            dp_i_2 = dp_i_1;
            dp_i_1 = dp_i;
        }
        return dp_i;
    }
}

时空复杂度

1.时间复杂度
O(n)
2.空间复杂度
​ 方法一：O(n) 备忘录需要空间 。
方法二：O(1)

备注

  1. Arrays.fill(memo, -1); 将数组memo 所有位置的值赋值为-1
  2. Math.max(a,b) 求a，b中最大值
  3. Math.min(a,b) 求a，b中最小值

213. 打家劫舍 II

213. 打家劫舍 II
在这里插入图片描述

思路

首尾房间不能同时被抢，那么只可能有三种不同情况：要么都不被抢；要么第一间房子被抢最后一间不抢；要么最后一间房子被抢第一间不抢。事实上，只要比较情况二和情况三就行了，因为这两种情况对于房子的选择余地比情况一大呀，房子里的钱数都是非负数，能选择的房子多，最优决策结果肯定不会小。

代码

class Solution{
	public int rob(int[] nums) {
    int n = nums.length;
    if (n == 1) return nums[0];
    return Math.max(robRange(nums, 0, n - 2), 
                    robRange(nums, 1, n - 1));
	}
// 仅计算闭区间 [start,end] 的最优结果
	int robRange(int[] nums, int start, int end) {
	    int n = nums.length;
	    int dp_i_1 = 0, dp_i_2 = 0;
	    int dp_i = 0;
	    for (int i = end; i >= start; i--) {
	        dp_i = Math.max(dp_i_1, nums[i] + dp_i_2);
	        dp_i_2 = dp_i_1;
	        dp_i_1 = dp_i;
	    }
	    return dp_i;
	}
}

时空复杂度

1.时间复杂度
O(n)，其中 n 是数组长度。需要对数组遍历两次，计算可以偷窃到的最高总金额。
2.空间复杂度
​O(1)

备注

337. 打家劫舍 III

337. 打家劫舍 III
在这里插入图片描述

思路

动态规划。
选择：
返回一个大小为 2 的数组 arr
arr[0] 表示不抢 root 的话，得到的最大钱数
arr[1] 表示抢 root 的话，得到的最大钱数
分别递归左右子树得到结果。

代码

/**
 * 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 rob(TreeNode root) {
        int[] res = dp(root);
        return Math.max(res[0], res[1]);
    }
    /* 返回一个大小为 2 的数组 arr
    arr[0] 表示不抢 root 的话，得到的最大钱数
    arr[1] 表示抢 root 的话，得到的最大钱数 */
    public int[] dp(TreeNode root) {
        if (root == null) return new int[]{0, 0};
        int[] left = dp(root.left);
        int[] right = dp(root.right);
        // 抢，下家就不能抢了
        int rob = root.val + left[0] + right[0];
        // 不抢，下家可抢可不抢，取决于收益大小
        int not_rob = Math.max(left[0],left[1]) + Math.max(right[0],right[1]);
        return new int[]{not_rob, rob};
    }
}

时空复杂度

1.时间复杂度
O(N)
2.空间复杂度
​空间复杂度只有递归函数堆栈所需的空间 O(N)

备注

  1. int[] res = new int[]{not_rob, rob}; 声明，初始化数组

112. 路径总和

112. 路径总和
在这里插入图片描述

思路

递归：输入一个根节点，返回该根节点到叶子节点是否存在一条和为 targetSum 的路径。每次向下走一个节点，将targetSum减去之前节点的val，直到到达根节点。

代码

/**
 * 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 hasPathSum(TreeNode root, int targetSum) {
        if(root==null) return false;
        if(root.left==null && root.right ==null) {
            return targetSum == root.val;
        }
        return hasPathSum(root.left,targetSum-root.val) || hasPathSum(root.right,targetSum-root.val);
    }
}

时空复杂度

1.时间复杂度
O(N)，其中 N 是树的节点数。对每个节点访问一次。
2.空间复杂度
O(H)，其中 H是树的高度。空间复杂度主要取决于递归时栈空间的开销，最坏情况下，树呈现链状，空间复杂度为O(N)。平均情况下树的高度与节点数的对数正相关，空间复杂度为O(logN)。

备注

69. x 的平方根

69. x 的平方根
在这里插入图片描述

思路

二分查找，由于 xx平方根的整数部分ans 是满足 k^2 ≤x 的最大k值，因此我们可以对 k进行二分查找，从而得到答案。

代码

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = l + (r - l)/2;
            if ((long) mid * mid <= x) {
                ans = mid;
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }
}

时空复杂度

1.时间复杂度
O(logx)，即为二分查找需要的次数。
2.空间复杂度
​O(1)

备注

64. 最小路径和

64. 最小路径和
在这里插入图片描述

思路

动态规划：在二维矩阵中求最优化问题（最大值或者最小值），肯定需要递归（不断选择不同路径） + 备忘录（解决重叠子问题，防止重复访问）。

代码

class Solution {
    int[][] memo;
    public int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
         // 构造备忘录，初始值全部设为 -1,后续的值更新为到达当前下标的最小路径和
        memo = new int[m][n];
        for(int[] row:memo){
            Arrays.fill(row,-1);
        }
        //从右下角往回反推，到右下角的最小路径和 = min（到上边位置的最小路径和，到左边位置的最小路径和）+ 右下角的值。
        return dp(grid,m-1,n-1);
    }
    //grid数组，当前所在下标
    public int dp(int[][] grid,int x,int y) {
        //base case
        if(x==0&&y==0) return grid[0][0];
        //越界处理:如果索引出界，返回一个很大的值，保证在取 min 的时候不会被取到
        if(x<0||y<0) return Integer.MAX_VALUE;
        // 避免重复计算
        if (memo[x][y] != -1) {
            return memo[x][y];
        }
        // 将计算结果记入备忘录
        memo[x][y] = Math.min(
            dp(grid, x - 1, y),
            dp(grid, x, y - 1)
        ) + grid[x][y];

        return memo[x][y];
    }
}

时空复杂度

1.时间复杂度
O(MN)
2.空间复杂度
O(MN)

备注

  1. 整数最大值 Integer.MAX_VALUE
  2. 整数最小值 Integer.MIN_VALUE
  3. 关于备忘录：
    1）构造备忘录，并初始化默认值
    2）递归过程中，先查询备忘录，有直接返回，没有则将结果记录到备忘录。
【Java每日一题】2.和数最大操作II-动态规划
tRNA的博客
06-08 333
题目难度：中等 主要提升：for循环思想、动态规划思想、数组操作
2742.力扣每日一题6/28 Java(0-1背包问题)
天天困啊的博客
06-28 1098
你必须找到你的宝藏，否则你在途中发现的一切便全都失去了意义。——保罗·柯艾略。
力扣每日练习-java版（一）
阿江的博客
02-02 1385
力扣每日练习（一）2000. 反转单词前缀思路代码时空复杂度备注48. 旋转图像思路代码时空复杂度备注22. 括号生成思路代码时空复杂度备注617. 合并二叉树思路代码时空复杂度160. 相交链表思路代码时空复杂度备注78. 子集思路代码时空复杂度备注 2000. 反转单词前缀 https://leetcode-cn.com/problems/reverse-prefix-of-word/ 思路 1.找字符所在位置，没找到返回原字符串，否则进行第二步 2.反转0 ~ i位置的字符串，拼接上i+1 ~ n-
*JAVA* 精选力扣题—第1题（变更性别）
m0_50575131的博客
06-01 282
*JAVA* 精选力扣题—第1题（变更性别）题目描述例子题目分析方法一：使用 UPDATE 和 CASE...WHEN方法二：使用IF语句一行代码方法三：字母和ASCII互转方法四：异或方法五：replace 题目描述 给定一个 salary 表，如下所示，有 m = 男性 和 f = 女性 的值。交换所有的 f 和 m 值（例如，将所有 f 值更改为 m，反之亦然）。要求只使用一个更新（Update）语句，并且没有中间的临时表。注意，您必只能写一个 Update 语句，请不要编写任何 Selec
力扣-80题（Java）
qq_40467670的博客
04-06 262
题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii/ 题目如下： class Solution { public int removeDuplicates(int[] nums) { int i,count=1,num=nums[0],pos=1,length=nums.length; for(i=1;i<nums.length;i++){
力扣每日练习-java版（五）
阿江的博客
02-16 562
力扣每日练习-java版（五）287. 寻找重复数思路方法1.暴力双重循环 - 力扣超时方法2.哈希表HashSet - 不符合题目复杂度要求方法3.二分法方法4.二进制方法5.快慢指针代码时空复杂度备注题目思路代码时空复杂度备注题目思路代码时空复杂度备注题目思路代码时空复杂度备注题目思路代码时空复杂度备注 287. 寻找重复数 https://leetcode-cn.com/problems/find-the-duplicate-number/ 思路 方法1.暴力双重循环 - 力扣超时 时间复杂度O(n2
蓝桥杯算法练习：力扣每日题解与Java实战
力扣每日一题是该平台提供的一种定期练习服务，旨在帮助用户通过每日练习来逐步提升算法能力。 结合蓝桥杯和力扣的练习，有助于参赛者在算法竞赛中取得更好的成绩。此类练习通常要求参赛者熟练掌握Java编程语言，...
java程序员每日力扣算法练习实践指南
标题“javalruleetcode-leetCodeAlgorithm:练习算法知识”所涉及的知识点包括Java编程语言、数据结构与算法、LeetCode平台以及开源项目。 Java是一种广泛使用的高级编程语言，它以面向对象、平台无关性以及安全性为...
3112.力扣每日一题7/18 Java 迪杰斯特拉（Dijkstra）算法
最新发布
天天困啊的博客
07-19 860
迪杰斯特拉算法的时间复杂度通常为 O(N²),其中N是顶点的数量。如果使用二叉堆如果使用二堆（或斐波那契堆）来优化选择最小距离顶点的操作，时间复杂度可以优化到O((N+M)logN),其中M是边的数量。同时考虑每个节点的消失时间，如果在节点消失之前无法到达，则标记为不可达（-1）。它的基本思想是：从一个起始顶点出发，逐步向外扩展，每次选择距离起始顶点最近且未被处理过的顶点，然后更新该顶点相邻顶点的距离。的数组来存储每个节点的最少到达时间和一个优先级队列，空间复杂度主要取决于节点数量。，还使用了一个长度为。
3011.力扣每日一题7/13 Java（冒泡排序）
天天困啊的博客
07-13 1310
冒泡排序解法以及冒泡排序讲解
动态规划入门
底层码农
10-11 6143
动态规划入门
Arrays.fill()的错误用法-源码解析
linry的博客
10-30 975
引言： 在刷算法题时，Coders往往只考虑时间复杂度问题，而空间时间复杂度常以空间换时间的方式反向增加。常遇空间问题有迭代开辟了数组空间，为了更优化空间复杂度，常以全局变量数组形式声明，数组赋值解决空间优化问题。 相关工作： 数组问题可以概况为一维、二维、三维和高维数组赋值。查看部分博客对二维数组赋值中Arrayss.fill有错误使用问题，为方面后期学习复习和理解，我们将深入Arrays.fill()源码理解赋值的正确方式。 错误用例： ...
java中数组的初始化（Arrays.fill（））
AI蜗牛之家
10-11 1万+
用法1：接受2个参数 Arrays.fill（ a1, value ）; 注：a1是一个数组变量，value是一个a1中元素数据类型的值，作用：填充a1数组中的每个元素都是value 例如： boolean[] a1 = new boolean[5]; Arrays.fill( a1,true ); 结果 a1[] = {true,true,true,true,true}; 用法
Arrays.fill（）方法
年少有为的博客
09-09 2万+
Java数组Arrays.fill（）方法 实用型方法 用于一维数组、二维数组的初始化或者填充 对于一维数组和二维数组写点学习心得 在Java API 中的 public static void fill(Object[] a, int fromIndex, int toIndex, Object val)将指定的 Object 引用分配给指定 Object 数组指定范围中的每个元素。...
关于Arrays.fill问题
我的博客
01-23 366
@Test public void test() { List<Integer>[] routes = new List[100]; List<Integer>[] routes2 = new List[100]; Arrays.fill(routes, new ArrayList<>()); for (int i = 0; i < 100; ++i) { routes2[i] = new ArrayList<Integer
使用Arrays.fill()方法对数组元素填充
LL__Sunny的博客
04-19 1454
##### 使用Arrays.fill()方法对数组元素填充 package com; import java.util.Arrays; /* * 使用Arrays.fill()方法对数组元素填充 */ public class L_input_ArrayFill { public static void main(String[] args) { // TODO Auto-ge...
Java数组Arrays.fill（）方法
热门推荐
I can do
11-26 7万+
Java数组Arrays.fill（）方法 Java API  中的 Fill    public static void fill(Object[] a,  int fromIndex,  int toIndex,   Object val)将指定的 Object 引用分配给指定 Object 数组指定范围中的每个元素。填充的范围从索引 fromIndex（包括）一直到索引 toIndex（
java代码实现自定义栈 + 时间复杂度分析
weixin_33941350的博客
05-18 234
如果是还不知道栈是啥玩意的同学们请查看我在CSDN写的一篇关于栈的博客： https://blog.csdn.net/qq_43059674/article/details/86567733 自定义栈java实现代码： 接口定义： /** * 定义栈接口 * * @author 20190313 * */ public interface Stack<T&...
Arrays.fill()
答案是肯定的
10-24 3966
Arrays.fill()功能很Arrays.fill()功能很有限，只能用同一个值填充各个位置
评论
添加红包

请填写红包祝福语或标题

个

红包个数最小为10个

元

红包金额最低5元

当前余额3.43元 前往充值 >
需支付：10.00元
成就一亿技术人!
领取后你会自动成为博主和红包主的粉丝 规则
hope_wisdom
发出的红包
实付元
使用余额支付
点击重新获取
扫码支付
钱包余额 0

抵扣说明：

1.余额是钱包充值的虚拟货币，按照1:1的比例进行支付金额的抵扣。
2.余额无法直接购买下载，可以购买VIP、付费专栏及课程。

余额充值