网站模板源文件,网站产品标题怎么写,建设一个商城式网站可以吗,网站服务公司代买空间有无义务hello 大家好#xff0c;我是星恒 今天给大家带来的是hash#xff0c;思路有好几种#xff0c;需要注意的是这中简单的题目需要仔细看条件#xff0c;往往他们有对应题目的特殊的解法 题目#xff1a;leetcode 2744给你一个下标从 0 开始的数组 words #xff0c;数组中包… hello 大家好我是星恒 今天给大家带来的是hash思路有好几种需要注意的是这中简单的题目需要仔细看条件往往他们有对应题目的特殊的解法 题目leetcode 2744给你一个下标从 0 开始的数组 words 数组中包含 互不相同 的字符串。如果字符串 words[i] 与字符串 words[j] 满足以下条件我们称它们可以匹配
字符串 words[i] 等于 words[j] 的反转字符串。0 i j words.length
请你返回数组 words 中的 最大 匹配数目。注意每个字符串最多匹配一次。
示例 示例 1
输入words [cd,ac,dc,ca,zz]
输出2
解释在此示例中我们可以通过以下方式匹配 2 对字符串
- 我们将第 0 个字符串与第 2 个字符串匹配因为 word[0] 的反转字符串是 dc 并且等于 words[2]。
- 我们将第 1 个字符串与第 3 个字符串匹配因为 word[1] 的反转字符串是 ca 并且等于 words[3]。
可以证明最多匹配数目是 2 。示例 2
输入words [ab,ba,cc]
输出1
解释在此示例中我们可以通过以下方式匹配 1 对字符串
- 我们将第 0 个字符串与第 1 个字符串匹配因为 words[1] 的反转字符串 ab 与 words[0] 相等。
可以证明最多匹配数目是 1 。示例 3
输入words [aa,ab]
输出0
解释这个例子中无法匹配任何字符串。提示
1 words.length 50words[i].length 2words 包含的字符串互不相同。words[i] 只包含小写英文字母。
分析思路1
将字符串反转然后将字符串存入hash中反转字符串将反转后的字符串存入hash中如果存在就1如果反转后和之前一样就不1遍历hash如果hash值是2的数就是有反转串的人计数由于每对反转串都会被计数两次所以最后要除以2
思路2直接遍历如果相同就count 1如何避免多次计数只要第二次循环j从第一次循环i开始循环就可以了
思路3哈希表对于比较方便得到反转字符串的语言我们可以在哈希集合中存储字符串本身对于其它语言我们可以存储字符串的哈希值改为判断 words[i]\textit{words}[i]words[i] 的反转字符串的哈希值是否存在。哈希值需要保证不会冲突本题中字符串的长度为 222 并且只包含小写字母因此可以使用 100ab100a b100ab 作为哈希值其中 aaa 和 bbb 分别是两个字符的 ASCII\text{ASCII}ASCII 值。
题解我的题解
class Solution {public int maximumNumberOfStringPairs(String[] words) {MapString, Integer maps new HashMap();int count 0; for (int i 0; i words.length; i) {maps.put(words[i], 1);words[i] reverse(words[i]);}for (int i 0; i words.length; i) {if (!words[i].equals(reverse(words[i]))) {maps.put(words[i], maps.getOrDefault(words[i], 0) 1);}}for (Map.EntryString, Integer map: maps.entrySet()) {if (map.getValue() 2) {count;}}return count/2;}public String reverse(String s) {char[] arr s.toCharArray();int left 0, right s.length() - 1;while(left right) {char temp arr[left];arr[left] arr[right];arr[right] temp;left;right--;}return new String(arr);}
}知识点
getOrDefault()字符串反转转字符数组 - 双指针遍历交换 - 字符数组转为字符串Map遍历遍历项的类型Map.Entry字符串比较值大小 equals()
官方题解1
class Solution {public int maximumNumberOfStringPairs(String[] words) {int n words.length;int ans 0;for (int i 0; i n; i) {for (int j i 1; j n; j) {if (words[i].charAt(0) words[j].charAt(1) words[i].charAt(1) words[j].charAt(0)) {ans;}}}return ans;}
}官方题解2哈希
class Solution {public int maximumNumberOfStringPairs(String[] words) {int n words.length;int ans 0;SetInteger seen new HashSetInteger();for (int i 0; i n; i) {if (seen.contains(words[i].charAt(1) * 100 words[i].charAt(0))) {ans;}seen.add(words[i].charAt(0) * 100 words[i].charAt(1));}return ans;}
}
