力扣中级算法(一)【数组和字符串】

本文中的题目均来自力扣,代码默认以C#实现,伪代码仅用来帮助描述,不严格遵循某种语言的语法。

  • 可前往GitHub下载Markdown 笔记

数组和字符串问题在面试中出现频率很高,你极有可能在面试中遇到。

我们推荐以下题目:字母异位词分组,无重复字符的最长子串 和 最长回文子串。



49. 字母异位词分组

难度:中等

给定一个字符串数组,将字母异位词组合在一起。字母异位词指字母相同,但排列不同的字符串。

示例:

输入: ["eat", "tea", "tan", "ate", "nat", "bat"]
输出:
[
 ["ate","eat","tea"],
 ["nat","tan"],
 ["bat"]
]

说明:

  • 所有输入均为小写字母。
  • 不考虑答案输出的顺序。

解题思路

  • 朴素的想法是,遍历整个字符串数组,把异位词放到同一个列表中,那么如何判断异位词呢?
  • 我们可以重新定义每个单词的哈希规则,让异位词映射到同一个哈希值上,这有一些困难,我们也可以对每个单词按照统一规则排序,那么异位词在排序后必然是相同的。
  • 以排序后的单词作为哈希表的键,不失为一种方法。

方法一:哈希表

public IList<IList<string>> GroupAnagrams(string[] strs)
{
    var dict = new Dictionary<string, IList<string>>();
    foreach (var item in strs)
    {
        var key = new string(item.OrderBy(x=>x).ToArray());
        if (dict.ContainsKey(key))
        {
            dict[key].Add(item);
        }
        else
        {
            dict[key] = new List<string> { item }; 
        }
    }
    
    return dict.Values.ToList();
}

3. 无重复字符的最长子串

难度:中等

给定一个字符串,请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。

示例 2:

输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。

示例 3:

输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
     请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。

解题思路

  • 朴素的想法是,遍历整个字符串,从每个字符开始,向右进行试探,直到找到第一个重复的字符。

  • 然后,返回所有可能的无重复字符子串中的最大的一个

方法一:暴力枚举

public int LengthOfLongestSubstring(string s)
{
    var set = new HashSet<char>();
    var res = 0;
    
    for (int i = 0; i < s.Length; i++)
    {
        for (int j = i; j < s.Length; j++)
            if (!set.Add(s[j])) break;
        
        res = Math.Max(set.Count, res);
        set.Clear();
    }
    
    return res;
}
  • 在上面的方法中,我们每次探测到一个无重复子串的时候都重新回到 i + 1 的位置,再次进行试探。
  • 稍加思考,我们就会发现,这样的操作是完全没有必要的,原因如下:
    • 如果第i个字符不是重复的,那么再次探测的结果一定小于刚刚探测的结果。
    • 如果第i个字符是重复的,那么再次探测的结果才可能大于刚刚探测的结果。
  • 所以,我们完全可以避免一部分重复的计算,这也是我们优化算法一直以来的思路。
  • 我们可以直接移动多次i指针,直到与j指针指向的字符相同。

方法二:滑动窗口

public int LengthOfLongestSubstring(string s)
{
    var set = new HashSet<char>();
    var res = 0;
    for (int i = 0, j = 0; j < s.Length; i++)
    {
        while (j < s.Length && set.Add(s[j])) { j++; }

        res = Math.Max(set.Count, res);
        set.Remove(s[i]);
    }
    
    return res;
}

5. 最长回文子串

难度:中等

给定一个字符串 s,找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

示例 1:

输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。

示例 2:

输入: "cbbd"
输出: "bb"

解题思路

  • 朴素的想法是,穷举所有的可能,对于每一个子串,我们都判断一下它是不是回文串。

  • 显然,这并不是一个很好的办法,不过我们可以再次基础上看看有没有优化的空间。

    • 首先,我们可以从大到小的搜索子串,这样一旦找到某个符合条件的子串,我们就可以停止接下来的搜索,跳到下一层继续搜索。
    • 其次,我们可以判断一下要搜索的子串长度有没有超过当前解,如果没有超过,就说明不存在更优解,也没有必要搜索。

方法一:暴力枚举

public string LongestPalindrome(string s)
{
    var res = "";
    for (int i = 0, j = s.Length - 1; j - i + 1 > res.Length; i++) // 判断有无更优解
    {
        for (int k = j; k - i + 1 > res.Length; k--) // 一旦找到就停止了搜索
            if (IsP(i, k)) res = s.Substring(i, k - i + 1);
    }

    return res;
	// 判断是否为质数。
    bool IsP(int start, int end)
    {
        for (int i = start, j = end; i < j; i++, j--)
            if (!s[i].Equals(s[j])) return false;

        return true;
    }
}
  • 除了剪枝之外,我们能不能考虑别的优化方案呢?
  • 稍加思考,我们发现,在判断一个子串是否为回文串的过程中,我们存在大量的重复计算。
  • 我们不难得出这样的判断,如果一个字符串是回文串,那么去掉首尾两个字符,依然是回文串。例如:
ababa => bab => a 
  • 假如现在有一个字符串是这样的abcdefdcba,我们在用双指针判断回文串的时候,虽然abcd四个字符前后都相等,但ef两个字符并不相等,如果再次基础上,我们又扫描到了aabcdefdcbaa子串,这显然是一种不必要的重复计算。

  • 我们可以用DP[i][j]来记录i-j的子串是否是回文串,不难得出

    DP[i][j] = DP[i+1][j-1] and (s[i] == s[j])
    
    
  • 最后,考虑一下我们要从哪里开始填充我们的DP,长度为4的子串是根据长度为2的子串的情况得到的,长度为3的子串是根据长度为1的子串得到的。

  • 所以,我们应该让长度从小到大的填充DP,并且,对于长度1和长度2的子串,进行初值处理。

方法二:动态规划

public string LongestPalindrome(string s)
{
    var res = "";
    var dp = new bool[s.Length, s.Length]; // dp[i,j] 表示 i-j 的子串是否为回文串。

    for (int l = 0; l < s.Length; l++) // 从长度为1的子串开始填充
    {
        for (int i = 0; i + l < s.Length; i++)
        {
            var j = i + l;
            switch (l)
            {
                case 0:
                    dp[i, j] = true;
                    break;
                case 1:
                    dp[i, j] = s[i] == s[j];
                    break;
                default:
                    dp[i, j] = dp[i + 1, j - 1] && (s[i] == s[j]);
                    break;
            }

            if (dp[i, j] && (l + 1 > res.Length)) res = s.Substring(i, l + 1);
        }
    }

    return res;
}
内容来源于网络如有侵权请私信删除