工会教工之家网站建设,wordpress博客打开慢,武安市城乡建设局网站,建筑设计案例网站国企年终 今天刷到一个近期帖子:「中国建设银行#xff0c;这年终奖噶噶高!!!!」 先撇去具体内容不看#xff0c;能在自然年的 月初#xff0c;就把去年的奖金发了的企业#xff0c;首先值得一个点赞。 再细看内容#xff0c;年终奖是一个 字头的 位数。 由于国企通常没… 国企年终 今天刷到一个近期帖子:「中国建设银行这年终奖噶噶高!!!!」 先撇去具体内容不看能在自然年的 月初就把去年的奖金发了的企业首先值得一个点赞。 再细看内容年终奖是一个 字头的 位数。 由于国企通常没有类似「互联网动辄 个月以上作为年终奖」这样的说法因此这个奖金数即使去掉当月薪资直接除 然后对标互联网的到手月收入都不算是一个能够被嘲笑的数字。 所以我有点没看懂评论区 这是花式嘲笑还是花式羡慕呢 真的就简中网这个特有的调侃类发言我都不敢想象用这些数据训练出来的 AI到底能不能正常理解人类表达的意思。 看到最后大多都是类似上图的奇怪发言。 只有少数和楼主同是银行员工的网友在认真发言 这这没法评啊这 ... 回归主线。 建设银行的题单没有找到倒是找到一个农业银行的题单。 乍一眼看过去好像没有什么互联网公司的题单重简单题占比如此重。 那来一道多少沾边的「中国农业银行」面试题。 这也是该公司题单中唯三困难题中的第二道。 至于第一道题我们已经 讲过。是一道很有意思的用初中知识出成的算法题当时不少同学直呼「有思路但无从下手」。 今天一起来看看这第二题又怎么样。 题目描述 平台LeetCode 题号44 给定一个字符串 (s) 和一个字符模式 (p) 实现一个支持 ? 和 * 的通配符匹配。 ? 可以匹配任何单个字符。 * 可以匹配任意字符串包括空字符串。 两个字符串完全匹配才算匹配成功。 说明: s 可能为空且只包含从 a-z 的小写字母。 p 可能为空且只包含从 a-z 的小写字母以及字符 ? 和 *。 示例 1: 输入:s aap a输出: false解释: a 无法匹配 aa 整个字符串。 示例 2: 输入:s aap *输出: true解释: * 可以匹配任意字符串。 示例 3: 输入:s cbp ?a输出: false解释: ? 可以匹配 c, 但第二个 a 无法匹配 b。 示例 4: 输入:s adcebp *a*b输出: true解释: 第一个 * 可以匹配空字符串, 第二个 * 可以匹配字符串 dce. 示例 5: 输入:s acdcbp a*c?b输出: false 动态规划 整理一下题意对于字符串 p 而言有三种字符 普通字符需要和 s 中同一位置的字符完全匹配 ?能够匹配 s 中同一位置的任意字符 *能够匹配任意字符串 所以本题关键是分析当出现 * 这种字符时是匹配 0 个字符、还是 1 个字符、还是 2 个字符 ... 本题可以使用动态规划进行求解 状态定义f(i,j) 代表考虑 s 中以 i 为结尾的子串和 p 中的 j 为结尾的子串是否匹配。即最终我们要求的结果为 f[n][m] 。 状态转移也就是我们要考虑 f(i,j) 如何求得前面说到了 p 有三种字符所以这里的状态转移也要分三种情况讨论 p[j] 为普通字符匹配的条件是前面的字符匹配同时 s 中的第 i 个字符和 p 中的第 j 位相同。 即 f(i,j) f(i - 1, j - 1) s[i] p[j] 。 p[j] 为 .匹配的条件是前面的字符匹配s 中的第 i 个字符可以是任意字符。即 f(i,j) f(i - 1, j - 1) p[j] .。 p[j] 为 *可匹配任意长度的字符可以匹配 0 个字符、匹配 1 个字符、匹配 2 个字符 3.1. 当匹配为 0 个f(i,j) f(i, j - 1) 3.2. 当匹配为 1 个f(i,j) f(i - 1, j - 1) 3.3. 当匹配为 2 个f(i,j) f(i - 2, j - 1) ... 3.k. 当匹配为 k 个f(i,j) f(i - k, j - 1) 因此对于 p[j] * 的情况想要 f(i, j) true只需要其中一种情况为 true 即可。也就是状态之间是「或」的关系 这意味着我们要对 k 种情况进行枚举检查吗 其实并不用对于这类问题我们通常可以通过「代数」进简化将 i - 1 代入上述的式子 可以发现f[i - 1][j] 与 f[i][j] 中的 f[i][j - 1] 开始的后半部分是一样的因此有 PS. 其实类似的推导我在 10. 正则表达式匹配 也做过第 10 题的推导过程还涉及等差概念我十分推荐你去回顾一下。如果你能搞懂第 10 题整个过程这题其实就是小 Case。 编码细节 通过上述的推导过程你会发现设计不少的「回退检查」操作即遍历到 i 位要回头检查 i - 1 等因此我们可以将「哨兵技巧」应用到本题往两个字符串的头部插入哨兵 对于 p[j] . 和 p[j] 普通字符 的情况想要为 true其实有共同的条件 f[i - 1][j - 1] true因此可以合到一起来做 Java 代码 class Solution { public boolean isMatch(String s, String p) { int n s.length(), m p.length(); // 技巧往原字符头部插入空格这样得到 char 数组是从 1 开始而且可以使得 f[0][0] true可以将 true 这个结果滚动下去 s s; p p; char[] ss s.toCharArray(), pp p.toCharArray(); // f(i,j) 代表考虑 s 中的 1~i 字符和 p 中的 1~j 字符 是否匹配 boolean[][] f new boolean[n 1][m 1]; f[0][0] true; for (int i 0; i n; i) { for (int j 1; j m; j) { if (pp[j] *) { f[i][j] f[i][j - 1] || (i - 1 0 f[i - 1][j]); } else { f[i][j] i - 1 0 f[i - 1][j - 1] (ss[i] pp[j] || pp[j] ?); } } } return f[n][m]; }} C 代码 class Solution {public: bool isMatch(string s, string p) { int n s.length(), m p.length(); s s; p p; vectorvectorbool f(n 1, vectorbool(m 1, false)); f[0][0] true; for (int i 0; i n; i) { for (int j 1; j m; j) { if (p[j] *) { f[i][j] f[i][j - 1] || (i - 1 0 f[i - 1][j]); } else { f[i][j] i - 1 0 f[i - 1][j - 1] (s[i] p[j] || p[j] ?); } } } return f[n][m]; }}; Python 代码 class Solution: def isMatch(self, s: str, p: str) - bool: n, m len(s), len(p) s s p p f [[False] * (m 1) for _ in range(n 1)] f[0][0] True for i in range(n 1): for j in range(1, m 1): if p[j] *: f[i][j] f[i][j - 1] or (i - 1 0 and f[i - 1][j]) else: f[i][j] i - 1 0 and f[i - 1][j - 1] and (s[i] p[j] or p[j] ?) return f[n][m] TypeScript 代码 function isMatch(s: string, p: string): boolean { const n s.length, m p.length; s s; p p; const f new Array(n 1).fill(false).map(() new Array(m 1).fill(false)); f[0][0] true; for (let i 0; i n; i) { for (let j 1; j m; j) { if (p[j] *) { f[i][j] f[i][j - 1] || (i - 1 0 f[i - 1][j]); } else { f[i][j] i - 1 0 f[i - 1][j - 1] (s[i] p[j] || p[j] ?); } } } return f[n][m];}; 时间复杂度 n 表示 s 的长度 m 表示 p 的长度总共 个状态。复杂度为 空间复杂度使用了二维数组记录结果。复杂度为 再次强调动态规划本质上是枚举不重复的暴力枚举因此其复杂度很好分析有多少个状态就要被计算多少次复杂度就为多少。 我是宫水三叶每天都会分享算法题解并和大家聊聊近期的所见所闻。 欢迎关注明天见。 更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 本文由 mdnice 多平台发布
