0705学习

agile Posted on Jul 5 2023

面试 leetcode学习

-   剑指 Offer 27. 二叉树的镜像
请完成一个函数，输入一个二叉树，该函数输出它的镜像

```C#
public TreeNode MirrorTree(TreeNode root)
{
    if (root == null)
    {
        return root;
    }
    var left = MirrorTree(root.left);
    var right = MirrorTree(root.right);
    root.left = right;
    root.right = left;
    return root;
}
```

---

-   剑指 Offer 28. 对称的二叉树
请实现一个函数，用来判断一棵二叉树是不是对称的。如果一棵二叉树和它的镜像一样，那么它是对称的。

```C#
//递归
public bool IsSymmetric(TreeNode root)
{
    if (root == null)
    {
        return true;
    }

return __Help(root.left, root.right);
}

private bool __Help(TreeNode left, TreeNode right)
{
    if (left == null ^ right == null)
    {
        return false;
    }

if (left == null && right == null)
    {
        return true;
    }

if (left.val != right.val)
    {
        return false;
    }

return __Help(left.right, right.left) && __Help(left.left, right.right);
}

//迭代
public bool IsSymmetric2(TreeNode root)
{
    if (root == null)
    {
        return true;
    }

var queue = new Queue<TreeNode>();
    queue.Enqueue(root.left);
    queue.Enqueue(root.right);
    while (queue.Count > 0)
    {
        var nodeLeft = queue.Dequeue();
        var nodeRight = queue.Dequeue();
        if (nodeLeft == null ^ nodeRight == null)
        {
            return false;
        }

if (nodeLeft == null && nodeRight == null)
        {
            continue;
        }

if (nodeLeft.val != nodeRight.val)
        {
            return false;
        }

queue.Enqueue(nodeLeft.left);
        queue.Enqueue(nodeRight.right);
        queue.Enqueue(nodeLeft.right);
        queue.Enqueue(nodeRight.left);
    }

return true;
}
```

---

-   剑指 Offer 10- I. 斐波那契数列
写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
斐波那契数列由 0 和 1 开始，之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。

---

```C#
private Dictionary<int, int> __cache = new Dictionary<int, int>();

public int Fib(int n)
{
    if (n <= 1)
    {
        return n;
    }

if (__cache.TryGetValue(n, out var v))
    {
        return v;
    }

var l = Fib(n - 1) + Fib(n - 2);
    v = (l % 1000000007);
    __cache[n] = v;
    return v;
}
// 循环求余法：
// 大数越界： 随着n增大,f(n)会超过 Int32 甚至 Int64 的取值范围，导致最终的返回值错误。
public int Fib2(int n)
{
    if (n <= 1)
    {
        return n;
    }

var sum = 0;
    var a = 0;
    var b = 1;
    for (var i = 1; i < n; i++)
    {
        sum = (a + b) % 1000000007;
        a = b;
        b = sum;
    }

return sum;
}
```

---

-   剑指 Offer 10- II. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
答案需要取模 1e9+7（1000000007），如计算初始结果为：1000000008，请返回 1。输入：n = 0 输出：1

---

```C#
public int NumWays(int n)
{
    if (n <= 1)
    {
        return 1;
    }

int a = 1, b = 1, sum = 0;
    for (int i = 1; i < n; i++)
    {
        sum = (a + b) % 1000000007;
        a = b;
        b = sum;
    }

return sum;
}

//完全背包问题
// 在纯完全背包问题中，先遍历物品还是先遍历背包都可以。但本题是是排列问题，
// 即有顺序地进行排列，那就需要先遍历背包 。如果组合问题，并不关心物品使用的顺序，
// 而关心的是物品有没有被用到，所以先遍历物品。
// 总结：
// 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
// 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

// 背包容量是n,物品有两个1,2，物品的价值和重量相等。
// 跳跃台阶可以看出是用1和2按照顺序组成n这样一个数。
// 也可以理解为用1，2物品填满背包，这里要获得填满背包的方法，所以是背包计数，
// 状态转移方程dp[j] = dp[i] + dp[j-num[i]];
public int NumWays2(int n)
{
    var dp = new int[n + 1];
    var nums = new int[2] { 1, 2 };
    dp[0] = 1;
    for (int j = 1; j <= n; j++)
    {
        foreach (var i in nums)
        {
            if (j >= i)
                dp[j] += dp[j - i] % 1000000007;
        }
    }

return dp[n];
}
```

---

-   剑指 Offer 63. 股票的最大利润
假设把某股票的价格按照时间先后顺序存储在数组中，请问买卖该股票一次可能获得的最大利润是多少？

---

```C#
public int MaxProfit(int[] prices)
{
    if (prices.Length == 0)
    {
        return 0;
    }

return profiles;
}

// 设动态规划列表dp,dp[i]代表以prices[i]为结尾的子数组的最大利润
// 由于题目限定 “买卖该股票一次” ，因此前i日最大利润dp[i]
// 等于前i-1日最大利润dp[i-1]和第i日卖出的最大利润中的最大值
// dp[i] = Math.Max(dp[i-1],prices[i]-min(prices[0:i]))

public int MaxProfit2(int[] prices)
{
    var cost = int.MaxValue;
    var profit = 0;
    foreach (var t in prices)
    {
        cost = Math.Min(cost, t);
        profit = Math.Max(profit, t - cost);
    }

return profit;
}
```

---

-   剑指 Offer 42. 连续子数组的最大和
输入一个整型数组，数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。

---

