0824学习

agile Posted on Aug 25 2023

面试排序 leetcode学习

-   删除有序数组中的重复项-26
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 升序 排列

---

```C#
public int RemoveDuplicates(int[] nums)
{
    var recordIndex = 0;
    for (var i = 1; i < nums.Length; i++)
    {
        if (nums[i] == nums[recordIndex]) continue;
        if (recordIndex + 1 != i)
        {
            (nums[recordIndex + 1], nums[i]) = (nums[i], nums[recordIndex + 1]);
        }

recordIndex++;
    }

return recordIndex + 1;
}
```

---

-   删除有序数组中的重复项 II-80
给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 2：
输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按升序排列

---

```C#
public int RemoveDuplicates(int[] nums)
{
    if (nums.Length <= 2)
    {
        return nums.Length;
    }

var index = 1;
    for (var i = 2; i < nums.Length; i++)
    {
        if (nums[i] != nums[index] || nums[i] != nums[index - 1])
        {
            nums[++index] = nums[i];
        }
    }

return index + 1;
}
```

---

-   搜索旋转排序数组-33
整数数组 nums 按升序排列，数组中的值 互不相同 。
在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
示例 1：
输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

---

```C#
// 定理一：只有在顺序区间内才可以通过区间两端的数值判断target是否在其中。
// 定理二：判断顺序区间还是乱序区间，只需要对比 left 和 right 是否是顺序对即可，left <= right，顺序区间，否则乱序区间。
// 定理三：每次二分都会至少存在一个顺序区间。
public int Search(int[] nums, int target)
{
    if (nums.Length == 1)
    {
        return target == nums[0] ? 0 : -1;
    }

var left = 0;
    var right = nums.Length - 1;
    while (left <= right)
    {
        var mid = left + (right - left) / 2;
        var midValue = nums[mid];
        if (midValue == target)
        {
            return mid;
        }

//表面left =》mid递增 左边有序
        if (nums[left] <= midValue)
        {
            //target在left mid之间
            if (midValue > target && nums[left] <= target)
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        else //mid right递增 右边有序
        {
            // target在mid right之间
            if (midValue < target && nums[right] >= target)
            {
                left = mid + 1;
            }
            else
            {
                right = mid - 1;
            }
        }
    }

return -1;
}
```

---

