哈喽！大家好，我是IT技术猿猴，最爱海贼王
是一位爱好技术的【技术宅男】！

 如果有对技术感兴趣的宅友，欢迎关注
❤️❤️❤️感谢各位❤️❤️❤️
————————————————

本文介绍：大学时期的算法题

️‍下面请看本篇文章目录

目录

️‍不用加减乘除做加法

二叉搜索树与双向链表

剪绳子

删除链表中重复的结点

数组中重复的数字

链表中环的入口结点

斐波那契数列

二维数组中的查找

和为S的连续正数序列

两个链表的第一个公共结点

连续子数组的最大和

链表中倒数第k个结点

和为S的两个数字

数组中只出现一次的数字

二叉树中和为某一值的路径

字符流中第一个不重复的字符

第一个只出现一次的字符

数据流中的中位数

二叉树的下一个结点

数字在排序数组中出现的次数

丑数

矩阵中的路径

树的子结构

数组中的逆序对

️‍不用加减乘除做加法

using System;
namespace Add {

    class Solution {

        /// 

        /// 解法，位运算
        /// 基本思路：
        /// 以十进制加法为例，36 + 78
        /// 加法过程可以分为三步：
        /// 1. 不考虑进位，相加各位的值。得到 04
        /// 2. 计算进位（该位有进位则为1，无进位则为0）。得到 11。再左移一位。最终得到 110
        /// 3. 使用得到的两个值，重复上面两步。 04 + 110 得到 114
        /// 二进制同理也可以使用上面3步模拟加法
        /// 1. 不考虑进位，相加各位的值。这里不能使用加法，使用异或运算代替。00得0 01得1 11得0
        /// 2. 计算进位。这里利用与运算得到。00得0 01得0 11得1(进位)
        /// 负数是使用补码表示，所以同样适用上述算法
        /// 

        public int Add(int num1, int num2)
        {
            while(num2 != 0){
                int temp = num1 ^ num2;
                num2 &= num1;
                num2 <<= 1;
                num1 = temp;
            }
            return num1;
        }

        public void Test() {

            int num1 = 1;
            // num1 = 0;
            num1 = -6;

            int num2 = 4;
            num2 = -3;
            // num2 = 0;

            Console.WriteLine(Add(num1, num2));
        }
    }
}

二叉搜索树与双向链表

using System;
using System.Collections.Generic;
namespace Convert {

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法1，递归
        /// 基本思路：
        /// 采用中序遍历，左，中，右
        /// 先将左子树转换为双向链表，再将右子树转换为双向链表
        /// 转换过程是一直使用pLast记录当前链表的末尾
        /// 其中Convert函数返回的节点一直是链表的首端
        /// 

        private TreeNode pLast;
        public TreeNode Convert(TreeNode pRootOfTree)
        {
            if(pRootOfTree == null) return null;
            TreeNode head = Convert(pRootOfTree.left);
            pRootOfTree.left = pLast;
            if(pLast != null)
                pLast.right = pRootOfTree;
            pLast = pRootOfTree;
            Convert(pRootOfTree.right);
            return head == null ? pRootOfTree : head;
        }

        /// 

        /// 解法2，递归
        /// 基本思路：
        /// 和解法1类似，但采用中序遍历的变体，右，中，左
        /// 转换过程是一直使用pHead记录当前链表的头部
        /// 

        private TreeNode pHead;
        public TreeNode Convert2(TreeNode pRootOfTree)
        {
            if(pRootOfTree == null) return null;
            Convert2(pRootOfTree.right);
            pRootOfTree.right = pHead;
            if(pHead != null)
                pHead.left = pRootOfTree;
            pHead = pRootOfTree;
            Convert2(pRootOfTree.left);
            return pHead;
        }

        /// 

        /// 解法3，非递归
        /// 基本思路：
        /// 中序遍历的非递归实现
        /// 转换过程是一直使用last记录当前链表的末尾
        /// 

        public TreeNode Convert3(TreeNode pRootOfTree)
        {
            if(pRootOfTree == null) return null;
            Stack stack = new Stack();
            TreeNode root = pRootOfTree, head = null, last = null;
            while(root != null || stack.Count > 0){
                while(root != null){
                    stack.Push(root);
                    root = root.left;
                }
                root = stack.Pop();
                if(head == null) 
                    head = root;
                root.left = last;
                if(last != null)
                    last.right = root;
                last = root;
                root = root.right;
            }
            return head;
        }

        public void Print(TreeNode root){
            TreeNode node = null;
            while(root != null){
                Console.Write(root.val + " ");
                node = root;
                root = root.right;
            }
            Console.WriteLine();
            while(node != null){
                Console.Write(node.val + " ");
                node = node.left;
            }
            Console.WriteLine();
        }

        public void Test() {
            
            TreeNode pRootOfTree = new TreeNode(8);
            pRootOfTree.left = new TreeNode(4);
            pRootOfTree.right = new TreeNode(12);

            pRootOfTree.left.left = new TreeNode(2);
            pRootOfTree.left.right = new TreeNode(6);
            pRootOfTree.right.left = new TreeNode(10);
            pRootOfTree.right.right = new TreeNode(14);

            pRootOfTree.left.left.left = new TreeNode(0);
            pRootOfTree.left.left.right = new TreeNode(3);
            pRootOfTree.left.right.left = new TreeNode(5);
            pRootOfTree.left.right.right = new TreeNode(7);
            pRootOfTree.right.left.left = new TreeNode(9);
            // pRootOfTree = null;
           
            // Print(Convert(pRootOfTree));
            // Print(Convert2(pRootOfTree));
            Print(Convert3(pRootOfTree));
        }
    }
}

剪绳子

using System;
namespace CutRope {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 找规律，先列出n的前几项
        /// 2  1 * 1
        /// 3  1 * 2
        /// 4  2 * 2
        /// 5  2 * 3
        /// 6  3 * 3
        /// 7  2 * 2 * 3
        /// 8  2 * 3 * 3
        /// 9  3 * 3 * 3
        /// 10 2 * 2 * 3 * 3
        /// 11 2 * 3 * 3 * 3
        /// 可以发现除了特殊的n=2, n=3以外，其他值都是由2和3组成
        /// 问题在于如何确定2和3的个数
        /// 观察发现，2, 3的个数与 n / 3, n % 3 有关
        /// 2的个数要么是0个或1个或2个，不会是3个，因为当可以2 * 2 * 2 时应该用 3 * 3 表示
        /// 进一步总结可得n % 3 = 0 时 2的个数是0，3的个数是n/3
        /// n % 3 = 1时 2的个数是2，3的个数n/3 - 1
        /// 否则2的个数是1，3的个数是n/3
        /// 

        public int CutRope(int number)
        {
            if(number == 2 || number == 3) return number - 1;
            int mod = number % 3;
            int div = number / 3;
            if(mod == 0) return (int)Math.Pow(3, div);
            else if(mod == 1) return 2 * 2 * (int)Math.Pow(3, div - 1);
            else return 2 * (int)Math.Pow(3, div); 
        }

