0709学习

agile Posted on Jul 9 2023

面试 leetcode学习

-   剑指 Offer 54. 二叉搜索树的第 k 大节点
给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
![WX20230709-0954182x.png](https://tools.nxcloud.club:12500/images/2023/07/09/WX20230709-0954182x.png)

```C#
public int KthLargest(TreeNode root, int k)
{
    return __Help(root, ref k);
}

private int __Help(TreeNode root, ref int k)
{
    var result = 0;
    if (root.right != null && k > 0)
    {
        result = __Help(root.right, ref k);
    }

if (--k == 0)
    {
        result = root.val;
    }

if (root.left != null && k > 0)
    {
        result = __Help(root.left, ref k);
    }

return result;
}
```

---

-   剑指 Offer 45. 把数组排成最小的数
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
输入: [10,2]
输出: "102"
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

---
![WX20230709-1427102x.png](https://tools.nxcloud.club:12500/images/2023/07/09/WX20230709-1427102x.png)

---

```
字符串 xy < yx , yz < zy ，需证明 xz < zx 一定成立。

设十进制数 x, y, z 分别有 a, b, c 位，则有：
（左边是字符串拼接，右边是十进制数计算，两者等价）
xy = x * 10^b + y 
yx = y * 10^a + x

则 xy < yx 可转化为：
x * 10^b + y < y * 10^a + x
x (10^b - 1) < y (10^a - 1)
x / (10^a - 1) < y / (10^b - 1)     ①

同理， 可将 yz < zy 转化为：
y / (10^b - 1) < z / (10^c - 1)     ②

将 ① ② 合并，整理得：
x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1)
x / (10^a - 1) < z / (10^c - 1)
x (10^c - 1) < z (10^a - 1)
x * 10^c + z < z * 10^a + x
∴  可推出 xz < zx ，传递性证毕
```

---

```C#
private string[] _strings;

private void __Init(int[] nums)
{
    _strings = new string[nums.Length];
    for (var i = 0; i < _strings.Length; i++)
    {
        _strings[i] = $"{nums[i]}";
    }
}

public string MinNumber(int[] nums)
{
    __Init(nums);
    __InsertSort(nums);
    return __MinValue();
}

private void __InsertSort(int[] nums)
{
    for (var i = 1; i < _strings.Length; i++)
    {
        var baseValue = _strings[i];
        var j = i - 1;
        for (; j >= 0; j--)
        {
            if (__Compare(_strings[j], baseValue))
            {
                _strings[j + 1] = _strings[j];
            }
            else
            {
                break;
            }
        }

_strings[j + 1] = baseValue;
    }
}

private string __MinValue()
{
    var sb = new StringBuilder();
    for (var i = 0; i < _strings.Length; i++)
    {
        sb.Append(_strings[i]);
    }

return sb.ToString();
}

private bool __Compare(string first, string baseString)
{
    return (first + baseString).CompareTo(baseString + first) >= 0;
}

public string MinNumber2(int[] nums)
{
    __Init(nums);
    __QuickSort();
    return __MinValue();
}

private int __MidValue(int left, int right)
{
    var mid = left + (right - left) / 2;
    if (__Compare(_strings[left], _strings[right]) ^ __Compare(_strings[left], _strings[mid]))
    {
        return left;
    }

if (__Compare(_strings[right], _strings[left]) ^ __Compare(_strings[right], _strings[mid]))
    {
        return right;
    }

return mid;
}

private void __QuickSort()
{
    var left = 0;
    var right = _strings.Length - 1;
    __Sort(left, right);
}

private void __Sort(int left, int right)
{
    while (true)
    {
        if (left > right)
        {
            return;
        }

var mid = __Partition(left, right);
        if (mid - left < right - mid)
        {
            __Sort(left, mid - 1);
            left = mid + 1;
        }
        else
        {
            __Sort(mid + 1, right);
            right = mid - 1;
        }
    }
}

private int __Partition(int left, int right)
{
    var mid = __MidValue(left, right);
    var midValue = _strings[mid];
    var start = left;
    (_strings[left], _strings[mid]) = (_strings[mid], _strings[left]);
    while (left < right)
    {
        while (left < right && __Compare(_strings[right], midValue))
        {
            right--;
        }

while (left < right && __Compare(midValue, _strings[left]))
        {
            left++;
        }

(_strings[left], _strings[right]) = (_strings[right], _strings[left]);
    }

(_strings[left], _strings[start]) = (_strings[start], _strings[left]);
    return left;
}
```

-   剑指 Offer 61. 扑克牌中的顺子
从若干副扑克牌中随机抽 5 张牌，判断是不是一个顺子，即这5张牌是不是连续的。2～10为数字本身，A为1，J为11，Q为12，K为13，而大、小王为 0 ，可以看成任意数字。A 不能视为 14。

---

```C#
public bool IsStraight(int[] nums)
{
    var min = int.MaxValue;
    var max = int.MinValue;
    for (int i = 0; i < nums.Length; i++)
    {
        var v = nums[i];
        if (v == 0)
        {
            continue;
        }

if (min > v)
        {
            min = v;
        }
        else if (min == v)
        {
            return false;
        }

if (max < v)
        {
            max = v;
        }
        else if (max == v)
        {
            return false;
        }
    }

if (max - min > 4)
    {
        return false;
    }

for (int i = 0; i < nums.Length; i++)
    {
        var index = i;
        while (nums[index] != 0 && index != (nums[index] - min))
        {
            var numsIndexValue = nums[index];
            if (nums[numsIndexValue - min] == numsIndexValue)
            {
                return false;
            }

(nums[index], nums[numsIndexValue - min]) = (nums[numsIndexValue - min], nums[index]);
        }
    }

return true;
}

public bool IsStraight2(int[] nums)
{
    var bucket = new int[14];
    for (var i = 0; i < nums.Length; i++)
    {
        var v = nums[i];
        if (v != 0 && bucket[v] != 0)
        {
            return false;
        }

bucket[v]++;
    }

var left = 1;
    var right = 13;
    while (bucket[left] == 0 && left < right)
    {
        left++;
    }

while (bucket[right] == 0 && right > left)
    {
        right--;
    }

return right - left <= 4;
}
```

-   剑指 Offer 40. 最小的 k 个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

---
![WX20230709-1750082x.png](https://tools.nxcloud.club:12500/images/2023/07/09/WX20230709-1750082x.png)

---

```C#
private int __Parent(int index)
{
    return (index - 1) / 2;
}

private int __Left(int p)
{
    return p * 2 + 1;
}

private int __Right(int p)
{
    return p * 2 + 2;
}

private void __Low(int[] arr, int parentIndex, int length)
{
    while (true)
    {
        var left = __Left(parentIndex);
        var right = __Right(parentIndex);
        var minIndex = parentIndex;
        if (parentIndex >= 0 && left <= length - 1 && arr[minIndex] > arr[left])
        {
            minIndex = left;
        }

if (parentIndex >= 0 && right < length - 1 && arr[minIndex] > arr[right])
        {
            minIndex = right;
        }

if (parentIndex == minIndex)
        {
            break;
        }

(arr[minIndex], arr[parentIndex]) = (arr[parentIndex], arr[minIndex]);
        parentIndex = minIndex;
    }
}

//堆排序
public int[] GetLeastNumbers(int[] arr, int k)
{
    if (arr.Length <= 0 || arr.Length < k)
    {
        return arr;
    }

var parentIndex = __Parent(arr.Length - 1);
    for (int i = parentIndex; i >= 0; i--)
    {
        __Low(arr, i, arr.Length);
    }

for (int i = 0; i < k; i++)
    {
        (arr[0], arr[arr.Length - 1 - i]) = (arr[arr.Length - 1 - i], arr[0]);
        __Low(arr, 0, arr.Length - 1 - i);
    }

var result = new int[k];
    Array.Copy(arr, arr.Length - k, result, 0, k);
    return result;
}

//快排
public int[] GetLeastNumbers2(int[] arr, int k)
{
    if (arr.Length <= 0 || arr.Length < k)
    {
        return arr;
    }

return __QuickSort(arr, k, 0, arr.Length - 1);
}

//快排为什么先移动右边？？？？
//这里，来个极端案例，比如，第一个数就是最小的数，如果先让左指针动，左指针是遇到大于key的值才停下，
//此时其实左指针多往右跑了一步，到第二个位置才会停下，
//因为谁先动就会先判断谁，所以最终结果是左右指针相遇在第二个位置，第一个数其实和第二个数交换了，
//向后错了一位。所以，如果左指针先动的话，其实，最终，把第一个基准数和左右指针相遇时的位置交换这一步会出错，
//左右指针比应该原本应该相遇的位置右移一位。
// 当然，如果你理解了这个过程，就应该明白，如果key是从最右边选的话，那么就应该从左指针先动了。
private int __Partition(int[] arr, int left, int right)
{
    var l = left;
    var r = right;
    var baseValue = arr[l];
    while (l < r)
    {
        while (l < r && arr[r] >= arr[left])
        {
            r--;
        }

while (l < r && arr[l] <= arr[left])
        {
            l++;
        }

(arr[l], arr[r]) = (arr[r], arr[l]);
    }

(arr[l], arr[left]) = (arr[left], arr[l]);

return l;
}

private int[] __QuickSort(int[] arr, int k, int left, int right)
{
    var mid = __Partition(arr, left, right);
    if (mid > k)
    {
        return __QuickSort(arr, k, left, mid - 1);
    }

if (mid < k)
    {
        return __QuickSort(arr, k, mid + 1, right);
    }

var d = new int [k];
    Array.Copy(arr, d, k);
    return d;
}
```