深圳华强北做网站,新闻联播俄罗斯与乌克兰,如何弄一个自己的公众号,psd wordpress 模板怎么用【题解】—— 每日一道题目栏 上接#xff1a;【题解】—— LeetCode一周小结1
8.回旋镖的数量
题目链接#xff1a;447. 回旋镖的数量
给定平面上 n 对 互不相同 的点 points #xff0c;其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 #xff0c;其…
【题解】—— 每日一道题目栏 上接【题解】—— LeetCode一周小结1
8.回旋镖的数量
题目链接447. 回旋镖的数量
给定平面上 n 对 互不相同 的点 points 其中 points[i] [xi, yi] 。回旋镖 是由点 (i, j, k) 表示的元组 其中 i 和 j 之间的距离和 i 和 k 之间的欧式距离相等需要考虑元组的顺序。
返回平面上所有回旋镖的数量。
示例 1 输入points [[0,0],[1,0],[2,0]] 输出2 解释两个回旋镖为 [[1,0],[0,0],[2,0]] 和 [[1,0],[2,0],[0,0]] 示例 2 输入points [[1,1],[2,2],[3,3]] 输出2 示例 3 输入points [[1,1]] 输出0 提示 n points.length 1 n 500 points[i].length 2 -104 xi, yi 104 所有点都 互不相同 题解 方法枚举 计数 哈希表 可以枚举 points 中的每个点作为回旋镖的点 i然后用一个哈希表 cnt记录其他点到 i 的距离出现的次数。 如果有 x 个点到 i的距离相等那么我们可以任选其中 2 个点作为回旋镖的 j 和 k方案数为 Ax2x(x−1)。因此我们对哈希表中的每个值 x都计算并累加 Ax2 就可以得到满足题目要求的回旋镖数量之和。 ps距离那里用平方比较就可以直接用整数比避免了小数带来的误差。
class Solution {public int numberOfBoomerangs(int[][] points) {int ans 0; // 初始化结果为0for (int[] p1 : points) { // 遍历所有点MapInteger, Integer cnt new HashMap(); // 创建一个哈希表用于存储距离的计数for (int[] p2 : points) { // 再次遍历所有点// 计算两点之间的距离的平方int d (p1[0] - p2[0]) * (p1[0] - p2[0]) (p1[1] - p2[1]) * (p1[1] - p2[1]); cnt.merge(d, 1, Integer::sum); // 将距离的平方作为键出现次数作为值存入哈希表}for (int x : cnt.values()) { // 遍历哈希表中的所有值ans x * (x - 1); // 计算每个距离的平方出现的次数的组合数并累加到结果中}}return ans; // 返回结果}
} 9.字符串中的额外字符
题目链接2707. 字符串中的额外字符
给你一个下标从 0 开始的字符串 s 和一个单词字典 dictionary 。你需要将 s 分割成若干个 互不重叠 的子字符串每个子字符串都在 dictionary 中出现过。s 中可能会有一些 额外的字符 不在任何子字符串中。
请你采取最优策略分割 s 使剩下的字符 最少 。
示例 1 输入s “leetscode”, dictionary [“leet”,“code”,“leetcode”] 输出1 解释将 s 分成两个子字符串下标从 0 到 3 的 “leet” 和下标从 5 到 8 的 “code” 。只有 1个字符没有使用s下标为 4所以我们返回 1 。 示例 2 输入s “sayhelloworld”, dictionary [“hello”,“world”] 输出3 解释将 s 分成两个子字符串下标从 3 到 7 的 “hello” 和下标从 8 到 12 的 “world” 。下标为 0 1 和 2 的字符没有使用say所以我们返回 3 。 提示 1 s.length 50 1 dictionary.length 50 1 dictionary[i].length 50 dictionary[i] 和 s 只包含小写英文字母。 dictionary 中的单词互不相同。 题解 学习原来还可以这样
方法一哈希表 动态规划 我们可以用一个哈希表 ss 记录字段中的所有单词方便我们快速判断一个字符串是否在字典中。 接下来我们定义 f[i]表示字符串 s 的前 i 个字符的最小额外字符数初始时 f[0]0。 当 i≥1 时第 i 个字符 s[i−1]可以作为一个额外字符此时 f[i]f[i−1]1如果在 j∈[0,i−1]中存在一个下标 j使得 s[j…i)在哈希表 ss 中那么我们可以将 s[j…i) 作为一个单词此时 f[i]f[j]。 综上我们可以得到状态转移方程 f[i]min{f[i−1]1,minj∈[0,i−1]f[j]} 其中 i≥1而 j∈[0,i−1] 且 s[j…i)在哈希表 ss 中。 最终答案为 f[n]。
class Solution {public int minExtraChar(String s, String[] dictionary) {// 创建一个HashSet用于存储字典中的字符串SetString ss new HashSet();for (String w : dictionary) {ss.add(w);}// 获取字符串s的长度int n s.length();// 创建一个长度为n1的整型数组f用于存储动态规划的结果int[] f new int[n 1];// 初始化f[0]为0f[0] 0;// 遍历字符串s的每一个字符for (int i 1; i n; i) {// 将f[i-1]1赋值给f[i]f[i] f[i - 1] 1;// 遍历字符串s的前i个字符for (int j 0; j i; j) {// 如果字典中包含从j到i的子串则更新f[i]的值if (ss.contains(s.substring(j, i))) {f[i] Math.min(f[i], f[j]);}}}// 返回f[n]即最小额外字符数return f[n];}
} 时间复杂度 O(n3L)空间复杂度 O(nL)。其中 n 是字符串 s 的长度而 L 是字典中所有单词的长度之和。
方法二字典树 动态规划 (确实没想到字典树倒序) 我们可以借助字典树来优化方法一的时间复杂度。 具体地我们首先将字典中的每个单词逆序插入到字典树 rootrootroot 中然后我们定义 f[i]f[i]f[i] 表示字符串 sss 的前 iii 个字符的最小额外字符数初始时 f[0]0f[0] 0f[0]0。 当 i≥1 时第 i 个字符 s[i−1]可以作为一个额外字符此时 f[i]f[i−1]1我们也可以在 [0…i−1] 的范围内逆序枚举下标 j判断 s[j…i)是否在字典树 root 中如果存在那么我们可以将 s[j…i) 作为一个单词此时 f[i]f[j]。
class Node {// 定义一个长度为26的Node数组用于存储子节点Node[] children new Node[26];// 标记当前节点是否为单词结尾boolean isEnd;
}class Solution {public int minExtraChar(String s, String[] dictionary) {// 创建根节点Node root new Node();// 遍历字典中的每个单词for (String w : dictionary) {Node node root;// 从单词的最后一个字符开始遍历for (int k w.length() - 1; k 0; --k) {// 计算字符在数组中的索引int i w.charAt(k) - a;// 如果当前字符对应的子节点不存在则创建一个新的子节点if (node.children[i] null) {node.children[i] new Node();}// 移动到下一个子节点node node.children[i];}// 标记当前单词的最后一个字符对应的子节点为单词结尾node.isEnd true;}// 获取字符串的长度int n s.length();// 创建一个长度为n1的整数数组用于存储动态规划的结果int[] f new int[n 1];// 初始化动态规划数组for (int i 1; i n; i) {f[i] f[i - 1] 1;Node node root;// 从字符串的倒数第二个字符开始遍历for (int j i - 1; j 0; --j) {// 移动到下一个子节点node node.children[s.charAt(j) - a];// 如果当前子节点不存在则跳出循环if (node null) {break;}// 如果当前子节点表示一个单词结尾并且从当前位置到字符串开头的子串长度小于已知的最小额外字符数则更新最小额外字符数if (node.isEnd f[j] f[i]) {f[i] f[j];}}}// 返回最小额外字符数return f[n];}
} 时间复杂度 O(n2 L)空间复杂度 O(nL×∣Σ∣)。其中 n 是字符串 s 的长度而 L 是字典中所有单词的长度之和另外 ∣Σ∣ 是字符集的大小本题中字符集为小写英文字母因此 ∣Σ∣26。 10.删除子串后的字符串最小长度
题目链接2696. 删除子串后的字符串最小长度 类似题目20. 有效的括号
给你一个仅由 大写 英文字符组成的字符串 s 。
你可以对此字符串执行一些操作在每一步操作中你可以从 s 中删除 任一个 “AB” 或 “CD” 子字符串。
通过执行操作删除所有 “AB” 和 “CD” 子串返回可获得的最终字符串的 最小 可能长度。
注意删除子串后重新连接出的字符串可能会产生新的 “AB” 或 “CD” 子串。
示例 1 输入s “ABFCACDB” 输出2 解释你可以执行下述操作 从 “ABFCACDB” 中删除子串 “AB”得到 s “FCACDB” 。 从 “FCACDB” 中删除子串 “CD”得到 s “FCAB” 。 从 “FCAB” 中删除子串 “AB”得到 s “FC” 。 最终字符串的长度为 2 。 可以证明 2 是可获得的最小长度。 示例 2 输入s “ACBBD” 输出5 解释无法执行操作字符串长度不变。 提示 1 s.length 100 s 仅由大写英文字母组成 题解 方法栈 用栈来做消消乐遍历s串如果栈不为空且只要栈顶元素是A当前遍历到的元素是B或者栈顶元素是C当前遍历到的元素是D就进行弹栈操作否则压栈。最后栈的大小就是删除子串后的字符串最小长度。 ps可以在栈中预先放入一个空字符这样就不需要在遍历字符串时判断栈是否为空了最后返回栈的大小减一即可。
class Solution {public int minLength(String s) {DequeCharacter ans new ArrayDeque();ans.push( );for (char c : s.toCharArray()) {if ((c B ans.peek() A) || (c D ans.peek() C)) {ans.pop();} else {ans.push(c);}}return ans.size() - 1;}
}
方法:数组模拟栈 类似题目20. 有效的括号 题目中可以删除子串 AB 或 CD并且子串删除后可能形成新的子串。 我们可以将 A 和 C 看成左括号B 和 D看成右括号。当遇到 B 和 D 时我们就要看之前有没有匹配的 A 和 C。
因此我们可以使用栈来存储待匹配的字符:
如果当前字符为 B( D )就看栈顶元素是否为 A ( C )。如果是匹配成功将栈顶元素弹出。如果不是匹配失败当前字符也要入栈阻断匹配。如果当前字符为其他字符入栈等待匹配阻断匹配。 ps通过栈的能够及时将可以构成子串的字符移除栈内留下的一定是待匹配的字符A/C或者是不可匹配的字符非ABCD字符阻断B和AC和D的匹配
class Solution {public int minLength(String s) {int n s.length();char[] st new char[n]; // 利用数组模拟栈int top -1; // 栈顶索引初始为-1表示空栈for(int i 0; i n; i){char ch s.charAt(i);if(top ! -1 (ch B st[top] A || ch D st[top] C)){// 栈不为空且当前字符与栈顶字符匹配成功弹出栈顶字符【即栈顶指针前移一位】top--;}else{st[top] ch; // 入栈等待匹配【相当于栈顶指针先后移一位指向新元素要加入的位置】}}return top 1; // 栈内剩下的字符个数即为删除子串后的字符数}
}11.构造有效字符串的最少插入数
题目链接2645. 构造有效字符串的最少插入数
给你一个字符串 word 你可以向其中任何位置插入 “a”、“b” 或 “c” 任意次返回使 word 有效 需要插入的最少字母数。
如果字符串可以由 “abc” 串联多次得到则认为该字符串 有效 。
示例 1 输入word “b” 输出2 解释在 “b” 之前插入 “a” 在 “b” 之后插入 “c” 可以得到有效字符串 “abc” 。 示例 2 输入word “aaa” 输出6 解释在每个 “a” 之后依次插入 “b” 和 “c” 可以得到有效字符串 “abcabcabc” 。 示例 3 输入word “abc” 输出0 解释word 已经是有效字符串不需要进行修改。 提示 1 word.length 50 word 仅由字母 “a”、“b” 和 “c” 组成。 题解 方法一考虑相邻字母 我们将 word 简记为 s。 对于两个相邻字符 x 和 yx 在 y 左侧使 s 有效的话需要插入y−x−1个字母。 考虑到这y−x−1可能是个负数可以通过如下技巧转换在 [0,2] 内(y−x−13) mod 3
例如 xa,yc则有 (c−a2) mod 31意思是需要补一个字母 ‘b’。例如 xc,ya则有 (a−c2) mod 30无需补字母。 最后补齐开头的 s[0]−a和结尾的 c−s[n−1]。这俩可以合并为 s[0]−s[n−1]2。
class Solution {public int addMinimum(String word) {char[] s word.toCharArray();int ans s[0] 2 - s[s.length - 1];for (int i 1; i s.length; i) {ans (s[i] 2 - s[i - 1]) % 3;}return ans;}
}方法二考虑 abc 的个数 假设答案由 t个 ‘abc’ 组成那么需要插入的字符个数为 3t−n。(n为s的长度 对于两个相邻字符 x 和 yx 在 y 左侧
如果 xy那么 x 和 y 可以在同一个 ‘abc’ 内否则一定不在。t不变如果 x≥y那么 x 和 y 一定不在同一个 ‘abc’内。t 例如 s‘caa’中的 s[0]≥s[1],s[1]≥s[2]所以需要 t3 个 ‘abc’即 ‘abcabcabc’。 所以综上所述 t 就是 x≥y 的时候次数加一。
class Solution {public int addMinimum(String word) {char[] s word.toCharArray();int t 1;for (int i 1; i s.length; i) {// 两个相邻字符 x 和 yx 在 y 左侧if (s[i - 1] s[i]) { // x≥y的情况必须生成一个新的 abc t;}}return t * 3 - s.length;}
}12.统计出现过一次的公共字符串
题目链接2085. 统计出现过一次的公共字符串
给你两个字符串数组 words1 和 words2 请你返回在两个字符串数组中 都恰好出现一次 的字符串的数目。
示例 1 输入words1 [“leetcode”,“is”,“amazing”,“as”,“is”], words2 [“amazing”,“leetcode”,“is”] 输出2 解释 “leetcode” 在两个数组中都恰好出现一次计入答案。“amazing” 在两个数组中都恰好出现一次计入答案。“is” 在两个数组中都出现过但在 words1 中出现了 2 次不计入答案。“as” 在 words1 中出现了一次但是在 words2 中没有出现过不计入答案。 所以有 2 个字符串在两个数组中都恰好出现了一次。 示例 2 输入words1 [“b”,“bb”,“bbb”], words2 [“a”,“aa”,“aaa”] 输出0 解释没有字符串在两个数组中都恰好出现一次。 示例 3 输入words1 [“a”,“ab”], words2 [“a”,“a”,“a”,“ab”] 输出1 解释唯一在两个数组中都出现一次的字符串是 “ab” 。 提示 1 words1.length, words2.length 1000 1 words1[i].length, words2[j].length 30 words1[i] 和 words2[j] 都只包含小写英文字母。 题解 要找到在两个字符串数组中 都恰好出现一次 的字符串的数目分三步走
利用哈希表 counts1 统计第一个字符串数组 words1 每个字符串出现的次数。利用哈希表 counts2统计第二个字符串数组 words2 每个字符串出现的次数。从哈希表 counts1 中找到次数为 1 的字符串并且这些字符串在 counts2 次数也为1。
class Solution {public int countWords(String[] words1, String[] words2) {// 统计words1中每个字符出现的次数MapString, Integer counts1 new HashMap(); for(String w1: words1){counts1.put(w1, counts1.getOrDefault(w1, 0) 1);}// 统计words2中每个字符出现的次数MapString, Integer counts2 new HashMap();for(String w2: words2){counts2.put(w2, counts2.getOrDefault(w2, 0) 1);}// 统计同时在words1和words2出现且出现次数均为1得到字符串个数int ans 0;for(String word: counts1.keySet()){// 遍历counts1找到在words1出现一次同时在words2出现一次// if(counts1.getOrDefault(word, 0) 1 counts2.getOrDefault(word, 0) 1)if(counts1.get(word) 1 counts2.getOrDefault(word, 0) 1)ans 1;}return ans;}
}13.构造限制重复的字符串
题目链接2182. 构造限制重复的字符串
给你一个字符串 s 和一个整数 repeatLimit 用 s 中的字符构造一个新字符串 repeatLimitedString 使任何字母 连续 出现的次数都不超过 repeatLimit 次。你不必使用 s 中的全部字符。
返回 字典序最大的 repeatLimitedString 。
如果在字符串 a 和 b 不同的第一个位置字符串 a 中的字母在字母表中出现时间比字符串 b 对应的字母晚则认为字符串 a 比字符串 b 字典序更大 。如果字符串中前 min(a.length, b.length) 个字符都相同那么较长的字符串字典序更大。
示例 1 输入s “cczazcc”, repeatLimit 3 输出“zzcccac” 解释使用 s 中的所有字符来构造 repeatLimitedString “zzcccac”。 字母 ‘a’ 连续出现至多 1 次。 字母 ‘c’ 连续出现至多 3 次。 字母 ‘z’ 连续出现至多 2 次。 因此没有字母连续出现超过 repeatLimit 次字符串是一个有效的repeatLimitedString 。 该字符串是字典序最大的 repeatLimitedString 所以返回 “zzcccac” 。 注意尽管 “zzcccca” 字典序更大但字母 ‘c’ 连续出现超过 3 次所以它不是一个有效的 repeatLimitedString 。 示例 2 输入s “aababab”, repeatLimit 2 输出“bbabaa” 解释 使用 s 中的一些字符来构造 repeatLimitedString “bbabaa”。 字母 ‘a’ 连续出现至多 2 次。 字母 ‘b’ 连续出现至多 2 次。 因此没有字母连续出现超过 repeatLimit 次字符串是一个有效的 repeatLimitedString 。 该字符串是字典序最大的 repeatLimitedString 所以返回 “bbabaa” 。 注意尽管 “bbabaaa” 字典序更大但字母 ‘a’ 连续出现超过 2 次所以它不是一个有效的 repeatLimitedString 。 提示 1 repeatLimit s.length 105 s 由小写英文字母组成 题解 根据题意我们要将字符串s重新排列成字典序最大的字符串并且任何字符连续出现的次数都不能超过规定的repeatLimitedString次。并且单靠字典序无法比较字符串大小时才会去比较字符串长度。 那么我们就能知道更大的字典序是比字符串的长度更重要的 那么我们肯定要将字符串中字典序最大的字母放在最前如果连续次数达到了repeatLimitedString次那么我们就要在其后面插入一个稍小于当前字母字典序的字母。 所以我们可以用一个长度为26的int数组str存放字符串s,数组下标0-25分别代表a-z数组值为当前字母出现的次数。 倒序遍历数组str便可得到字典序降序的字母。将其依此拼成字符串同时使用数组nums记录当前字母出现的次数如果次数等于repeatLimitedString就寻找比当前数组下标稍小的位置也就是字典序稍小的字母插入到字符串末尾并清空出现次数。
class Solution {public String repeatLimitedString(String s, int repeatLimit) {//str用来记录字符串s每个字母出现的次数int[] str new int[26];for (int i 0;i s.length();i ) {str[s.charAt(i) - a] ;}//用来记录for循环遍历开始的位置int temp 25;//nums用来记录字母的连续次数(这里可以优化,一个整型就可以解决问题)int[] nums new int[26];//使用StringBuilder对字符串进行操作效率更高(我记得是)StringBuilder sb new StringBuilder();while (temp 0) {//这里while套for纯脱裤子放屁了。for循环末尾有个breakfor (int i temp;i 0;i --) {//所有字母都用完了if (i 0 str[i] 0) {temp -1;break;}//避免重复循环无意义区域if (str[i] 0) {//这里就是 如果temp --;continue;}//在末尾添加字符串sb.append((char)(i a));//连续字母个数1nums[i] ;//当前字母剩余可用个数-1str[i] --;//达到设定的次数并且此字符还有没插入字符串的有剩余if (nums[i] repeatLimit str[i] 0) {//没有能插入的字母了因为没有比a字典序更小的了if (i 0) {temp -2;break;}//寻找比i较小的下标较小的字典序for (int j i - 1;j 0;j --) {//没有剩余字母了a-z都没有剩余了if (j 0 str[j] 0) {temp -1;break;}//确保当前字母有剩余(我们总不能插入一个没出现过的字母或者用完了的字母吧)if (str[j] ! 0) {sb.append((char)(j a));nums[i] 0;str[j] --;break;}}}break;}}return sb.toString();}
}14.删除排序链表中的重复元素
题目链接83. 删除排序链表中的重复元素 给定一个已排序的链表的头 head 删除所有重复的元素使每个元素只出现一次 。返回 已排序的链表 。
示例 1 输入head [1,1,2] 输出[1,2] 示例 2 输入head [1,1,2,3,3] 输出[1,2,3] 提示 链表中节点数目在范围 [0, 300] 内 -100 Node.val 100 题目数据保证链表已经按升序 排列 题解 方法链表 指定 cur 指针指向头部 head
当 cur 和 cur.next 的存在为循环结束条件当二者有一个不存在时说明链表没有去重复的必要了当 cur.val 和 cur.next.val 相等时说明需要去重则将 cur 的下一个指针指向下一个的下一个这样就能达到去重复的效果 如果不相等则 cur 移动到下一个位置继续循环
/*** Definition for singly-linked list.* public class ListNode {* int val;* ListNode next;* ListNode() {}* ListNode(int val) { this.val val; }* ListNode(int val, ListNode next) { this.val val; this.next next; }* }*/
class Solution {public ListNode deleteDuplicates(ListNode head) { ListNode cur head;while(cur ! null cur.next ! null) {//因为链表可能给的[] 所以cur!null的判定也要给上~if(cur.val cur.next.val) {//因为是升序排列 所以也只可能是挨着的二位相同cur.next cur.next.next;//删除重复的cur.next}else {cur cur.next;//cur继续前移}}return head;//返回结果链表}
}下接【题解】—— LeetCode一周小结3