        /// 

        /// 解法2，贪婪算法
        /// 基本思路：
        /// 根据解法1列出的n的前几项，可以发现，对于每个大于4的值来说，都希望分出更多的3
        /// 比如5 希望分成 2 * 3
        /// 比如8 希望分成 5 * 3，再分成 2 * 3 * 3
        /// 

        public int CutRope2(int number)
        {
            if(number == 2 || number == 3) return number - 1;
            int ret = 1;
            while(number > 4){
                ret *= 3;
                number -= 3;
            }
            return ret * number;
        }

        /// 

        /// 解法3，动态规划
        /// 基本思路：
        /// 对于除n = 2和n = 3的特殊情况以外，使用dp数组记录前面的计算结果
        /// 求解n的最大乘积时，通过遍历每一种分段情况（分段从2开始，因为分出1的段的情况一定不是最大乘积），
        /// 取每种分段情况中乘积最大的为结果
        /// 再利用dp中的记录值，避免重复的计算
        /// 

        public int CutRope3(int number)
        {
            if(number == 2 || number == 3) return number - 1;
            int[] dp = new int[number + 1];
            dp[2] = 2;
            dp[3] = 3;
            int res =  0;
            for (int i = 4; i < number + 1; i++)
            {
                for(int j = 2; j < i / 2 + 1; j ++){
                   res = Math.Max(dp[i - j] * dp[j], res);
                }
                dp[i] = res;
            }
            return dp[number];
        }


    
        public void Test() {

            int number = 2;
            // number = 3;
            // number = 5;
            // number = 6;
            // number = 7;
            // number = 30;

            // Console.WriteLine(CutRope(number));
            // Console.WriteLine(CutRope2(number));
            Console.WriteLine(CutRope3(number));
        }
    }
}

删除链表中重复的结点

using System;
using System.Collections.Generic;
namespace DeleteDuplication {

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法
        /// 基本思路：
        /// 利用left指针指向确定不重复的元素
        /// 利用right指针查找重复的元素
        /// 如果right指针没有找到重复的元素，则两个指针同时右移一位，查找剩余的元素
        /// 如果有找到重复的元素，则将left的next直接指向right.next，以移除重复的元素
        /// 构造了一个head节点，为了方便处理头元素可能是重复元素需要移除的情况
        /// 

        public ListNode DeleteDuplication(ListNode pHead)
        {
            ListNode head = new ListNode(0);
            head.next = pHead;
            ListNode left = head, right = head.next;
            while(right != null){
                while(right.next != null && right.next.val == right.val){
                    right = right.next;
                }
                if(left.next == right)
                    left = left.next;
                else
                    left.next = right.next;
                right = right.next;
            }
            return head.next; 
        }

        public void Print(ListNode node) {
            if (node == null){
                Console.WriteLine("null");
                return;
            }
            while(node != null) {
                Console.WriteLine(node.val);
                node = node.next;
            }
        }

        public void Test() {
            ListNode pHead = null;
            pHead = new ListNode(1);
            // pHead.next = new ListNode(1);
            pHead.next = new ListNode(3);
            pHead.next.next = new ListNode(3);
            pHead.next.next.next = new ListNode(3);
            pHead.next.next.next.next = new ListNode(4);
            pHead.next.next.next.next.next = new ListNode(4);
            pHead.next.next.next.next.next.next = new ListNode(5);

            Print(DeleteDuplication(pHead));
        }
    }
}

数组中重复的数字

using System;
namespace Duplicate {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 利用长度为n的辅助数组记录每个数字的出现次数
        /// 

        public bool Duplicate(int[] numbers, int[] duplication)
        {
            if (numbers == null){
                return false;
            }
            int[] array = new int[numbers.Length];
            for(int i = 0; i < numbers.Length; i ++){
                if(++ array[numbers[i]] > 1){
                    duplication[0] = numbers[i];
                    return true;
                }
            }
            return false;
        }

        /// 

        /// 解法2
        /// 基本思路：
        /// 不使用辅助数组，利用原数组保存遍历的信息
        /// 当一个数字被访问后，将该数字作为下标位置上的数减去数组的长度（使这个数一定小于0）
        /// 之后再遇到相同的数字时，发现对应的下标位置上的数已经小于0，则说明出现了重复元素
        /// 

        public bool Duplicate2(int[] numbers, int[] duplication)
        {
            if (numbers == null){
                return false;
            }
            for(int i = 0; i < numbers.Length; i ++){
                int num = numbers[i] < 0 ? numbers[i] + numbers.Length : numbers[i];
                if(numbers[num] < 0){
                    duplication[0] = num;
                    return true;
                }
                numbers[num] -= numbers.Length;
            }
            return false;
        }

        /// 

        /// 解法3
        /// 基本思路：
        /// 不使用辅助数组
        /// 每访问到一个数字，判断这个数字与其下标是否相等，若不相等，则将该数字与以该数字值为下标的位置上的数字进行交换
        /// 如果要交换的两个数字相等，则找到了重复数字
        /// 

        public bool Duplicate3(int[] numbers, int[] duplication)
        {
            if (numbers == null){
                return false;
            }
            for(int i = 0; i < numbers.Length; i ++){
                while(i != numbers[i]){
                    int temp = numbers[numbers[i]];
                    if(numbers[i] == temp){
                        duplication[0] = numbers[i];
                        return true;
                    }
                    numbers[numbers[i]] = numbers[i];
                    numbers[i] = temp;
                }
            }
            return false;
        }

        public void Test() {

            int[] numbers = new int[]{2,3,1,0,2,5,3};
            // numbers = null;
            // numbers = new int[]{};
            // numbers = new int[]{0};
            // numbers = new int[]{0, 0};
            // numbers = new int[]{0, 2, 3, 3, 2};

            int[] duplication = new int[1];

            // Console.WriteLine(Duplicate(numbers, duplication));
            Console.WriteLine(Duplicate2(numbers, duplication));
            // Console.WriteLine(Duplicate3(numbers, duplication));
            
            Console.WriteLine(duplication[0]);
        }
    }
}

链表中环的入口结点

