第一天

剑指 Offer 09. 用两个栈实现队列

题解

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.AppendTail(value);
 * int param_2 = obj.DeleteHead();
 */
public class CQueue
{
    private Stack<int> _a, _b;

    public CQueue()
    {
        _a = new Stack<int>();
        _b = new Stack<int>();
    }

    public void AppendTail(int value)
    {
        _a.Push(value);
    }

    public int DeleteHead()
    {
        if (_b.Count > 0)
            return _b.Pop();
        if (_a.Count == 0)
            return -1;
        while (_a.Count > 0)
            _b.Push(_a.Pop());
        return _b.Pop();
    }
}

后记

没什么，经典双栈拼接队列。

剑指 Offer 30. 包含min函数的栈 - 力扣（LeetCode）

题解

public class MinStack
{
    private Stack<int> _a, _minStack;

    /** initialize your data structure here. */
    public MinStack()
    {
        _a = new Stack<int>();
        _minStack = new Stack<int>();
    }


    public void Push(int x)
    {
        _a.Push(x);
        if (_minStack.Count == 0 || _minStack.Peek() >= x)
            _minStack.Push(x);
    }

    public void Pop()
    {
        if (_a.Pop() == _minStack.Peek())
        {
            _minStack.Pop();
        }
    }

    public int Top()
    {
        return _a.Peek();
    }

    public int Min()
    {
        return _minStack.Peek();
    }
}

后记

其实这个玩意最好还是直接记录一下，但是感觉没必要。

第二天

剑指 Offer 06. 从尾到头打印链表 - 力扣（LeetCode）

题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution
{
    private Stack<int> _stack = new Stack<int>();

    public int[] ReversePrint(ListNode head)
    {
        while (head != null)
        {
            _stack.Push(head.val);
            head = head.next;
        }

        int[] res = new int[_stack.Count];
        for (int i = 0; i < res.Length; i++)
            res[i] = _stack.Pop();
        return res;
    }
}

后记

最大的难点居然是有人Length拼了四次才拼对。

剑指 Offer 24. 反转链表 - 力扣（LeetCode）

题解

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur != null)
        {
            ListNode temp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = temp;
        }
        return pre;
    }
}

后记

我是废物！

剑指 Offer 35. 复杂链表的复制 - 力扣（LeetCode）

题解

哈希表 + 迭代

/*
// Definition for a Node.
public class Node {
    public int val;
    public Node next;
    public Node random;
    
    public Node(int _val) {
        val = _val;
        next = null;
        random = null;
    }
}
*/

public class Solution
{
    private Dictionary<Node, Node> _nodeDic;

    public Node CopyRandomList(Node head)
    {
        _nodeDic = new Dictionary<Node, Node>();

        if (head == null)
        {
            return null;
        }

        Node tempNode = head;

        while (tempNode != null)
        {
            _nodeDic.Add(tempNode, new Node(tempNode.val));
            tempNode = tempNode.next;
        }

        tempNode = head;
        while (tempNode != null)
        {
            if (tempNode.next != null)
                _nodeDic[tempNode].next = _nodeDic[tempNode.next];
            if (tempNode.random != null)
                _nodeDic[tempNode].random = _nodeDic[tempNode.random];
            tempNode = tempNode.next;
        }

        return _nodeDic[head];
    }
}

拼接 + 拆分

    public Node CopyRandomList(Node head)
    {
        if (head == null)
            return null;

        Node tempNode = head;
        while (tempNode != null)
        {
            Node temp = new Node(tempNode.val);
            temp.next = tempNode.next;
            tempNode.next = temp;

            tempNode = tempNode.next.next;
        }

        tempNode = head;
        while (tempNode != null)
        {
            if (tempNode.random != null)
                tempNode.next.random = tempNode.random.next;
            tempNode = tempNode.next.next;
        }

        Node cur = head.next;
        Node res = head.next;
        tempNode = head;

        while (cur.next != null)
        {
            tempNode.next = cur.next;
            cur.next = cur.next.next;

            cur = cur.next;
            tempNode = tempNode.next;
        }

        tempNode.next = null;
        return res;
    }
}

