0704学习

agile Posted on Jul 4 2023

面试 leetcode学习

-   剑指 Offer 04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

---

```C#
//转为二叉树（类似树的思想）
public bool FindNumberIn2DArray(int[][] matrix, int target)
{
    var iLength = matrix.Length - 1;
    if (iLength < 0)
    {
        return false;
    }

return false;
}

private int __row;
private int __column;
private int[][] __matrix;
private int __target;

//递归
public bool FindNumberIn2DArray2(int[][] matrix, int target)
{
    __row = matrix.Length;
    if (__row == 0)
    {
        return false;
    }

__column = matrix[0].Length;
    __matrix = matrix;
    __target = target;
    return __Help(0, __column - 1);
}

private bool __Help(int x, int y)
{
    if (x >= __row || y < 0)
    {
        return false;
    }

if (__matrix[x][y] > __target)
    {
        return __Help(x, y - 1);
    }

if (__matrix[x][y] < __target)
    {
        return __Help(x + 1, y);
    }

return true;
}
```

---

-   剑指 Offer 11. 旋转数组的最小数字
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
给你一个可能存在 重复 元素值的数组 numbers ，它原来是一个升序排列的数组，并按上述情形进行了一次旋转。请返回旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一次旋转，该数组的最小值为 1。  
注意，数组 [a[0], a[1], a[2], ..., a[n-1]] 旋转一次 的结果为数组 [a[n-1], a[0], a[1], a[2], ..., a[n-2]] 。

---

```C#
public int MinArray(int[] numbers)
{
    var length = numbers.Length;
    var left = 0;
    var right = length - 1;
    while (left < right)
    {
        var mid = left + (right - left) / 2;
        if (numbers[mid] > numbers[right])
        {
            left = mid + 1;
        }
        else if (numbers[mid] < numbers[right])
        {
            right = mid;
        }
        else
        {
            right = mid - 1;
        }
    }

return numbers[left];
}
```

-   剑指 Offer 50. 第一个只出现一次的字符
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

---

```C#
public char FirstUniqChar(string s)
{
    var chars = new int[26];
    foreach (var c in s)
    {
        chars[c - 'a'] += 1;
    }

foreach (var c in s)
    {
        if (chars[c - 'a'] == 1)
        {
            return c;
        }
    }

return ' ';
}
```

---

-   剑指 Offer 32 - I. 从上到下打印二叉树

```C#
public int[] LevelOrder(TreeNode root)
{
    if (root == null)
    {
        return Array.Empty<int>();
    }

var result = new List<int>();
    var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    while (queue.Count > 0)
    {
        var size = queue.Count;
        for (var i = 0; i < size; i++)
        {
            var node = queue.Dequeue();
            result.Add(node.val);
            if (node.left != null)
            {
                queue.Enqueue(node.left);
            }

if (node.right != null)
            {
                queue.Enqueue(node.right);
            }
        }
    }

return result.ToArray();
}

public IList<IList<int>> LevelOrder2(TreeNode root)
{
    var list = new List<IList<int>>();
    if (root == null)
    {
        return list;
    }

var queue = new Queue<TreeNode>();
    queue.Enqueue(root);
    var flag = true;
    while (queue.Count > 0)
    {
        var size = queue.Count;
        var itemList = new int[size];
        for (var i = 0; i < size; i++)
        {
            var node = queue.Dequeue();
            if (flag)
            {
                itemList[i] = node.val;
            }
            else
            {
                itemList[size - 1 - i] = node.val;
            }

if (node.left != null)
            {
                queue.Enqueue(node.left);
            }

if (node.right != null)
            {
                queue.Enqueue(node.right);
            }
        }

flag = !flag;

list.Add(itemList);
    }

return list;
}
```

-   剑指 Offer 26. 树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)
B是A的子结构， 即 A中有出现和B相同的结构和节点值。

---

```C#
public bool IsSubStructure(TreeNode A, TreeNode B)
{
    if (A == null || B == null)
    {
        return false;
    }

if (__Help(A, B))
    {
        return true;
    }

return IsSubStructure(A.left, B) || IsSubStructure(A.right, B);
}

private bool __Help(TreeNode a, TreeNode b)
{
    if (a.val != b.val || a.left == null && b.left != null || a.right == null && b.right != null)
    {
        return false;
    }

var flag = true;
    if (a.left != null && b.left != null)
    {
        flag = __Help(a.left, b.left);
    }

if (flag && a.right != null && b.right != null)
    {
        flag = __Help(a.right, b.right);
    }

return flag;
}
```