0731学习

agile Posted on Jul 31 2023

面试 leetcode学习

-   两两交换链表中的节点 - 24-tx
给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）
输入：head = [1,2,3,4]
输出：[2,1,4,3]

---

```C#
public ListNode SwapPairs(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

var dummy = new ListNode(-1);
    var p1 = head;
    var p2 = head.next;
    dummy.next = p2;
    while (p1 != null && p2 != null)
    {
        var t = p2.next;
        var tt = t?.next;
        p2.next = p1;
        if (t != null && tt != null)
        {
            p1.next = tt;
        }
        else
        {
            p1.next = t;
        }

p1 = t;
        p2 = tt;
    }

return dummy.next;
}

public ListNode SwapPairs2(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

var p1 = head;
    var p2 = head.next;
    var t = p2.next;
    p2.next = p1;
    p1.next = SwapPairs2(t);
    return p2;
}
```

---

-   870. 优势洗牌-tx
给定两个长度相等的数组 nums1 和 nums2，nums1 相对于 nums2 的优势可以用满足 nums1[i] > nums2[i] 的索引 i 的数目来描述。
返回 nums1 的任意排列，使其相对于 nums2 的优势最大化。
示例 1：
输入：nums1 = [2,7,11,15], nums2 = [1,10,4,11]
输出：[2,11,7,15]

---

![1690795371096_2.png](https://tools.nxcloud.club:12500/images/2023/07/31/1690795371096_2.png)

---

```C#
public int[] AdvantageCount(int[] nums1, int[] nums2)
{
    var length = nums1.Length;
    for (int index = 0; index < length; index++)
    {
        var baseValue = nums2[index];
        var swapIndex = index;
        var swapValue = int.MaxValue;
        var minValue = nums1[index];
        var minIndex = index;
        var flag = false;
        for (var i = index; i < length; i++)
        {
            var c = nums1[i];
            if (c < minValue)
            {
                minValue = c;
                minIndex = i;
            }

if (c > baseValue && c < swapValue)
            {
                flag = true;
                swapIndex = i;
                swapValue = c;
                if (c - baseValue == 1)
                {
                    break;
                }
            }
        }

if (!flag)
        {
            (nums1[index], nums1[minIndex]) = (nums1[minIndex], nums1[index]);
        }
        else
        {
            (nums1[index], nums1[swapIndex]) = (nums1[swapIndex], nums1[index]);
        }
    }

return nums1;
}

public int[] AdvantageCount2(int[] nums1, int[] nums2)
{
    var nums1Index = new int[nums1.Length];
    var nums2Index = new int[nums2.Length];
    for (var i = 0; i < nums2.Length; i++)
    {
        nums1Index[i] = i;
        nums2Index[i] = i;
    }

//下标从大到小排序
    Array.Sort(nums1Index, (i, i1) => nums1[i] - nums1[i1]);
    Array.Sort(nums2Index, (i, i1) => nums2[i] - nums2[i1]);

return result;
}
```

-   2410. 运动员和训练师的最大匹配数
给你一个下标从 0 开始的整数数组 players ，其中 players[i] 表示第 i 名运动员的 能力 值，同时给你一个下标从 0 开始的整数数组 trainers ，其中 trainers[j] 表示第 j 名训练师的 训练能力值 。
如果第 i 名运动员的能力值 小于等于 第 j 名训练师的能力值，那么第 i 名运动员可以 匹配 第 j 名训练师。除此以外，每名运动员至多可以匹配一位训练师，每位训练师最多可以匹配一位运动员。
请你返回满足上述要求 players 和 trainers 的 最大 匹配数。
示例 1：
输入：players = [4,7,9], trainers = [8,2,5,8]
输出：2
解释：
得到两个匹配的一种方案是：players[0] 与 trainers[0] 匹配，因为 4 <= 8 。players[1] 与 trainers[3] 匹配，因为 7 <= 8 。
可以证明 2 是可以形成的最大匹配数。

---

```C#
public int MatchPlayersAndTrainers(int[] players, int[] trainers)
{
    Array.Sort(players);
    Array.Sort(trainers);
    var p = 0;
    var t = 0;
    var pLength = players.Length;
    var tLength = trainers.Length;
    var count = 0;
    while (p < pLength && t < tLength)
    {
        if (players[p] <= trainers[t])
        {
            count++;
            p++;
            t++;
        }
        else
        {
            t++;
        }
    }

return count;
}
```

---

-   662. 二叉树最大宽度 -字节
给你一棵二叉树的根节点 root ，返回树的 最大宽度 。
树的 最大宽度 是所有层中最大的 宽度 。
每一层的 宽度 被定义为该层最左和最右的非空节点（即，两个端点）之间的长度。将这个二叉树视作与满二叉树结构相同，两端点间会出现一些延伸到这一层的 null 节点，这些 null 节点也计入长度。
题目数据保证答案将会在  32 位 带符号整数范围内。

---

```C#
private int _maxWidth = 0;

public int WidthOfBinaryTree(TreeNode root)
{
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    var queueWidth = new Queue<long>();
    queueWidth.Enqueue(1);
    while (queue.Count > 0)
    {
        var size = queue.Count;
        var min = (long)0;
        var max = (long)0;
        for (int i = 0; i < size; i++)
        {
            var q = queue.Dequeue();
            var w = queueWidth.Dequeue();
            if (min == 0)
            {
                min = w;
                max = w;
            }
            else
            {
                min = Math.Min(min, w);
                max = Math.Max(max, w);
            }

if (q.left != null)
            {
                queue.Enqueue(q.left);
                queueWidth.Enqueue(w * 2 - 1);
            }

if (q.right != null)
            {
                queue.Enqueue(q.right);
                queueWidth.Enqueue(w * 2);
            }
        }

_maxWidth = Math.Max(_maxWidth, (int)(max - min + 1));
    }

return _maxWidth;
}
```

---