0814学习

agile Posted on Aug 23 2023

面试 leetcode学习

-   字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
示例 2:
输入: num1 = "123", num2 = "456"
输出: "56088"
提示：
1 <= num1.length, num2.length <= 200
num1 和 num2 只能由数字组成。
num1 和 num2 都不包含任何前导零，除了数字0本身

---

```C#
public string Multiply(string num1, string num2)
{
    if (num1 == "0" || num2 == "0")
    {
        return "0";
    }

var str = new List<string>();
    var sb = new StringBuilder();
    var extra = 0;
    var maxLength = 0;
    for (var i = 0; i < num1.Length; i++)
    {
        var v1 = num1[num1.Length - i - 1] - '0';
        extra = 0;
        sb.Clear();
        for (var j = num2.Length - 1; j >= 0; j--)
        {
            var v2 = num2[j] - '0';
            var t = v1 * v2 + extra;
            sb.Insert(0, t % 10);
            extra = t / 10;
        }

if (extra != 0)
        {
            sb.Insert(0, extra);
        }

var index = i;
        while (index-- > 0)
        {
            sb.Append(0);
        }

maxLength = Math.Max(sb.Length, maxLength);
        str.Add(sb.ToString());
    }

extra = 0;
    sb.Clear();
    for (int i = 0; i < maxLength; i++)
    {
        var sum = extra;
        for (int j = 0; j < str.Count; j++)
        {
            var cStr = str[j];
            if (cStr.Length >= i + 1)
            {
                sum += cStr[cStr.Length - 1 - i] - '0';
            }
        }

sb.Insert(0, sum % 10);
        extra = sum / 10;
    }

if (extra != 0)
    {
        sb.Insert(0, extra);
    }

return sb.ToString();
}

public string Multiply2(string num1, string num2)
{
    if (num1 == "0" || num2 == "0")
    {
        return "0";
    }

var num = new int[num1.Length + num2.Length];
    for (var i = num1.Length - 1; i >= 0; i--)
    {
        var v1 = num1[i] - '0';
        for (var j = num2.Length - 1; j >= 0; j--)
        {
            var v2 = num2[j] - '0';
            var t = num[i + j + 1] + v1 * v2;
            num[i + j + 1] = t % 10;
            num[i + j] += t / 10;
        }
    }

var sb = new StringBuilder();
    for (var i = 0; i < num.Length; i++)
    {
        if (i == 0 && num[i] == 0)
        {
            continue;
        }

sb.Append(num[i]);
    }

return sb.ToString();
}
```

---

-   最长公共前缀-14
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
示例 1：
输入：strs = ["flower","flow","flight"]
输出："fl"

---

```C#
public string LongestCommonPrefix(string[] strs)
{
    var length = strs[0].Length;
    var sb = new StringBuilder();
    for (int i = 0; i < length; i++)
    {
        var a = strs[0][i];
        for (int j = 1; j < strs.Length; j++)
        {
            var s = strs[j];
            if (s.Length >= i + 1 && s[i] == a)
            {
                continue;
            }

return sb.ToString();
        }

sb.Append(a);
    }

return sb.ToString();
}
```
---

