0714学习

agile Posted on Jul 13 2023

面试 leetcode学习

-   剑指 Offer 57 - II. 和为 s 的连续正数序列
输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。
示例 1：
输入：target = 9
输出：[[2,3,4],[4,5]]
示例 2：
输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]
限制：
1 <= target <= 10^5

---

![WX20230713-1426502x.png](https://tools.nxcloud.club:12500/images/2023/07/13/WX20230713-1426502x.png)
![WX20230713-1427142x.png](https://tools.nxcloud.club:12500/images/2023/07/13/WX20230713-1427142x.png)
![1611495306-LsrxgS-Picture2.png](https://tools.nxcloud.club:12500/images/2023/07/13/1611495306-LsrxgS-Picture2.png)

---

```C#
//(j+1)j/2-(1+i-1)*(i-1)/2 = target
//j*j+j-i*i+i=2*target
public int[][] FindContinuousSequence(int target)
{
    var sequences = new List<int[]>();
    int i = 1;
    double j = 2.0;
    while (i < j)
    {
        j = (-1 + Math.Sqrt(1 + 4 * (long)(i * i) - 4 * i + 8 * target)) / 2;
        if (j == (int)j)
        {
            var jint = (int)j;
            int[] result = new int[jint - i + 1];
            for (int k = i; k <= jint; k++)
            {
                result[k - i] = k;
            }

sequences.Add(result);
        }

i++;
    }

return sequences.ToArray();
}

public int[][] FindContinuousSequence2(int target)
{
    var sequences = new List<int[]>();
    if (target <= 2)
    {
        return sequences.ToArray();
    }

int i = 1;
    var j = 2;
    var sum = 3;
    while (i < j)
    {
        if (sum == target)
        {
            var result = new int[j - i + 1];
            for (var k = i; k <= j; k++)
            {
                result[k - i] = k;
            }

sequences.Add(result);
        }

if (sum < target)
        {
            j++;
            sum += j;
        }
        else
        {
            sum -= i;
            i++;
        }
    }

return sequences.ToArray();
}
```

---

-   剑指 Offer 62. 圆圈中最后剩下的数字
0,1,···,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字（删除后从下一个数字开始计数）。求出这个圆圈里剩下的最后一个数字。
例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1：
输入: n = 5, m = 3
输出: 3
示例 2：
输入: n = 10, m = 17
输出: 2
限制：
1 <= n <= 10^5
1 <= m <= 10^6
[约瑟夫环问题](https://note.nxcloud.club:12270/blog/post/agile/%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF%E9%97%AE%E9%A2%98)

---

```C#
public int LastRemaining(int n, int m)
{
    if (m == 1)
    {
        return n - 1;
    }

var list = new List<int>();
    for (var i = 0; i < n; i++)
    {
        list.Add(i);
    }

var index = 0;
    while (list.Count > 1)
    {
        index = (index + m - 1) % list.Count;
        list.RemoveAt(index);
    }

return list[0];
}

public int LastRemaining2(int n, int m)
{
    var x = 0;
    for (var i = 2; i <= n; i++)
    {
        x = (x + m) % i;
    }

return x;
}

// f(n,m)=(f(n-1,m)+m)%n
// f(10,3)=(f(9,3)+3)%10
// f(9,3)=(f(8,3)+3)%9
// ……
// f(2,3)=(f(1,3)+3)%2
// f(1,3)=0
public int LastRemaining3(int n, int m)
{
    if (n == 1)
    {
        return 0;
    }

return (LastRemaining3(n - 1, m) + m) % n;
}
```

---

-   剑指 Offer 29. 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字。

---

```C#
public int[] SpiralOrder(int[][] matrix)
{
    var row = matrix.Length;
    if (row <= 0)
    {
        return Array.Empty<int>();
    }

var column = matrix[0].Length;
    if (column <= 0)
    {
        return Array.Empty<int>();
    }

var spiralArray = new int[row * column];
    var minRowIndex = 0;
    var maxRowIndex = row - 1;
    var minColumnIndex = 0;
    var maxColumnIndex = column - 1;
    var index = 0;
    while (index < spiralArray.Length)
    {
        if (index < spiralArray.Length)
        {
            for (int i = minColumnIndex; i <= maxColumnIndex; i++)
            {
                spiralArray[index++] = matrix[minRowIndex][i];
            }

minRowIndex++;
        }

if (index < spiralArray.Length)
        {
            for (int i = minRowIndex; i <= maxRowIndex; i++)
            {
                spiralArray[index++] = matrix[i][maxColumnIndex];
            }

maxColumnIndex--;
        }

if (index < spiralArray.Length)
        {
            for (int i = maxColumnIndex; i >= minColumnIndex; i--)
            {
                spiralArray[index++] = matrix[maxRowIndex][i];
            }

maxRowIndex--;
        }

if (index < spiralArray.Length)
        {
            for (int i = maxRowIndex; i >= minRowIndex; i--)
            {
                spiralArray[index++] = matrix[i][minColumnIndex];
            }

minColumnIndex++;
        }
    }

return spiralArray;
}
```

-   剑指 Offer 31. 栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如，序列 {1,2,3,4,5} 是某栈的压栈序列，序列 {4,5,3,2,1} 是该压栈序列对应的一个弹出序列，但 {4,3,5,1,2} 就不可能是该压栈序列的弹出序列。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1

---

示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。

---

提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。

---

![WX20230713-1924522x.png](https://tools.nxcloud.club:12500/images/2023/07/13/WX20230713-1924522x.png)

---

```C#
//pushed数组有两个指针，一个指向top顶端，一个指向将要插入序列，popped有一个指针，表示当前遍历到需要pop的数值，每次都是通过比较top指针和popped指针指向的值
public bool ValidateStackSequences(int[] pushed, int[] popped)
{
    if (pushed.Length == 0)
    {
        return true;
    }

pushed[++topIndex] = pushed[pushedArrayIndex++];
        }
    }

return true;
}
```
---