0721学习

agile Posted on Jul 21 2023

面试 leetcode学习

-   剑指 Offer 17. 打印从 1 到最大的 n 位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
用返回一个整数列表来代替打印
n 为正整数

---

```C#
private int __Max(int n)
{
    int i = 1;
    while (n > 0)
    {
        i *= 10;
        n--;
    }

return i;
}

public int[] PrintNumbers(int n)
{
    var max = __Max(n);
    var result = new int[max - 1];
    for (int i = 1; i < max; i++)
    {
        result[i - 1] = i;
    }

return result;
}

private char[] _chars = new[] { '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' };

private int _length;

private int _startIndex;
private int _nine;

public string PrintNumbers2(int n)
{
    var sb = new StringBuilder();
    var fill = new char[n];
    _length = n;
    _nine = 0;
    _startIndex = n - 1;
    __Help(sb, 0, fill);
    return sb.ToString();
}

private void __Help(StringBuilder sb, int n, char[] fill)
{
    if (n == _length)
    {
        var s = new string(fill);
        s = s.Substring(_startIndex);
        if (s != "0")
        {
            sb.Append(s);
            sb.Append(',');
        }

if (_length - _startIndex == _nine)
        {
            _startIndex--;
        }

return;
    }

for (int i = 0; i < _chars.Length; i++)
    {
        if (_chars[i] == '9')
        {
            _nine++;
        }

fill[n] = _chars[i];
        __Help(sb, n + 1, fill);
    }

_nine--;
}
```

---

-   剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000

---

```C#
private int _pairs = 0;
private int[] _nums;

public int ReversePairs(int[] nums)
{
    if (nums.Length <= 1)
    {
        return 0;
    }

_pairs = 0;
    _nums = nums;

__Help(0);
    return _pairs;
}

private void __Help(int index)
{
    if (index >= _nums.Length - 1)
    {
        return;
    }

var v = _nums[index];
    for (int i = index + 1; i < _nums.Length; i++)
    {
        if (v > _nums[i])
        {
            _pairs++;
        }
    }

__Help(index + 1);
}

public int ReversePairs2(int[] nums)
{
    _nums = nums;
    _pairs = 0;
    Divided(0, nums.Length - 1);
    return _pairs;
}

private void Divided(int left, int right)
{
    if (left >= right)
    {
        return;
    }

var mid = left + (right - left) / 2;
    Divided(left, mid);
    Divided(mid + 1, right);
    Merge(left, mid, right);
}

private void Merge(int left, int mid, int right)
{
    var temp = new int[right - left + 1];
    Array.Copy(_nums, left, temp, 0, temp.Length);
    var leftStart = 0;
    var leftEnd = mid - left;
    var rightStart = leftEnd + 1;
    var rightEnd = right - left;
    var i = leftStart;
    var j = rightStart;
    for (var k = left; k <= right; k++)
    {
        if (i > leftEnd)
        {
            _nums[k] = temp[j++];
        }
        else if (j > rightEnd || temp[i] <= temp[j])
        {
            _nums[k] = temp[i++];
        }
        else
        {
            //当左边数组的大于右边数组的元素时，就对当前元素以及后面的元素的个数进行统计，
            //此时这个数就是，逆序数
            //定义一个计数器，记下每次合并中存在的逆序数。
            _nums[k] = temp[j++];
            _pairs += leftEnd - i + 1;
        }
    }
}
```

---

-   两数相加-腾讯
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

---

```C#
public ListNode AddTwoNumbers(ListNode l1, ListNode l2)
{
    var dummy = new ListNode(-1);
    var extra = 0;
    var current = dummy;
    while (l1 != null && l2 != null)
    {
        var v = l1.val + l2.val + extra;
        extra = v / 10;
        current.next = new ListNode(v % 10);
        l1 = l1.next;
        l2 = l2.next;
        current = current.next;
    }

var last = (l1 == null) ? l2 : l1;
    while (last != null)
    {
        var v = last.val + extra;
        extra = v / 10;
        current.next = new ListNode(v % 10);
        last = last.next;
        current = current.next;
    }

if (extra != 0)
    {
        current.next = new ListNode(extra);
    }

return dummy.next;
}
```