大学时期的压箱底东西拿出来了-算法合集-1

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

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

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

🏳️‍🌈下面请看本篇文章目录

目录

🏳️‍🌈不用加减乘除做加法

📢二叉搜索树与双向链表

📣剪绳子

💞删除链表中重复的结点

🎉数组中重复的数字

🔥链表中环的入口结点

🔥斐波那契数列

🔥二维数组中的查找

🔥和为S的连续正数序列

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

🔥连续子数组的最大和

🔥链表中倒数第k个结点

🔥和为S的两个数字

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

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

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

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

🔥数据流中的中位数

🔥二叉树的下一个结点

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

🔥丑数

🔥矩阵中的路径

🔥树的子结构

🔥数组中的逆序对

🏳️‍🌈不用加减乘除做加法

/*
题目名称：
不用加减乘除做加法题目描述：
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。代码结构：
class Solution
{public int Add(int num1, int num2){// write code here}
}
*/
using System;
namespace Add {class Solution {/// <summary>/// 解法，位运算/// 基本思路：/// 以十进制加法为例，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(进位)/// 负数是使用补码表示，所以同样适用上述算法/// </summary>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));}}
}

📢二叉搜索树与双向链表

/*
题目名称：
二叉搜索树与双向链表题目描述：
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
要求不能创建任何新的结点，只能调整树中结点指针的指向。代码结构：
class Solution
{public TreeNode Convert(TreeNode pRootOfTree){// write code here}
}补充：
二叉搜索树（Binary Search Tree）定义：
1. 可以是空树
2. 若不是空树若它的左子树不空，则左子树所有节点的值均小于它的根节点的值若它的右子树不空，则右子树所有节点的值均大于它的根节点的值它的左，右子树也分别为二叉搜索树   
*/
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 {/// <summary>/// 解法1，递归/// 基本思路：/// 采用中序遍历，左，中，右/// 先将左子树转换为双向链表，再将右子树转换为双向链表/// 转换过程是一直使用pLast记录当前链表的末尾/// 其中Convert函数返回的节点一直是链表的首端/// </summary>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;}/// <summary>/// 解法2，递归/// 基本思路：/// 和解法1类似，但采用中序遍历的变体，右，中，左/// 转换过程是一直使用pHead记录当前链表的头部/// </summary>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;}/// <summary>/// 解法3，非递归/// 基本思路：/// 中序遍历的非递归实现/// 转换过程是一直使用last记录当前链表的末尾/// </summary>public TreeNode Convert3(TreeNode pRootOfTree){if(pRootOfTree == null) return null;Stack<TreeNode> stack = new Stack<TreeNode>();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));}}
}

📣剪绳子

/*
题目名称：
剪绳子题目描述：
给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），
每段绳子的长度记为k[0],k[1],...,k[m]。
请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？
例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。输入描述：
输入一个数n，意义见题面。（2 <= n <= 60）输出描述：
输出答案。代码结构：
class Solution
{public int cutRope(int number){// write code here}
}补充：
动态规划求解问题的特征：
1. 求问题的最优解，整体的最优解依赖于子问题的最优解
2. 从上往下分析问题，从下往上求解问题
*/
using System;
namespace CutRope {class Solution {/// <summary>/// 解法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/// </summary>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); }/// <summary>/// 解法2，贪婪算法/// 基本思路：/// 根据解法1列出的n的前几项，可以发现，对于每个大于4的值来说，都希望分出更多的3/// 比如5 希望分成 2 * 3/// 比如8 希望分成 5 * 3，再分成 2 * 3 * 3/// </summary>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;}/// <summary>/// 解法3，动态规划/// 基本思路：/// 对于除n = 2和n = 3的特殊情况以外，使用dp数组记录前面的计算结果/// 求解n的最大乘积时，通过遍历每一种分段情况（分段从2开始，因为分出1的段的情况一定不是最大乘积），/// 取每种分段情况中乘积最大的为结果/// 再利用dp中的记录值，避免重复的计算/// </summary>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));}}
}

💞删除链表中重复的结点

/*
题目名称：
删除链表中重复的结点题目描述：
在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 
例如，链表1->2->3->3->4->4->5 处理后为 1->2->5代码结构：
class Solution
{public ListNode deleteDuplication(ListNode pHead){// write code here}
}
*/
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 {/// <summary>/// 解法/// 基本思路：/// 利用left指针指向确定不重复的元素/// 利用right指针查找重复的元素/// 如果right指针没有找到重复的元素，则两个指针同时右移一位，查找剩余的元素/// 如果有找到重复的元素，则将left的next直接指向right.next，以移除重复的元素/// 构造了一个head节点，为了方便处理头元素可能是重复元素需要移除的情况/// </summary>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;elseleft.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));}}
}

🎉数组中重复的数字

/*
题目名称：
数组中重复的数字题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。
数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。
请找出数组中任意一个重复的数字。 
例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。代码结构：
class Solution
{public bool duplicate(int[] numbers, int[] duplication){// write code here}
}
*/
using System;
namespace Duplicate {class Solution {/// <summary>/// 解法1/// 基本思路：/// 利用长度为n的辅助数组记录每个数字的出现次数/// </summary>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;}/// <summary>/// 解法2/// 基本思路：/// 不使用辅助数组，利用原数组保存遍历的信息/// 当一个数字被访问后，将该数字作为下标位置上的数减去数组的长度（使这个数一定小于0）/// 之后再遇到相同的数字时，发现对应的下标位置上的数已经小于0，则说明出现了重复元素/// </summary>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;}/// <summary>/// 解法3/// 基本思路：/// 不使用辅助数组/// 每访问到一个数字，判断这个数字与其下标是否相等，若不相等，则将该数字与以该数字值为下标的位置上的数字进行交换/// 如果要交换的两个数字相等，则找到了重复数字/// </summary>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]);}}
}

🔥链表中环的入口结点

/*
题目名称：
链表中环的入口结点题目描述：
给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。代码结构：
class Solution
{public ListNode EntryNodeOfLoop(ListNode pHead){// write code here}
}
*/
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 {/// <summary>/// 解法1/// 基本思路：/// 使用Dictionary记录每个节点是否出现过，如果某个节点重复出现则该节点是环的入口节点/// </summary>public ListNode EntryNodeOfLoop(ListNode pHead){Dictionary<ListNode, bool> dic = new Dictionary<ListNode, bool>();while(pHead != null){if(dic.ContainsKey(pHead)){return pHead;}else{dic[pHead] = true;}pHead = pHead.next;}return null;}/// <summary>/// 解法2，断链法/// 基本思路：/// 首先判断链表是否包含环。/// 定义快慢指针，快指针走两步，慢指针走一步，如果有环，快慢指针一定会相遇（快指针会追上慢指针）。/// 如果一个链表包含环，则该链表可以无限遍历下去。/// 此时每遍历到一个节点，便将该节点的前驱节点的next置为空（断链，断开前驱节点与当前节点的连接）/// 当某个节点的next为空时，说明此前已经被破坏过，该节点即为环的入口节点/// 注意，这种解法会破坏原链表的结构/// </summary>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;}/// <summary>/// 解法3/// 基本思路：/// 定义一个快指针，一个慢指针，都指向链表的头部/// 如果链表包含环，假设环长度为n。/// 让快指针先走n步，然后再让快慢指针一起走（都是每次走一步），则它们一定相遇于环的入口节点/// 问题在于如何计算环的长度/// 上面在判断是否包含环时，会找到使两个指针相遇的节点，这个相遇点一定在环内。/// 从这个相遇点继续遍历，再次回到相遇点时经过的长度就是环长/// </summary>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;}/// <summary>/// 解法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)/// 因此两个指针分别从链表起点和相遇点开始移动，一定会在环入口点相遇/// </summary>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);}}}
}

🔥斐波那契数列

/*
题目名称：
斐波那契数列题目描述：
大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
n<=39代码结构：
class Solution
{public int Fibonacci(int n){// write code here}
}补充：
斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34、……，因数学家列昂纳多·斐波那契以兔子繁殖为例子而引入，故又称为兔子数列
*/
using System;
namespace Fibonacci {class Solution {/// <summary>/// 解法1/// 基本思路：/// 斐波那契数列可以用公式表示为F(n) = F(n-1) + F(n-2)/// 在不考虑效率的情况下可以直接使用递归求得/// </summary>public int Fibonacci(int n){if(n == 0 || n == 1){return n;}return Fibonacci(n - 1) + Fibonacci(n - 2);}/// <summary>/// 解法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/// </summary>public int Fibonacci2(int n){int i = 0, j = 1;while(n -- > 0){i = i + j;j = i - j;}return i;}/// <summary>/// 解法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/// </summary>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; // 0n = 1; // 1n = 2; // 1n = 3; // 2n = 4; // 3n = 39;// Console.WriteLine(Fibonacci(n));// Console.WriteLine(Fibonacci2(n));Console.WriteLine(Fibonacci3(n));}}
}

🔥二维数组中的查找

/*
题目名称：
二维数组中的查找题目描述：
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。代码结构：
class Solution
{public bool Find(int target, int[][] array){// write code here}
}想法：
先从左到右遍历，如果元素没有target大，就往右找，如果比target小，就不知道应该怎么找了
如果下面的元素都比target小，不就可以向下找了吗
对，可以从左下角开始找，从左到右递增，从下到上递减
1  2  3  4
2  3  4  5
*/
using System;
namespace Find {class Solution {/// <summary>/// 解法1/// 基本思路：/// 根据数组从左到右递增，从上到下递增的特性可以发现，/// 当从数组的左下角开始判断时，从左到右是递增的，从下到上是递减的/// 此时，如果target比当前元素大，就向右找，如果比当前元素小，就向上找/// 从数组的右上角开始也是类似的/// </summary>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的连续正数序列

/*
题目名称：
和为S的连续正数序列题目描述：
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。
没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。
现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序代码结构：
using System.Collections.Generic;
class Solution
{public List<List<int>> FindContinuousSequence(int sum){// write code here}
}
*/
using System;
using System.Collections.Generic;
namespace FindContinuousSequence {class Solution {/// <summary>/// 解法1/// 基本思路：/// 利用双指针，构造一个“窗口”，计算这个窗口内的元素之和（公式：(首+尾)*个数/2 ）/// 如果和等于sum，则将窗口内的元素加入到列表中，同时窗口整体右移，寻找下一个和等于sum的窗口/// 如果和小于sum，则right指针右移，增大窗口内的元素之和/// 如果和大于sum，则left指针右移，减小窗口内的元素之和/// </summary>public List<List<int>> FindContinuousSequence(int sum) {List<List<int>> lists = new List<List<int>>();int left =  1, right = 2;while(left < right && right < sum){int cur = (left + right) * (right - left + 1) / 2;if(cur == sum){List<int> list = new List<int>();for(int i = left; i <= right; i ++){list.Add(i);}lists.Add(list);left ++;right ++;}else if(cur < sum){right ++;}else{left ++;}}return lists;}/// <summary>/// 解法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)/// </summary>public List<List<int>> FindContinuousSequence2(int sum) {List<List<int>> lists = new List<List<int>>();for(int n = (int)Math.Sqrt(2 * sum); n >= 2; n --){if((n & 1) == 1 && sum % n == 0 || sum % n * 2 == n){List<int> list = new List<int>();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<List<int>> lists) {foreach(List<int> list in lists){foreach(int i in list){Console.Write(i + " ");}Console.WriteLine();}}public void Test() {int sum = 100;// sum = 102;// sum = 1;// List<List<int>> lists = FindContinuousSequence(sum);List<List<int>> lists = FindContinuousSequence2(sum);Print(lists);}}
}

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

/*
题目名称：
两个链表的第一个公共结点题目描述：
输入两个链表，找出它们的第一个公共结点。代码结构：
class Solution
{public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){// write code here}
}
*/
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 {/// <summary>/// 解法1/// 基本思路：/// 利用Dictionary的特性保存链表1的所有节点/// 遍历链表2，第一个在Dictionary中的节点就是第一个公共节点/// </summary>public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2){Dictionary<ListNode, bool> dic = new Dictionary<ListNode, bool>();while(pHead1 != null){dic[pHead1] = true;pHead1 = pHead1.next;}while(pHead2 != null){if(dic.ContainsKey(pHead2)){return pHead2;}pHead2 = pHead2.next;}return null;}/// <summary>/// 解法2/// 基本思路：/// 使用两个指针p1, p2，分别遍历两个链表一遍/// 如果两个链表长度相同：///     如果有公共节点，则第一遍就可以找到公共节点///     如果没有公共节点，则两个指针同时指向null，结束循环/// 如果两个链表长度不相同：///     如果有公共节点，则两个链表构成Y型结构，即a+n和b+n(n表示公共部分)，则遍历到a+n+b和b+n+a的位置，一定是公共节点///     如果没有公共节点，则两个指针分别走到a+b和b+a，同时指向null，结束循环/// </summary>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;}/// <summary>/// 解法3/// 基本思路：/// 如果两个链表有公共节点，则有相同的尾部，即构成Y型结构/// 先计算出两个链表的长度差，然后让较长的链表先走长度差个元素，然后两个链表再一起走，寻找公共节点/// </summary>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;}/// <summary>/// 解法4/// 基本思路：/// 思路与解法3基本相同，也是让较长的链表先走长度差个元素/// 区别在于不用单独计算每个链表的长度，是一种更优雅的代码实现/// </summary>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");}}}
}

🔥连续子数组的最大和

/*
题目名称：
连续子数组的最大和题目描述：
HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:
在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。
但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？
例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)代码结构：
class Solution
{public int FindGreatestSumOfSubArray(int[] array){// write code here}
}
*/
using System;
namespace FindGreatestSumOfSubArray {class Solution {/// <summary>/// 解法1/// 基本思路：/// 依次遍历数组元素，是否吸收前面的元素作为连续子数组的前缀的标准是，它们的和是否为正数/// 例如当遍历到元素A时/// 判断元素A前面的元素和是否是正数，是正数，则加上A对最终的结果产生积极影响，保留前面的元素/// 否则丢弃前面的元素直接从A开始继续寻找最大和。/// </summary>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;}/// <summary>/// 解法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)中的较大值/// </summary>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个结点

/*
题目名称：
链表中倒数第k个结点题目描述：
输入一个链表，输出该链表中倒数第k个结点。代码结构：
class Solution
{public ListNode FindKthToTail(ListNode head, int k){// write code here}
}
*/
using System;
namespace FindKthToTail {public class ListNode{public int val;public ListNode next;public ListNode (int x){val = x;}}class Solution {/// <summary>/// 解法/// 基本思路：/// 使用两个指针p, q，通过p = p.next不断遍历链表，当p先走了k步后，q指针再通过q = q.next往下走/// 这样相当于p指针一直提前q指针k个节点/// 当p指针指向链表末尾时，q指针指向的就是倒数第k个结点/// </summary>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");elseConsole.WriteLine(node.val);}}
}

🔥和为S的两个数字

/*
题目名称：
和为S的两个数字题目描述：
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S。
如果有多对数字的和等于S，输出两个数的乘积最小的。输出描述:
对应每个测试案例，输出两个数，小的先输出。代码结构：
class Solution
{public List<int> FindNumbersWithSum(int[] array, int sum){// write code here}
}
*/
using System;
using System.Collections.Generic;
namespace FindNumbersWithSum {class Solution {/// <summary>/// 解法1/// 基本思路：/// 使用双指针left, right，左右逼近。题目要求乘积最小的先输出，实际上两个数离得越远，乘积越小/// 如果array[left] + array[right] == sum，得到答案/// 如果array[left] + array[right] < sum，left++，left指针右移/// 如果array[left] + array[right] > sum，right--，right指针左移/// </summary>public List<int> FindNumbersWithSum(int[] array, int sum){List<int> list = new List<int>();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;}/// <summary>/// 解法1结合二分查找/// 基本思路：/// 本来直接使用解法1就可以AC了，不过我第一次提交的时候可能牛客出了什么问题，提示超时，所以有了这个结合二分查找的思路/// 利用三个指针start(指向左边的值)，left, right。其中left和right通过二分查找，寻找右边的值/// 当右边的值未找到时，start++，start指针右移，start右边的数组继续进行二分查找/// 通过保证start指向的值是左边值中最小的来确定得到的两个数乘积最小/// </summary>public List<int> FindNumbersWithSum2(int[] array, int sum){List<int> list = new List<int>();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<int> 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<int> list = FindNumbersWithSum(array, sum);// List<int> list = FindNumbersWithSum2(array, sum);Print(list);}}
}

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

/*
题目名称：
数组中只出现一次的数字题目描述：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。代码结构：
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
class Solution
{public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2){// write code here}
}
*/
using System;
using System.Collections.Generic;
namespace FindNumsAppearOnce {class Solution {/// <summary>/// 解法1/// 基本思路：/// 遍历数组，统计每个数字出现的次数，然后返回出现次数等于1的数字/// </summary>public void FindNumsAppearOnce(int[] array, int[] num1, int[] num2){if(array == null){return;}Dictionary<int, int> dic = new Dictionary<int, int>();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<int, int> pair in dic){if(pair.Value == 1){if (!flag){num1[0] = pair.Key;flag = true;}else{num2[0] = pair.Key;}}}}/// <summary>/// 解法2，异或运算/// 基本思路：/// 利用异或运算的性质，两个相同的数字异或为0，任何数字和0异或都是其本身/// 题目提到除了两个只出现一次的数字A,B以外，其他数字都出现了两次，那么将数组中的所有元素进行异或运算/// 得到的结果ret一定就是A,B异或的值（根据上面两条异或的性质）/// 对于这个结果ret的二进制值按位遍历，找到第一个1所在的位置，记为index（这个1表示的是A,B中不同的位）/// 再遍历一次数组，根据每个元素的二进制index位置是否为1，进行分组。/// 每两个相同的元素一定都分在了一组，A，B一定不在一组/// 然后再对这两组元素按照最开始的思路依次异或，得到的值一定就是A和B/// </summary>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]);}}
}

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

/*
题目名称：
二叉树中和为某一值的路径题目描述：
输入一颗二叉树的根节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。代码结构：
class Solution
{public List<List<int>> FindPath(TreeNode root, int expectNumber){// write code here}
}
*/
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 {/// <summary>/// 解法，递归/// 基本思路：/// 通过定义成员变量list记录在递归过程中经过的每一个节点/// 当找到根节点时，且路径上的节点和值等于目标值时，则找到一条路径/// 算法的重点在于当递归经过一个节点将其加入到list中后/// 递归回溯以后再使用RemoveAt方法将其移除进行回退/// </summary>private List<List<int>> pathList = new List<List<int>>();private List<int> list = new List<int>();public List<List<int>> 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<int>(list));}FindPath(root.left, expectNumber);FindPath(root.right, expectNumber);list.RemoveAt(list.Count - 1);}return pathList;}public void Print(List<List<int>> lists){if(lists == null){Console.WriteLine("null");return;}foreach (List<int> 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));}}
}

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

/*
题目名称：
字符流中第一个不重复的字符题目描述：
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。
当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。输出描述：
如果当前字符流没有存在出现一次的字符，返回#字符。代码结构：
class Solution
{public char FirstAppearingOnce(){// write code here}public void Insert(char c){// write code here}
}
*/
using System;
using System.Collections.Generic;
namespace FirstAppearingOnce {class Solution {/// <summary>/// 解法1/// 基本思路：/// 根据ASCII码一共定义了128个字符，因此使用长度为128的数组记录每个字符的出现字数/// 当每个字符出现1次时，入队列。查找第一个不重复字符时，将出现次数不为1的字符，出队。/// 这样队首的元素就是第一个不重复的字符/// </summary>int[] array = new int[128];Queue<char> queue = new Queue<char>();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);}}/// <summary>/// 解法2/// 基本思路：/// 使用长度为128的数组记录只出现1次的字符的出现顺序，出现大于1次的字符对应的值都为-1，未出现的对应为0/// 遍历数组，找到数组中元素值最小且大于0的，就是第一个不重复的字符/// </summary>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());}}
}

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

/*
题目名称：
第一个只出现一次的字符题目描述：
在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置,
如果没有则返回 -1（需要区分大小写）.代码结构：
class Solution
{public int FirstNotRepeatingChar(string str){// write code here}
}
*/
using System;
namespace FirstNotRepeatingChar {class Solution {/// <summary>/// 解法/// 解题思路：/// 先遍历一遍字符串统计每个字符的出现次数，然后再遍历一遍字符串，找出第一个出现次数为1的字符的索引/// 利用0 - 57的数组下标，来对应A(65) - Z(90) - a(97) - z(122)的ASCII值/// 例如65对应的是下标0, 122对应的是下标57/// </summary>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));}}
}

🔥数据流中的中位数

/*
题目名称：
数据流中的中位数题目描述：
如何得到一个数据流中的中位数？
如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。代码结构：
class Solution
{public void Insert(int num){// write code here}public double GetMedian(){// write code here}
}
*/
using System;
namespace GetMedian {public class TreeNode {public TreeNode left;public TreeNode right;public int val;public TreeNode(int x){val = x;}}class Solution {/// <summary>/// 解法1/// 基本思路：/// 插入时，动态构建二叉搜索树，小于根节点值的放到左子树，大于等于根节点值的放到右子树/// 获取中位数时查找儿叉搜索树即可/// </summary>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;}/// <summary>/// TODO 利用优先队列，构建两个堆，大顶堆和小顶堆/// </summary>public void Test() {Insert(1);Insert(3);Insert(4);Insert(1);Console.WriteLine(GetMedian());}}
}

🔥二叉树的下一个结点

/*
题目名称：
二叉树的下一个结点题目描述：
给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。代码结构：
class Solution
{public TreeLinkNode GetNext(TreeLinkNode pNode){// write code here}
}
*/
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 {/// <summary>/// 解法/// 基本思路：/// 中序遍历的顺序是先左节点，再根节点，再右节点/// 1. 节点为空，返回空/// 2. 如果节点有右节点，则一直向下寻找该右节点的左节点，直到叶子节点为止，即为下一个节点/// 3. 如果节点有父节点，且是父节点的左节点，则返回父节点。否则继续判断其父节点是否满足条件，直到父节点为空。/// 前中后续遍历介绍 https://blog.csdn.net/FightLei/article/details/89281600/// </summary>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);}}}
}

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

/*
题目名称：
数字在排序数组中出现的次数题目描述：
统计一个数字在排序数组中出现的次数。代码结构：
class Solution
{public int GetNumberOfK(int[] data, int k){// write code here}
}
*/
using System;
namespace GetNumberOfK {class Solution {/// <summary>/// 解法，二分查找/// 在排序数组中查找，首先想到的是二分查找/// 由于数组中的数字都是整数，所以可以通过分别查找k+0.5和k-0.5这两个数字应该插入的位置/// 两个位置的差值就是数字k的个数/// 由于题目未说明排序数组是递增还是递减，所以通过increase标志判断/// </summary>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));}}
}

🔥丑数

/*
题目名称：
丑数题目描述：
把只包含质因子2、3和5的数称作丑数（Ugly Number）。
例如6、8都是丑数，但14不是，因为它包含质因子7。 
习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。代码结构：
class Solution
{public int GetUglyNumber_Solution(int index){// write code here}
}
*/
using System;
using System.Collections.Generic;
namespace GetUglyNumber {class Solution {/// <summary>/// 解法/// 基本思路：/// 丑数只包含因子2,3,5（除1以外），所以除1外的所有丑数都可以用2x * 3y * 5z表示/// 问题的关键在于如何按照从小到大的顺序获取丑数/// 显然的是每获取到一个丑数x，我们都可以通过2x，3x, 5x算出三个新的丑数，但是新算出的丑数和之前已经算出的丑数的大小不好比较/// 我们可以分三个队列来解决这个问题，分别是乘2，乘3，乘5的队列/// 通过乘以2得到的丑数都放到乘2的队列中，乘3和乘5的同理，这样单看每个队列中的丑数一定是从小到大排列的/// 此时这个三个队列头中的最小值就是整个待排丑数中的最小值，也就是我们要获取的下一个丑数值/// 下面的代码是利用q2,q3,q5一直表示各自队列的头被计算出来时使用的丑数的索引/// </summary>public int GetUglyNumber_Solution(int index){if(index <= 0){return 0;}List<int> list = new List<int>(){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));}}
}

🔥矩阵中的路径

/*
题目名称：
矩阵中的路径题目描述：
请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。 
例如 a b c e s f c s a d e e 矩阵中包含一条字符串"bcced"的路径，
但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
路径不能再次进入该格子。代码结构：
class Solution
{public bool hasPath(string matrix, int rows, int cols, string path){// write code here}
}
*/
using System;
namespace HasPath {class Solution {/// <summary>/// 解法/// 基本思路：/// 将matrix字符串转换为多维数组，分别以数组的每个元素为起点，判断路径是否存在/// 从起点开始按上下左右的顺序搜索，已经经过的元素标记为-1/// 如果此路不通，则回溯到上一层，并还原标记位/// </summary>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));}}
}

🔥树的子结构

/*
题目名称：
树的子结构题目描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）代码结构：
class Solution
{public bool HasSubtree(TreeNode pRoot1, TreeNode pRoot2){// write code here}
}
*/
using System;
namespace HasSubtree {public class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode (int x){val = x;}}class Solution {/// <summary>/// 解法，递归/// 基本思路：/// 如果两颗树的根节点相同，则接着判断两颗树的左右子树是否是子树关系///     如果也是的话直接返回true///     如果不是的话，就什么也不做，因为目前仍不能判断B是不是A的子树/// 接着判断B是否是A的左子树的子树，如果是的直接返回true/// 接着判断B是否是A的右子树的子树，如果是的直接返回true/// </summary>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));}}
}

🔥数组中的逆序对

/*
题目名称：
数组中的逆序对题目描述：
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
输入一个数组,求出这个数组中的逆序对的总数P。
并将P对1000000007取模的结果输出。 即输出P%1000000007输入描述：
题目保证输入的数组中没有的相同的数字
数据范围：对于%50的数据,size<=10^4对于%75的数据,size<=10^5对于%100的数据,size<=2*10^5代码结构：
class Solution
{public int InversePairs(int[] data){// write code here}
}
*/
using System;
namespace InversePairs {class Solution {/// <summary>/// 解法，归并排序思想/// 基本思路：/// 将含有n个元素的数组，不断的进行二分为两个子数组。直到每个子数组都只含有一个元素。/// 再进行合并两个子数组，利用一个临时数组，不断从两个子数组中选出最大值放到临时数组中。/// 在比较时，由于每个子数组都是有序递减的，所以只需要比较子数组的首元素即可（此时进行逆序对的数量统计，如果/// 该元素已经大于右边子数组的首元素，则右边子数组的所有元素都小于该元素，即都可以和该元素构成逆序对）。/// 归并排序介绍 https://www.cnblogs.com/iwiniwin/p/12609549.html/// </summary>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));}}
}

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