using System;
using System.Collections.Generic;
namespace EntryNodeOfLoop {

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 使用Dictionary记录每个节点是否出现过，如果某个节点重复出现则该节点是环的入口节点
        /// 

        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            Dictionary dic = new Dictionary();
            while(pHead != null){
                if(dic.ContainsKey(pHead)){
                    return pHead;
                }else{
                    dic[pHead] = true;
                }
                pHead = pHead.next;
            }
            return null;
        }

        /// 

        /// 解法2，断链法
        /// 基本思路：
        /// 首先判断链表是否包含环。
        /// 定义快慢指针，快指针走两步，慢指针走一步，如果有环，快慢指针一定会相遇（快指针会追上慢指针）。
        /// 如果一个链表包含环，则该链表可以无限遍历下去。
        /// 此时每遍历到一个节点，便将该节点的前驱节点的next置为空（断链，断开前驱节点与当前节点的连接）
        /// 当某个节点的next为空时，说明此前已经被破坏过，该节点即为环的入口节点
        /// 注意，这种解法会破坏原链表的结构
        /// 

        public ListNode EntryNodeOfLoop2(ListNode pHead)
        {
            ListNode slow = pHead, fast = pHead;
            bool hasRing = false;
            while(fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
                if (slow == fast){
                    hasRing = true;
                    break;
                }
            }
            if(hasRing){
                slow = pHead;
                fast = pHead.next;
                while(fast != null){
                    slow.next = null;
                    slow = fast;
                    fast = fast.next;
                }
                return slow;
            }
            return null;
        }

        /// 

        /// 解法3
        /// 基本思路：
        /// 定义一个快指针，一个慢指针，都指向链表的头部
        /// 如果链表包含环，假设环长度为n。
        /// 让快指针先走n步，然后再让快慢指针一起走（都是每次走一步），则它们一定相遇于环的入口节点
        /// 问题在于如何计算环的长度
        /// 上面在判断是否包含环时，会找到使两个指针相遇的节点，这个相遇点一定在环内。
        /// 从这个相遇点继续遍历，再次回到相遇点时经过的长度就是环长
        /// 

        public ListNode EntryNodeOfLoop3(ListNode pHead)
        {
            ListNode p = pHead, q = pHead;
            bool hasRing = false;
            while(q != null && q.next != null){
                p = p.next;
                q = q.next.next;
                if (p == q){
                    hasRing = true;
                    break;
                }
            }
            if(hasRing){
                ListNode r = pHead;
                do{
                    r = r.next;
                    p = p.next;
                }while(p != q);
                p = pHead;
                while(r != p){
                    r = r.next;
                    p = p.next;
                }
                return p;
            }
            return null;
        }

        /// 

        /// 解法4
        /// 基本思路：
        /// 首先判断链表是否包含换环，利用快慢指针找到相遇点
        /// 假设链表起点到环的入口点距离为a，环的入口点到相遇点距离为b（顺时针），相遇点到环的入口点距离为c（顺时针）
        /// 定义快指针走两步，慢指针走一步，所以快指针走过的路程是慢指针的2倍
        /// 则快指针走过的距离为 x = a + n（b + c）+ b
        /// 慢指针走过的距离为 y = a + b
        /// 由 x = 2y 得 a + n（b + c）+ b = 2 * (a + b)
        /// 进一步推导得到 a = (n - 1) *（b + c）+ c
        /// 表示从链表起点到环入口点的距离 = (n - 1)环长 + 相遇点到环入口点的长度(c)
        /// 因此两个指针分别从链表起点和相遇点开始移动，一定会在环入口点相遇
        /// 

        public ListNode EntryNodeOfLoop4(ListNode pHead)
        {
            ListNode p = pHead, q = pHead;
            bool hasRing = false;
            while(q != null && q.next != null){
                p = p.next;
                q = q.next.next;
                if(p == q){
                    hasRing = true;
                    break;
                }
            }
            if(hasRing){
                p = pHead;
                while(p != q){
                    p = p.next;
                    q = q.next;
                }
                return p;
            }
            return null;
        }

        public void Test() {
            
            ListNode pHead = new ListNode(1);
            // pHead = null;
            pHead.next = new ListNode(2);
            pHead.next.next = new ListNode(3);
            pHead.next.next.next = new ListNode(4);
            pHead.next.next.next = pHead.next.next;

            
            // ListNode node = EntryNodeOfLoop(pHead);
            // ListNode node = EntryNodeOfLoop2(pHead);
            // ListNode node = EntryNodeOfLoop3(pHead);
            ListNode node = EntryNodeOfLoop4(pHead);

            if(node == null){
                Console.WriteLine("null");
            }else{
                Console.WriteLine(node.val);
            }
        }
    }
}

斐波那契数列

using System;
namespace Fibonacci {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 斐波那契数列可以用公式表示为F(n) = F(n-1) + F(n-2)
        /// 在不考虑效率的情况下可以直接使用递归求得
        /// 

        public int Fibonacci(int n)
        {
            if(n == 0 || n == 1){
                return n;
            }
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }

        /// 

        /// 解法2， 动态规划
        /// 基本思路：
        /// 递归的思想是自顶向下的，Fn的求解基于Fn-1和Fn-2，Fn-1的求解又基于Fn-2和Fn-3等等依次类推。
        /// 而现在我们可以反过来，自底向上，在已知F1 = 1，F2 = 1的情况下求解F3，再利用F3和F2求解F4直到求出Fn。
        /// 即不使用递归，使用循环迭代的方式。我们可以给这种方式起一个高大上的名字，动态规划。
        /// 动态规划介绍 https://www.cnblogs.com/iwiniwin/p/10798884.html
        /// 

        public int Fibonacci2(int n)
        {
            int i = 0, j = 1;
            while(n -- > 0){
                i = i + j;
                j = i - j;
            }
            return i;
        }

        /// 

        /// 解法3，矩阵的快速幂
        /// 基本思路：
        /// 首先归纳出斐波那契数列和矩阵的关系
        /// 我们已知斐波那契第n项，Fn = F(n - 1) + F(n - 2)，可以将它们转换成如下所示的矩阵形式
        /// 
        ///     Fn              Fn-1 + Fn-2            Fn-1 * 1 + Fn-2 * 1        1  1       Fn-1
        /// [        ]  =  [                    ] = [                      ]  = [      ] * [      ]
        ///     Fn-1                Fn-1               Fn-1 * 1 + Fn-2 * 0        1  0       Fn-2
        /// 
        /// 进而推导出
        /// 
        ///     Fn           1  1                   F1
        /// [        ]  =  [      ]的 n - 1次方 * [     ]
        ///     Fn-1         1  0                   F0
        /// 
        /// 然后直接编程计算矩阵乘法以及矩阵快速幂并代入公式即可
        /// 快速幂以及详细推导过程介绍 https://www.cnblogs.com/iwiniwin/p/10798884.html
        /// 

        public int[,] multiply(int[,] m1, int[,] m2){
            return new int[,]{
                {m1[0, 0] * m2[0, 0] + m1[0, 1] * m2[1, 0], m1[0, 0] * m2[0, 1] + m1[0, 1] * m2[1, 1]},
                {m1[1, 0] * m2[0, 0] + m1[1, 1] * m2[1, 0], m1[1, 0] * m2[0, 1] + m1[1, 1] * m2[1, 1]},
            };
        }

        public int[,] pow(int[,] matrix, int n){
            int[,] ret = new int[,]{{1, 0}, {0, 1}};
            while(n > 0){
                if((n & 1) > 0) {
                    ret = multiply(ret, matrix);
                }
                n = n >> 1;
                matrix = multiply(matrix, matrix);
            }
            return ret;
        }

