哈喽！大家好，我是IT技术猿猴，最爱海贼王💞💞💞
是一位爱好技术的【技术宅男】！😜😜😜
💞💞💞 如果有对技术感兴趣的宅友，欢迎关注💞💞💞
❤️❤️❤️感谢各位❤️❤️❤️
————————————————
🏳️🌈下面请看本篇文章目录
目录
🏳️🌈整数中1出现的次数（从1到n整数中1出现的次数）
📢孩子们的游戏(圆圈中最后剩下的数)
📣数组中出现次数超过一半的数字
💞机器人的运动范围
🎉构建乘积数组
🔥二进制中1的个数
🏳️🌈字符串的排列
📢平衡二叉树
📣旋转数组的最小数字
💞表示数值的字符串
🎉栈的压入、弹出序列
🔥对称的二叉树
🏳️🌈跳台阶
📢变态跳台阶
📣二叉搜索树的第k个结点
💞左旋转字符串
🎉扑克牌顺子
🔥正则表达式匹配
🏳️🌈滑动窗口的最大值
📢合并两个排序的链表
📣二叉树的镜像
🏳️🌈整数中1出现的次数（从1到n整数中1出现的次数）
/*题目名称：整数中1出现的次数（从1到n整数中1出现的次数）题目描述：求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。代码结构：class Solution{public int NumberOf1Between1AndN_Solution(int n){// write code here}}*/using System;namespace NumberOf1Between1AndN {class Solution {/// <summary>/// 解法1/// 基本思路：/// 逐一考察1~n的每一个数里有多少个1。每个数字可以通过对10求余来判断最后一位是否为1/// 时间复杂度是n*ln(n)/// </summary>public int NumberOf1Between1AndN_Solution(int n){int count = 0;for(int i = 1; i < n + 1; i ++){int m = i;while(m > 0){if(m % 10 == 1){count ++;}m = m / 10;}}return count;}/// <summary>/// 解法2，数学归纳法/// 首先来看每个数字的个位是1的情况/// 以0-9为一个阶段会包含一个1，包含x个完整阶段就包含x个1。/// 对非完整阶段，比如6，显然如果这个数小于1就包含0个，大于等于1就包含1个/// 因此公式是：n / 10 * 1 + (n % 10) < 1 ? 0 : 1 /// 再来看十位/// 以0-99为一个阶段，十位上会包含10个1（10 - 19）/// 对于非完整阶段，假设为m，如果m小于10就是0个，m大于等于10且小于19就是m - 10 + 1，m大于19就是10/// 再来看百位/// 以0-999为一个阶段，百位上会包含100个1（100 - 199）/// 对于非完整阶段，假设为m，如果m小于100就是0个，m大于等于100且小于199就是m - 100 + 1，m大于199就是100/// 千位，万位等等以此类推，总结公式就是/// 以i表示位数/// count(i) = n / (i * 10) * i + f(n % (i * 10))/// f(mod) = if(mod < i) return 0 elseif mod < (2 * i -1) return mod - i + 1 else return i/// 对于f(mod)中的if else同样可以再进行归纳/// f(mod) = (0和mod - i + 1中的较大值)和i中的较小值/// </summary>public int NumberOf1Between1AndN_Solution2(int n){int count = 0;for(int i = 1; i <= n; i = i * 10){count += n / (i * 10) * i + Math.Min(Math.Max(0, n % (i * 10) - i + 1), i);}return count;}public void Test() {Console.WriteLine(NumberOf1Between1AndN_Solution(11));Console.WriteLine(NumberOf1Between1AndN_Solution2(1));}}}
📢孩子们的游戏(圆圈中最后剩下的数)
/*题目名称：孩子们的游戏(圆圈中最后剩下的数)题目描述：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)如果没有小朋友，请返回-1代码结构：class Solution{public int LastRemaining_Solution(int n, int m){// write code here}}*/using System;namespace LastRemaining {class Solution {/// <summary>/// 解法/// 基本思路：/// 约瑟夫环问题，遍历到数组末尾时再从头开始遍历，模拟环/// 使用array数组记录每个编号是否被移除 0表示未移除 -1表示移除/// while循环不断遍历array数组，直到所有元素值都为-1，表示全部被移除/// 最后一个被移除的元素就是要找的小朋友/// </summary>public int LastRemaining_Solution(int n, int m){int[] array = new int[n];int count = 0, temp = 0;int index = 0;while(count < n){if(index == n){index = 0;}if(array[index] == 0){if(temp == m - 1){array[index] = -1;temp = 0;count ++;}else{temp ++;}}index ++;}return index - 1;}public void Test() {int n = 1;// n = 0;// n = 5;// n = 6;int m = 1;// m = 2;// m = 3;Console.WriteLine(LastRemaining_Solution(n, m));}}}
📣数组中出现次数超过一半的数字
/*题目名称：数组中出现次数超过一半的数字题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。代码结构：class Solution{public int MoreThanHalfNum_Solution(int[] numbers){// write code here}}*/using System;using System.Collections.Generic;namespace MoreThanHalfNum {class Solution {/*解法1基本思路：利用Dictinary记录每个元素的出现次数，如果该元素出现次数大于数组的一半则输出*/public int MoreThanHalfNum_Solution(int[] numbers){if (numbers == null) return 0;Dictionary<int, int> dic = new Dictionary<int, int>();foreach(int i in numbers){if (dic.ContainsKey(i)){dic[i] ++;}else{dic.Add(i, 1);}if (dic[i] > numbers.Length / 2){return i;}}return 0;}/*解法2基本思路：如果存在元素的数量大于数组的一半，那么排序后，数组中间的那个数一定是该元素。比如{1,2,2,2,2,2,3,4,5}排序后再判断数组中间的那个数出现次数是否大于数组长度的一半*/public int MoreThanHalfNum_Solution2(int[] numbers){if (numbers != null && numbers.Length > 0){Array.Sort(numbers);int num = numbers[numbers.Length / 2];int count = 0;foreach(int i in numbers){if (i == num){count ++;}}if (count > numbers.Length / 2){return num;}}return 0;}/*解法3基本思路：类似于阵地攻守，第一个数字作为第一个士兵，守阵地 count = 1遇到相同数字：count++遇到不同数字：count--，即遇到敌人当遇到count = 0的情况，这表示该士兵阵亡，使用下一个数字代替如果一个元素的数量超过数组长度的一半，则它的数量应该比其他剩余元素数量之和还要多，则剩下的那个数字就是该元素最后再加一次循环，判断该元素数量是否查过数组长度的一半即可*/public int MoreThanHalfNum_Solution3(int[] numbers){if (numbers != null && numbers.Length > 0){int count = 0;int num = 0;foreach(int i in numbers){if (count == 0){num = i;count = 1;}else{if(i == num){count ++;}else{count --;}}}count = 0;foreach (int i in numbers){if (i == num) {count ++;}}if (count > numbers.Length / 2) {return num;}}return 0;}public void Test() {int[] numbers = new int[]{1,2,3,2,2,2,5,4,2};// numbers = null;// numbers = new int[]{0, 1, 0};// Console.WriteLine(MoreThanHalfNum_Solution(numbers));// Console.WriteLine(MoreThanHalfNum_Solution2(numbers));// Console.WriteLine(MoreThanHalfNum_Solution3(numbers));}}}
💞机器人的运动范围
/*题目名称：机器人的运动范围题目描述：地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？代码结构：class Solution{public int movingCount(int threshold, int rows, int cols){// write code here}}*/using System;namespace MovingCount {class Solution {/// <summary>/// 解法/// 基本思路：/// 利用递归，从0，0点，开始向上下左右开始搜索/// 利用flag数组记录搜索过的节点，置为true。/// 利用count统计进入的格子个数/// 注意，这里在回溯的时候是不用将标记还原的/// </summary>int count = 0;public int Calc(int num) {int sum = 0;while(num > 0){sum += num % 10;num /= 10;}return sum;}public void MovingCountImpl(int threshold, int rows, int cols, int row, int col, bool[,] flag) {if(row < 0 || row >= rows || col < 0 || col >= cols || flag[row, col]){return;}if(Calc(row) + Calc(col) > threshold){return;}count ++;flag[row, col] = true;MovingCountImpl(threshold, rows, cols, row, col + 1, flag);MovingCountImpl(threshold, rows, cols, row, col - 1, flag);MovingCountImpl(threshold, rows, cols, row + 1, col, flag);MovingCountImpl(threshold, rows, cols, row - 1, col, flag);}public int MovingCount(int threshold, int rows, int cols){bool[,] flag = new bool[rows, cols];count = 0;MovingCountImpl(threshold, rows, cols, 0, 0, flag);return count;}public void Test() {int threshold = 9;int rows = 100;int cols = 100;Console.WriteLine(MovingCount(threshold, rows, cols));}}}
🎉构建乘积数组
/*题目名称：构建乘积数组题目描述：给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。代码结构：class Solution{public int[] multiply(int[] A){// write code here}}*/using System;namespace Multiply {class Solution {/// <summary>/// 解法1/// 基本思路：/// 对于每个元素B[i]/// 先计算i左边的元素乘积 B[i] = B[0] * B[1] * B[2] * ... * B[i - 1]/// 再计算i右边的元素乘积 B[i] = B[i + 1] * B[i + 2] * ... * B[n - 1]/// 再把两边的乘积相乘/// </summary>public int[] Multiply(int[] A){if (A == null) return A;int[] B = new int[A.Length];int ret = 1;for(int i = 0; i < A.Length; ret *= A[i ++]){B[i] = ret;}ret = 1;for(int i = A.Length - 1; i >= 0; ret *= A[i --]) {B[i] *= ret;}return B;}public void Print(int[] array) {foreach (int item in array){ Console.WriteLine(item);}} public void Test() {int[] A = new int[]{1, 2, 3, 4};// A = new int[]{1, 2, 3, 4, 5};// A = new int[]{0};// A = new int[]{0, 1};Print(Multiply(A));}}}
🔥二进制中1的个数
/*题目名称：二进制中1的个数题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。代码结构：class Solution{public int NumberOf1(int n){// write code here}}补充：正数的补码等于其原码负数的补码等于其原码按位取反后（除了最高位）加1*/using System;namespace NumberOf1 {class Solution {/// <summary>/// 解法1/// 基本思路：/// 对于本题，首先想到的是将目标数一直右移，然后将该数和1相与，计算1的个数，直到该二进制数为0为止/// 但是考虑负数的情况，和正数右移最高位补0不同的是，负数右移最高位补1，这样就会有无数个1，导致循环无法停止/// 既然将目标数右移和1与行不通，那么我们可以反过来/// 将1不断左移（从最低位到最高位每一位依次是1，其他位是0），然后和目标数相与来求1的个数/// </summary>public int NumberOf1(int n){int unit = 1, count = 0;while(unit != 0){if((n & unit) != 0){count ++;}unit <<= 1;}return count;}/// <summary>/// 解法2/// 基本思路：/// 上面解法1的时间复杂度是O(n的位数)，n有所少位就要循环多少次。可以利用一个小技巧，降低算法的时间复杂度。/// 对于数值n，将n - 1后再和n相与，得到的值相当于将n从右边数的第一个1变成0。/// n的二进制表示中有多少个1，就能变多少次。时间复杂度可以优化为O(n中1的个数)/// 详细介绍 /iwiniwin/p/11058255.html/// </summary>public int NumberOf12(int n){int count = 0;while(n != 0){count ++;n &= (n - 1);}return count;}public void Test() {int n = 6;n = 1;n = 0;n = -1;n = -20;// Console.WriteLine(NumberOf1(n));Console.WriteLine(NumberOf12(n));}}}
🏳️🌈字符串的排列
/*题目名称：字符串的排列题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述:输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。代码结构：class Solution{public List<string> Permutation(string str){// write code here}}*/using System;using System.Collections.Generic;namespace Permutation {class Solution {/*解法1，递归基本思路：对于目标字符串，每次首先确定第一个字符。例如对于字符串abc，则第一个字符可以是a或b或c然后将除去选取的第一个字符外的剩下字符串进行递归，重复上面的操作，直到剩下的字符串长度为1为止。通过HashSet过滤重复的字符串，通过Sort方法进行排序对于字符串abc，递归过程如下所示选取a为第一个字符（剩下字符串bc）选取b为第一个字符（剩下字符串c，长度为1，结束递归，得到字符串abc）选取c为第一个字符（剩下字符串b，长度为1，结束递归，得到字符串acb）选取b为第一个字符（剩下字符串ac）选取a为第一个字符（剩下字符串c，长度为1，结束递归，得到字符串bac）选取c为第一个字符（剩下字符串b，长度为1，结束递归，得到字符串bca）选取c为第一个字符（剩下字符串ab）选取a为第一个字符（剩下字符串c，长度为1，结束递归，得到字符串cab）选取b为第一个字符（剩下字符串b，长度为1，结束递归，得到字符串cba）*/public void PermutationImpl(string pre, string str, HashSet<string> set){if (str.Length == 1) {set.Add(pre + str);return;}for(int i = 0; i < str.Length; i ++) {PermutationImpl(pre + str[i], str.Remove(i, 1), set);}}public List<string> Permutation(string str){HashSet<string> set = new HashSet<string>();PermutationImpl("", str, set);List<string> list = new List<string>(set);list.Sort();return list;}/*解法2，递归基本思路：和解法1思路相同。区别在于选取首字符后剩余字符串的表示和重复字符串的过滤对剩余字符串的处理，解法1是通过str.Remove(i, 1)返回的新字符串表示剩余字符串解法2是通过char数组，swap方法依次将选取的字符和index位置的元素互换，然后index+1及之后的就是剩余字符串对重复字符串的处理，解法1是通过HashSet的特性自动过滤重复字符串（即使往HashSet中Add重复字符串也会被自动忽略）解法2是通过算法判断是重复字符串则不再Add，如果选取的首字符相同，则剩下的元素的全排列结果必然是重复的，可以过滤*/public void Swap(char[] chars, int i, int j){char temp = chars[i];chars[i] = chars[j];chars[j] = temp;}public void PermutationImpl2(char[] chars, int index, List<string> list){if (index == chars.Length){list.Add(new string(chars));return;}HashSet<char> set = new HashSet<char>();for(int i = index; i < chars.Length; i ++){if (!set.Contains(chars[i])){set.Add(chars[i]);Swap(chars, i, index);PermutationImpl2(chars, index + 1, list);Swap(chars, index, i);}}}public List<string> Permutation2(string str){List<string> list = new List<string>();if (str != null && str.Length > 0){char[] chars = str.ToCharArray();PermutationImpl2(chars, 0, list);list.Sort();}return list;}/*解法3，字典序全排列算法基本思路：顾名思义就是按照字典的顺序（a-z, 1-9）列出所有的排列。对于数字串1234我们可以知道其最小排列为1234（从左到右依次递增）其最大排列为4321（从右到左依次递增）对于给定字符串1342，下一个恰好比它大的是1423 字典序算法的重点就是如何求得这个下一个刚刚比它大的排列我们已经知道从右到左依次递增的排列是最大的，那么越满足这个条件的排列就是越大的从右到左，我们找到第一个不满足这个条件的数（即左边的数比右边的数小），记下它的位置，将这个不符合条件的数和右边比它大的数中的最小数进行交换，然后将这个位置右边的数进行翻转即可（因为这个位置的数值已经比原字符串大了，所以这个位置右边的数应该是最小的）字符串1342的求解下一个恰好比它大的字符串的过程如下1. 从右到左找到第一个不满足递增规律的数，即32. 将3和它右边比它大的数中的最小数即4进行交换，得到14323. 然后将4之后的字符串翻转，得到1423*/public void Reverse(char[] chars, int index){for(int i = index; i <= (index + (chars.Length- 1 - index)/2); i ++){Swap(chars, i, chars.Length - 1 - i + index);}}public List<string> Permutation3(string str){List<string> list = new List<string>();if (str != null && str.Length > 0){char[] chars = str.ToCharArray();Array.Sort(chars);list.Add(new string(chars));while(true){int i = chars.Length - 1;while(i > 0 && chars[i - 1] >= chars[i]){i --;}if(i == 0) break;int j = i;while(j < chars.Length && chars[j] > chars[i - 1]){j ++ ;}Swap(chars, i - 1, j - 1);Reverse(chars, i);list.Add(new string(chars));}}return list;}public void Print(List<string> list) {foreach (string item in list){Console.WriteLine(item);}}public void Test() {// Print(Permutation("abc"));Print(Permutation2("aba"));// Print(Permutation3("abac"));}}}
📢平衡二叉树
/*题目名称：平衡二叉树题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。代码结构：class Solution{public bool IsBalanced_Solution(TreeNode pRoot){// write code here}}补充：平衡二叉树定义：1. 可以是空树2. 假如不是空树，任何一个节点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1*/using System;namespace IsBalanced {public class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode (int x){val = x;}}class Solution {/// <summary>/// 解法，递归/// 基本思路：/// 按照平衡二叉树的定义，递归计算左右子树的高度差是否大于1来判断是否是平衡二叉树/// 如果发现某棵树的左右子树高度差大于1，即不是平衡二叉树，则直接返回-1，终止递归/// </summary>public int TreeDepth(TreeNode node){if(node == null){return 0;}int left = TreeDepth(node.left);if(left == - 1){return -1;}int right = TreeDepth(node.right);if(right == - 1){return -1;}if(Math.Abs(left - right) > 1){return -1;}return left > right ? left + 1 : right + 1;}public bool IsBalanced_Solution(TreeNode pRoot){if(TreeDepth(pRoot) == -1){return false;}return true;}public void Test() {TreeNode node = new TreeNode(1);// node = null;node.left = new TreeNode(2);node.left.left = new TreeNode(3);node.right = new TreeNode(4);node.right.right = new TreeNode(5);// node.right.right.right = new TreeNode(6);node.right.right.left = new TreeNode(7); Console.WriteLine(IsBalanced_Solution(node));}}}
📣旋转数组的最小数字
/*题目名称：旋转数组的最小数字题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。代码结构：class Solution{public int minNumberInRotateArray(int[] rotateArray){// write code here}}*/using System;namespace MinNumberInRotateArray {class Solution {/// <summary>/// 解法1/// 基本思路：/// 对于非减数组来说，数组左边的元素一定小于等于数组右边的元素。/// 当对非减数组进行旋转后（把数组最开始的元素搬到末尾），/// 则在遍历过程中可能会出现左边的元素反而小于右边的元素，当第一次出现这种情况时，/// 一定是原非减数组的开头，即整个数组的最小元素。/// </summary>public int MinNumberInRotateArray(int[] rotateArray){for(int i = 0; i < rotateArray.Length - 1; i ++){if(rotateArray[i] > rotateArray[i + 1]){return rotateArray[i + 1];}}return rotateArray.Length == 0 ? 0 : rotateArray[rotateArray.Length - 1];}/// <summary>/// 解法2/// 基本思路：/// 对于有序数组的查找问题，首先想到的就是二分查找。/// 本题是非递减数组的旋转数组，仍具有一定的顺序性，所以稍微修改一下二分查找仍然可以解题/// 旋转数组可以看成是由左右两个递增数组组成/// 通过将right指向的元素与middle指向的元素比较/// 如果小于，则说明middle处于左边的递增数组，left = middle + 1，搜寻范围右移/// 如果大于，则说明middle处于右边的递增数组，right = middle，搜寻范围左移/// 如果等于，此时并不能判断到底处于左边还是右边，可以看成是顺序性丢失了，此时right -- ，二分查找退化为普通顺序遍历/// 二分查找介绍 /iwiniwin/p/10793650.html/// </summary>public int MinNumberInRotateArray2(int[] rotateArray){if(rotateArray.Length == 0) return 0;int left = 0, right = rotateArray.Length - 1;while(left < right){int middle = (right + left) / 2;if(rotateArray[right] < rotateArray[middle]){left = middle + 1;}else if(rotateArray[right] > rotateArray[middle]){right = middle;}else{right --;}}return rotateArray[left];}public void Test() {int[] rotateArray = new int[]{1, 2, 3, 4, 0};rotateArray = new int[]{};rotateArray = new int[]{3, 4, 5, 5, 5, 6, 6, 1, 1, 2};// rotateArray = new int[]{3, 4, 5, 5, 2, 2};// rotateArray = new int[]{1, 2, 1};// rotateArray = new int[]{1, 0};// rotateArray = new int[]{1};// rotateArray = new int[]{10,1,10,10,10};rotateArray = new int[]{10,10,10,1,10,10};// Console.WriteLine(MinNumberInRotateArray(rotateArray));Console.WriteLine(MinNumberInRotateArray2(rotateArray));}}}
💞表示数值的字符串
/*题目名称：表示数值的字符串题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。代码结构：class Solution{public bool isNumeric(char[] str){// write code here}}*/using System;using System.Text.RegularExpressions;namespace IsNumeric {class Solution {/// <summary>/// 解法1/// 基本思路：/// 根据数值字符串标准判断，每个字符满足如下条件/// 1. 字符是'0'-'9'/// 2. 字符是'+'或'-'，只能出现在首位或'e'/'E'的后面/// 3. 字符是'e'/'E'，只能出现一次，且不能在首尾/// 4. 字符是'.'，只能出现一次，且不能在首位（可以在尾部），且不能在'e'/'E'之后出现/// </summary>public bool IsNumeric(char[] str){if(str == null || str.Length == 0) return false;int dotCount = 0, eCount = 0;for(int i = 0; i < str.Length; i ++){if(str[i] >= '0' && str[i] <= '9') continue;if(str[i] == '+' || str[i] == '-'){if(i == 0 || (i > 0 && (str[i - 1] == 'e' || str[i - 1] == 'E'))) continue;}if((str[i] == 'e' || str[i] == 'E') && i > 0 && i < str.Length - 1 && eCount == 0){eCount ++;continue;}if(str[i] == '.' && i > 0 && i < str.Length && eCount == 0 && dotCount == 0){dotCount ++;continue;}return false;}return true;}/// <summary>/// 解法2/// 基本思路：/// 使用正则表达式进行匹配/// </summary>public bool IsNumeric2(char[] str){return Regex.IsMatch(new string(str), @"^[+-]?\d*(\.\d+)?([eE][+-]?\d+)?$");}/// <summary>/// TODO 状态迁移表解法/// </summary>public void Test() {char[] str = new char[]{'1', '.', '2', '.', '3'};// str = new char[]{'+', '1', '2'};// str = new char[]{'5', 'e', '2'};// str = new char[]{'3', '.', '1', '4'};// str = new char[]{'-', '1', 'E', '-', '5'};// str = new char[]{'1', '2', 'e'};// str = new char[]{'1', '2', 'e', '+', '4', '.', '3'};// str = new char[]{'1', 'a', '3', '.', '4'};// str = new char[]{'-', '.', '1', '2'};// Console.WriteLine(IsNumeric(str));Console.WriteLine(IsNumeric2(str));}}}
🎉栈的压入、弹出序列
/*题目名称：栈的压入、弹出序列题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）代码结构：class Solution{public bool IsPopOrder(int[] pushV, int[] popV){// write code here}}*/using System;using System.Collections.Generic;namespace IsPopOrder {class Solution {/// <summary>/// 解法/// 基本思路：/// 使用一个辅助栈根据pushV来模拟入栈，同时通过popV模拟出栈/// 当辅助栈最后为空，则表示popV是pushV的弹出序列/// </summary>public bool IsPopOrder(int[] pushV, int[] popV){Stack<int> stack = new Stack<int>();for(int i = 0, j = 0; i < pushV.Length; i ++){stack.Push(pushV[i]);while(stack.Count > 0 && stack.Peek() == popV[j]){stack.Pop();j ++;}}return stack.Count == 0;}public void Test() {int[] pushV = new int[]{1, 2, 3, 4, 5};// pushV = new int[]{1, 2};int[] popV = new int[]{4, 5, 3, 2, 1};// popV = new int[]{4, 3, 5, 1, 2};// popV = new int[]{1, 2};Console.WriteLine(IsPopOrder(pushV, popV));}}}
🔥对称的二叉树
/*题目名称：对称的二叉树题目描述：请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。代码结构：class Solution{public bool isSymmetrical(TreeNode pRoot){// write code here}}*/using System;using System.Collections.Generic;namespace IsSymmetrical {public class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode (int x){val = x;}}class Solution {/// <summary>/// 解法1，递归/// 基本思路：/// 判断一棵二叉树是否是对称的，就是递归判断它的左右子树是否是对称/// 1. 左子树的val是否等于右子树的val/// 2. 左子树的左子树是否和右子树的右子树对称/// 3. 左子树的右子树是否和右子树的左子树对称/// </summary>public bool IsSymmetricalImpl(TreeNode root1, TreeNode root2){if(root1 == null && root2 == null){return true;}if(root1 != null && root2 != null && root1.val == root2.val){return IsSymmetricalImpl(root1.left, root2.right) && IsSymmetricalImpl(root1.right, root2.left);}return false;}public bool IsSymmetrical(TreeNode pRoot){if(pRoot != null){return IsSymmetricalImpl(pRoot.left, pRoot.right);}return true;}/// <summary>/// 解法2，BFS/// 基本思路：/// 广度优先搜索，每次左子树和右子树成对入队，成对出队/// 出队时，比较这一对，记为left，right/// 1. 都为空，继续/// 2. 一个为空一个不为空，返回false/// 3. 都不为空，比较val，不相等返回false/// 4. val相等，继续入队(left.left，right.right), (left.right, right.left)/// </summary>public bool IsSymmetrical2(TreeNode pRoot){if(pRoot == null){return true;}Queue<TreeNode> queue = new Queue<TreeNode>();queue.Enqueue(pRoot.left);queue.Enqueue(pRoot.right);while(queue.Count > 0){TreeNode left = queue.Dequeue();TreeNode right = queue.Dequeue();if(left == null && right == null){continue;}if(left != null && right != null && left.val == right.val){queue.Enqueue(left.left);queue.Enqueue(right.right);queue.Enqueue(left.right);queue.Enqueue(right.left);}else{return false;}}return true;}/// <summary>/// 解法3，DFS/// 基本思路：/// 深度优先搜索，基本思路与BFS类似，只是使用栈保存成对的节点/// </summary>public bool IsSymmetrical3(TreeNode pRoot){if(pRoot == null){return true;}Stack<TreeNode> stack = new Stack<TreeNode>();stack.Push(pRoot.left);stack.Push(pRoot.right);while(stack.Count > 0){TreeNode left = stack.Pop();TreeNode right = stack.Pop();if(left == null && right == null){continue;}if(left == null || right == null){return false;}if(left.val != right.val){return false;}stack.Push(left.left);stack.Push(right.right);stack.Push(left.right);stack.Push(right.left);}return true;}public void Test() {TreeNode pRoot = null;pRoot = new TreeNode(0);pRoot.left = new TreeNode(1);pRoot.left.left = new TreeNode(2);pRoot.left.right = new TreeNode(3);pRoot.right = new TreeNode(1);pRoot.right.right = new TreeNode(2);pRoot.right.left = new TreeNode(3);// Console.WriteLine(IsSymmetrical(pRoot));// Console.WriteLine(IsSymmetrical2(pRoot));Console.WriteLine(IsSymmetrical3(pRoot));}}}
🏳️🌈跳台阶
/*题目名称：跳台阶题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。代码结构：class Solution{public int JumpFloor(int number){// write code here}}*/using System;namespace JumpFloor {class Solution {/// <summary>/// 解法/// 基本思路： /// 对于n级台阶，设一共有F(n)种跳法/// 第一次青蛙可以选择跳1级，则剩下的跳法就是F(n-1) /// 青蛙也可以选择跳2级，则剩下的跳法就是F(n-2) /// 即F(n) = F(n-1) + F(n-2)，这不就是斐波那契数列嘛/// 所以求斐波那契数列的解法都可以用于这道题 详情可参考 Fibonacci.cs 文件/// 这里给出简单的递归解法，其余斐波那契数列解法不再赘述/// </summary>public int JumpFloor(int number){if(number <= 2){return number;}return JumpFloor(number - 1) + JumpFloor(number - 2);}public void Test() {int number = 0;number = 2;number = 3;number = 4;number = 39;Console.WriteLine(JumpFloor(number));}}}
📢变态跳台阶
/*题目名称：变态跳台阶题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。代码结构：class Solution{public int jumpFloorII(int number){// write code here}}想法：当拿到一道题时，不知道怎么下手去解题，毫无头绪时，试着找找规律，可能会有惊喜*/using System;namespace JumpFloorII {class Solution {/// <summary>/// 解法1/// 基本思路：/// 列出结果的前几项，找找规律，可能会有意想不到的收获/// 对于1级台阶，青蛙只有1 = 2^0种跳法/// 对于2级台阶，青蛙有2 = 2^1种跳法（分别是{1,1}, {2}）/// 对于3级台阶，青蛙有4 = 2^2种跳法（分别是{1,1,1}, {1,2}, {2,1}, {3}）/// 对于4级台阶，青蛙有8 = 2^3种跳法（分别是{1,1,1,1}, {1,1,2}, {1,2,1}, {2,1,1}, {2,2}, {1,3}, {3,1}, {4}）/// 不难发现，对于n级台阶，总跳法数是2^(n-1)/// 最终这道题被转换成如何求解2^(n-1)，可以使用整数的快速幂解题/// 详细介绍 /iwiniwin/p/10807310.html/// </summary>public int JumpFloorII(int number){if(number <= 0) return 0;int n = number - 1;int m = 2;int ret = 1;while(n > 0){if((n & 1) > 0){ret *= m;}m *= m;n >>= 1;}return ret;}/// <summary>/// 解法2/// 基本思路：/// 对于求解2^(n-1)，可以继续优化，利用左移运算，只使用一行代码就可以得到2^(n-1)/// 对于数字1，左移1位二进制表示是10，即2 = 2^1/// 左移2位是100，即4 = 2^2/// 左移3位是1000，即8 = 2^3/// 以此类推，左移n位，就是2^n/// </summary>public int JumpFloorII2(int number){return number > 0 ? 1 << (number - 1) : 0;}/// <summary>/// 解法3，递归/// 基本思路：/// 先来看F(n)，对于一个n级台阶来说/// 青蛙第一次可以跳1级，则还剩n - 1级台阶，即F(n - 1)/// 青蛙第一次可以跳2级，则还剩n - 2级台阶，即F(n - 2)/// .../// 青蛙第一次可以跳n - 1级，则还剩1级台阶，即F(1)/// 青蛙第一次可以跳n级，即1种跳法/// 则F(n) = F(n - 1) + F(n - 2) + F(n - 3) + F(n - 4) + ... + F(1) + 1/// 很显然F(1）= 1，在已知F(1)的情况下，我们可以利用递归解这道题/// </summary>public int JumpFloorII3(int number){int count = number > 0 ? 1 : 0;for(int i = number - 1; i > 0; i --){count += JumpFloorII3(i);}return count;}public void Test() {int number = 3;number = 5;// number = 1;// number = 0;// Console.WriteLine(JumpFloorII(number));Console.WriteLine(JumpFloorII2(number));// Console.WriteLine(JumpFloorII3(number));}}}
📣二叉搜索树的第k个结点
/*题目名称：二叉搜索树的第k个结点题目描述：给定一棵二叉搜索树，请找出其中的第k小的结点。例如，（5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。代码结构：class Solution{public TreeNode KthNode(TreeNode pRoot, int k){// write code here}}补充：二叉搜索树（Binary Search Tree）定义：1. 可以是空树2. 若不是空树若它的左子树不空，则左子树所有节点的值均小于它的根节点的值若它的右子树不空，则右子树所有节点的值均大于它的根节点的值它的左，右子树也分别为二叉搜索树*/using System;using System.Collections.Generic;namespace KthNode {public class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode (int x){val = x;}}class Solution {/// <summary>/// 解法1/// 基本思路：/// 根据二叉搜索树定义，采用中序遍历（先左节点，再根节点，再右节点）/// 找到的第k个节点，就是第k小的节点/// </summary>int index = 0;public TreeNode KthNode(TreeNode pRoot, int k){if(pRoot != null){TreeNode node = KthNode(pRoot.left, k);if(node != null){return node;}index ++;if(index == k){return pRoot;}node = KthNode(pRoot.right, k);if(node != null){return node;}}return null;}/// <summary>/// 解法2/// 基本思路：/// 中序遍历的非递归实现，利用辅助栈，优先入栈左节点，再入栈 出栈节点的右节点/// 每次出栈，相当于找到一个节点，找到的第k个节点即为第k小的节点/// </summary>public TreeNode KthNode2(TreeNode pRoot, int k){if(pRoot == null) return null;Stack<TreeNode> stack = new Stack<TreeNode>();stack.Push(pRoot);TreeNode node = pRoot.left;while(stack.Count > 0 || node != null){if(node == null){node = stack.Pop();if(--k == 0){return node;}node = node.right;}else{stack.Push(node);node = node.left;}}return null;}public void Test() {TreeNode pRoot = null;pRoot = new TreeNode(5);pRoot.left = new TreeNode(3);pRoot.right = new TreeNode(7);pRoot.left.left = new TreeNode(2);pRoot.left.right = new TreeNode(4);pRoot.right.left = new TreeNode(6);pRoot.right.right = new TreeNode(8);// TreeNode node = KthNode(pRoot, 1);TreeNode node = KthNode2(pRoot, 5);if(node == null){Console.WriteLine("null");}else{Console.WriteLine(node.val);}}}}
💞左旋转字符串
/*题目名称：左旋转字符串题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！代码结构：class Solution{public string LeftRotateString(string str, int n){// write code here}}*/using System;namespace LeftRotateString {class Solution {/// <summary>/// 解法1/// 基本思路：/// 利用对字符串的长度求余，处理左移位数大于字符串长度的情况/// 小于字符串长度的左移，通过分割字符串后调转位置得到/// </summary>public string LeftRotateString(string str, int n){if(str == null || str.Length == 0){return str;}int index = n % str.Length;char[] array = str.ToCharArray();return new string(array, index, str.Length - index) + new string(array, 0, index);}/// <summary>/// 解法2/// 基本思路：/// 同样利用对字符串的长度求余，处理左移位数大于字符串长度的情况/// 对于小于字符串长度的左移，利用 XY的翻转 = YX = （X的翻转 + Y的翻转）的翻转 得到/// </summary>public void Reverse(char[] array, int i, int j){for(int m = i, n = j; m < n; m ++, n --){char temp = array[m];array[m] = array[n];array[n] = temp;}}public string LeftRotateString2(string str, int n){if(str == null || str.Length == 0){return str;}int index = n % str.Length;char[] array = str.ToCharArray();Reverse(array, 0, index - 1);Reverse(array, index, array.Length - 1);Reverse(array, 0, array.Length - 1);return new string(array);}public void Test() {string str = "abcXYZdef";// str = null;// str = "";int n = 3;// n = 0;// n = 1;// n = 9;// n = 10;Console.WriteLine(LeftRotateString(str, n));// Console.WriteLine(LeftRotateString2(str, n));}}}
🎉扑克牌顺子
/*题目名称：扑克牌顺子题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。代码结构：class Solution{public bool IsContinuous(int[] numbers){// write code here}}*/using System;namespace IsContinuous {class Solution {/// <summary>/// 解法1/// 基本思路：/// 先将数组进行排序，同时计算0的个数/// 遍历排序后的数组，要满足，不能有相同元素，不连续元素用0足够补/// </summary>public void Swap(int[] array, int i, int j){int temp = array[i];array[i] = array[j];array[j] = temp;}public bool IsContinuous(int[] numbers){if (numbers == null || numbers.Length == 0){return false;}int count = 0;for(int i = 0; i < numbers.Length; i ++){int index = i;for(int j = i + 1; j < numbers.Length; j ++){if (numbers[j] < numbers[index]){index = j;}}if(numbers[index] == 0){count ++;}Swap(numbers, i, index);}for(int i = count; i < numbers.Length - 1; i ++){int minus = numbers[i + 1] - numbers[i];if(minus != 1){if(minus == 0){return false;}else if((minus - 1) <= count){count -= (minus - 1);}else{return false;}}}return true;}/// <summary>/// 解法2/// 基本思路：/// 满足如下条件的牌可以组成顺子：/// 1. 除0以外，没有重复的牌/// 2. 除0以外，统计最大牌和最小牌，最大牌-最小牌的差值要小于牌的总数/// </summary>public bool IsContinuous2(int[] numbers){if (numbers == null || numbers.Length == 0){return false;}int[] array = new int[14];int max = -1, min = 14;for(int i = 0; i < numbers.Length; i ++){array[numbers[i]] ++;if(numbers[i] == 0){continue;}if(array[numbers[i]] > 1){return false;}if(numbers[i] > max){max = numbers[i];}if(numbers[i] < min){min = numbers[i];}}if(max - min < numbers.Length){return true;}return false;}public void Test() {int[] numbers = new int[]{1, 3, 0, 0, 5};// numbers = null;// numbers = new int[]{};// numbers = new int[]{0};// numbers = new int[]{1, 2, 3, 0, 6};// numbers = new int[]{1, 2, 3, 0, 6, 0};// numbers = new int[]{1, 2, 3, 4, 4};// numbers = new int[]{1, 2, 3, 4, 4, 0, 0};// numbers = new int[]{1, 2, 3, 4, 6};// Console.WriteLine(IsContinuous(numbers));Console.WriteLine(IsContinuous2(numbers));}}}
🔥正则表达式匹配
/*题目名称：正则表达式匹配题目描述：请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配代码结构：class Solution{public bool match(char[] str, char[] pattern){// write code here}}*/using System;namespace Match {class Solution {/// <summary>/// 解法1/// 基本思路：/// 当出现x*时，即任意一个字符加上'*'/// 1. x*消耗0个字符，模式串后移两位，字符串不动/// 2. x*消耗1个字符，模式串后移两位，字符串后移一位/// 3. x*消耗多个字符，即匹配下一个字符，模式串不动，字符串后移一位/// （注意，当这个'x'和字符串对应位的字符不相等时，x*只能等于消耗0个字符）/// 未出现时/// 1. 若模式串与字符串对应位字符相等，则都后移一位，匹配剩余的/// 2. 若不相等，直接返回匹配失败/// </summary>public bool MatchImpl(char[] str, int sIndex, char[] pattern, int pIndex) {if(sIndex == str.Length && pIndex == pattern.Length) return true;if(pIndex < pattern.Length - 1 && pattern[pIndex + 1] == '*'){if (sIndex < str.Length && (str[sIndex] == pattern[pIndex]|| pattern[pIndex] == '.')) {return MatchImpl(str, sIndex, pattern, pIndex + 2) || MatchImpl(str, sIndex + 1, pattern, pIndex) || MatchImpl(str, sIndex + 1, pattern, pIndex + 2);}else{return MatchImpl(str, sIndex, pattern, pIndex + 2);}}if(sIndex >= str.Length || pIndex >= pattern.Length) return false;if(str[sIndex] == pattern[pIndex] || pattern[pIndex] == '.') {return MatchImpl(str, sIndex + 1, pattern, pIndex + 1);}else {return false;}}public bool Match(char[] str, char[] pattern){return MatchImpl(str, 0, pattern, 0);}/// <summary>/// 解法2，动态规划/// 基本思路：/// 构建动态规划转移方程f[i,j]，表示字符串的前i个字符与模式串的前j个字符是否匹配/// 对于不包含"*"的情况///f[i, j] = f[i - 1, j - 1] && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.');///表示前i个字符与模式串的前j个字符匹配的前提是，前i - 1个字符与前j - 1个字符匹配且第i个字符与第j个字符相等或第j个字符是"."/// 对于包含"*"的情况///"*"表示出现0次时/// f[i, j] |= f[i, j - 2];/// 表示前i个字符与模式串的前j个字符匹配的前提是，前i个字符与前j - 2个字符匹配即可（相当于把x*忽略掉）///"*"表示出现1次或多次时/// f[i, j] |= f[i - 1, j] && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.');/// 表示前i个字符与模式串的前j个字符匹配的前提是，前i - 1个字符与前j个字符匹配且第i个字符与"*"前的字符相等或"*"前的字符是"."/// 补充说明/// f[0, 0]就表示空字符串与空模式串是否匹配/// f[1, 1]就表示字符串第一个字符与模式串第一个字符是否匹配/// f[str.Length, pattern.Length]就表示字符串str与模式串pattern是否匹配/// </summary>public bool Match2(char[] str, char[] pattern){bool[,] f = new bool[str.Length + 1, pattern.Length + 1];for(int i = 0; i <= str.Length; i ++){for(int j = 0; j <= pattern.Length; j ++){if(j == 0)f[i, j] = i == 0;else{if(pattern[j - 1] == '*'){if(j >= 2)f[i, j] |= f[i, j - 2];if(i > 0)f[i, j] |= f[i - 1, j] && (str[i - 1] == pattern[j - 2] || pattern[j - 2] == '.');}else if(i > 0){f[i, j] = f[i - 1, j - 1] && (str[i - 1] == pattern[j - 1] || pattern[j - 1] == '.');}}}}return f[str.Length, pattern.Length];}public void Test() {char[] str = new char[]{'a', 'a', 'a'};// str = new char[]{};// str = new char[]{'a', 'b', 'b', 'b', '*'};// str = new char[]{'a', 'b', 'b', 'b'};// str = new char[]{'a', 'b', 'c', '.', '*', 'f', '*', 's'};// str = new char[]{'a'};// str = new char[]{'a', 'a'};char[] pattern = new char[]{'a', '.', 'a'};// pattern = new char[]{'a', '*', 'a', 'a'};// pattern = new char[]{'b', '*', 'a', 'a', 'a'};// pattern = new char[]{'b', '*'};// pattern = new char[]{'a', 'b', '*'};// pattern = new char[]{'a', 'b', '*', '*'};// pattern = new char[]{'.', '*'};// pattern = new char[]{'*', '*'};// pattern = new char[]{};// pattern = new char[]{'.'};// Console.WriteLine(Match(str, pattern));Console.WriteLine(Match2(str, pattern));}}}
🏳️🌈滑动窗口的最大值
/*题目名称：滑动窗口的最大值题目描述：给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。代码结构：class Solution{public int[] maxInWindows(int[] num, int size){// write code here}}*/using System;using System.Collections.Generic;namespace MaxInWindows {class Solution {/// <summary>/// 解法1/// 基本思路：/// 最直观的解法，针对每一个size大小的窗口，都重新计算出最大值/// 但效率不高，没有利用好前面窗口已经算出的最大值/// </summary>public int[] MaxInWindows(int[] num, int size){if(num == null || num.Length < size || size <= 0) {return new int[]{};}int[] ret = new int[num.Length - size + 1];for(int i = 0; i < num.Length - size + 1; i ++){int max = num[i];for(int j = 1; j < size; j ++){if(num[i + j] > max){max = num[i + j];}}ret[i] = max;}return ret;}/// <summary>/// 解法2，双端队列/// 基本思路：/// 利用双端队列的首部记录每个窗口的最大值/// 每新增一个元素/// 1. 从队列首部开始判断，每个元素是否已经超出窗口范围，是的话移除/// 2. 从队列尾部开始判断，新增的元素是否比队列内的元素大，是的话移除（保证队列首部一定是最大值）/// 3. 将新增的元素从尾部加入队列/// </summary>public int[] MaxInWindows2(int[] num, int size){if(num == null || size <= 0 || num.Length < size){return new int[]{};}int[] ret = new int[num.Length - size + 1];LinkedList<int> list = new LinkedList<int>();for(int i = 0; i < num.Length; i ++){while(list.Count > 0 && i - size >= list.First.Value) list.RemoveFirst();while(list.Count > 0 && num[i] >= num[list.Last.Value]) list.RemoveLast();list.AddLast(i);if(i - size + 1 >= 0){ret[i - size + 1] = num[list.First.Value];}}return ret;}public void Print(int[] num) {if(num == null){Console.WriteLine("null");return;}foreach(int i in num){Console.WriteLine(i);}}public void Test() {int[] num = new int[]{2,3,4,2,6,2,5,1};int size = 3;// Print(MaxInWindows(num, size));Print(MaxInWindows2(num, size));}}}
📢合并两个排序的链表
/*题目名称：合并两个排序的链表题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。代码结构：class Solution{public ListNode Merge(ListNode pHead1, ListNode pHead2){// write code here}}*/using System;namespace Merge {public class ListNode{public int val;public ListNode next;public ListNode (int x){val = x;}}class Solution {/// <summary>/// 解法1/// 基本思路：/// 同时遍历两个链表，比较两个链表的首结点，优先合并其中较小的节点/// 当两个链表长度不同时，最后再合并两个链表中较长链表的剩余节点/// </summary>public ListNode Merge(ListNode pHead1, ListNode pHead2){ListNode pHead = new ListNode(0);ListNode head = pHead;while(pHead1 != null && pHead2 != null){if(pHead2.val < pHead1.val){head.next = pHead2;pHead2 = pHead2.next;}else{head.next = pHead1;pHead1 = pHead1.next;}head = head.next;}if(pHead1 != null){head.next = pHead1;}if(pHead2 != null){head.next = pHead2;}return pHead.next;}/// <summary>/// 解法2，递归/// 基本思路：/// 首先算法合并两个链表头节点中较小的节点，即将较小的节点作为新链表的头结点/// 然后通过递归寻找新链表头结点的下一个节点，过程如下/// 如果链表1的头结点较小，则链表1向下走一步，链表1指向下一个节点，找到链表1与链表2中较小的头结点/// 如果链表2的头结点较小，则链表2向下走一步，链表2指向下一个节点，找到链表1与链表2中较小的头结点/// </summary>public ListNode Merge2(ListNode pHead1, ListNode pHead2){if(pHead1 == null) return pHead2;if(pHead2 == null) return pHead1;if(pHead2.val < pHead1.val){pHead2.next = Merge2(pHead1, pHead2.next);return pHead2;}else{pHead1.next = Merge2(pHead1.next, pHead2);return pHead1;}}public void Print(ListNode head){while(head != null){Console.WriteLine(head.val);head = head.next;}}public void Test() {ListNode pHead1 = new ListNode(1);pHead1.next = new ListNode(2);pHead1.next.next = new ListNode(3);pHead1.next.next.next = new ListNode(4);// pHead1 = null;ListNode pHead2 = new ListNode(0);pHead2.next = new ListNode(3);pHead2.next.next = new ListNode(4);pHead2.next.next.next = new ListNode(5);// pHead2 = null;// Print(Merge(pHead1, pHead2));Print(Merge2(pHead1, pHead2));}}}
📣二叉树的镜像
/*题目名称：二叉树的镜像题目描述：操作给定的二叉树，将其变换为源二叉树的镜像。输入描述：二叉树的镜像定义：源二叉树 8/ \6 10/ \ / \5 7 9 11镜像二叉树8/ \10 6/ \ / \11 9 7 5代码结构：class Solution{public TreeNode Mirror(TreeNode root){// write code here}}*/using System;using System.Collections.Generic;namespace Mirror {public class TreeNode{public int val;public TreeNode left;public TreeNode right;public TreeNode (int x){val = x;}}class Solution {/// <summary>/// 解法1，递归/// 基本思路：/// 先翻转根节点的左右子节点，然后通过递归再分别翻转左右子节点的子节点/// </summary>public TreeNode Mirror(TreeNode root){if(root != null){TreeNode node = root.left;root.left = root.right;root.right = node;Mirror(root.left);Mirror(root.right);}return root;}/// <summary>/// 解法2，非递归/// 利用栈结构遍历每一个节点，替换该节点的左右子节点/// </summary>public TreeNode Mirror2(TreeNode root){Stack<TreeNode> stack = new Stack<TreeNode>();stack.Push(root);while(stack.Count > 0){TreeNode node = stack.Pop();if(node != null){TreeNode temp = node.left;node.left = node.right;node.right = temp;stack.Push(node.left);stack.Push(node.right);}}return root;}public void Print(TreeNode root){Queue<TreeNode> queue = new Queue<TreeNode>();queue.Enqueue(root);while(queue.Count > 0){TreeNode node = queue.Dequeue();if(node == null){Console.Write("# ");} else{Console.Write(node.val + " ");queue.Enqueue(node.left);queue.Enqueue(node.right);}}Console.WriteLine();}public void Test() {TreeNode root = new TreeNode(8);root.left = new TreeNode(6);root.right = new TreeNode(10);// root.left.left = new TreeNode(5);// root.left.right = new TreeNode(7);root.right.left = new TreeNode(9);// root.right.right = new TreeNode(11);// root = null;// Print(Mirror(root));Print(Mirror2(root));}}}
各位走过路过，不要错过，记得关注我哦
如果觉得《大学压箱底的东西拿出来了-算法合集2》对你有帮助，请点赞、收藏，并留下你的观点哦！