-    螺旋矩阵 II-59
给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1：
![spiraln.jpg](https://tools.nxcloud.club:12500/images/2023/08/25/spiraln.jpg)
输入：n = 3
输出：[[1,2,3],[8,9,4],[7,6,5]]

---

```C#
public int[][] GenerateMatrix(int n)
{
    if (n == 1)
    {
        return new[] { new[] { 1 } };
    }

var result = new int[n][];
    for (var i = 0; i < n; i++)
    {
        result[i] = new int[n];
    }

var minRow = 0;
    var maxRow = n - 1;
    var minColumn = 0;
    var maxColumn = n - 1;
    int currentN = 1;
    var maxSize = n * n;
    while (currentN <= maxSize)
    {
        for (int i = minColumn; i <= maxColumn; i++)
        {
            result[minRow][i] = currentN++;
        }

minRow++;

for (int i = minRow; i <= maxRow; i++)
        {
            result[i][maxColumn] = currentN++;
        }

maxColumn--;

for (int i = maxColumn; i >= minColumn; i--)
        {
            result[maxRow][i] = currentN++;
        }

maxRow--;

for (int i = maxRow; i >= minRow; i--)
        {
            result[i][minColumn] = currentN++;
        }

minColumn++;
    }

return result;
}
```

---

-   旋转链表-61
给你一个链表的头节点 head ，旋转链表，将链表每个节点向右移动 k 个位置。
示例 1：
![roate2.jpg](https://tools.nxcloud.club:12500/images/2023/08/25/roate2.jpg)
输入：head = [0,1,2], k = 4
输出：[2,0,1]
提示：
链表中节点的数目在范围 [0, 500] 内
-100 <= Node.val <= 100
0 <= k <= 2 * 109

---

```C#
public ListNode RotateRight(ListNode head, int k)
{
    if (k == 0 || head == null || head.next == null)
    {
        return head;
    }

var maxCount = 0;
    var tempNode = head;
    ListNode lastNode = null;
    while (tempNode != null)
    {
        maxCount++;
        lastNode = tempNode;
        tempNode = tempNode.next;
    }

var count = k % maxCount;
    if (count == 0)
    {
        return head;
    }

var preCount = maxCount - count;
    var realHead = head;
    ListNode preRealHead = null;
    while (preCount > 0)
    {
        preRealHead = realHead;
        realHead = realHead.next;
        preCount--;
    }

preRealHead.next = null;
    lastNode.next = head;
    return realHead;
}
```

---

-    合并两个有序数组-88
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

---

```C#
public void Merge(int[] nums1, int m, int[] nums2, int n)
{
    if (n == 0)
    {
        return;
    }

if (m == 0)
    {
        Array.Copy(nums2, nums1, n);
        return;
    }

// Console.WriteLine(nums1);
}

public void Merge2(int[] nums1, int m, int[] nums2, int n)
{
    if (n == 0)
    {
        return;
    }

if (m == 0)
    {
        Array.Copy(nums2, nums1, n);
        return;
    }

Console.WriteLine(nums1);
}
```

---

-   汇总区间-228
给定一个  无重复元素 的 有序 整数数组 nums 。
返回 恰好覆盖数组中所有数字 的 最小有序 区间范围列表 。也就是说，nums 的每个元素都恰好被某个区间范围所覆盖，并且不存在属于某个范围但不属于 nums 的数字 x 。
列表中的每个区间范围 [a,b] 应该按如下格式输出：
"a->b" ，如果 a != b
"a" ，如果 a == b
示例 1：
输入：nums = [0,1,2,4,5,7]
输出：["0->2","4->5","7"]
解释：区间范围是：
[0,2] --> "0->2"
[4,5] --> "4->5"
[7,7] --> "7"

---

```C#
public IList<string> SummaryRanges(int[] nums)
{
    var result = new List<string>();
    if (nums.Length == 0)
    {
        return result;
    }

if (nums.Length == 1)
    {
        result.Add($"{nums[0]}");
        return result;
    }

long firstNum = nums[0];
    long secondNum = firstNum - 1;
    for (var i = 1; i < nums.Length; i++)
    {
        var v = nums[i];
        if (firstNum > secondNum)
        {
            if (firstNum + 1 == v)
            {
                secondNum = v;
            }
            else
            {
                result.Add($"{firstNum}");
                firstNum = v;
                secondNum = v - 1;
            }
        }
        else
        {
            if (secondNum + 1 == v)
            {
                secondNum = v;
            }
            else
            {
                result.Add($"{firstNum}->{secondNum}");
                firstNum = v;
                secondNum = v - 1;
            }
        }
    }

if (firstNum > secondNum)
    {
        result.Add($"{firstNum}");
    }
    else
    {
        result.Add($"{firstNum}->{secondNum}");
    }

return result;
}

public IList<string> SummaryRanges2(int[] nums)
{
    var result = new List<string>();
    for (int i = 0, j, n = nums.Length; i < n; i = j + 1)
    {
        var first = nums[i];
        j = i;
        while (j + 1 < n && nums[j + 1] == nums[j] + 1)
        {
            ++j;
        }

result.Add(i == j ? $"{first}" : $"{first}->{nums[j]}");
    }

return result;
}
```

---

-   格雷编码-89
n 位格雷码序列 是一个由 2n 个整数组成的序列，其中：
每个整数都在范围 [0, 2n - 1] 内（含 0 和 2n - 1）
第一个整数是 0
一个整数在序列中出现 不超过一次
每对 相邻 整数的二进制表示 恰好一位不同 ，且
第一个 和 最后一个 整数的二进制表示 恰好一位不同
给你一个整数 n ，返回任一有效的 n 位格雷码序列 。
示例 1：
输入：n = 2
输出：[0,1,3,2]
解释：
[0,1,3,2] 的二进制表示是 [00,01,11,10] 。
- 00 和 01 有一位不同
- 01 和 11 有一位不同
- 11 和 10 有一位不同
- 10 和 00 有一位不同
[0,2,3,1] 也是一个有效的格雷码序列，其二进制表示是 [00,10,11,01] 。
- 00 和 10 有一位不同
- 10 和 11 有一位不同
- 11 和 01 有一位不同
- 01 和 00 有一位不同

---

![Snip20230827_28.png](https://tools.nxcloud.club:12500/images/2023/08/27/Snip20230827_28.png)

---

```C#
private List<int> __result;
private int __length;
private int __n;
private List<int> __default;

public IList<int> GrayCode(int n)
{
    __result = new List<int>();
    __length = (int)Math.Pow(2, n);

__n = n;
    __default = new List<int>();
    for (int i = 0; i < n; i++)
    {
        __default.Add(1 << i);
    }

__Help(0, new List<int>() { 0 });
    return __result;
}

private void __Help(int value, List<int> result)
{
    if (result.Count == __length)
    {
        if (__default.Contains(result[__length - 1]))
        {
            __result = new List<int>(result);
        }

return;
    }

for (var i = 0; i < __n; i++)
    {
        if (__result.Count == __length)
        {
            return;
        }

var newValue = value | __default[i];
        if (newValue == value)
        {
            //111*010=====>101
            var t = (__length - 1) ^ __default[i];
            //011&101 => 
            newValue = value & t;
        }

if (result.Contains(newValue))
        {
            continue;
        }

result.Add(newValue);
        __Help(newValue, result);
        result.Remove(newValue);
    }
}

public IList<int> GrayCode2(int n)
{
    var result = new List<int>();
    __n = n;
    __Dfs(result, 0, 0, 0);
    return result;
}

private void __Dfs(List<int> result, int parentNum, int depth, int isLeft)
{
    if (depth == __n)
    {
        result.Add(parentNum);
        return;
    }

__Dfs(result, (parentNum << 1) | isLeft, depth + 1, 0);
    __Dfs(result, (parentNum << 1) | isLeft ^ 1, depth + 1, 1);
}
```

---

-   只出现一次的数字-136
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
提示：
1 <= nums.length <= 3 * 104
-3 * 104 <= nums[i] <= 3 * 104
除了某个元素只出现一次以外，其余每个元素均出现两次。

---
```C#
public int SingleNumber(int[] nums)
{
    var result = 0;
    foreach (var v in nums)
    {
        /*
        由异或满足分配律，结合律和分配律，以及0^0=0,0^a=a,a^a=0
        将所有元素异或，最终得到不同的元素
     */
        result ^= v;
    }

return result;
}
```
---

-   环形链表-141
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
示例 1：
![circularlinkedlist.png](https://tools.nxcloud.club:12500/images/2023/08/27/circularlinkedlist.png)
输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。

---
```C#
public bool HasCycle(ListNode head)
{
    if (head == null || head.next == null)
    {
        return false;
    }

var p1 = head;
    var p2 = head.next;
    while (true)
    {
        if (p2 == null)
        {
            return false;
        }

if (p1 == p2)
        {
            return true;
        }

p1 = p1.next;
        p2 = p2.next?.next;
    }
}
```
---

-   环形链表 II-142
给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
示例 1：
![circularlinkedlist.png](https://tools.nxcloud.club:12500/images/2023/08/27/circularlinkedlist.png)
输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点
解释：链表中有一个环，其尾部连接到第二个节点。

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

```C#
public ListNode DetectCycle(ListNode head)
{
    var fast = head;
    var slow = head;
    //f=2s  fast 每轮走2步
    //f=s+nb  双指针都走过a步，然后在环内绕圈直到重合，重合时fast比slow多走环的长度整数倍
    //s=nb
    while (true)
    {
        if (fast == null || fast.next == null)
        {
            return null;
        }

fast = fast.next.next;
        slow = slow.next;
        if (fast == slow)
        {
            break;
        }
    }

// 如果让指针从链表头部一直向前走并统计步数k，那么所有走到链表入口节点时的步数是：k = a + nb ，
    // 即先走a步到入口节点，之后每绕1圈环（b步）都会再次到入口节点。而目前 slow 指针走了 nb 步。
    // 因此，我们只要想办法让 slow 再走 a 步停下来，就可以到环的入口。

fast = head;
    while (fast != slow)
    {
        fast = fast.next;
        slow = slow.next;
    }

return fast;
}
```

---

-   排序链表-148
给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
示例 1：
![sort_list_1.jpg](https://tools.nxcloud.club:12500/images/2023/08/28/sort_list_1.jpg)
输入：head = [4,2,1,3]
输出：[1,2,3,4]

---

```C#
class ListNodeCompare : IComparer<ListNode>
{
    public int Compare(ListNode x, ListNode y)
    {
        if (x == null)
        {
            return -1;
        }

if (y == null)
        {
            return 1;
        }

return x.val > y.val ? 1 : -1;
    }
}

//堆排序
public ListNode SortList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

var queue = new PriorityQueue<ListNode, ListNode>(new ListNodeCompare());
    var q = head;
    while (q != null)
    {
        queue.Enqueue(q, q);
        q = q.next;
    }

var dummy = new ListNode(-1);
    var current = dummy;
    while (queue.Count > 0)
    {
        current.next = queue.Dequeue();
        current = current.next;
    }

current.next = null;

return dummy.next;
}

//冒泡排序
public ListNode BubbleSortList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

return dummy.next;
}

//插入排序
public ListNode InsertSortList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

var dummy = new ListNode(-1)
    {
        next = head
    };
    var current = head.next;
    //已经拍好序，最后指向null
    head.next = null;
    while (current != null)
    {
        var nextCurrent = current.next;
        var pt = dummy;
        var t = dummy.next;
        while (t != null && t.val < current.val)
        {
            pt = t;
            t = t.next;
        }

//前一个指向当前值
        pt.next = current;
        // 当前值指向下一个
        current.next = t;

current = nextCurrent;
    }

return dummy.next;
}

//选择排序
public ListNode SelectionSortList(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

var dummy = new ListNode(-1);
    var currentDummy = dummy;
    var top = head;
    while (top != null)
    {
        ListNode minPre = null;
        var min = top;
        var current = top.next;
        var currentPre = top;
        while (current != null)
        {
            if (current.val < min.val)
            {
                min = current;
                minPre = currentPre;
            }

currentPre = current;
            current = current.next;
        }

if (min == top)
        {
            top = top.next;
        }
        else
        {
            minPre.next = min.next;
        }

currentDummy.next = min;
        currentDummy = currentDummy.next;
        currentDummy.next = null;
    }

return dummy.next;
}

//归并排序自顶向下
public ListNode SortList2(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

return __Divided(head);
}

private ListNode __Divided(ListNode left)
{
    if (left == null || left.next == null)
    {
        return left;
    }

var slow = left;
    var fast = left.next;
    while (fast != null && fast.next != null)
    {
        slow = slow.next;
        fast = fast.next.next;
    }

var mid = slow.next;
    slow.next = null;
    var l = __Divided(left);
    var r = __Divided(mid);
    return __Merge(l, r);
}

private ListNode __Merge(ListNode left, ListNode right)
{
    var dummy = new ListNode(-1);
    var current = dummy;
    while (left != null && right != null)
    {
        if (left.val < right.val)
        {
            current.next = left;
            left = left.next;
        }
        else
        {
            current.next = right;
            right = right.next;
        }

current = current.next;
        current.next = null;
    }

current.next = left != null ? left : right;
    return dummy.next;
}

//归并排序，自底向上
public ListNode SortList3(ListNode head)
{
    if (head == null || head.next == null)
    {
        return head;
    }

var p = head;
    var length = 0;
    while (p != null)
    {
        p = p.next;
        length++;
    }

var dummy = new ListNode(-1)
    {
        next = head
    };
    for (var subLength = 1; subLength < length; subLength <<= 1)
    {
        var pre = dummy;
        var current = pre.next;
        while (current != null)
        {
            var first = current;
            for (var i = 0; i < subLength - 1 && current.next != null; i++)
            {
                current = current.next;
            }

var second = current.next;
            current.next = null;
            current = second;

for (int i = 0; i < subLength - 1 && current != null && current.next != null; i++)
            {
                current = current.next;
            }

ListNode next = null;
            if (current != null)
            {
                next = current.next;
                current.next = null;
            }

current = next;

var merge = __Merge(first, second);
            pre.next = merge;
            while (pre.next != null)
            {
                pre = pre.next;
            }
        }
    }

return dummy.next;
}
```

---

-   最小栈-155
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int val) 将元素val推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。
示例 1:
输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

---

```C#
public class MinStack
{
    private Stack<int> __values;
    private Stack<int> __minValues;

public MinStack()
    {
        __values = new Stack<int>();
        __minValues = new Stack<int>();
    }

public void Push(int val)
    {
        __values.Push(val);
        if (__minValues.Count > 0)
        {
            var currentMin = __minValues.Peek();
            __minValues.Push(currentMin < val ? currentMin : val);
        }
        else
        {
            __minValues.Push(val);
        }
    }

public void Pop()
    {
        if (__values.Count > 0)
        {
            __values.Pop();
            __minValues.Pop();
        }
    }

public int Top()
    {
        if (__values.Count > 0)
        {
            return __values.Peek();
        }

return -1;
    }

public int GetMin()
    {
        if (__minValues.Count > 0)
        {
            return __minValues.Peek();
        }

return -1;
    }
}
```

---

-   相交链表-160
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
图示两个链表在节点 c1 开始相交：
![160_statement.png](https://tools.nxcloud.club:12500/images/2023/08/28/160_statement.png)
题目数据 保证 整个链式结构中不存在环。
注意，函数返回结果后，链表必须 保持其原始结构 。
提示：
listA 中节点数目为 m
listB 中节点数目为 n
1 <= m, n <= 3 * 104
1 <= Node.val <= 105
0 <= skipA <= m
0 <= skipB <= n
如果 listA 和 listB 没有交点，intersectVal 为 0
如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]

---

```C#
public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
    if (headA == null || headB == null)
    {
        return null;
    }

var tempA = headA;
    var tempB = headB;

while (tempA != tempB)
    {
        tempA = tempA == null ? headB : tempA.next;
        tempB = tempB == null ? headA : tempB.next;
    }

return tempA;
}
```
---

-   多数元素-169
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]
输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]
输出：2
提示：
n == nums.length
1 <= n <= 5 * 104
-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题

---
```C#
public int MajorityElement(int[] nums)
{
    var chooseValue = nums[0];
    var chooseNum = 1;
    for (var i = 1; i < nums.Length; i++)
    {
        if (chooseNum == 0)
        {
            chooseValue = nums[i];
            chooseNum = 1;
        }
        else
        {
            if (chooseValue == nums[i])
            {
                chooseNum++;
            }
            else
            {
                chooseNum--;
            }
        }
    }

return chooseValue;
}
```
---

-   反转链表-206
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
![rev1ex1.jpg](https://tools.nxcloud.club:12500/images/2023/08/28/rev1ex1.jpg)
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

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

ListNode pre = null;
    var current = head;
    while (current.next != null)
    {
        var tempNext = current.next;
        current.next = pre;
        pre = current;
        current = tempNext;
    }

current.next = pre;
    return current;
}
```
---

-   除自身以外数组的乘积-238
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums = [1,2,3,4]
输出: [24,12,8,6]
提示：
2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内

---
```C#
public int[] ProductExceptSelf(int[] nums)
{
    var result = new int[nums.Length];
    result[0] = 1;
    //1,2,3,4
    //1,1,2,6
    for (int i = 1; i < nums.Length; i++)
    {
        result[i] = result[i - 1] * nums[i - 1];
    }

// 24,12,4,1
    var lastValue = 1;
    for (int i = nums.Length - 2; i >= 0; i--)
    {
        lastValue *= nums[i + 1];
        result[i] *= lastValue;
    }

return result;
}
```
---