后记

第一种解法偏常规，主要需要判空。

第二种解法你会发现题目十分阴间，比如37行的tempNode.next = null，如果没有这一句话，该题目错误。因为你必须还原原链表，但是我明明只需要返回新链表啊！！你怎么能检测原链表啊！！！你是怎么做到的啊。第二种解法还是需要多看看。

第三天

剑指 Offer 05. 替换空格 - 力扣（LeetCode）

硬写

public class Solution
{
    public string ReplaceSpace(string s)
    {
        StringBuilder sb = new StringBuilder();
        foreach (char c in s)
        {
            if (c == ' ')
                sb.Append("%20");
            else
                sb.Append(c);
        }

        return sb.ToString();
    }
}

后记

没什么东西，标准题解的语言中大部分没有可变字符串。我是懒鬼，我选择可变。

剑指 Offer 58 - II. 左旋转字符串 - 力扣（LeetCode）

硬写

public class Solution
{
    public string ReverseLeftWords(string s, int n)
    {
        StringBuilder sb = new StringBuilder();
        for (int i = n; i < n + s.Length; i++)
        {
            sb.Append(s[i % s.Length]);
        }

        return sb.ToString();
    }
}

后记

sb yyds。

第四天

剑指 Offer 03. 数组中重复的数字 - 力扣（LeetCode）

题解

public class Solution
{
    public int FindRepeatNumber(int[] nums)
    {
        int i = 0;
        while (i < nums.Length)
        {
            // 当前索引满足条件
            if (nums[i] == i)
            {
                i++;
                continue;
            }

            if (nums[nums[i]] == nums[i])
                return nums[i];
            (nums[nums[i]], nums[i]) = (nums[i], nums[nums[i]]);
        }

        return 0;
    }
}

后记

想笑啊。排行最优的算法是桶排序。

剑指 Offer 53 - I. 在排序数组中查找数字 I - 力扣（LeetCode）

题解

