目录
最⻓回⽂串（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定⼀个包含⼤写字⺟和⼩写字⺟的字符串 s ，返回通过这些字⺟构造成的最⻓的回⽂串。在构造过程中，请注意区分⼤⼩写。⽐如 "Aa" 不能当做⼀个回⽂字符串。
⽰例1:
输⼊:s="abccccdd"
输出:7
解释:
我们可以构造的最⻓的回⽂串是"dccaccd",它的⻓度是7。⽰例2:
输⼊:s="a"
输出:1
⽰例3：
输⼊:s="aaaaaccc"
输出:7
提⽰:
◦ 1 <= s.length <= 2000
◦ s 只由⼩写和/或⼤写英⽂字⺟组成
讲解算法原理
解法（贪⼼）：
贪⼼策略：
⽤尽可能多的字符去构造回⽂串：
a. 如果字符出现偶数个，那么全部都可以⽤来构造回⽂串；b. 如果字符出现奇数个，减去⼀个之后，剩下的字符能够全部⽤来构造回⽂串；c. 最后再判断⼀下，如果有字符出现奇数个，就把它单独拿出来放在中间。
编写代码
c++算法代码：
class Solution
{
public:
int longestPalindrome(string s)
{
// 1. 计数 - ⽤数组模拟哈希表
int hash[127] = { 0 };
for(char ch : s) hash[ch]++;
// 2. 统计结果
int ret = 0;
for(int x : hash)
{
ret += x / 2 * 2;
}
return ret < s.size() ? ret + 1 : ret;
}
};java算法代码：
class Solution
{
public int longestPalindrome(String s)
{
// 1. 计数 - ⽤数组模拟哈希表
int[] hash = new int[127];
for(int i = 0; i < s.length(); i++)
{
hash[s.charAt(i)]++;
}
// 2. 统计结果
int ret = 0;
for(int x : hash)
{
ret += x / 2 * 2;
}
return ret < s.length() ? ret + 1 : ret;
}
}增减字符串匹配（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
由范围 [0,n] 内所有整数组成的 n + 1 个整数的排列序列可以表⽰为⻓度为 n 的字符串 s ，其中:
• 如果 perm[i] < perm[i + 1] ，那么 s[i] == 'I'
• 如果 perm[i] > perm[i + 1] ，那么 s[i] == 'D'
给定⼀个字符串 s ，重构排列 perm 并返回它。如果有多个有效排列perm，则返回其中任何⼀个。
⽰例1：
输⼊：s="IDID"
输出：[0,4,1,3,2]
⽰例2：
输⼊：s="III"
输出：[0,1,2,3]
⽰例3：
输⼊：s="DDI"
输出：[3,2,0,1]
提⽰：
◦ 1 <= s.length <= 10(5)
◦ s 只包含字符 "I" 或 "D"
讲解算法原理
解法（贪⼼）：
贪⼼策略：
a. 当遇到 'I' 的时候，为了让下⼀个上升的数可选择的「范围更多」，当前选择「最⼩」的那
个数；
b. 当遇到 'D' 的时候，为了让下⼀个下降的数可选择的「范围更多」，选择当前「最⼤」的那
个数。
编写代码
c++算法代码：
class Solution
{
public:
vector<int> diStringMatch(string s)
{
int left = 0, right = s.size(); // ⽤ left，right 标记最⼩值和最⼤值 vector<int> ret;
for(auto ch : s)
{
if(ch == 'I') ret.push_back(left++);
else ret.push_back(right--);
}
ret.push_back(left); // 把最后⼀个数放进去
return ret;
}
};java算法代码：
class Solution
{
public int[] diStringMatch(String s)
{
int n = s.length();
int left = 0, right = n; // ⽤ left，right 标记最⼩值和最⼤值 int[] ret = new int[n + 1];
for(int i = 0; i < n; i++)
{
if(s.charAt(i) == 'I')
{
ret[i] = left++;
}
else
{
ret[i] = right--;
}
}
ret[n] = left; // 把最后⼀个数放进去
return ret;
}
}