        public int Fibonacci3(int n)
        {
            int[,] unit = new int[,]{{1, 1}, {1, 0}};
            int[,] matrix = new int[,]{{1, 0}, {0, 0}};
            int[,] ret = multiply(pow(unit, n - 1), matrix);
            return n == 0 ? 0 : ret[0, 0];
        }

        public void Test() {

            int n = 0; // 0
            n = 1; // 1
            n = 2; // 1
            n = 3; // 2
            n = 4; // 3

            n = 39;

            // Console.WriteLine(Fibonacci(n));
            // Console.WriteLine(Fibonacci2(n));
            Console.WriteLine(Fibonacci3(n));
        }
    }
}

二维数组中的查找

using System;
namespace Find {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 根据数组从左到右递增，从上到下递增的特性可以发现，
        /// 当从数组的左下角开始判断时，从左到右是递增的，从下到上是递减的
        /// 此时，如果target比当前元素大，就向右找，如果比当前元素小，就向上找
        /// 从数组的右上角开始也是类似的
        /// 

        public bool Find(int target, int[][] array)
        {
            int row = array.Length - 1, col = 0;
            while(row >= 0 && col < array[row].Length){
                if(array[row][col] == target){
                    return true;
                }else if(array[row][col] > target){
                    row --;
                }else{
                    col ++;
                }
            }
            return false;
        }

        public void Test() {

            int target = 8;
            int[][] array = new int[][]{
                new int[]{1, 2, 3, 6}, 
                new int[]{2, 3, 4, 10}
            };

            Console.WriteLine(Find(target, array));
        }
    }
}

和为S的连续正数序列

using System;
using System.Collections.Generic;
namespace FindContinuousSequence {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 利用双指针，构造一个“窗口”，计算这个窗口内的元素之和（公式：(首+尾)*个数/2 ）
        /// 如果和等于sum，则将窗口内的元素加入到列表中，同时窗口整体右移，寻找下一个和等于sum的窗口
        /// 如果和小于sum，则right指针右移，增大窗口内的元素之和
        /// 如果和大于sum，则left指针右移，减小窗口内的元素之和
        /// 

        public List> FindContinuousSequence(int sum) {
            List> lists = new List>();
            int left =  1, right = 2;
            while(left < right && right < sum){
                int cur = (left + right) * (right - left + 1) / 2;
                if(cur == sum){
                    List list = new List();
                    for(int i = left; i <= right; i ++){
                        list.Add(i);
                    }
                    lists.Add(list);
                    left ++;
                    right ++;
                }else if(cur < sum){
                    right ++;
                }else{
                    left ++;
                }
            }
            return lists;
        }

        /// 

        /// 解法2
        /// 基本思路：
        /// 通过数列的平均值以及长度可以推导出数列
        /// 已知数列的和为sum，假设数列的长度为n
        /// 则n为奇数时，sum = 平均值 * n，即满足条件 sum % n == 0
        /// n为偶数时，sum = 平均值（为一个小数xx.5） * n，即 sum / n == xx.5
        /// 小数部分是0.5，说明余数是除数的一半，进一步得到 sum % n = n / 2
        /// 再来看n的取值范围，根据求和公式（1 + n） * n / 2 = sum 得到 n < sqrt(2 * sum)
        /// 

        public List> FindContinuousSequence2(int sum) {
            List> lists = new List>();
            for(int n = (int)Math.Sqrt(2 * sum); n >= 2; n --){
                if((n & 1) == 1 && sum % n == 0 || sum % n * 2 == n){
                    List list = new List();
                    for(int i = sum / n - (n - 1) / 2, j = 0; j < n; i ++,j ++){
                        list.Add(i);
                    } 
                    lists.Add(list);
                }
            }
            return lists;
        }

        public void Print(List> lists) {
            foreach(List list in lists){
                foreach(int i in list){
                    Console.Write(i + " ");
                }
                Console.WriteLine();
            }
        }

        public void Test() {

            int sum = 100;
            // sum = 102;
            // sum = 1;

            // List> lists = FindContinuousSequence(sum);
            List> lists = FindContinuousSequence2(sum);

            Print(lists);
        }
    }
}

两个链表的第一个公共结点

using System;
using System.Collections.Generic;
namespace FindFirstCommonNode {

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 利用Dictionary的特性保存链表1的所有节点
        /// 遍历链表2，第一个在Dictionary中的节点就是第一个公共节点
        /// 

        public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2)
        {
            Dictionary dic = new Dictionary();
            while(pHead1 != null){
                dic[pHead1] = true;
                pHead1 = pHead1.next;
            }
            while(pHead2 != null){
                if(dic.ContainsKey(pHead2)){
                    return pHead2;
                }
                pHead2 = pHead2.next;
            }
            return null;
        }

        /// 

        /// 解法2
        /// 基本思路：
        /// 使用两个指针p1, p2，分别遍历两个链表一遍
        /// 如果两个链表长度相同：
        ///     如果有公共节点，则第一遍就可以找到公共节点
        ///     如果没有公共节点，则两个指针同时指向null，结束循环
        /// 如果两个链表长度不相同：
        ///     如果有公共节点，则两个链表构成Y型结构，即a+n和b+n(n表示公共部分)，则遍历到a+n+b和b+n+a的位置，一定是公共节点
        ///     如果没有公共节点，则两个指针分别走到a+b和b+a，同时指向null，结束循环
        /// 

        public ListNode FindFirstCommonNode2(ListNode pHead1, ListNode pHead2)
        {
            ListNode p1 = pHead1, p2 = pHead2; 
            while(p1 != p2){
                p1 = (p1 == null) ? pHead2 : p1.next;
                p2 = (p2 == null) ? pHead1 : p2.next;
            }
            return p1;
        }

        /// 

        /// 解法3
        /// 基本思路：
        /// 如果两个链表有公共节点，则有相同的尾部，即构成Y型结构
        /// 先计算出两个链表的长度差，然后让较长的链表先走长度差个元素，然后两个链表再一起走，寻找公共节点
        /// 

        public int GetListLength(ListNode head){
            int count = 0;
            while(head != null){
                count ++;
                head = head.next;
            }
            return count;
        }

        public ListNode FindFirstCommonNode3(ListNode pHead1, ListNode pHead2)
        {
            int len1 = GetListLength(pHead1);
            int len2 = GetListLength(pHead2);
            while(len1 > len2){
                pHead1 = pHead1.next;
                len1 --;
            }
            while(len2 > len1){
                pHead2 = pHead2.next;
                len2 --;
            }
            while(len1 > 0){
                if(pHead1 == pHead2){
                    return pHead1;
                }
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
                len1 --;
            }
            return null;
        }

        /// 

        /// 解法4
        /// 基本思路：
        /// 思路与解法3基本相同，也是让较长的链表先走长度差个元素
        /// 区别在于不用单独计算每个链表的长度，是一种更优雅的代码实现
        /// 

        public ListNode FindFirstCommonNode4(ListNode pHead1, ListNode pHead2)
        {
            ListNode p1 = pHead1, p2 = pHead2;
            while(p1 != null && p2 != null){
                p1 = p1.next;
                p2 = p2.next;
            }
            while(p1 != null){
                p1 = p1.next;
                pHead1 = pHead1.next;
            }
            while(p2 != null){
                p1 = p1.next;
                pHead2 = pHead2.next;
            }
            while(pHead1 != pHead2){
                pHead1 = pHead1.next;
                pHead2 = pHead2.next;
            }
            return pHead1;
        }

        public void Test() {
            ListNode p1 = new ListNode(1);
            p1.next = new ListNode(2);
            p1.next.next = new ListNode(3);

            ListNode p2 = new ListNode(4);
            p2.next = new ListNode(2);
            p2.next.next = new ListNode(5);

            p1.next.next = p2.next;

            // ListNode ret = FindFirstCommonNode(p1, p2);
            // ListNode ret = FindFirstCommonNode2(p1, p2);
            // ListNode ret = FindFirstCommonNode3(p1, p2);
            ListNode ret = FindFirstCommonNode4(p1, p2);
            if(ret != null){
                Console.WriteLine(ret.val);
            }else{
                Console.WriteLine("null");
            }
        }
    }
}

