网站设计报价,做app网站公司名称,网站建设类的手机软件,phpmysql网站开发技术项目式教程####【题目描述】
给定一个包含大写字母和小写字母的字符串#xff0c;找到通过这些字母构造成的最长的回文串。在构造过程中#xff0c;请注意区分大小写。比如 Aa 不能当做一个回文字符串。注意:
假设字符串的长度不会超过 1010。示例 1:输入:
abccccdd…####【题目描述】
给定一个包含大写字母和小写字母的字符串找到通过这些字母构造成的最长的回文串。在构造过程中请注意区分大小写。比如 Aa 不能当做一个回文字符串。注意:
假设字符串的长度不会超过 1010。示例 1:输入:
abccccdd输出:
7解释: 我们可以构造的最长的回文串是dccaccd, 它的长度是 7。
贪心
class Solution {public int longestPalindrome(String s) {int[] count new int[128];for (char c: s.toCharArray())count[c];int ans 0;for (int v: count) {ans v / 2 * 2;if (v % 2 1 ans % 2 0)ans;}return ans;}
}int数组实现
class Solution {public int longestPalindrome(String s) {int[] cnt new int[58];for (char c : s.toCharArray()) {cnt[c - A] 1;}int ans 0;for (int x: cnt) {// 字符出现的次数最多用偶数次。
//如果 x 是奇数x 1 的结果就是1偶数就是0实现了偶数不变、奇数减1的逻辑
// (x 1) 1 先右移一位去掉最末位的0或1再左移一位也实现了偶数不变、奇数减1的逻辑。ans x - (x 1);}// 如果最终的长度小于原字符串的长度说明里面某个字符出现了奇数次那么那个字符可以放在回文串的中间所以额外再加一。return ans s.length() ? ans 1 : ans; }
}Java8的流式风格
class Solution {public int longestPalindrome(String s) {
//s.chars()的返回值是一个 IntStream就是Int的流.boxed()会装箱返回StreamInteger.collect()是聚合的算子Collectors.toMap的三个参数分别是 keyMappervalueMapper 和 mergeFunction。分别表示聚合出来的 Map 的 key 是什么value 是什么如果遇到key相同的怎么合并值。
//MapInteger, Integer count s.chars().boxed().collect(Collectors.toMap(k - k, v - 1, Integer::sum));
// counter.values() 返回的是map值的集合CollectionInteger先用.stream()转成流以后利用mapToInt 转成 IntStream因为 IntStream 是支持 sum 算子的通过sum算子进行求和。int ans count.values().stream().mapToInt(i - i - (i 1)).sum();return ans s.length() ? ans 1 : ans;}
}Hashmap
class Solution {public int longestPalindrome(String s) {if (s null) return 0;MapCharacter, Integer map new HashMap();for (int i 0; i s.length(); i){if (map.containsKey(s.charAt(i))){map.replace(s.charAt(i), map.get(s.charAt(i)) 1);} else {map.put(s.charAt(i), 1);}}int result 0;for (Map.EntryCharacter, Integer entry : map.entrySet()){if (entry.getValue() % 2 0) {result entry.getValue();} else {result entry.getValue() - 1;}}if (result s.length()) result;return result;}
}####【总结】
取模运算转化正数
取模是一个消耗较大的操作因此大多数语言的编译器比如C都对模运算进行了优化Java中是不存在无符号整型的数字是用补码来表示的最高位是符号位0表示正数1表示负数
//正数能优化 负数不能优化
int a -3 % 2; // -1
int b -3 1; // 1x 87;
x % 2 x (2 - 1) 1010111 1 1 1;
x % 4 x (4 - 1) 1010111 11 11 3;
x % 8 x (8 - 1) 1010111 111 111 7;
x % 16 x (16 - 1) 1010111 1111 111 7;
x % 32 x (32 - 1) 1010111 11111 10111 2一题多解多思考不要总想遍历否则很难进步
资料参考整理来自https://mp.weixin.qq.com/s/HtDYSfaikwHozUrksU0A1w