```C#
// 设动态规划列表dp,dp[i]代表以元素nums[i]为结尾的连续子数组最大和
// 若dp[i-1]<<0,说明dp[i-1]对dp[i]产生负贡献，即 dp[i-1]+num[i]还不如num[i]本身大
// dp[i]=>{
    // 1=>dp[i-1]+num[i]，dp[i-1]>0
    // 2=>nums[i] dp[i-1]<=0
    // }
public int MaxSubArray(int[] nums)
{
    var maxSum = nums[0];
    var beforeMaxSum = nums[0];
    for (int i = 1; i < nums.Length; i++)
    {
        beforeMaxSum = Math.Max(beforeMaxSum + nums[i], nums[i]);
        maxSum = Math.Max(beforeMaxSum, maxSum);
    }

return maxSum;
}
```

---

-   剑指 Offer 47. 礼物的最大价值
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？

---

```C#
// 从棋盘的左上角开始拿格子里的礼物，并每次 向右 或者 向下 移动一格、直到到达棋盘的右下角。
// 根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达
// 设f(i,j)为从棋盘左上角走至单元格(i,j)的礼物最大累计价值，易得到以下递推关系：f(i,j)等于f(i,j-1)和f(i-1,j)中的较大值 
// 加上当前单元格礼物价值grid[i][j]
public int MaxValue(int[][] grid)
{
    var row = grid.Length;
    var col = grid[0].Length;
    for (int i = 0; i < row; i++)
    {
        for (int j = 0; j < col; j++)
        {
            if (i >= 1 && j >= 1)
            {
                grid[i][j] += Math.Max(grid[i - 1][j], grid[i][j - 1]);
            }
            else
            {
                if (i >= 1 && j == 0)
                {
                    grid[i][j] += grid[i - 1][j];
                }
                else if (i == 0 && j >= 1)
                {
                    grid[i][j] += grid[i][j - 1];
                }
            }
        }
    }

return grid[row - 1][col - 1];
}
```

---

-   剑指 Offer 46. 把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。请编程实现一个函数，用来计算一个数字有多少种不同的翻译方法。

[![WX20230705-1905552x.png](https://tools.nxcloud.club:12500/images/2023/07/05/WX20230705-1905552x.png)](https://tools.nxcloud.club:12500/image/xnd7)

```C#
private int __length = 0;

private void __SplitNum(int num, out int[] array)
{
    if (num == 0)
    {
        array = new int[__length];
        return;
    }

var mod = num % 10;
    var index = __length;
    __length++;
    __SplitNum(num / 10, out array);
    array[__length - 1 - index] = mod;
}

public int TranslateNum(int num)
{
    if (num < 10)
    {
        return 1;
    }

__length = 0;
    __SplitNum(num, out var array);
    var dp = new int[array.Length];
    dp[0] = 1;
    for (int i = 1; i < array.Length; i++)
    {
        var temp = array[i - 1] * 10 + array[i];
        if (array[i - 1] == 0 || temp > 25)
        {
            dp[i] = dp[i - 1];
            continue;
        }

if (i == 1)
        {
            dp[i] = 2;
        }
        else
        {
            dp[i] += dp[i - 1] + dp[i - 2];
        }
    }

return dp[array.Length - 1];
}

public int TranslateNum2(int num)
{
    __length = 0;
    __SplitNum(num, out var array);
    var a = 1;
    var b = 1;
    var sum = 1;
    for (var i = 1; i < array.Length; i++)
    {
        var temp = array[i - 1] * 10 + array[i];
        if (array[i - 1] == 0 || temp > 25)
        {
            continue;
        }

sum = a + b;
        a = b;
        b = sum;
    }

return sum;
}
```

---

-   剑指 Offer 48. 最长不含重复字符的子字符串
请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。
![WX20230706-1040092x.png](https://tools.nxcloud.club:12500/images/2023/07/06/WX20230706-1040092x.png)

---

```C#
public int LengthOfLongestSubstring(string s)
{
    var length = s.Length;
    if (length <= 1)
    {
        return length;
    }

var currentStartIndex = 0;
    var maxSubStringLength = 1;
    for (int i = 1; i < length; i++)
    {
        var c = s[i];
        var j = currentStartIndex;
        for (j = currentStartIndex; j < i; j++)
        {
            if (s[j] == c)
            {
                currentStartIndex = j + 1;
                break;
            }
        }

maxSubStringLength = Math.Max(maxSubStringLength, i - currentStartIndex + 1);
    }

return maxSubStringLength;
}

public int LengthOfLongestSubstring2(string s)
{
    var length = s.Length;
    if (length <= 1)
    {
        return length;
    }

cache[c] = i;
        currentLength = currentLength < i - index ? currentLength + 1 : i - index;
        maxLength = Math.Max(maxLength, currentLength);
    }

return maxLength;
}
```

---
-   剑指 Offer 58 - I. 翻转单词顺序
输入一个英文句子，翻转句子中单词的顺序，但单词内字符的顺序不变。为简单起见，标点符号和普通字母一样处理。例如输入字符串"I am a student. "，则输出"student. a am I"。

---

```C#
public string ReverseWords(string s)
{
    s = s.Trim();
    var sb = new StringBuilder();
    var sArray = s.Split(' ');
    for (int i = sArray.Length - 1; i >= 0; i--)
    {
        if (sArray[i] != "")
        {
            sb.Append(sArray[i].Trim());
            if (i > 0)
            {
                sb.Append(" ");
            }
        }
    }

return sb.ToString();
}
```

---