连续子数组的最大和

using System;
namespace FindGreatestSumOfSubArray {
    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 依次遍历数组元素，是否吸收前面的元素作为连续子数组的前缀的标准是，它们的和是否为正数
        /// 例如当遍历到元素A时
        /// 判断元素A前面的元素和是否是正数，是正数，则加上A对最终的结果产生积极影响，保留前面的元素
        /// 否则丢弃前面的元素直接从A开始继续寻找最大和。
        /// 
        public int FindGreatestSumOfSubArray(int[] array)
        {
            if(array == null || array.Length == 0){
                return 0;
            }
            int max = array[0];
            int sum = max;
            for(int i = 1; i < array.Length; i ++){
                if(sum < 0){
                    sum = array[i];
                }else{
                    sum += array[i];
                }
                if(sum > max){
                    max = sum;
                }
            }
            return max;
        }

        /// 

        /// 解法2，动态规划
        /// 基本思路：
        /// 可以这样理解，假设前n-1个连续元素最大和为x，
        /// 那前n个连续元素最大和就是x加最后一个元素值和最后一个元素值中的较大值
        /// F(n) = max(F(n -1) + array[n], array[n])，这里的array[n]表示数组末尾元素的值
        /// 注意这里的F(n)，并不表示最终结果。最终结果应该是F(1),F(2)..F(n)中的较大值
        /// 
        public int FindGreatestSumOfSubArray2(int[] array)
        {
            if(array == null || array.Length == 0){
                return 0;
            }
            int f = array[0], m = f;
            for(int i = 1; i < array.Length; i ++){
                f = (f + array[i]) > array[i] ? (f + array[i]) : array[i];
                m = m > f ? m : f;
            }
            return m;
        }

        public void Test() {
            int[] array = new int[]{6,-3,-2,7,-15,1,2,6};
            array = new int[]{-9, -8, 2, -1, 3};
            // array = null;

            // Console.WriteLine(FindGreatestSumOfSubArray(array));
            Console.WriteLine(FindGreatestSumOfSubArray2(array));
        }

    }
}

链表中倒数第k个结点

using System;
namespace FindKthToTail {

    public class ListNode
    {
        public int val;
        public ListNode next;
        public ListNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法
        /// 基本思路：
        /// 使用两个指针p, q，通过p = p.next不断遍历链表，当p先走了k步后，q指针再通过q = q.next往下走
        /// 这样相当于p指针一直提前q指针k个节点
        /// 当p指针指向链表末尾时，q指针指向的就是倒数第k个结点
        /// 

        public ListNode FindKthToTail(ListNode head, int k)
        {
            ListNode p = head, q = null;
            while(p != null){
                if(q != null)
                    q = q.next;
                else if(--k == 0)
                    q = head;
                p = p.next;
            }
            return q;
        }

        public void Test() {

            ListNode head = new ListNode(1);
            head.next = new ListNode(2);
            head.next.next = new ListNode(3);
            head.next.next.next = new ListNode(4);

            int k = 3;
            // k = 1;
            // k = 0;
            // k = -3;

            ListNode node = FindKthToTail(head, k);
            if(node == null)
                Console.WriteLine("null");
            else
                Console.WriteLine(node.val);
        }
    }
}

和为S的两个数字

using System;
using System.Collections.Generic;
namespace FindNumbersWithSum {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 使用双指针left, right，左右逼近。题目要求乘积最小的先输出，实际上两个数离得越远，乘积越小
        /// 如果array[left] + array[right] == sum，得到答案
        /// 如果array[left] + array[right] < sum，left++，left指针右移
        /// 如果array[left] + array[right] > sum，right--，right指针左移
        /// 

        public List FindNumbersWithSum(int[] array, int sum)
        {
            List list = new List();
            if(array == null){
                return list;
            }
            int left = 0, right = array.Length - 1;
            while(left < right){
                int cur = array[left] + array[right];
                if(cur == sum){
                    list.Add(array[left]);
                    list.Add(array[right]);
                    break;
                }else if(cur < sum){
                    left ++;
                }else{
                    right --;
                }
            }
            return list;
        }

        /// 

        /// 解法1结合二分查找
        /// 基本思路：
        /// 本来直接使用解法1就可以AC了，不过我第一次提交的时候可能牛客出了什么问题，提示超时，所以有了这个结合二分查找的思路
        /// 利用三个指针start(指向左边的值)，left, right。其中left和right通过二分查找，寻找右边的值
        /// 当右边的值未找到时，start++，start指针右移，start右边的数组继续进行二分查找
        /// 通过保证start指向的值是左边值中最小的来确定得到的两个数乘积最小
        /// 

        public List FindNumbersWithSum2(int[] array, int sum)
        {
            List list = new List();
            if(array == null){
                return list;
            }
            int start = 0;
            int left = 1, right = array.Length - 1;
            while(start < right){
                int mid = (left + right) / 2;
                int cur = array[start] + array[mid];
                if(cur == sum){
                    list.Add(array[start]);
                    list.Add(array[mid]);
                    break;
                }else if(cur < sum){
                    left = mid + 1;
                }else{
                    right = mid - 1;
                }
                if(left > right){
                    start ++;
                    left = start + 1;
                }
            }
            return list;
        }

        public void Print(List list) {
            foreach(int i in list){
                Console.WriteLine(i);
            }
        }