public class Solution {
    public int Search(int[] nums, int target) {
        int left = 0, right = nums.Length - 1;
        while(left <= right)
        {
            int mid = right - (right - left) / 2;
            if(nums[mid] <= target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        int resRight = left;
        if(right >= 0 && nums[right] != target)
            return 0;
        left = 0;
        right = nums.Length - 1;
        while(left <= right)
        {
            int mid = right - (right - left) / 2;
            if(nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }

        int resLeft = right;
        return resRight - resLeft - 1;
    }
}

后记

二分好难啊。但是？这玩意在leetcode不如一句return nums.Count(num => num == target);，Linq太强啦呜呜呜。

剑指 Offer 53 - II. 0～n-1中缺失的数字 - 力扣（LeetCode）

题解

public class Solution
{
    public int MissingNumber(int[] nums)
    {
        int left = 0, right = nums.Length - 1;
        while (left <= right)
        {
            int mid = right - (right - left) / 2;
            if (nums[mid] == mid)
                left = mid + 1;
            else
                right = mid - 1;
        }

        return left;
    }
}

后记

最快的还是暴力，我想笑啊。

第五天

剑指 Offer 04. 二维数组中的查找 - 力扣（LeetCode）

题解

public class Solution
{
    public bool FindNumberIn2DArray(int[][] matrix, int target)
    {
        if (matrix == null || matrix.Length == 0)
            return false;

        int x = 0;
        int y = matrix[0].Length - 1;

        while (x < matrix.Length && y >= 0)
        {
            if (matrix[x][y] == target)
                return true;
            else if (matrix[x][y] < target)
                x++;
            else
                y--;
        }

        return false;
    }
}

后记

我好烦判空啊！

剑指 Offer 11. 旋转数组的最小数字 - 力扣（LeetCode）

题解

public class Solution
{
    public int MinArray(int[] numbers)
    {
        int left = 0;
        int right = numbers.Length - 1;

        while (left < right)
        {
            int mid = left - (left - right) / 2;

            if (numbers[mid] < numbers[right])
            {
                right = mid;
            }
            else if (numbers[mid] > numbers[right])
            {
                left = mid + 1;
            }
            else
            {
                right--;
            }
        }

        return numbers[left];
    }
}

后记

呜呜呜，我真的不会二分。

剑指 Offer 50. 第一个只出现一次的字符 - 力扣（LeetCode）

题解

public class Solution {
    public char FirstUniqChar(string s) {
        if (s.Length != 0) {
            Dictionary<char, bool> dic = new Dictionary<char, bool>();
            foreach(char c in s) {
                if (dic.ContainsKey(c)) 
                    dic[c] = false;
                else 
                    dic.Add(c, true);
            }
            foreach (var d in dic)
            {
                if (d.Value) 
                    return d.Key;
            }
        }
        return ' ';
    }
}

后记

没什么，感觉不如原神。

第六天

剑指 Offer 32 - I. 从上到下打印二叉树 - 力扣（LeetCode）

题解

public class Solution
{
    public int[] LevelOrder(TreeNode root)
    {
        if (root == null)
            return new int[0];

        Queue<TreeNode> treeNodes = new Queue<TreeNode>();
        List<int> res = new List<int>();
        treeNodes.Enqueue(root);
        while (treeNodes.Count > 0)
        {
            TreeNode now = treeNodes.Dequeue();
            res.Add(now.val);
            if (now.left != null)
                treeNodes.Enqueue(now.left);
            if (now.right != null)
                treeNodes.Enqueue(now.right);
        }

        return res.ToArray();
    }
}

后记

treeNodes.Enqueue(root); 添加元素

treeNodes.Dequeue(); 取出元素

狠狠牢记API

剑指 Offer 32 - II. 从上到下打印二叉树 II - 力扣（LeetCode）

题解

public class Solution
{
    public IList<IList<int>> LevelOrder(TreeNode root)
    {
        var ans = new List<IList<int>>();
        if (root == null) return ans;
        var q = new Queue<TreeNode>();
        q.Enqueue(root);
        while (q.Count > 0)
        {
            var level = new List<int>();
            for (int cnt = q.Count; cnt > 0; cnt--)
            {
                var cur = q.Dequeue();
                level.Add(cur.val);
                if (cur.left != null) q.Enqueue(cur.left);
                if (cur.right != null) q.Enqueue(cur.right);
            }

            ans.Add(level);
        }

        return ans;
    }
}

后记

这个BFS有点意思啊。

剑指 Offer 32 - III. 从上到下打印二叉树 III - 力扣（LeetCode）

题解

public class Solution
{
    public IList<IList<int>> LevelOrder(TreeNode root)
    {
        List<IList<int>> list = new List<IList<int>>();
        Queue<TreeNode> queue = new Queue<TreeNode>();
        if (root != null)
        {
            queue.Enqueue(root);
        }

        while (queue.Count > 0)
        {
            List<int> tempList = new List<int>();
            int count = queue.Count;
            for (int i = 0; i < count; i++)
            {
                TreeNode tree = queue.Dequeue();
                if (list.Count % 2 == 0)
                {
                    tempList.Add(tree.val);
                }
                else
                {
                    tempList.Insert(0, tree.val);
                }

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

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

            list.Add(tempList);
        }

        return list;
    }
}

后记

其实今天这几个题，都是BFS。。。

第七天

剑指 Offer 26. 树的子结构 - 力扣（LeetCode）

题解

public class Solution {
    public bool IsSubStructure(TreeNode A, TreeNode B)
    {
        if (A == null || B == null)
            return false;
        return Helper(A, B) || IsSubStructure(A.left, B) || IsSubStructure(A.right, B);
    }

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

后记

怎么又是搜索。

剑指 Offer 27. 二叉树的镜像 - 力扣（LeetCode）

题解

public class Solution
{
    public TreeNode MirrorTree(TreeNode root)
    {
        if (root == null)
            return null;
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.Push(root);
        while (stack.Count > 0)
        {
            var nowRoot = stack.Pop();
            if (nowRoot.left != null)
                stack.Push(nowRoot.left);
            if (nowRoot.right != null)
                stack.Push(nowRoot.right);

            (nowRoot.left, nowRoot.right) = (nowRoot.right, nowRoot.left);
        }

        return root;
    }
}

后记

突然发现自己雀氏老了

剑指 Offer 28. 对称的二叉树 - 力扣（LeetCode）

题解

public class Solution
{
    public bool IsSymmetric(TreeNode root)
    {
        if (root == null) return true;
        return (Helper(root.left, root.right));
    }

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

后记

麻，我真的不喜欢递归。

第八天

剑指 Offer 10- I. 斐波那契数列 - 力扣（LeetCode）

题解

public class Solution
{
    public int Fib(int n)
    {
        int a = 0, b = 1, sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }

        return a;
    }
}

后记

递归会爆。

剑指 Offer 10- II. 青蛙跳台阶问题 - 力扣（LeetCode）

题解

public class Solution
{
    public int NumWays(int n)
    {
        int a = 1, b = 1, sum = 0;
        for (int i = 0; i < n; i++)
        {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }

        return a;
    }
}

后记

和上面一模一样。

剑指 Offer 63. 股票的最大利润 - 力扣（LeetCode）

题解

public class Solution
{
    public int MaxProfit(int[] prices)
    {
        int res = 0;
        int cost = int.MaxValue;

        foreach (var price in prices)
        {
            if (price < cost)
                cost = price;
            else if (res < price - cost)
                res = price - cost;
        }

        return res;
    }
}

后记

这题为什么要说是DP（我感觉不来啊）

第九天

剑指 Offer 42. 连续子数组的最大和 - 力扣（LeetCode）

题解

public class Solution
{
    public int MaxSubArray(int[] nums)
    {
        int[] dp = new int[nums.Length];
        int res = int.MinValue;
        for (int i = 0; i < nums.Length; i++)
        {
            if (i == 0)
                dp[i] = nums[i];
            else
                dp[i] = Math.Max(nums[i], dp[i - 1] + nums[i]);

            if (res < dp[i])
                res = dp[i];
        }

        return res;
    }
}

后记

dp[i]具体为以i结尾的子数组和最大值。

剑指 Offer 47. 礼物的最大价值 - 力扣（LeetCode）

题解

public class Solution
{
    public int MaxValue(int[][] grid)
    {
        if (grid == null)
            return 0;
        int[,] dp = new int[grid.Length, grid[0].Length];
        for (int i = 0; i < grid.Length; i++)
        {
            for (int j = 0; j < grid[0].Length; j++)
            {
                if (i == 0 && j == 0)
                    dp[i, j] = grid[i][j];
                else if (i == 0 && j != 0)
                    dp[i, j] = dp[i, j - 1] + grid[i][j];
                else if (i != 0 && j == 0)
                    dp[i, j] = dp[i - 1, j] + grid[i][j];
                else
                    dp[i, j] = Math.Max(dp[i, j - 1], dp[i - 1, j]) + grid[i][j];
            }
        }

        return dp[grid.Length - 1, grid[0].Length - 1];
    }
}

后记

我的礼物呢。

第十天

剑指 Offer 46. 把数字翻译成字符串 - 力扣（LeetCode）

题解

public class Solution
{
    public int TranslateNum(int num)
    {
        string numStr = num.ToString();
        int a = 1, b = 1;
        int c = 0;
        for (int i = 1; i < numStr.Length; i++)
        {
            int number = int.Parse(numStr.Substring(i - 1, 2));
            if (number is >= 10 and <= 25)
                c = a + b;
            else
                c = b;

            a = b;
            b = c;
        }

        return b;
    }
}

后记

翻译个羁绊。

剑指 Offer 48. 最长不含重复字符的子字符串 - 力扣（LeetCode）

题解

public class Solution
{
    public int LengthOfLongestSubstring(string s)
    {
        var set = new HashSet<char>();
        int ans = 0;
        for (int l = 0, r = 0; r < s.Length; r++)
        {
            while (set.Contains(s[r]))
            {
                set.Remove(s[l++]);
            }

            ans = Math.Max(r - l + 1, ans);
            set.Add(s[r]);
        }

        return ans;
    }
}

后记

DP？给我双指针！

第十一天

剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode）

题解

public class Solution
{
    public ListNode DeleteNode(ListNode head, int val)
    {
        if (head == null)
            return null;
        if (head.val == val)
            return head.next;
        ListNode pre = head;
        ListNode now = head.next;
        while (now != null)
        {
            if (now.val == val)
            {
                pre.next = now.next;
                break;
            }

            pre = now;
            now = now.next;
        }

        return head;
    }
}

后记

啊啊啊啊，我想睡觉。

剑指 Offer 22. 链表中倒数第k个节点 - 力扣（LeetCode）

题解

public class Solution {
    public ListNode GetKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode now = head;
        for (int i = 0; i < k; fast = fast.next, i++)
        {
            if (fast == null)
                return null;
        }

        while (fast != null)
        {
            now = now.next;
            fast = fast.next;
        }

        return now;
    }
}

后记

睡觉拉。

第十二天

剑指 Offer 25. 合并两个排序的链表 - 力扣（LeetCode）

题解

public class Solution
{
    public ListNode MergeTwoLists(ListNode l1, ListNode l2)
    {
        ListNode preHead = new ListNode(10086);
        ListNode now = preHead;

        while (l1 != null && l2 != null)
        {
            if (l1.val < l2.val)
            {
                now.next = l1;
                l1 = l1.next;
            }
            else
            {
                now.next = l2;
                l2 = l2.next;
            }

            now = now.next;
        }

        if (l1 == null)
            now.next = l2;
        else
            now.next = l1;
        return preHead.next;
    }
}

后记

突然感觉难度降低了好多。

面试题52. 两个链表的第一个公共节点 - 力扣（LeetCode）

题解

public class Solution
{
    public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
    {
        if (headA == null || headB == null)
            return null;

        ListNode a = headA;
        ListNode b = headB;
        while (a != b)
        {
            a = (a == null) ? headB : a.next;
            b = (b == null) ? headA : b.next;
        }

        return a;
    }
}

后记

这些好像考的雀氏还挺多。

第十三天

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（LeetCode）

题解

public class Solution
{
    public int[] Exchange(int[] nums)
    {
        int n = nums.Length;
        int l = 0, r = n - 1;
        while (l < r)
        {
            while (l < r && Check(nums[l])) l++;
            while (l < r && !Check(nums[r])) r--;
            (nums[l], nums[r]) = (nums[r], nums[l]);
        }

        return nums;
    }

    bool Check(int n) => (n & 1) == 1;
}

后记

元组是真滴好用。

剑指 Offer 57. 和为s的两个数字 - 力扣（LeetCode）

题解

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int left = 0, right = nums.Length - 1;
        while (left < right)
        {
            if (nums[left] + nums[right] == target)
                return new int[] { nums[left], nums[right] };
            else if (nums[left] + nums[right] < target)
                left++;
            else
                right--;
        }

        return null;
    }
}

后记

又困了。

剑指 Offer 58 - I. 翻转单词顺序 - 力扣（LeetCode）

题解

public class Solution
{
    public string ReverseWords(string s)
    {
        string[] str = s.Trim().Split(" ");
        StringBuilder sb = new StringBuilder();
        for (var i = str.Length - 1; i >= 0; i--)
        {
            if (str[i] == "") continue;
            if (i == str.Length - 1)
            {
                sb.Append($"{str[i]}");
            }
            else
            {
                sb.Append(" " + $"{str[i]}");
            }
        }

        return sb.ToString();
    }
}

后记

居然没有删除所有空格？？

第十四天

面试题12. 矩阵中的路径 - 力扣（LeetCode）

题解

public class Solution
{
    public bool Exist(char[][] board, string word)
    {
        for (int x = 0; x < board.Length; x++)
        for (int y = 0; y < board[0].Length; y++)
            if (DFS(x, y, 0, board, word))
                return true;
        return false;
    }

    public bool DFS(int x, int y, int index, char[][] board, string word)
    {
        if (x < 0 || x >= board.Length || y < 0 || y >= board[0].Length || board[x][y] != word[index])
            return false;
        if (index == word.Length - 1)
            return true;
        index++;
        board[x][y] = '\0';

        if (DFS(x + 1, y, index, board, word) || DFS(x - 1, y, index, board, word) ||
            DFS(x, y + 1, index, board, word) || DFS(x, y - 1, index, board, word))
            return true;
        board[x][y] = word[index - 1];
        return false;
    }
}

后记

三百万年前曾写过这道题，拿着当年的答案复制过来，竟发现耗时多了一倍！

剑指 Offer 13. 机器人的运动范围 - 力扣（LeetCode）

题解

public class Solution
{
    public bool[][] visited;
    public int m, n, k;

    public int MovingCount(int m, int n, int k)
    {
        this.m = m;
        this.n = n;
        this.k = k;
        visited = new bool[m][];
        for (int i = 0; i < m; i++)
            visited[i] = new bool[n];
        return DFS(0, 0, 0, 0);
    }

    public int DFS(int i, int j, int si, int sj)
    {
        if (i >= m || j >= n || k < si + sj || visited[i][j])
            return 0;
        visited[i][j] = true;
        return 1 + DFS(i + 1, j, GetNumber(i + 1), GetNumber(j)) + DFS(i, j + 1, GetNumber(i), GetNumber(j + 1));
    }

    public int GetNumber(int x)
    {
        int res = 0;
        while (x != 0)
        {
            res += x % 10;
            x /= 10;
        }

        return res;
    }
}

后记

又是三万年前的代码。（但是这个代码风格不像是我写的啊）

第十五天

剑指 Offer 34. 二叉树中和为某一值的路径 - 力扣（LeetCode）

题解

public class Solution
{
    public List<IList<int>> Res = new();
    public List<int> Path = new List<int>();

    public IList<IList<int>> PathSum(TreeNode root, int target)
    {
        DFS(root, target);
        return Res;
    }

    public void DFS(TreeNode root, int target)
    {
        if (root == null)
            return;

        Path.Add(root.val);
        target -= root.val;
        if (target == 0)
            Res.Add(new List<int>(Path));

        DFS(root.left, target);
        DFS(root.right, target);
    Path.RemoveAt(Path.Count);
        target += root.val;
    }
}

后记

题目要根节点到叶子节点，我看成了节点到子节点。。。我是瞎子

剑指 Offer 36. 二叉搜索树与双向链表 - 力扣（LeetCode）

题解

public class Solution
{
    public Node Head, Pre;

    public Node TreeToDoublyList(Node root)
    {
        if (root == null)
            return null;
        DFS(root);

        Head.left = Pre;
        Pre.right = Head;
        return Head;
    }

    public void DFS(Node root)
    {
        if (root == null)
            return;

        DFS(root.left);
        if (Pre == null)
            Head = root;
        else
            Pre.right = root;
        root.left = Pre;
        Pre = root;
        DFS(root.right);
    }
}

后记

感觉不如笔仙。

剑指 Offer 54. 二叉搜索树的第k大节点 - 力扣（LeetCode）

题解

public class Solution
{
    public int Res;
    public int K;

    public int KthLargest(TreeNode root, int k)
    {
        K = k;
        DFS(root);
        return Res;
    }

    public void DFS(TreeNode root)
    {
        if (root == null)
            return;
        DFS(root.right);
        if (--K == 0)
            Res = root.val;
        DFS(root.left);
    }
}

后记

该拿字段记录就用字段，这种题没必要折腾自己。

第十六天

剑指 Offer 45. 把数组排成最小的数 - 力扣（LeetCode）

题解

public class Solution
{
    public string MinNumber(int[] nums)
    {
        List<string> list = new List<string>(nums.Length);
        list.AddRange(nums.Select(t => t.ToString()));
        list.Sort(((x, y) => (x + y).CompareTo(y + x)));
        StringBuilder sb = new StringBuilder();
        foreach (var s in list)
        {
            sb.Append(s);
        }

        return sb.ToString();
    }
}

后记

这个sb不会被审查把（

剑指 Offer 61. 扑克牌中的顺子 - 力扣（LeetCode）

题解

public class Solution
{
    public bool IsStraight(int[] nums)
    {
        int zero = 0;
        Array.Sort(nums);
        for (int i = 0; i < nums.Length - 1; i++)
        {
            if (nums[i] == 0)
                zero++;
            else if (nums[i] == nums[i + 1])
                return false;
        }

        return nums[^1] - nums[zero] < 5;
    }
}

后记

有个傻逼不知道顺子是啥，算了半天都感觉不对劲，被迫去看题解，之后发现我顺了个寂寞（）。

第十七天

剑指 Offer 40. 最小的k个数 - 力扣（LeetCode）

题解

public class Solution
{
    public int[] GetLeastNumbers(int[] arr, int k)
    {
        Array.Sort(arr);
        int[] res = new int[k];
        for (int i = 0; i < k; i++)
            res[i] = arr[i];
        return res;
    }
}

后记

不会真的有人手写排序把。

剑指 Offer 41. 数据流中的中位数 - 力扣（LeetCode）

题解

public class MedianFinder
{
    private PriorityQueue<int, int> _minHeap;
    private PriorityQueue<int, int> _maxHeap;

    /** initialize your data structure here. */
    public MedianFinder()
    {
        _minHeap = new PriorityQueue<int, int>(Comparer<int>.Create((x, y) => y - x));
        _maxHeap = new PriorityQueue<int, int>();
    }

    public void AddNum(int num)
    {
        if (_minHeap.Count == _maxHeap.Count)
        {
            _maxHeap.Enqueue(num, num);
            int number = _maxHeap.Dequeue();
            _minHeap.Enqueue(number, number);
        }
        else
        {
            _minHeap.Enqueue(num, num);
            int number = _minHeap.Dequeue();
            _maxHeap.Enqueue(number, number);
        }
    }

    public double FindMedian()
    {
        if (_minHeap.Count == _maxHeap.Count)
        {
            return (_maxHeap.Peek() + _minHeap.Peek()) / 2;
        }
        else
        {
            return _maxHeap.Peek();
        }
    }
}

后记

这里面多半得全文背诵，不过也要看是否支持**.net6**，不支持原地自闭。

第十八天

剑指 Offer 55 - I. 二叉树的深度 - 力扣（LeetCode）

题解

public class Solution
{
    public int MaxDepth(TreeNode root)
    {
        if (root == null)
            return 0;
        return Math.Max(MaxDepth(root.left), MaxDepth(root.right)) + 1;
    }
}

后记

无后记。

剑指 Offer 55 - II. 平衡二叉树 - 力扣（LeetCode）

题解

public class Solution
{
    public bool IsBalanced(TreeNode root)
    {
        return Height(root) >= 0;
    }

    public int Height(TreeNode root)
    {
        if (root == null)
            return 0;

        int leftHeight = Height(root.left);
        int rightHeight = Height(root.right);

        if (leftHeight == -1 || rightHeight == -1 || Math.Abs(leftHeight - rightHeight) >= 2)
            return -1;
        else
            return Math.Max(leftHeight, rightHeight) + 1;
    }
}

后记

我真的好讨厌搜索啊。

第十九天

剑指 Offer 64. 求1+2+…+n - 力扣（LeetCode）

题解

public class Solution
{
    private int res;

    public int SumNums(int n)
    {
        bool x = n > 1 && SumNums(n - 1) > 0;
        res += n;
        return res;
    }
}

后记

这是一道完全没有用的题。

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（LeetCode）

题解

class Solution
{ 
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q)
    {
        TreeNode* now = root;
        while (now)
        {
            if (p->val < now->val && q->val < now->val)
                now = now->left;
            else if (p->val > now->val && q->val > now->val)
                now = now->right;
            else
                break;
        }

        return now;
    }
};

后记

sb题，没有C#

剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（LeetCode）

题解

class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root == NULL || root == p || root == q)
            return root;
        TreeNode* left = lowestCommonAncestor(root->left, p, q);
        TreeNode* right = lowestCommonAncestor(root->right, p, q);
        if(left == NULL)
            return right;
        if(right == NULL)
            return left;
        return root;
    }
};