0802学习

agile Posted on Aug 2 2023

面试回文 leetcode学习

-   最长回文子串-05-腾讯
给你一个字符串 s，找到 s 中最长的回文子串。
如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。
提示：
1 <= s.length <= 1000
s 仅由数字和英文字母组成

---

```C#
public string LongestPalindrome(string s)
{
    //设置窗口大小
    for (var i = s.Length - 1; i >= 1; i--)
    {
        //滑动窗口
        for (var j = 0; j < s.Length - i; j++)
        {
            var l = j;
            var r = j + i;
            while (l < r)
            {
                if (s[l] != s[r])
                {
                    break;
                }

l++;
                r--;
            }

if (l >= r)
            {
                return s.Substring(j, i + 1);
            }
        }
    }

return $"{s[0]}";
}

// 中心扩展算法
public string LongestPalindrome2(string s)
{
    if (s.Length <= 1)
    {
        return s;
    }

var start = 0;
    var end = 0;
    for (int i = 0; i < s.Length - 1; i++)
    {
        var l1 = __Expand(i, i, s);
        var l2 = __Expand(i, i + 1, s);
        var l = Math.Max(l1, l2);
        if (l > end - start)
        {
            start = i - (l - 1) / 2;
            end = i + l / 2;
        }
    }

return s.Substring(start, end - start + 1);
}

private int __Expand(int i, int j, string s)
{
    while (i >= 0 && j < s.Length && s[i] == s[j])
    {
        i--;
        j++;
    }

return j - i - 1;
}

//动态规划
//dp[i][j]=dp[i+1][j-1]&s[i]==s[j]
public string LongestPalindrome3(string s)
{
    var length = s.Length;
    if (length < 2)
    {
        return s;
    }

var dp = new bool[length][];
    for (int i = 0; i < length; i++)
    {
        dp[i] = new bool[length];
        dp[i][i] = true;
    }

if (dp[i][j] && j - i > temp)
            {
                temp = j - i;
                start = i;
                end = j;
            }
        }
    }

return s.Substring(start, end - start + 1);
}
```

---

-    回文数-腾讯-09
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
提示：
-231 <= x <= 231 - 1
进阶：你能不将整数转为字符串来解决这个问题吗？

---

```C#
public bool IsPalindrome(int x)
{
    if (x < 0)
    {
        return false;
    }

return true;
}

public bool IsPalindrome2(int x)
{
    if (x < 0 || x % 10 == 0 && x != 0)
    {
        return false;
    }

var num = 0;
    while (x > num)
    {
        num = num * 10 + x % 10;
        x /= 10;
    }

// 当数字长度为奇数时，我们可以通过 num/10 去除处于中位的数字。
    // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，num = 123，
    // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
    return x == num || x == num / 10;
}
```

---

-    整数反转-腾讯-07
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
提示：
-231 <= x <= 231 - 1

---

```C#
public int Reverse(int x)
{
    var num = 0;
    var max10 = int.MaxValue / 10;
    var offsetMax10 = int.MaxValue % 10;
    while (x != 0)
    {
        var offsetX = x % 10;
        //判断是否 大于 最大32位整数
        if (num > max10 || num == max10 && offsetX > offsetMax10)
        {
            return 0;
        }

//判断是否 小于 最小32位整数
        if (num < -max10 || num == -max10 && offsetX < -offsetMax10 - 1)
        {
            return 0;
        }

num = num * 10 + offsetX;
        x /= 10;
    }

return num;
}
```

---

-   回文子串-647
给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。

---

```C#
public int CountSubstrings(string s)
{
    if (s.Length < 2)
    {
        return 1;
    }

var length = s.Length;
    var num = length;
    var dp = new bool[length][];
    for (var i = 0; i < length; i++)
    {
        dp[i] = new bool[length];
        dp[i][i] = true;
    }

for (int i = length - 2; i >= 0; i--)
    {
        for (int j = i + 1; j < length; j++)
        {
            if (s[i] == s[j])
            {
                if (j - i < 3)
                {
                    dp[i][j] = true;
                }
                else
                {
                    dp[i][j] = dp[i + 1][j - 1];
                }

if (dp[i][j])
                {
                    num++;
                }
            }
            else
            {
                dp[i][j] = false;
            }
        }
    }

return num;
}
```

---