        public void Test() {

            int[] array = new int[]{1, 2, 3, 3, 4, 4, 5, 6};
            // array = null;

            int sum = 8;
            // sum = 7;
            // sum = 100;
            // sum = 1;

            List list = FindNumbersWithSum(array, sum);
            // List list = FindNumbersWithSum2(array, sum);
            Print(list);
        }
    }
}

数组中只出现一次的数字

using System;
using System.Collections.Generic;
namespace FindNumsAppearOnce {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 遍历数组，统计每个数字出现的次数，然后返回出现次数等于1的数字
        /// 

        public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2)
        {
            if(array == null){
                return;
            }
            Dictionary dic = new Dictionary();
            for(int i = 0; i < array.Length; i ++){
                if(dic.ContainsKey(array[i])){
                    dic[array[i]] ++;
                }else{
                    dic[array[i]] = 1;
                }
            }
            bool flag = false;
            foreach(KeyValuePair pair in dic){
                if(pair.Value == 1){
                    if (!flag){
                        num1[0] = pair.Key;
                        flag = true;
                    }else{
                        num2[0] = pair.Key;
                    }
                }
            }
        }

        /// 

        /// 解法2，异或运算
        /// 基本思路：
        /// 利用异或运算的性质，两个相同的数字异或为0，任何数字和0异或都是其本身
        /// 题目提到除了两个只出现一次的数字A,B以外，其他数字都出现了两次，那么将数组中的所有元素进行异或运算
        /// 得到的结果ret一定就是A,B异或的值（根据上面两条异或的性质）
        /// 对于这个结果ret的二进制值按位遍历，找到第一个1所在的位置，记为index（这个1表示的是A,B中不同的位）
        /// 再遍历一次数组，根据每个元素的二进制index位置是否为1，进行分组。
        /// 每两个相同的元素一定都分在了一组，A，B一定不在一组
        /// 然后再对这两组元素按照最开始的思路依次异或，得到的值一定就是A和B
        /// 

        public void FindNumsAppearOnce2(int[] array, int[] num1, int[] num2)
        {
            if(array == null){
                return;
            }
            int ret = 0;
            foreach(int i in array){
                ret ^= i;
            }
            int index = 0;
            while(ret > 0 && (ret & 1) == 0){
                ret >>= 1;
                index ++;
            }
            foreach(int i in array){
                if((i >> index & 1) == 1){
                    num1[0] ^= i;
                }else{
                    num2[0] ^= i;
                }
            }
        }

        public void Test() {

            int[] array = new int[]{};
            // array = null;
            array = new int[]{1, 2, 3, 3, 2, 4, 4, 5};
            // array = new int[]{1, 2, 2, 1, 3, 4, 4, 5, 6, 5};
            // array = new int[]{1, 2};


            int[] num1 = new int[1];
            int[] num2 = new int[1];
            // FindNumsAppearOnce(array, num1, num2);
            FindNumsAppearOnce2(array, num1, num2);

            Console.WriteLine(num1[0]);
            Console.WriteLine(num2[0]);
        }
    }
}

二叉树中和为某一值的路径

using System;
using System.Collections.Generic;
namespace FindPath {

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode (int x)
        {
            val = x;
        }
    }

    class Solution {
        
        /// 

        /// 解法，递归
        /// 基本思路：
        /// 通过定义成员变量list记录在递归过程中经过的每一个节点
        /// 当找到根节点时，且路径上的节点和值等于目标值时，则找到一条路径
        /// 算法的重点在于当递归经过一个节点将其加入到list中后
        /// 递归回溯以后再使用RemoveAt方法将其移除进行回退
        /// 

        private List> pathList = new List>();
        private List list = new List();

        public List> FindPath(TreeNode root, int expectNumber)
        {
            if(root != null && root.val <= expectNumber){
                list.Add(root.val);
                expectNumber -= root.val;
                if(expectNumber == 0 && root.left == null && root.right == null){
                    pathList.Add(new List(list));
                }
                FindPath(root.left, expectNumber);
                FindPath(root.right, expectNumber);
                list.RemoveAt(list.Count - 1);
            }
            return pathList;
        }

        public void Print(List> lists){
            if(lists == null){
                Console.WriteLine("null");
                return;
            }
            foreach (List list in lists)
            {
                foreach (int item in list)
                {
                    Console.Write(item + " ");   
                }
                Console.WriteLine();
            }
        }

        public void Test() {
            
            TreeNode root = new TreeNode(1);
            root.left = new TreeNode(0);
            root.left.right = new TreeNode(1);
            root.left.left = new TreeNode(0);
            root.right = new TreeNode(1);
            root.right.right = new TreeNode(0);
            // root = null;

            int expectNumber = 2;

            Print(FindPath(root, expectNumber));
        }
    }
}

字符流中第一个不重复的字符

using System;
using System.Collections.Generic;
namespace FirstAppearingOnce {

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 根据ASCII码一共定义了128个字符，因此使用长度为128的数组记录每个字符的出现字数
        /// 当每个字符出现1次时，入队列。查找第一个不重复字符时，将出现次数不为1的字符，出队。
        /// 这样队首的元素就是第一个不重复的字符
        /// 

        int[] array = new int[128];
        Queue queue = new Queue();

        public char FirstAppearingOnce()
        {
            while(queue.Count > 0 && array[queue.Peek()] != 1){
                queue.Dequeue();
            }
            return queue.Count == 0 ? '#' : queue.Peek();
        }

        public void Insert(char c)
        {
            array[c] ++;
            if(array[c] == 1){
                queue.Enqueue(c);
            }
        }


        /// 

        /// 解法2
        /// 基本思路：
        /// 使用长度为128的数组记录只出现1次的字符的出现顺序，出现大于1次的字符对应的值都为-1，未出现的对应为0
        /// 遍历数组，找到数组中元素值最小且大于0的，就是第一个不重复的字符
        /// 

        int[] array2 = new int[128];
        int index = 0;
        public char FirstAppearingOnce2()
        {
            int min = int.MaxValue;
            char c = '#';
            for(int i = 0; i < array2.Length; i ++){
                if(array2[i] > 0 && array2[i] < min){
                    min = array2[i];
                    c = (char)i;
                }
            }
            return c; 
        }

        public void Insert2(char c)
        {
            if(array2[c] == 0){
                array2[c] = ++index;
            }else{
                array2[c] = -1;
            }
        }

        public void Test() {
            // Insert('.');
            Insert('g');
            Insert('o');
            // Insert('o');
            // Insert('g');
            // Insert('l');
            // Insert('e');
            
            Console.WriteLine(FirstAppearingOnce());
        }
    }
}

第一个只出现一次的字符

using System;
namespace FirstNotRepeatingChar {
    class Solution {

        /// 

        /// 解法
        /// 解题思路：
        /// 先遍历一遍字符串统计每个字符的出现次数，然后再遍历一遍字符串，找出第一个出现次数为1的字符的索引
        /// 利用0 - 57的数组下标，来对应A(65) - Z(90) - a(97) - z(122)的ASCII值
        /// 例如65对应的是下标0, 122对应的是下标57
        /// 