-   字符串转换整数 (atoi)-8
请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。
函数 myAtoi(string s) 的算法如下：
1.读入字符串并丢弃无用的前导空格
2.检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3.读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，"123" -> 123， "0032" -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
4.如果整数数超过 32 位有符号整数范围 [−231,  231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：
本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

---

```C#
public int MyAtoi(string s)
{
    if (s.Length <= 0)
    {
        return 0;
    }

s = s.Trim(' ');
    var queue = new Queue<int>();
    var firstCheck = false;
    var flag = 1;
    foreach (var c in s)
    {
        if (!firstCheck)
        {
            firstCheck = true;
            switch (c)
            {
                case '+':
                    flag = 1;
                    continue;
                    break;
                case '-':
                    flag = -1;
                    continue;
                    break;
            }
        }

if (char.IsDigit(c))
        {
            queue.Enqueue(c - '0');
        }
        else
        {
            break;
        }
    }

long sum = 0;

while (queue.Count > 0)
    {
        var popValue = queue.Dequeue();
        if ((popValue > 2 && queue.Count >= 9) || popValue != 0 && queue.Count > 10)
        {
            return flag == 1 ? int.MaxValue : int.MinValue;
        }

sum += popValue * (long)Math.Pow(10, queue.Count);

if (flag == 1)
        {
            if (sum > int.MaxValue)
            {
                return int.MaxValue;
            }
        }
        else
        {
            if (sum * -1 < int.MinValue)
            {
                return int.MinValue;
            }
        }
    }

return (int)sum * flag;
}
```
---

-   两数之和-01
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

---

```C#
public int[] TwoSum(int[] nums, int target)
{
    var length = nums.Length;
    var cache = new Dictionary<int, List<int>>();
    for (var i = 0; i < length; i++)
    {
        var v = nums[i];
        if (cache.TryGetValue(v, out var list))
        {
            list.Add(i);
        }
        else
        {
            cache[v] = new List<int> { i };
        }
    }

Array.Sort(nums);
    var left = 0;
    var right = length - 1;
    while (left < right)
    {
        var l = nums[left];
        var r = nums[right];
        if (l + r == target)
        {
            if (l != r) return new[] { cache[l][0], cache[r][0] };
            var list = cache[l];
            return new[] { list[0], list[1] };
        }

if (l + r > target)
        {
            right--;
        }
        else
        {
            left++;
        }
    }

return Array.Empty<int>();
}

public int[] TwoSum2(int[] nums, int target)
{
    var cache = new Dictionary<int, int>();
    for (var i = 0; i < nums.Length; i++)
    {
        var v = nums[i];
        if (cache.TryGetValue(target - v, out var index))
        {
            return new[] { i, index };
        }

cache[v] = i;
    }

return Array.Empty<int>();
}
```

-   盛最多水的容器-11
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。

---
![Snip20230811_12.png](https://tools.nxcloud.club:12500/images/2023/08/11/Snip20230811_12.png)

---

```C#
public int MaxArea(int[] height)
{
    var max = int.MinValue;
    var left = 0;
    var right = height.Length - 1;
    while (left < right)
    {
        var l = height[left];
        var r = height[right];
        var width = right - left;
        var minHeight = Math.Min(l, r);
        var maxHeight = Math.Max(l, r);
        var minArea = minHeight * width;
        max = Math.Max(max, minHeight * width);
        if (maxHeight * (width - 1) < minArea)
        {
            left++;
            right--;
        }
        else
        {
            if (l >= r)
            {
                right--;
            }
            else if (l < r)
            {
                left++;
            }
        }
    }

return max;
}
```

---

-   三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

---

```C#
public IList<IList<int>> ThreeSum(int[] nums)
{
    Array.Sort(nums);
    var leftIndex = 0;
    var rightIndex = nums.Length - 1;
    //中间值初始比左边序列大1
    var midIndex = 1;
    var result = new List<IList<int>>();
    //左边的值肯定是小于等于0
    while (nums[leftIndex] <= 0 && leftIndex < nums.Length - 2)
    {
        var leftNum = nums[leftIndex];
        //中间值的序列肯定小于右边的序列
        if (midIndex < rightIndex)
        {
            //表示leftNum太大
            if (leftNum + nums[rightIndex] + nums[rightIndex - 1] < 0 && nums[rightIndex - 1] >= 0)
            {
                leftIndex++;
            }
            else
            {
                //保证leftnum不变，如果相加和小于0,则midIndex右移，如果相加和大于0，则rightIndex左移
                while (midIndex < rightIndex)
                {
                    var temp = leftNum + nums[midIndex] + nums[rightIndex];
                    if (temp == 0)
                    {
                        result.Add(new List<int> { leftNum, nums[midIndex], nums[rightIndex] });
                        midIndex++;
                        //可能碰到相邻rightNum一样
                        __FormatRightIndex(nums, midIndex, ref rightIndex);
                    }
                    else if (temp < 0)
                    {
                        midIndex++;
                    }
                    else
                    {
                        __FormatRightIndex(nums, midIndex, ref rightIndex);
                    }
                }

leftIndex++;
            }
        }
        else
        {
            break;
        }

//还原mideIndex,rightIndex
        midIndex = leftIndex + 1;
        rightIndex = nums.Length - 1;

//可能leftnum相邻相等
        while (leftIndex < nums.Length - 2 && nums[leftIndex] == leftNum)
        {
            leftIndex++;
            midIndex = leftIndex + 1;
            rightIndex = nums.Length - 1;
        }
    }

return result;
}

private void __FormatRightIndex(int[] nums, int midIndex, ref int rightIndex)
{
    var rightNum = nums[rightIndex];
    rightIndex--;
    while (midIndex < rightIndex && nums[rightIndex] == rightNum)
    {
        rightIndex--;
    }
}
```

---

-   有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
1.左括号必须用相同类型的右括号闭合。
2.左括号必须以正确的顺序闭合。
3.每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
提示：
1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

---

```C#
public bool IsValid(string s)
{
    if (s.Length % 2 == 1)
    {
        return false;
    }

return stack.Count == 0;
}
```

---

-   最接近的三数之和-16
给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。
返回这三个数的和。
假定每组输入只存在恰好一个解。
示例 1：
输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。
提示：
3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-104 <= target <= 104

---
```C#
public int ThreeSumClosest(int[] nums, int target)
{
    var length = nums.Length;
    if (length == 3)
    {
        return nums[0] + nums[1] + nums[2];
    }

Array.Sort(nums);
    var sum1 = nums[length- 1] + nums[length - 2] + nums[length - 3];
    if (target >= sum1)
    {
        return sum1;
    }

sum1 = nums[0] + nums[1] + nums[2];
    if (target <= sum1)
    {
        return sum1;
    }

var leftIndex = 0;
    var rightIndex = length - 1;
    var midIndex = 1;
    var minValue = nums[length - 1] + nums[length - 2] + nums[length - 3];
    while (leftIndex < nums.Length - 2)
    {
        while (midIndex < rightIndex)
        {
            var sum = nums[leftIndex] + nums[midIndex] + nums[rightIndex];
            if (sum == target)
            {
                return target;
            }

__MinValue(sum, target, ref minValue);
            if (sum < target)
            {
                midIndex++;
            }

if (sum > target)
            {
                __MoveRightIndex(nums, midIndex, ref rightIndex);
            }
        }

__MoveLeftIndex(nums, target, ref leftIndex);
        midIndex = leftIndex + 1;
        rightIndex = length - 1;
    }

return minValue;
}

private void __MoveLeftIndex(int[] nums, int target, ref int leftIndex)
{
    var currentValue = nums[leftIndex];
    leftIndex++;
    while (leftIndex < nums.Length - 2 && target >= nums[leftIndex] && nums[leftIndex] == currentValue)
    {
        leftIndex++;
    }
}

private void __MoveRightIndex(int[] nums, int midIndex, ref int rightIndex)
{
    var currentValue = nums[rightIndex];
    rightIndex--;
    while (midIndex < rightIndex && nums[rightIndex] == currentValue)
    {
        rightIndex--;
    }
}

private void __MinValue(int sum, int target, ref int minValue)
{
    var absSumDelta = Math.Abs(sum - target);
    var absMinDelta = Math.Abs(minValue - target);
    if (absSumDelta < absMinDelta)
    {
        minValue = sum;
    }
}
```

---

-   合并两个有序链表-21
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
示例 1：
![merge_ex1.jpg](https://tools.nxcloud.club:12500/images/2023/08/23/merge_ex1.jpg)
输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]
提示：
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列

---

```C#
public ListNode MergeTwoLists(ListNode list1, ListNode list2)
{
    if (list1 == null || list2 == null)
    {
        return list1 == null ? list2 : list1;
    }

current.next = list1 == null ? list2 : list1;
    return dummy.next;
}

public ListNode MergeTwoLists2(ListNode list1, ListNode list2)
{
    if (list1 == null || list2 == null)
    {
        return list1 == null ? list2 : list1;
    }

ListNode head;
    if (list1.val < list2.val)
    {
        head = list1;
        list1 = list1.next;
    }
    else
    {
        head = list2;
        list2 = list2.next;
    }

head.next = MergeTwoLists2(list1, list2);
    return head;
}
```

---

-   合并 K 个升序链表-23
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6
提示：
k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

---

```C#
public ListNode MergeKLists(ListNode[] lists)
{
    if (lists.Length == 0)
    {
        return null;
    }

if (lists.Length == 1)
    {
        return lists[0];
    }

if (minListNode != null)
        {
            current.next = minListNode;
            current = minListNode;
            var index = listsCache.IndexOf(minListNode);
            if (minListNode.next == null)
            {
                listsCache.RemoveAt(index);
            }
            else
            {
                listsCache[index] = minListNode.next;
            }
        }
        else
        {
            return dummy.next;
        }
    }

return dummy.next;
}

class ListNodeCompare : IComparer<ListNode>
{
    public int Compare(ListNode x, ListNode y)
    {
        if (ReferenceEquals(x, y)) return 0;
        if (ReferenceEquals(null, y)) return 1;
        if (ReferenceEquals(null, x)) return -1;
        return x.val.CompareTo(y.val);
    }
}

public ListNode MergeKLists2(ListNode[] lists)
{
    var queue = new PriorityQueue<ListNode, ListNode>(new ListNodeCompare());
    foreach (var c in lists)
    {
        if (c != null)
        {
            queue.Enqueue(c, c);
        }
    }

var dummy = new ListNode(-1);
    var current = dummy;
    while (queue.Count > 0)
    {
        var node = queue.Dequeue();
        current.next = node;
        current = node;
        if (node.next != null)
        {
            queue.Enqueue(node.next, node.next);
        }
    }

return dummy.next;
}
```

---

-   每日温度-739
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

---
```C#
public int[] DailyTemperatures(int[] temperatures)
{
    var length = temperatures.Length;
    var result = new int[length];
    if (length == 1)
    {
        return result;
    }

for (var i = length - 2; i >= 0; i--)
    {
        __Compare(result, temperatures, i, i + 1);
    }

return result;
}

private void __Compare(int[] result, int[] temperatures, int currentIndex, int targetIndex)
{
    if (temperatures[currentIndex] < temperatures[targetIndex])
    {
        result[currentIndex] = targetIndex - currentIndex;
    }
    else
    {
        var index = result[targetIndex];
        if (index == 0)
        {
            return;
        }

__Compare(result, temperatures, currentIndex, targetIndex + index);
    }
}

//单调栈
public int[] DailyTemperatures2(int[] temperatures)
{
    var length = temperatures.Length;
    var result = new int[length];
    if (length == 1)
    {
        return result;
    }

var stack = new Stack<int>();
    for (int i = 0; i < length; i++)
    {
        var t = temperatures[i];
        while (stack.Count > 0 && t > temperatures[stack.Peek()])
        {
            var c = stack.Pop();
            result[c] = i - c;
        }

stack.Push(i);
    }

return result;
}
```

---