算法奇妙屋(三十八)-贪心算法学习之路 5
文章目录
- 一. 力扣 [409. 最长回文串](https://leetcode.cn/problems/longest-palindrome/description/)
- 1. 题目解析
- 2. 算法原理
- 3. 代码
- 二. 力扣 [942. 增减字符串匹配](https://leetcode.cn/problems/di-string-match/description/)
- 1. 题目解析
- 2. 算法原理
一. 力扣409. 最长回文串
1. 题目解析
给定的字符串s, 使用s中的字符, 来构建最长的回文串, 这里字符不必全部使用
2. 算法原理
这里有两个小技巧👇
1. 这里我们可以使用当前字符个数m / 2 后再✖️2, 这样无论m奇偶, 可以得到偶数的长度
2. 用最后ret长度与原长度比较, 来判断是否有奇数字符
3. 代码
使用哈希表
classSolution{publicintlongestPalindrome(Strings){HashMap<Character,Integer>hash=newHashMap<>();intn=s.length(),ret=0;for(inti=0;i<n;i++){charch=s.charAt(i);hash.put(ch,hash.getOrDefault(ch,0)+1);}for(Map.Entry<Character,Integer>entry:hash.entrySet()){ret+=entry.getValue()/2*2;}returnret==n?ret:ret+1;}}使用数组模拟哈希表, 效率更高, 且空间利用率更低
classSolution{publicintlongestPalindrome(Strings){int[]hash=newint[127];intn=s.length(),ret=0;for(inti=0;i<n;i++){hash[s.charAt(i)]++;}for(intx:hash){ret+=x/2*2;}returnret==n?ret:ret+1;}}二. 力扣942. 增减字符串匹配
1. 题目解析
这道题理解题意很重要, 要注意是0到n, 总共n+1个数
2. 算法原理
升序时, 当前位置选最小值, 那么后一个位置不论选什么必定都大于该值
降序时, 当前位置选最大值, 那么后一个位置不论选什么必定都小于该值