        public int FirstNotRepeatingChar(string str)
        {
            if(str == null){
                return - 1;
            }
            int[] arr = new int[58];
            for(int i = 0; i < str.Length; i ++){
                arr[(int)str[i] - 65] ++;
            }
            for(int i = 0; i < str.Length; i ++){
                if(arr[(int)str[i] - 65] == 1){
                    return i;
                }
            }
            return -1;
        }

        public void Test() {
            string str = "abcdAddcfa";
            // str = null;

            Console.WriteLine(FirstNotRepeatingChar(str));
        }
    }
}

数据流中的中位数

using System;
namespace GetMedian {

    public class TreeNode {
        public TreeNode left;
        public TreeNode right;
        public int val;
        public TreeNode(int x){
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法1
        /// 基本思路：
        /// 插入时，动态构建二叉搜索树，小于根节点值的放到左子树，大于等于根节点值的放到右子树
        /// 获取中位数时查找儿叉搜索树即可
        /// 

        TreeNode root = null;
        int count = 0;
        int index = 0;
        public void Insert(int num)
        {
            count ++;
            if(root == null){
                root = new TreeNode(num);
                return;
            }
            TreeNode node = root;
            while(true){
                if(num < node.val){
                    if(node.left == null || node.left.val < num){
                        TreeNode temp = node.left;
                        node.left = new TreeNode(num);
                        node.left.left = temp;
                        return;
                    }
                    node = node.left;
                }else{
                    if(node.right == null || node.right.val > num){
                        TreeNode temp = node.right;
                        node.right = new TreeNode(num);
                        node.right.right = temp;
                        return;
                    }
                    node = node.right;
                }
            }
        }

        public TreeNode GetKthNode(TreeNode pRoot, int k){
            if(pRoot != null && k > 0){
                TreeNode node = GetKthNode(pRoot.left, k);
                if(node != null){
                    return node;
                }
                index ++;
                if(index == k){
                    return pRoot;
                }
                node = GetKthNode(pRoot.right, k);
                if(node != null){
                    return node;
                }
            }
            return null;
        }

        public double GetMedian()
        {
            index = 0;
            if(count > 0){
                int median = count / 2 + 1 ;
                TreeNode node = GetKthNode(root, median);
                if((count & 1) == 0){
                    index = 0;
                    TreeNode last = GetKthNode(root, median - 1);
                    return (last.val + node.val) / 2.0d;
                }else{
                    return node.val;
                }
            }
            return 0;
        }

        /// 

        /// TODO 利用优先队列，构建两个堆，大顶堆和小顶堆
        /// 

        public void Test() {

            Insert(1);
            Insert(3);
            Insert(4);
            Insert(1);

            Console.WriteLine(GetMedian());
        }
    }
}

二叉树的下一个结点

using System;
namespace GetNext {

    public class TreeLinkNode
    {
        public int val;
        public TreeLinkNode left;
        public TreeLinkNode right;
        public TreeLinkNode next;
        public TreeLinkNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法
        /// 基本思路：
        /// 中序遍历的顺序是先左节点，再根节点，再右节点
        /// 1. 节点为空，返回空
        /// 2. 如果节点有右节点，则一直向下寻找该右节点的左节点，直到叶子节点为止，即为下一个节点
        /// 3. 如果节点有父节点，且是父节点的左节点，则返回父节点。否则继续判断其父节点是否满足条件，直到父节点为空。
        /// 前中后续遍历介绍 https://blog.csdn.net/FightLei/article/details/89281600
        /// 

        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode == null){
                return null;
            }

            if(pNode.right != null){
                pNode = pNode.right;
                while(pNode.left != null){
                    pNode = pNode.left;
                }
                return pNode;
            }

            while(pNode.next != null){
                if(pNode == pNode.next.left){
                    return pNode.next;
                }
                pNode = pNode.next;
            }

            return null;
        }

        public void Test() {
            TreeLinkNode pNode = null;
            pNode = new TreeLinkNode(0);
            pNode.left = new TreeLinkNode(1);
            pNode.left.next = pNode;

            pNode.left.right = new TreeLinkNode(3);
            pNode.left.right.next = pNode.left;


            pNode.right = new TreeLinkNode(2);
            pNode.right.next = pNode;

            pNode.right.left = new TreeLinkNode(4);
            pNode.right.left.next = pNode.right;
            
            TreeLinkNode node = GetNext(pNode);

            if (node == null){
                Console.WriteLine("null");
            }else{
                Console.WriteLine(node.val);
            }
        }
    }
}

数字在排序数组中出现的次数

using System;
namespace GetNumberOfK {

    class Solution {

        /// 

        /// 解法，二分查找
        /// 在排序数组中查找，首先想到的是二分查找
        /// 由于数组中的数字都是整数，所以可以通过分别查找k+0.5和k-0.5这两个数字应该插入的位置
        /// 两个位置的差值就是数字k的个数
        /// 由于题目未说明排序数组是递增还是递减，所以通过increase标志判断
        /// 

        public int Find(int[] data, double k){
            int left = 0, right = data.Length - 1;
            int mid = 0;
            bool increase = true;
            if(data[left] > data[right]){
                increase = false;
            }
            while(left <= right){
                mid = (left + right) / 2;
                if(data[mid] < k){
                    if(increase){
                        left = mid + 1;
                    }else{
                        right = mid - 1;
                    }
                    
                }else if(data[mid] > k){
                    if(increase){
                        right = mid - 1;
                    }else{
                        left = mid + 1;
                    }
                }
            }
            return increase ? left : -left;
        }

        public int GetNumberOfK(int[] data, int k)
        {
            if(data == null || data.Length == 0){
                return 0;
            }
            return Find(data, k + 0.5) - Find(data, k - 0.5);
        }

        public void Test() {
            int[] data = new int[]{1, 2, 3, 3, 4};
            // data = new int[]{3, 3, 3, 3, 3};
            // data = null;
            // data = new int[]{};
            // data = new int[]{4, 3, 3, 2, 1};
            int k = 3;

            Console.WriteLine(GetNumberOfK(data, k));
        }
    }
}

丑数

using System;
using System.Collections.Generic;
namespace GetUglyNumber {
    class Solution {

        /// 

        /// 解法
        /// 基本思路：
        /// 丑数只包含因子2,3,5（除1以外），所以除1外的所有丑数都可以用2x * 3y * 5z表示
        /// 问题的关键在于如何按照从小到大的顺序获取丑数
        /// 显然的是每获取到一个丑数x，我们都可以通过2x，3x, 5x算出三个新的丑数，但是新算出的丑数和之前已经算出的丑数的大小不好比较
        /// 我们可以分三个队列来解决这个问题，分别是乘2，乘3，乘5的队列
        /// 通过乘以2得到的丑数都放到乘2的队列中，乘3和乘5的同理，这样单看每个队列中的丑数一定是从小到大排列的
        /// 此时这个三个队列头中的最小值就是整个待排丑数中的最小值，也就是我们要获取的下一个丑数值
        /// 下面的代码是利用q2,q3,q5一直表示各自队列的头被计算出来时使用的丑数的索引
        /// 
        
