一只程序小洋 level
获赞
6
粉丝
2
关注
7
看过 TA
2
男
门头沟学院
2022
Java
IP属地：四川
一步一步，皆是进步！！
私信
关注
发布(86) 评论 刷题
2021-08-03 14:14
门头沟学院 Java
经典动态规划：二维（02）
题目： 给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。 两个相邻元素间的距离为 1  题解： 对于矩阵中的任意一个 1 以及一个 0，我们如何从这个 1 到达 0 并且距离最短呢？根据上面的做法，我们可以从 1 开始，先在水平方向移动，直到与 0 在同一列，随后再在竖直方向上移动，直到到达 0 的位置。这样一来，从一个固定的 1 走到任意一个 0，在距离最短的前提下可能有四种方法： 只有 水平向左移动 和 竖直向上移动； 只有 水平向左移动 和 竖直向下移动； 只有 水平向右移动 和 竖直向上...
0 点赞 评论 收藏
分享
2021-08-03 14:14
已编辑
门头沟学院 Java
经典动态规划：分割类题型——01（LC279）
题目：给定一个正整数，求其最少可以由几个完全平方数相加构成。 输入是给定的正整数，输出也是一个正整数，表示输入的数字最少可以由几个完全平方数相 加构成。 题解： 首先初始化长度为 n+1 的数组 dp，每个位置都为 0 如果 n 为 0，则结果为 0 对数组进行遍历，下标为 i，每次都将当前数字先更新为最大的结果，即 dp[i]=i，比如 i=4，最坏结果为 4=1+1+1+1 即为 4 个数字 动态转移方程为：dp[i] = MIN(dp[i], dp[i - j * j] + 1)，i 表示当前数字，j*j 表示平方数 时间复杂度：O(n*sqrt(n))O(n∗sqrt(n))，s...
0 点赞 评论 收藏
分享
2021-08-03 14:14
门头沟学院 Java
经典动态规划：分割类问题-02（LC91）
题目：已知字母 A-Z 可以表示成数字 1-26。给定一个数字串，求有多少种不同的字符串等价于这个数字串。 输入是一个由数字组成的字符串，输出是满足条件的解码方式总数 题解：对于给定的字符串 s，设它的长度为 n，其中的字符从左到右依次为 , s[n]s[1],s[2],⋯,s[n]。我们可以使用动态规划的方法计算出字符串 s 的解码方法数。 具体地，设 fi表示字符串 s 的前 i 个字符 s[1..i] 的解码方法数。在进行状态转移时，我们可以考虑最后一次解码使用了 s 中的哪些字符，那么会有下面的两种情况： 第一种情况是我们使用了一个字符，即 s[i] 进行解码，那么只要 s[i...
0 点赞 评论 收藏
分享
2021-08-03 14:13
门头沟学院 Java
经典动态规划：分割类问题-03（LC139）
题目：给定一个字符串和一个字符串集合，求是否存在一种分割方式，使得原字符串分割后的子字 符串都可以在集合内找到。 题解：类似于完全平方数分割问题，这道题的分割条件由集合内的字符串决定，因此在考虑每个分 割位置时，需要遍历字符串集合，以确定当前位置是否可以成功分割。注意对于位置 0，需要初 始化值为真。 对于检查一个字符串是否出现在给定的字符串列表里一般可以考虑哈希表来快速判断，同时也可以做一些简单的剪枝，枚举分割点的时候倒着枚举，如果分割点 j 到 ii的长度已经大于字典列表里最长的单词的长度，那么就结束枚举，但是需要注意的是下面的代码给出的是不带剪枝的写法。 优化一下，dp[i]只需要...
0 点赞 评论 收藏
分享
2021-08-03 14:13
已编辑
门头沟学院 Java
经典动态规划：二维-03（LC221）
题目：给定一个二维的 0-1 矩阵，求全由 1 构成的最大正方形面积 题解： 使用动态规划降低时间复杂度。我们用 dp(i,j) 表示以 (i,j) 为右下角，且只包含 1 的正方形的边长最大值。如果我们能计算出所有 dp(i,j) 的值，那么其中的最大值即为矩阵中只包含 1 的正方形的边长最大值，其平方即为最大正方形的面积。 那么如何计算 dp 中的每个元素值呢？对于每个位置(i,j)，检查在矩阵中该位置的值： 如果该位置的值是 0，则 dp(i,j)=0，因为当前位置不可能在由 1 组成的正方形中； 如果该位置的值是 1，则 dp(i,j) 的值由其上方、左方和左上方的三个相邻位...
0 点赞 评论 收藏
分享
2021-08-03 14:13
门头沟学院 Java
经典动态规划：子序列问题-01（LC300）
题目：输入是一个一维数组，输出是一个正整数，表示最长递增子序列的长度 注意： 按照 LeetCode 的习惯，子序列（subsequence）不必连续，子数组（subarray）或子字符串（substring）必须连续。 题解：对于子序列问题，第一种动态规划方法是，定义一个 dp 数组，其中 dp[i] 表示以 i 结尾的子序列的性质。在处理好每个位置后，统计一遍各个位置的结果即可得到题目要求的结果。在本题中，dp[i] 可以表示以 i 结尾的、最长子序列长度。对于每一个位置 i，如果其之前的某 个位置 j 所对应的数字小于位置 i 所对应的数字，则我们可以获得一个以 i 结尾的、长度为 ...
0 点赞 评论 收藏
分享
2021-08-03 14:12
门头沟学院 Java
经典动态规划：子序列-02（LC1143）
题目：给定两个字符串，求它们最长的公共子序列长度。 题解：对于子序列问题，动态规划方法是，定义一个 dp 数组，其中 dp[i] 表示到位置 i 为止 的子序列的性质，并不必须以 i 结尾。这样 dp 数组的最后一位结果即为题目所求，不需要再对每 个位置进行统计。我们可以建立一个二维数组 dp，其中 dp[i][j] 表示到第一个字符串位置 i 为止、到第二个字符串位置 j 为止、最长的公共子序列长度。 class Solution { public int longestCommonSubsequence(String text1, String text2) { in...
0 点赞 评论 收藏
分享
2021-08-03 14:12
已编辑
门头沟学院 Java
经典动态规划：背包问题！！（结合LC416官方视频解释！！）
题目： 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。 题解： 给定一个只包含正整数的非空数组 nums[0]，判断是否可以从数组中选出一些数字，使得这些数字的和等于整个数组的元素和的一半。因此这个问题可以转换成「0−1 背包问题」。这道题与传统的0−1 背包问题」的区别在于，传统的0−1 背包问题」要求选取的物品的重量之和不能超过背包的总容量，这道题则要求选取的数字的和恰好等于整个数组的元素和的一半。类似于传统的0−1 背包问题」，使用动态规划求解。 class Solution { public bo...
0 点赞 评论 收藏
分享
2021-08-03 14:11
门头沟学院 Java
学习记录套接字
应用层通过传输层进行数据通信时，TCP和UDP会遇到同时为多个应用程序进程提供并发服务的问题。多个TCP连接或多个应用程序进程可能需要 通过同一个TCP协议端口传输数据。为了区别不同的应用程序进程和连接，许多计算机操作系统为应用程序与TCP／IP协议交互提供了称为套接字 (Socket)的接口，区分不同应用程序进程间的网络通信和连接。 生成套接字，主要有3个参数：通信的目的IP地址、使用的传输 层协议(TCP或UDP)和使用的端口号。Socket原意是“插座”。通过将这3个参数结合起来，与一个“插座”Socket绑定，应用层就可以和传输 层通过套接字接口，区分来自不同应用程序进程或网络连接的...
0 点赞 评论 收藏
分享
2021-08-03 14:11
已编辑
门头沟学院 Java
经典动态规划：背包问题-（LC474）
题目：给定 m 个数字 0 和 n 个数字 1，以及一些由 0-1 构成的字符串，求利用这些数字最多可以构成多少个给定的字符串，字符串只可以构成一次。 思路： 把总共的 0 和 1 的个数视为背包的容量，每一个字符串视为装进背包的物品。这道题就可以使用 0-1 背包问题的思路完成，这里的目标值是能放进背包的字符串的数量 动态规划的思路是：物品一个一个尝试，容量一点一点尝试，每个物品分类讨论的标准是：选与不选。 定义状态：尝试题目问啥，就把啥定义成状态。dp[i][j][k] 表示输入字符串在子区间 [0, i] 能够使用 j 个 0 和 k 个 1 的字符串的最大数量。 初始化：为了...
0 点赞 评论 收藏
分享
2021-08-03 14:11
门头沟学院 Java
经典动态规划：背包问题-（LC322）
题目： 给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。 计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。 你可以认为每种硬币的数量是无限的。 题解： 我们采用自下而上的方式进行思考。仍定义 F(i) 为组成金额 i 所需最少的硬币数量，假设在计算 F(i) 之前，我们已经计算出 F(0)−F(i−1) 的答案。  c_j 代表的是第 j 枚硬币的面值，即我们枚举最后一枚硬币面额是 c_j ，那么需要从 i-c 这个金额的状态 F(i-c_j) 转移过来，再算上枚举的这枚硬币数量 1...
0 点赞 评论 收藏
分享
2021-07-21 22:13
门头沟学院 Java
记录暑假java后端深度底层学习计划
基础知识我把他分为两大部分:  1.后端通用基础知识： （1）计算机网络  （后端面试考查的重中之重，IP/TCP/UDP/HTTP相关协议等）      推荐书籍：《计算机网络，谢希仁第五版》      第4章到第7章网络安全必学，网络层与应用层，http协议是重中之重）        推荐深入学习书籍：《自顶向下计算机网络》，《图解HTTP》（把HTTP通过图讲得透彻）） （2）数据库           强烈推荐:《mysql技术内幕++InnoDB存储引擎》!!!《Redis设计与实现(第二版)》  第5章索引与算法，第6章锁，第7章事务是必须要反复学习阅读的重点章节） ...
0 点赞 评论 收藏
分享
关注他的用户也关注了：
牛客网
牛客企业服务