        public int GetUglyNumber_Solution(int index)
        {
            if(index <= 0){
                return 0;
            }
            List list = new List(){1};
            int q2 = 0, q3 = 0, q5 = 0;
            for(int i = 1; i < index; i ++){
                int num = Math.Min(list[q2] * 2, Math.Min(list[q3] * 3, list[q5] * 5));
                if(list[q2] * 2 == num){
                    q2 ++;
                }
                if(list[q3] * 3 == num){
                    q3 ++;
                }
                if(list[q5] * 5 == num){
                    q5 ++;
                }
                list.Add(num);
            }
            return list[index - 1];
        }

        public void Test() {
            int index = 7;
            // index = 11;

            Console.WriteLine(GetUglyNumber_Solution(index));
        }
    }
}

矩阵中的路径

using System;
namespace HasPath {

    class Solution {

        /// 

        /// 解法
        /// 基本思路：
        /// 将matrix字符串转换为多维数组，分别以数组的每个元素为起点，判断路径是否存在
        /// 从起点开始按上下左右的顺序搜索，已经经过的元素标记为-1
        /// 如果此路不通，则回溯到上一层，并还原标记位
        /// 

        public bool HasPathImpl(int[,] arr, int row, int col, string path, int index) {
            if(index >= path.Length){
                return true;
            }
            if(row < 0 || row >= arr.GetLength(0) || col < 0 || col >= arr.GetLength(1)){
                return false;
            }
            if(arr[row, col] == path[index]){
                int temp = arr[row, col];
                arr[row, col] = -1;
                bool ret = HasPathImpl(arr, row, col + 1, path, index + 1) || HasPathImpl(arr, row, col - 1, path, index + 1)
                    || HasPathImpl(arr, row + 1, col, path, index + 1) || HasPathImpl(arr, row - 1, col, path, index + 1);
                arr[row, col] = temp;
                return ret;
            }
            return false;
        }

        public bool HasPath(string matrix, int rows, int cols, string path)
        {
            int[,] arr = new int[rows, cols];
            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    arr[i, j] = matrix[i * cols + j];
                }
            }

            for (int i = 0; i < rows; i++)
            {
                for (int j = 0; j < cols; j++)
                {
                    bool ret = HasPathImpl(arr, i, j, path, 0);
                    if(ret){
                        return true;
                    }
                }
            }
            return false;
        }
    
        public void Test() {

            string matrix = "abcesfcsadee";
            int rows = 3;
            int cols = 4;
            string path = "bcced";
            // path = "abcb";
            // path = "bfb";

            Console.WriteLine(HasPath(matrix, rows, cols, path));
        }
    }
}

树的子结构

using System;
namespace HasSubtree {

    public class TreeNode
    {
        public int val;
        public TreeNode left;
        public TreeNode right;
        public TreeNode (int x)
        {
            val = x;
        }
    }

    class Solution {

        /// 

        /// 解法，递归
        /// 基本思路：
        /// 如果两颗树的根节点相同，则接着判断两颗树的左右子树是否是子树关系
        ///     如果也是的话直接返回true
        ///     如果不是的话，就什么也不做，因为目前仍不能判断B是不是A的子树
        /// 接着判断B是否是A的左子树的子树，如果是的直接返回true
        /// 接着判断B是否是A的右子树的子树，如果是的直接返回true
        /// 

        public bool HasSubtree(TreeNode pRoot1, TreeNode pRoot2)
        {
            if(pRoot1 == null || pRoot2 == null) return false;
            if(pRoot1.val == pRoot2.val)
                if((pRoot2.left == null || HasSubtree(pRoot1.left, pRoot2.left)) && (pRoot2.right == null || HasSubtree(pRoot1.right, pRoot2.right)))
                    return true;
            return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
        }

        public void Test() {

            TreeNode pRoot1 = new TreeNode(1);
            // pRoot1.left = new TreeNode(2);
            pRoot1.right = new TreeNode(1);
            pRoot1.right.left = new TreeNode(1);
            pRoot1.right.left.left = new TreeNode(2);

            TreeNode pRoot2 = new TreeNode(1);
            pRoot2.left = new TreeNode(2);
           
            Console.WriteLine(HasSubtree(pRoot1, pRoot2));
        }
    }
}

数组中的逆序对

using System;
namespace InversePairs {
    class Solution {

        /// 

        /// 解法，归并排序思想
        /// 基本思路：
        /// 将含有n个元素的数组，不断的进行二分为两个子数组。直到每个子数组都只含有一个元素。
        /// 再进行合并两个子数组，利用一个临时数组，不断从两个子数组中选出最大值放到临时数组中。
        /// 在比较时，由于每个子数组都是有序递减的，所以只需要比较子数组的首元素即可（此时进行逆序对的数量统计，如果
        /// 该元素已经大于右边子数组的首元素，则右边子数组的所有元素都小于该元素，即都可以和该元素构成逆序对）。
        /// 归并排序介绍 https://www.cnblogs.com/iwiniwin/p/12609549.html
        /// 

        public int Merge(int[] data, int start, int mid, int end){
            int count = 0;
            int i = start;
            int j = mid + 1;
            int k = 0;
            int[] temp = new int[end - start + 1];
            while(i <= mid && j <= end){
                if(data[i] > data[j]){
                    count += (end - j + 1);
                    if(count > 1000000007){
                        count %= 1000000007;
                    }
                    temp[k ++] = data[i ++];
                }else{
                    temp[k ++] = data[j ++];
                }
            }
            while(i <= mid){
                temp[k ++] = data[i ++];
            }
            while(j <= end){
                temp[k ++] = data[j ++];
            }
            for(i = 0; i < k; i ++){
                data[start + i] = temp[i];
            }
            return count;
        }

        public int MergeSort(int[] data, int start, int end){
            if(start >= end){
                return 0;
            }
            int mid = (start + end) / 2;
            return (MergeSort(data, start, mid) + MergeSort(data, mid + 1, end) + Merge(data, start, mid, end)) % 1000000007;
        }

        public int InversePairs(int[] data)
        {
            if(data == null){
                return 0;
            }
            return MergeSort(data, 0, data.Length - 1);
        }

        public void Test() {
            int[] data = new int[]{1, 6, 2, 8, 4, 1, 0, 7};
            // data = new int[]{1, 2, 3, 4, 5, 6, 7, 0};
            // data = null;
            // data = new int[]{};
            // data = new int[]{1, 1, 0};

            Console.WriteLine(InversePairs(data));
        }
    }
}

各位走过路过，不要错过，记得关注我哦