LeetCode题库
C#二维数组/参差数组定义
//C#数组-额理性未赋值为初始自int-0;bool-false;引用-null
int[] array = new int[10];
int[] array2 = new int[3] { 1,2,3 };
//2、二维数组
int[,] mar = new int[3, 3];
int[,] mar2 = new int[3, 3] { {1,2,3},{ 4,5,6},{ 7,8,9} };
//3、参差数组
//两行，第一行两列，第二行三列的参差数组
int[][] cc = new int[2][];//先定义两行
cc[0] = new int[2] { 2, 2 };//在定义每行列数
cc[1] = new int[3] { 3, 3, 3 };
-------------------------------------------------
排序查找算法、冒泡/选择/插入/快排/二分查找
///
/// 冒泡排序
///
///
public static void BubbleSort(int [] nums)
{
for (int i = 0; i < nums.Length; i++)
{
for (int j = 0; j < nums.Length-1-i; j++)
{
if (nums[j] > nums[j + 1])
Swap(ref nums[j], ref nums[j + 1]);
}
}
}
///
/// 选择排序：默认第一个为最小值，在后面找到更小的时就和默认最小的交换。再默认第二个为最小往下循环。
///
///
static void ChooseSort(int[] array)
{
for (int i = 0; i < array.Length-1; i++)
{
int minnum = array[i];
int minindex = i;
for (int j = i+1; j < array.Length; j++)
{
if(array[j]<minnum)
{
minnum = array[j];
minindex = j;
}
}
if(minindex!=i)
{
int temp = array[i];
array[i] = minnum;
array[minindex] = temp;
}
}
}
///
/// 直插排序
///
///
public static void InsertSort2(int[] nums)
{
int index, value;
for (int i = 1; i < nums.Length; i++)
{
value = nums[i];
index = i-1;
while(index>=0&&nums[index]>value)
{
nums[index+1] = nums[index];
index -= 1;
}
nums[index+1] = value;
}
}
//快速排序
static void Qsort(int[] array,int left,int right)
{
if(left<right)
{
int i = left;
int j = right + 1;
int provt = array[i];
do
{
do i++; while (array[i] < provt && i < array.Length-1);
do j--; while (array[j] > provt && j >= 0);
if(i<j)
{
Swap(ref array[i], ref array[j]);
}
} while (i<j);
Swap(ref array[left], ref array[j]);
Qsort(array, left, j - 1);
Qsort(array, j + 1, right);
}
}
//二分查找
static int BinarySearch_R(int[] dateArray, int x, int left, int right)
{
if (left <= right)
{
int mind = (left + right) / 2;
if (x < dateArray[mind])
return BinarySearch_R(dateArray, x, left, mind - 1);
else if (x > dateArray[mind])
return BinarySearch_R(dateArray, x, mind + 1, right);
else if (x == dateArray[mind])
return mind;
}
return -1;
}
225.队列实现栈-
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode复习
{
class MyStack
{
/*#region 双队列实现
Queue
Queue
public MyStack()
{
q1 = new Queue
q2 = new Queue
}
public void Push(int n)//入栈时直接压入入队
{
q1.Enqueue(n);
}
public int Pop()//弹出时将入队中的元素弹如中间队，只留下最后进入的-弹出元素，
{
if (q1.Count == 1)
return q1.Dequeue();
else
{
while (q1.Count != 1)
q2.Enqueue(q1.Dequeue());
}
int temp = q1.Dequeue();
while (q2.Count != 0)
q1.Enqueue(q2.Dequeue());
return temp;
}
public int Top()//直接使用弹出，在压入入队
{
int temp = Pop();
q1.Enqueue(temp);
return temp;
}
public bool Empty()//元素全部存在入队中
{
return q1.Count == 0;
}
#endregion*/
#region 单队列实现
Queue<int> QueueInput = new Queue<int>();
/** Push element x onto stack. */
public void Push(int x)//压入后，对队列进行移动，将新进入的元素移动到队首
{
QueueInput.Enqueue(x);
for (int i = 0; i < QueueInput.Count - 1; ++i)//将新入队的数移动N-1次后队列最前端
{
QueueInput.Enqueue(QueueInput.Dequeue());
}
}
/** Removes the element on top of the stack and returns that element. */
public int Pop()
{
return QueueInput.Dequeue();
}
/** Get the top element. */
public int Top()
{
return QueueInput.Peek();
}
/** Returns whether the stack is empty. */
public bool Empty()
{
return QueueInput.Count == 0;
}
#endregion
}
}
232.栈实现队列
using System;
using System.Collections.Generic;
using System.Text;
namespace LeetCode复习
{
class MyQueue
{
Stack
Stack
/** Initialize your data structure here. */
public MyQueue()
{
a = new Stack<int>();//压入入栈
b = new Stack<int>();//弹出栈
}
/** Push element x to the back of queue. */
public void Push(int x)//压入直接存入a
{
a.Push(x);
}
/** Removes the element from in front of queue and returns that element. */
public int Pop()//a全部弹出压入b得到的b即与a排序相反，通过b弹出即实现队列
{
if(b.Count==0)
{
while (a.Count != 0)
b.Push(a.Pop());
}
return b.Pop();
}
/** Get the front element. */
public int Peek()//
{
if(b.Count == 0)
{
while (a.Count != 0)
b.Push(a.Pop());
}
return b.Peek();
}
/** Returns whether the queue is empty. */
public bool Empty()
{
return a.Count == 0 && b.Count == 0;
}
}
}
/// 三数之和
public static List<List
{
List<List
Array.Sort
if (nums == null || nums[0] >= 0 || nums.Length < 3) return res;//数组为空，排序后最小值大于0，长度小于3，则没有结果返回空列表
for (int i = 0; i < nums.Length-2; i++)//外部总循环次数小于长度减2，由于包含satrt与end两个位置指针
{
if(i0||nums[i]!=nums[i-1])//首次循环或不重复时执行
{
int start = i + 1;//左指针较小的值，结果小于0时右移
int end = nums.Length - 1;//右指针较大的值，结果大于0时向左移
while(start<end)//内循环左指针小于右指针
{
if (nums[i] + nums[start] + nums[end] == 0)//满足条件将结果加入返回列表
{
res.Add(new List
start++;//左指针右移
end--;//右指针左移//寻找其他满足条件的组合
while (start < end && nums[start] == nums[start - 1])//保证不与之前的值重复
start++;
while (start < end && nums[end] == nums[end + 1])//保证不与之前的值重复
end--;
}else if(nums[i] + nums[start] + nums[end]<0)//小于0，start右移到更大的数
{
start++;
}else//大于0，end左移到更小的数
{
end--;
}
}
}
}
return res;
}
///
** /// 19:删除链表d第n个节点**
///
///
///
///
public ListNode RemoveNthFromEnd(ListNode head, int n)
{
if (head == null || head.next == null) return null;
ListNode dummy = new ListNode();
dummy.next = head;
ListNode l = dummy;
ListNode r = dummy;
for (int i = 0; i < n; i++)
{
r = r.next;
}
while(r.next!=null)
{
l = l.next;
r = r.next;
}
l.next = l.next.next;
return dummy.next;
}
20.有效括号(B站面试题)
///
/// 有效括号
///
class LeetCode20
{
public static bool IsValid(string s)
{
Stack
foreach (char c in s)
{
if(c
{
st.Push(c);
}else
{
if (st.Count == 0)
return false;
else
{
char temp = st.Pop();
if (c == ')')
{
if (temp != '(')
return false;
}
else if (c == ']')
{
if (temp != '[')
return false;
}
else if (c == '}')
{
if (temp != '{')
return false;
}
}
}
}
return st.Count == 0;
}
}
///
/// 移除元素：给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
///
class LC27
{
//将与val相等的值都移动到数组最右边，
public static int RemoveEle(int [] nums,int value)
{
if (nums == null || nums.Length == 0)
return 0;
int l = 0;
int r = nums.Length - 1;
while(l<r)
{
while(l<r&&nums[l]!=value)//左指针找与val相等的值
{
l++;
}
while(l<r&&nums[r]==value)//右指针找与val不相等的值
{
r--;
}
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
}
return nums[l] == value ? l : l + 1;//最后一个与val相等的值先被左指针找到，左指针位置的索引即移除val后的，前面元素的长度(数组从0开始)。
最后与val相等的值先被右指针找到，则l指向的即是不重复元素的中一个元素，数组索引值比实际长度小1，即返回l+1
}
}
————————————————————————————————————
48.旋转图像
class LC48
{
public static void rotate(int[][] matrix)
{
int n = matrix[0].Length;
if (n == 0 || n == 1) return;
for (int start = 0, end = n - 1; start < end; start++, end--)
{ //控制旋转层数（不断缩小圈的范围）
int s = start; int e = end;
while (s < end)
{ //完成一圈的旋转
int temp = matrix[start][s]; //temp<-左上角值
matrix[start][s] = matrix[e][start]; //左上角<-左下角
matrix[e][start] = matrix[end][e]; //左下角<-右下角
matrix[end][e] = matrix[s][end]; //右下角<-右上角
matrix[s][end] = temp; //右上角<-temp
s++; e--; //向右平移该层的圈
}
}
}
}
————————————————————————————————————
49.字母异为词分组
class LC49
{
public static List<List
{
//可变字符串：存储排序后的字符数组转为字符串
StringBuilder key = new StringBuilder();
//字典：键：排序后相同的字符(串有相同字符组成)，值：由相同字符组成的字符串数组
Dictionary<string, List
//遍历字符串数组中每个字符串
foreach (string s in strs)
{
char[] temp = s.ToCharArray();//字符串转为字符数组，用于排序
Array.Sort(temp);//调用数组类静态排序方法
key.Clear();//添加前先请空可变字符串
foreach (char c in temp)//将字符数组的每个字符添加到可变字符串
{
key.Append(c);
}
if (!strsGroupDict.ContainsKey(key.ToString()))//判断字典的键中是否包含此排序后的字符串
{
//不包含则新建键值对，键：此排序后的字符串，值：新建字符串可变数组(存储由相同字符组成的字符串)
strsGroupDict.Add(key.ToString(), new List
}
//创建后/或已经存在键的情况下，将当前字符添加到可变数组中
strsGroupDict[key.ToString()].Add(s);
}
return new List<List
}
}
//LC3无重复最长子串
public int LengthOfLongestSubstring(string s)
{
if (s == null || s.Length == 0) return 0;
int res = 0;
int l = 0;
HashSet
for (int i = 0; i < s.Length; i++)
{
if (!set.Contains(s[i]))
{
set.Add(s[i]);
res = Math.Max(res, set.Count);
}
else//包含时，顺序移除字符串中的字符直至不重复，加入集合
{
while (set.Contains(s[i]))
{
set.Remove(s[l]);
l += 1;
}
set.Add(s[i]);
}
}
return res;
}
//LC4：两有序数组中位数
public static double FindMedianSortedArrays(int[] nums1, int[] nums2)
{
if (nums1.Length == 0 && nums2.Length == 0) return (double)0;
List
double mid;
foreach (int n in nums2)
res.Add(n);
res.Sort();
if (res.Count % 2 == 1)
mid = res[res.Count / 2];
else
{
mid = (double)(res[res.Count / 2] + res[res.Count / 2 - 1]) / 2;
}
return mid;
}
LC53.最大子数组和
///
/// 给定一个整数数组 nums ，
/// 找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
///
class LC53最大子数组和
{
public int MaxSubArray(int[] nums)
{
if (nums == null || nums.Length == 0)
return 0;
int res = nums[0];
int sum = 0;
foreach (int n in nums)
{
if (sum > 0)//都为正数时所有元素和即为最大
sum += n;//连续数相加的最大值，小于0时说明有负数加入，
else//都为负数时即得到最大的负数
sum = n;//出现和小于0有负数加入，找到下一个从正数开始的元素
res = Math.Max(res, sum);//每次填入一个数时会取res，sum最大的值
}
return res;
}
}
/// <summary>
/// 动态规划
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public static int Maxsubarray2(int[] nums)
{
List<int> memolist = new List<int>();//动态规划列表
memolist.Add(nums[0]);
for (int i = 1; i < nums.Length; i++)
memolist.Add(Math.Max(nums[i] + memolist[i - 1], nums[i]));//判断当前元素计入子数组和后，与当前元素值比较，取大值决定计入总和还是从当前开始
memolist.Sort((a, b) => a > b?-1:1);//取动态规划数组中的最大值返回，避免首位就值最大
return memolist[0];
}
//动态规划内存优化
public static int Maxsubarray2(int[] nums)
{
int per =0, max = nums[0];
foreach (int n in nums)
{
per = Math.Max(per + n, n);
max = Math.Max(max, per);
}
return max;
}
70.爬楼梯(青蛙跳台阶)//动态规划/类似斐波那数列-LC509
public class Solution {
public int NumWays(int n) {
if (n < 2) return 1;
int[] res = new int[n];
res[0] = 1;
res[1] = 2;
for (int i = 2; i < n; i++)
{
res[i] = (res[i - 1] + res[i - 2]);//%1000000007;要求取余时
}
return res[n - 1];
//索引对应形式
int[] res = new int[n + 1];
res[1] = 1;
res[2] = 2;
for (int i = 3; i <= n; i++)
{
res[i] = res[i - 1] + res[i - 2];
}
return res[n];
}
}
//128.最长连续序列
public static int LongestConsecutive(int[] nums)
{
if (nums == null || nums.Length == 0) return 0;
Array.Sort(nums);//排序后去重
HashSet<int> set = new HashSet<int>();//使用集合不要求在原数组中连续
for (int i = 0; i < nums.Length; i++)
{
set.Add(nums[i]);
}
List<int> reslist = new List<int>();//结果列表，长度即为返回值
int res = 1;//数组长度大于0则至少返回1；
foreach (int n in set)
{
if (reslist.Count!=0 && reslist[reslist.Count - 1] + 1 == n)//不为空且连续时，计入返回列表
{
reslist.Add(n);
res = Math.Max(res, reslist.Count);//取返回列表长度最大值
}
else
{
reslist.Clear();//不连续时清空，重新计入
reslist.Add(n);
}
}
return res;
}
//134.加油站
public int CanCompleteCircuit(int[] gas, int[] cost)
{
int allgas = 0;
int allcast = 0;
for (int i = 0; i < gas.Length; i++)
{
allgas += gas[i];
allcast += cost[i];
}
if (allgas < allcast) return -1;
int gascurten = 0;
int start = 0;
for (int i = 0; i < gas.Length; i++)
{
gascurten = gascurten + gas[i] - cost[i];
if (gascurten < 0)
{
gascurten = 0;
start = i + 1;
}
}
return start;
}
//152.乘积最大子数组
public static int MaxSubProduct(int[]nums)
{
List
List
memomax.Add(nums[0]);
memomin.Add(nums[0]);
for (int i = 1; i < nums.Length; i++)
{
memomax.Add(Math.Max(Math.Max(nums[i]*memomax[i - 1], nums[i]*memomin[i-1]), nums[i]));
memomin.Add(Math.Min( Math.Min(nums[i] * memomin[i - 1],nums[i]*memomax[i-1]), nums[i]));
}
memomax.Sort();
return memomax[memomax.Count - 1];
}
// 153. 寻找旋转排序数组中的最小值
:假设按照升序排序的数组在预先未知的某个点上进行了旋转。例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] 。
public int FindMin(int[] nums)
{
//长度为1或未旋转时返回首位
if (nums.Length == 1 || nums[nums.Length - 1] > nums[0]) return nums[0];
//二分查找
int left = 0;
int right = nums.Length - 1;
while(left<right)
{
int mid = left + (right - left) / 2;//中间值索引
if (nums[mid] > nums[mid + 1])//中间值恰好为旋转前的末尾最大值，则mid+1即为最小值
return nums[mid + 1];
else if (nums[mid] < nums[mid - 1])//中间值恰好指向旋转前的最小值，则返回m
return nums[mid];
else if (nums[mid] > nums[left])//其他情况mid落在旋转后的两端数组中间时
left = mid + 1;//mid比left大则落在左半边，最小值在右边
else
right = mid - 1;//mid比left小则落在右半边，最小值在左边
}
return nums[0];//语法条件返回值无意义
}
class LC54螺旋矩阵
{
public List
{
if (matrix == null || matrix.Length == 0) return new List
//数组边界值
int top = 0,left = 0;
int bottom = matrix.Length - 1, right = matrix[0].Length - 1;
int direction = 1;//1,2,3,4：右下左上
List<int> res = new List<int>();
while (left <= right && top <= bottom)
{
switch (direction)
{
case 1://右移
for (int i = left; i <= right; i++)//从左到右遍历
res.Add(matrix[top][i]);//第一行从左到右加入返回列表
top += 1;//第一行遍历结束加一到下一行
direction = 2;
break;
case 2://下移
for (int i = top; i <= bottom; i++)//从上到下遍历
res.Add(matrix[i][right]);//最后一列从上到下
right -= 1;//左后一列遍历后减1，下次遍历前一列
direction = 3;
break;
case 3://左移
for (int i = right; i >=left ; i--)//从右到左遍历
res.Add(matrix[bottom][i]);//最后一行从右到左遍历
bottom -= 1;//遍历结束，下次从右到左遍历上一行
direction = 4;
break;
case 4://上移
for (int i = bottom; i >=top ; i--)//从下到上遍历
res.Add(matrix[i][left]);//第一列从下到上遍历，
left += 1;//下次从下到上遍历下一列
direction = 1;
break;
}
}
return res;
}
}
** // 55.跳跃游戏** ,贪心算法：maxjunp初始为最大索引，当前一个索引与此数组索引值相加大于maxump时则一定可以到达maxjump,maxjump一道前一个索引位置，最后判断maxjump是否等于0则返回true否则说明中间断开返回false
public bool Jump(int [] nums)
{
int maxjump = nums.Length;
for (int i = nums.Length-2; i >=0 ; i--)
{
if (i + nums[i] >= maxjump)
maxjump = i;
}
return maxjump == 0 ? true : false;
}
class LC62不同路径
{
///
/// 动态规划，dp[m,n] = dp[m-1,n]+dp[m,n-1];
///
///
///
///
public int UniquePaths(int m, int n)
{
int[,] dp = new int[m,n];
dp[0,0] = 1;
for (int i = 0; i < m; i++)
{
for (int j = 0; j < n; j++)
{
if (i - 1 >= 0 && i - 1 < m)
dp[i, j] += dp[i - 1,j];
if (j - 1 >= 0 && j - 1 < n)
dp[i, j] += dp[i, j - 1];
}
}
return dp[m - 1, n - 1];
}
}
public int UniquePath2(int m, int n)
{
int[,] dp = new int[m, n];
for (int i = 0; i < m; i++)
dp[i, 0] = 1;
for (int i = 0; i < n; i++)
dp[0, n] = 1;
for (int i = 1; i < m; i++)
{
for (int j = 1; j < n; j++)
{
dp[i, j] = dp[i, j - 1] + dp[i - 1, j];
}
}
return dp[m - 1, n - 1];
}
66.加一
public int[] PlusOne(int[] digits)
{
for (int i = digits.Length - 1; i >= 0; i--)
{
if (digits[i] != 9)
{
digits[i] += 1;
return digits;
}
else
digits[i] = 0;
}
List
res.Insert(0, 1);
return res.ToArray();
}
70.爬楼梯
public int ClimbStairs(int n)
{
if (n < 2) return 1;
int[] res = new int[n];
res[0] = 1;
res[1] = 2;
for (int i = 2; i < n; i++)
{
res[i] = res[i - 1] + res[i - 2];
}
return res[n - 1];
}
//73,矩阵置0
public void SetZeroes(int[][] matrix)
{
bool firstoColContentZero = false;
bool firstoRowContentZero = false;
//检测第一列是否有0
for (int i = 0; i < matrix.Length; i++)
{
if (matrix[i][0] == 0)
firstoColContentZero = true;
}
//检查第一行是否有0
for (int i = 0; i < matrix[0].Length; i++)
{
if (matrix[0][i] == 0)
firstoRowContentZero = true;
}
//使用第一行与第一列标记0
for (int i = 1; i < matrix.Length; i++)
{
for (int j = 1; j < matrix[0].Length; j++)
{
if(matrix[i][j]==0)
{
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
//使用第一行列中的0处理矩阵中的元素
for (int i = 1; i < matrix.Length; i++)
{
for (int j = 1; j < matrix[0].Length; j++)
{
if (matrix[i][0] == 0 || matrix[0][j] == 0)
matrix[i][j] = 0;
}
}
//首行存在0，本行全部置为0
if(firstoRowContentZero)
{
for (int i = 0; i < matrix[0].Length; i++)
{
matrix[0][i] = 0;
}
}
//首列存在0，本列全部置为0
if(firstoColContentZero)
{
for (int i = 0; i < matrix.Length; i++)
{
matrix[i][0] = 0;
}
}
}
//83.删除链表重复元素
public ListNode DeleteDuplicates(ListNode head)
{
if (head == null) return head;
HashSet
ListNode res = new ListNode();
res.next = head;
ListNode pov = new ListNode();
pov.next = head;
while (head != null)
{
if (!set.Contains(head.val))
{
set.Add(head.val);
head = head.next;
pov = pov.next;
}
else
{
pov.next = head.next;
head = head.next;
}
}
return res.next;
}
//链表为排好序的链表
public ListNode DeleteDuplicates2(ListNode head)
{
if (head == null || head.next == null) return head;
ListNode res = new ListNode();
res.next = head;
while (head != null && head.next != null)
{
if (head.val == head.next.val)
{
head.next = head.next.next;
}
else
head = head.next;
}
return res.next;
}
class LC74搜索矩阵
{
///
/// 二分法，一维，二维数组索引转换
///
///
///
///
public bool SearchMatrix(int[][] matrix, int target)
{
if (matrix == null || matrix.Length == 0) return false;
int row = matrix.Length;
int col = matrix[0].Length;
int l = 0;
int r = row * col - 1;
while(l<=r)
{
int mid = l + (r - l) / 2;
int ele = matrix[mid / col][mid % col];//一维索引二维
if (ele == target)
return true;
else if (ele > target)
r = mid;
else
l = mid + 1;
}
return false;
}
}
————————————————————————————————————
78/90.子集
///
/// 子集
///
class LC78
{
///
/// SubsetI
///
///
///
public static List<List
{
List<List
res.Add(new List
foreach (int n in nums)
{
int resLength = res.Count;
for (int i = 0; i < resLength; i++)
{
List
cur.Add(n);
res.Add(cur);
}
}
return res;
}
///
/// SubsetII
///
///
///
public static List<List
{
List<List
res.Add(new List
Array.Sort
foreach (int n in nums)
{
int resLength = res.Count;
for (int i = 0; i < resLength; i++)
{
List
cur.Add(n);
res.Add(cur);
}
}
List<List
foreach (List<int> list in res)
{
if (!Contants(resLast, list))
{
resLast.Add(list);
}
}
return resLast;
}
public static bool Contants(List<List<int>> res,List<int> slist)
{
if (res.Count == 0) return false;
bool conts = false;
foreach (var item in res)
{
if (CpList(item, slist))
conts = true;
}
return conts;
}
public static bool CpList(List<int> l1,List<int> l2)
{
bool res = true;
if (l1.Count != l2.Count)
return false;
else
{
for (int i = 0; i < l1.Count; i++)
{
if (l1[i] != l2[i])
res = false;
}
}
return res;
}
}
//121.买股票的最佳时机
public int MaxProfit(int[] prices)
{
if (prices == null || prices.Length == 0) return 0;
int minp = prices[0];
int maxp = 0;
for (int i = 1; i < prices.Length; i++)
{
if (prices[i] < minp)
minp = prices[i];
else if (prices[i] - minp > maxp)
maxp = prices[i] - minp;
}
return maxp;
}
//122.买股票的最佳时机II
public static int MaxProfitII(int[] prices)
{
if (prices == null || prices.Length == 0) return 0;
int allprice = 0;
int lop = prices[0], top = prices[0];
int i = 0;
while(i<prices.Length-1)
{
while (i<prices.Length-1 && prices[i] >= prices[i + 1])
i += 1;
lop = i;
while (i < prices.Length - 1 && prices[i] < prices[i + 1])
i += 1;
top = i;
allprice += prices[top] - prices[lop];
}
return allprice;
}
class _141环形链表
{
public bool HasCycle(ListNode head)
{
if (head == null || head.next == null)
{
return false;
}
ListNode slow = head;
ListNode fast = head.next;
while (slow != fast)
{
if (fast == null || fast.next == null)
{
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
//160.相交链表
public ListNode GetIntersectionNode(ListNode headA, ListNode headB)
{
if (headA == null || headB == null) return null;
HashSet
while(headA!=null)
{
list.Add(headA);
headA = headA.next;
}
while(headB!=null)
{
if (!list.Contains(headB))
{
list.Add(headB);
headB = headB.next;
}
else
return headB;
}
return null;
}
class LC162寻找峰值
{
///
/// 峰值元素是指其值大于左右相邻值的元素。二分法
///
///
///
public static int FindPeakElement(int[] nums)
{
if (nums == null || nums.Length == 0) return -1;
int l = 0;
int r = nums.Length - 1;
while (l<r)
{
int mid = (r + l) / 2;
//中间值右边的数小于mid则极值在左边，反之极值在右边
if (nums[mid] > nums[mid + 1])
r = mid;
else
l = mid + 1;
}
return l;
}
}
#region 查找最大重复值
//static Dictionary<int, int> dic = new Dictionary<int, int>();
//方法1：利用字典统计数组元素出现的次数。元素作为键，值存储数显次数。
static int SearchMaxRepet1(int[] array)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
int hrefLength = array.Length / 2;
for (int i = 0; i < array.Length; i++)
{
if (!dic.ContainsKey(array[i]))
dic.Add(array[i], 0);
}
for (int i = 0; i < array.Length; i++)
{
dic[array[i]] += 1;
}
foreach (int k in dic.Keys)
{
if (dic[k] > hrefLength)
return k;
}
return -1;
}
//方法2：排序发，排序后重复最多的值补丁集中在数组中间。
static int SearchMaxRepet2(int[] array)
{
QSort(new List<int>(array),0,array.Length-1);
return array[array.Length / 2];
}
//分治法
static int SearchMaxRepet3(int[] nums)
{
return GetMajority(nums, 0, nums.Length - 1);
}
/// <summary>
/// 分治法，获取众数
/// </summary>
/// <param name="nums"></param>
/// <param name="left"></param>
/// <param name="right"></param>
/// <returns></returns>
static int GetMajority(int [] nums,int left,int right)
{
if (left == right)//分为只有衣蛾元素时返回
return nums[left];
int mid = left + (right - left) / 2;//师爷咱们还是对半分
int leftMajority = GetMajority(nums, 0, mid);//左半边的中数
int rightMajority = GetMajority(nums, mid+1, right);//右半边的中数
if (leftMajority == rightMajority)//左右众数相同 则返回其中任意一个
return leftMajority;
//不相同则，则遍历数组统计该递归层左右那边众数出现的次数多
int leftCount = 0;
int rightCount = 0;
for (int i = left; i <=right; i++)
{
if (nums[i] == leftMajority)
leftCount++;
else if (nums[i] == rightMajority)
rightCount++;
}
return leftCount > rightCount ? leftMajority : rightMajority;
}
#endregion
————————————————————————————————————
public static string Maxnum(int[]nums)
{
StringBuilder snums = new StringBuilder();
for (int i = 0; i < nums.Length; i++)
{
snums.Append(nums[i]);
}
char[] cs = snums.ToString().ToCharArray();
Array.Sort
return string.Join("", cs);
}
179.最大数(网易面试题)
///
///179： 给定一组非负整数 nums，重新排列它们每个数字的顺序（每个数字不可拆分）使之组成一个最大的整数。
/// 用List对string进行排序
///
///
///
public static string LargestNum2(int[] nums)
{
if (nums == null) return "";
if (nums.Length == 1) return nums[0].ToString();
List<string> numsList = new List<string>();
for (int i = 0; i < nums.Length; i++)
{
numsList.Add(nums[i].ToString());
}
numsList.Sort((a, b) => { return (b + a).CompareTo(a + b); });
if (numsList[0].Equals("0")) return "0";
else return string.Join("",numsList.ToArray());
}
//数组中的数组成最小整数
public string PrintMinNumber(List<int> numbers)
{
List<string> slist = new List<string>();
foreach (int n in numbers)
{
slist.Add(n.ToString());
}
slist.Sort((a, b) => { return int.Parse(a + b) > int.Parse(b + a) ? 1 : -1; });//(a+b).CompareTo(b+a)
return string.Join("", slist);
}
///
///字符依次前后相加对比，结果大的放在前面
///
///
///
179.普通方法
public static string LargestNum(int[] nums)
{
if (nums == null) return "";
if (nums.Length == 1) return nums[0].ToString();
string[] st = new string[nums.Length];
//StringBuilder s = new StringBuilder();
for (int i = 0; i < nums.Length; i++)
{
st[i] = nums[i].ToString();
}
for (int i = 0; i < st.Length; i++)
{
for (int j = i+1; j < st.Length; j++)
{
if((st[i]+st[j]).CompareTo(st[j]+st[i])<0)
//s1.CompareTo(s2):
//s1>s2: 1
//s1=s2: 0
//s1<s2: -1
{
Swap(ref st[i], ref st[j]);
}
}
}
/foreach (string item in st)
{
s.Append(item);
}
return s.ToString();/
if (nums[0].Equals("0")) return "0";
else return string.Join("-", st);//使用字符连接字符串数组，返回连接后的字符
}
187.重复的DNA序列
public static List
{
List
if (s == null || s.Length < 11) return res;
Dictionary<string, int> dic = new Dictionary<string, int>();
//StringBuilder ele = new StringBuilder();
int i = 0;
while(i+10<=s.Length)
{
/ele.Clear();
ele.Append(s.Substring(i, 10));/
string ele = s.Substring(i, 10);
if (!dic.ContainsKey(ele.ToString()))
dic.Add(ele.ToString(), 1);
else if(!res.Contains(ele))
res.Add(ele.ToString());
i++;
}
return res;
}
//200.岛屿数量
///
/// 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
///
///
///
public static int CountIsland(char[][]grid)
{
if (grid == null || grid.Length == 0)
return 0;
int row = grid.Length;
int col = grid[0].Length;
int count = 0;
for (int i = 0; i < row; i++)
{
for (int j = 0; j < col; j++)
{
if (grid[i][j] == '1')
{
count++;
DFS(grid, i, j);
}
}
}
return count;
}
static void DFS(char[][] grid,int i,int j)
{
if(i<0||j<0||i>=grid.Length||j>=grid[0].Length||grid[i][j]=='0')
{
return;
}
grid[i][j] = '0';
DFS(grid, i + 1, j);
DFS(grid, i - 1, j);
DFS(grid, i, j + 1);
DFS(grid, i, j - 1);
}
//695.岛屿最大面积
public int MaxIsLandAre(int[][]grid)
{
if (grid == null || grid.Length == 0)
return 0;
int res = 0;
for (int i = 0; i < grid.Length; i++)
{
for (int j = 0; j < grid[0].Length; j++)
{
if(grid[i][j]==1)
{
int curentAre = DFS2(grid,i,j);
res = Math.Max(res, curentAre);
}
}
}
return res;
}
public int DFS2(int[][]grid,int i,int j)
{
if (i < 0 || j < 0 || i >= grid.Length || j >= grid[0].Length || grid[i][j] ==0)
{
return 0;
}
grid[i][j] = 0;
int are = 1;
are += DFS2(grid, i + 1, j);
are += DFS2(grid, i , j+1);
are += DFS2(grid, i - 1, j);
are += DFS2(grid, i , j-1);
return are;
}
}
//219：重复元素2：数组中存在相同元素，且索引值之差绝对值之多为k(小于等于)
public bool ContainsNearbyDuplicate(int[] nums, int k)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
if (dic.ContainsKey(nums[i]) && (i - dic[nums[i]] <= k))
return true;
else
dic[nums[i]] = i;
}
return false;
}
//198
public int Rob(int[] nums)
{
if (nums.Length == 0) return 0;
if (nums.Length == 1) return nums[0];
int p2 = nums[0];
int p1 = Math.Max(nums[0], nums[1]);
for (int i = 2; i < nums.Length; i++)
{
int temp = Math.Max(nums[i] + p2,p1);
p2 = p1;
p1 = temp;
}
return p1;
}
206.反转链表
class LC206
{
public static ListNode ReversList(ListNode head)
{
ListNode dummy = new ListNode();
dummy.next = head;
while(head!=null||head.next!=null)
{
ListNode next = head.next;
ListNode temp = dummy.next;
head.next = head.next.next;
dummy.next = next;
next.next = temp;
}
return dummy.next;
}
public static ListNode ReversList2(ListNode head)
{
if (head == null || head.next == null)
return head;
//返回末尾节点
ListNode res = ReversList2(head.next);
//节点指向反转：递归栈先入后出，先返回最后递归层的末尾节点
head.next.next = head;
head.next = null;
return res;
}
}
————————————————————————————————————
///
209.长度最小的子数组
/// 给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，
/// 并返回其长度。如果不存在符合条件的子数组，返回 0。
///
class LC209
{
///
/// 暴力法，可能输出的值即为1~数组最大长度，长度为n时如存在连续n个数的和>=s，则返回长度n
///
///
///
///
public static int MinSubArrayLen1(int s, int[] nums)
{
if (nums == null || nums.Length == 0)
return 0;
int size = 1;
while(size<=nums.Length)
{
for (int i = 0; i < nums.Length-size+1;i++)
{
int total = 0;
for (int j = i; j < i+size; j++)
{
total += nums[j];
}
if (total >= s)
return size;
}
size++;
}
return 0;
}
///
/// 滑动窗口法/双指针法
///
///
///
///
public static int MinSubArrayLen2(int s, int[] nums)
{
if (nums == null || nums.Length == 0)
return 0;
int i = 0;//左指针
int j = 0;//右指针
int result = nums.Length + 1;//返回结果默不可能比数组长度长，不变则不存在返回0
int total = 0;//窗口内数字的和
while (j<nums.Length)
{
total += nums[j];//计算窗口内数字和
j++;//右指针滑动
while(total>=s)//当窗口内数字和>=给定值时，更新返回值取最小长度
{
result = Math.Min(result, j - i);
total -= nums[i];//左指针开始移动，
i++;
//和仍大于等于给定时时继续移动，小于则退出循环，移动有指针
}
}//j移动到末尾时循环结束
return result == nums.Length + 1 ? 0 : result;//长度未更新则不存在返回0，更新则为最小值
}
}
————————————————————————————————————
217.重复元素
///
/// 给定一个整数数组，判断是否存在重复元素。
/// 如果任意一值在数组中出现至少两次，函数返回 true 。
/// 如果数组中每个元素都不相同，则返回 false
///
class LC217重复元素
{
///
/// 排序法，排序后存在两个相邻的数相同即存在重复的数
///
///
///
public static bool ContainsDuplicate(int[] nums)
{
if (nums == null || nums.Length == 0)
return false;
Array.Sort(nums);
//方式1
/int i = 0;
int j = i + 1;
while(j<nums.Length)
{
if (nums[i] == nums[j])
return true;
i++;
j++;
}/
//方式2
int prev = nums[0];
for (int i = 1; i < nums.Length; i++)
{
if (nums[i] == prev)
return true;
else
prev = nums[i];
}
return false;
}
/// <summary>
/// Set法，集合无法添加重复的元素，
/// 添加完成后集合长度与原数组长度不相等即存在重复的元素
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public static bool ContainsDuplicate2(int [] nums)
{
HashSet<int> set = new HashSet<int>(nums);
return nums.Length == set.Count ? false : true;
}
/// <summary>
/// 字典法，通过字典统计各元素出现的次数，存在次数大于1,
/// 即有值重复出现
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public static bool ContainsDuplicate3(int[] nums)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
foreach (int n in nums)
{
if(!dic.ContainsKey(n))
{
dic.Add(n, 1);
}else
{
dic[n] += 1;
}
}
foreach (var item in dic.Values)
{
if (item > 1)
return true;
}
return false;
}
}
//125.回文字符串
public static bool IsPalindrome(string s)
{
string str = Regex.Replace(s, "[^A-Za-z0-9]", "").ToLower();
Console.WriteLine(str);
char[] array = str.ToCharArray();
Array.Reverse(array);
return str.Equals(new string(array));
}
————————————————————————————————————
234.回文链表
///
/// 请判断一个链表是否为回文链表。回文正反相同的，1；121；1221.
///
class LC234回文链表
{
///
/// 双指针法，由于链表中不能向前移动，所以先将链表中的数，加到数组中
/// 然后左右指针向中间一定进行对比
///
///
///
public static bool IsPalindrome(ListNode head)
{
if (head == null || head.next == null)
return true;
List
while (head != null)
{
list.Add(head.val);
head = head.next;
}
int l = 0;
int r = list.Count - 1;
while(l<r)
{
if (!list[l].Equals(list[r]))//Equals比较的是值==比较的是索引可能不同
return false;
l++;
r--;
}
return true;
}
/// <summary>
/// 递归双指针法，全局变量指向头结点，递归到最后一个节点，
/// 比较最后一个节点与当前p指向的头结点，不想同则返回false，相同p向后移动，返回true
/// 回到上一层递归对比最后一个节点之前的节点，与当前p值不同则返回false，相同p继续向后移返回true
/// 继续回到上一层递归及其没有出现不等则返回true
/// </summary>
static ListNode p = new ListNode();
public static bool IsPalindrome2(ListNode head)
{
p = head;
return Recursion(head);
}
public static bool Recursion(ListNode head)
{
if (head == null)
return true;
if (!Recursion(head.next))
return false;
if (p.val != head.val)
return false;
p = p.next;
return true;
}
/// <summary>
/// 栈，将链表节点压入栈，弹出反序链表对比正序链表值是否一致。
/// </summary>
/// <param name="head"></param>
/// <returns></returns>
public static bool IsPalindrome3(ListNode head)
{
if (head == null || head.next == null)
return true;
ListNode temp = head;
Stack<int> stack = new Stack<int>();
while(temp!=null)//链表节点压入栈
{
stack.Push(temp.val);
temp = temp.next;
}
while (head != null && stack.Count != 0)//正反序对比
{
if (head.val != stack.Pop())
return false;
head = head.next;
}
return true;
}
}
238.除自身外数组的乘积
class LC238除自身外数组的乘积
{
public int[] ProductExceptSelf(int[] nums)
{
int[] res = new int[nums.Length];
int pr = 1;
for (int i = 0; i < nums.Length; i++)
{
res[i] = pr;//返回数组保存除当前索引值外左边所有元素的乘积
pr *= nums[i];
}
pr = 1;
for (int i = nums.Length-1; i >=0; i--)
{
res[i] *= pr;//返回数组当前索引值(即除自身外所有元素乘积=左边所有元素乘积*右边所有元素乘积)
pr *= nums[i];
}
return res;
}
}
———————————————————————————————————————
268丢失的数字
///
/// 给定一个包含 [0, n] 中 n 个数的数组 nums ，
/// 找出 [0, n] 这个范围内没有出现在数组中的那个数。
///
class LC268丢失的数字
{
///
/// 排序法 [0,n]，排序后数组与索引值不相等即，缺失索引位置的值
///
///
///
public int MissingNumber(int[] nums)
{
Array.Sort(nums);
for (int i = 0; i < nums.Length; i++)
{
if (i != nums[i])
return i;
}
return nums.Length;
}
///
/// 集合法，加入集合后，直接遍历判断集合不包含[0,n]中的那个值，
///
///
///
public static int MissingNumber2(int[] nums)
{
HashSet
foreach (int n in nums)
set.Add(n);
for (int i = 0; i < nums.Length; i++)
{
if (!set.Contains(i))
return i;
}
return nums.Length;
}
///
/// 数学法，[0,n]之和为“n*(n+1)/2“减去数组之和即为等于缺失的数值
///
///
///
public int MissingNumber3(int[] nums)
{
int sum = 0;
for (int i = 0; i < nums.Length; i++)
{
sum += nums[i];
}
return (nums.Length * (nums.Length + 1)) / 2 - sum;
}
}
class LC283移动0
{
public static void MoveZeroes(int [] nums)
{
int index = 0;
for (int i = 0; i < nums.Length; i++)//遍历数组将不为0的数放在前面
{
if(nums[i]!=0)
{
nums[index] = nums[i];
index++;
}
}
//以上遍历完成后index后面的元素都应该是0
for (int i = index; i < nums.Length; i++)
{
nums[i] = 0;
}
}
}
//328.奇偶链表
public ListNode OddEvenList(ListNode head)
{
if (head == null||head.next==null) return head;
ListNode odd = head;
ListNode even = head.next;
ListNode evenHead = head.next;
while (even != null&&even.next!=null)
{
odd.next = odd.next.next;
odd = odd.next;
even.next = even.next.next;
even = even.next;
}
odd.next = evenHead;
return head;
}
344.反转字符串
///
///系统函数
///
///
public void ReverseString(char[] s)
{
Array.Reverse
}
///
/// 双指针
///
///
public void ReverseString2(char[] s)
{
if (s == null || s.Length == 0) return;
int l = 0;
int r = s.Length - 1;
while(l<r)
{
char temp = s[l];
s[l] = s[r];
s[r] = temp;
l += 1;
r -= 1;
}
}
/// <summary>
/// 递归法
/// </summary>
/// <param name="s"></param>
public void ReverseString3(char[] s)
{
if (s == null || s.Length == 0) return;//为空或长度为0返回
Recursion(s, 0, s.Length - 1);//递归函数
}
private void Recursion(char[] s,int l,int r)
{
if (l >= r) return;//左右指针相等或相交时返回
Recursion(s, l + 1, r - 1);//左右两端对称的字符在同一递归层中，
//递归返回时，交换同递归层中的左右字符完成反转
char temp = s[l];
s[l] = s[r];
s[r] = temp;
}
class LC349相交数组
{
public int[] Intersection(int[] nums1, int[] nums2)
{
List
if (nums1 == null || nums1 == null || nums1.Length == 0 || nums2.Length == 0) return res .ToArray();
HashSet
HashSet
foreach (var item in set1)
{
if (set2.Contains(item))
res.Add(item);
}
return res.ToArray();
}
}
class LC485.最大连续1的个数
{
public static int FindMaxConsecutiveOnes(int [] nums)
{
int res = 0;
int count = 0;
for (int i = 0; i < nums.Length; i++)
{
if (nums[i] == 1)
count++;
else
{
res = Math.Max(res, count);
count = 0;
}
}
return Math.Max(res,count);
}
}
496.下一个更大元素_I
///
/// 给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
/// 找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
/// 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
/// 输出: [-1,3,-1]
///
class LC496下一个更大元素_I
{
public int[] NextGreaterElement(int[] nums1, int[] nums2)
{
List
Stack
for (int i = 0; i < nums2.Length; i++)//nums2装入栈中
{
stack.Push(nums2[i]);
}
foreach (int n in nums1)//遍历数组1
{
Stack<int> temp = new Stack<int>();//临时栈，储存nums2弹出的元素
bool isFind = false;//默认是否在nums2中找到nums1中的目标值
int max = -1;//默认右边未找到比n大的值
while(stack.Count!=0&&!isFind)//nums2不为空并且还2未找到n，进入循环
{
int top = stack.Pop();//栈顶元素(最右边的元素)
if (top > n)//弹出值比目标n大，更新最大值
max = top;
else if (top == n)//与n相等则找到了n
isFind = true;
temp.Push(top);//临时栈中存储nums2弹出的值，最后在返回给nums2栈，保持其不变
}
res.Add(max);//max加入返回数组，未更新则右边没有比n大的值，更新则max保存的即是右边第一个比n大的值
while (temp.Count != 0)//将临时栈的元素返还给nums2栈，使其保持不变，用于选择下一个num1中比n大的值
stack.Push(temp.Pop());
}
return res.ToArray();//遍历完nums1后返回结果类表转数组
}
}
class LC509斐波那契数
{
///
/// 斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。
/// 该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：
///
///
///
public int Fib(int n)
{
if (n < 2) return n == 1 ? 1 : 0;
int sum = Fib(n - 1) + Fib(n - 2);
return sum;
}
/// <summary>
/// 动态规划：
/// </summary>
/// <param name="n"></param>
/// <returns></returns>
public int Fib2(int n)
{
if (n < 2) return n == 1 ? 1 : 0;
int[] res = new int[n + 1];
res[0] = 0;
res[1] = 1;
for (int i = 2; i < res.Length; i++)
{
res[i] = res[i - 1] + res[i - 2];
}
return res[n];
}
//动态规划，空间复杂度优化
public int Fib3(int n)
{
if (n <= 1) return n;
int prev1 = 0;
int prev2 = 1;
int res = 0;
for (int i = 2; i <= n; i++)
{
res = prev1 + prev2;
prev1 = prev2;
prev2 = res;
}
return res;
}
}
//680.回文字符串II,允许删除一个字符实现回文字符串
public static bool IsPalindrome2(string s)
{
int left = 0;
int right = s.Length - 1;
while(left<right)
{
if(s[left]!=s[right])
{
return IsPs(s.Remove(left,1)) || IsPs(s.Remove(right,1));
}
left++;
right--;
}
return true;
}
public static bool IsPs(string s)
{
/int left = 0;
int right = s.Length - 1;
while (left < right)
{
if (s[left] != s[right])
{
return false;
}
left++;
right--;
}
return true;/
char[] sarray = s.ToCharArray();
Array.Reverse(sarray);
return s.Equals(new string(sarray));
}
class LC720词典中最长的单词
{
///
/// 暴力法，
///
///
///
public static string LongestWord(string[] words)
{
//边界条件
if (words == null || words.Length == 0) return "";
string res = "";//返回值
//将字符串数组存入集合方便快速查找
HashSet<string> wordset = new HashSet<string>(words);
//遍历集合
foreach (string word in wordset)
{
//如果当前单词的长度大于，预存的结果。或长度相同时排序较小，这可能成为新的res
if (word.Length > res.Length||(word.Length==res.Length&&word.CompareTo(res)<0))
{
bool isword = true;//默认可以是新的res
for (int i = 0; i < word.Length; i++)//遍历新word的每个word[0~i+1]顺序组合都在字典中存在
{
if(!wordset.Contains(word.Substring(0,i+1)))//有不存在的则不能成为新res，退出循环
{
isword = false;
break;
}
}
if (isword==true)//遍历后认为true则瞒住条件
res = word;//替换当前res
}
}
return res;//返回res
}
}
876.链表中间节点
//快慢指针法
public ListNode MiddleNode(ListNode head)
{
ListNode slow = head;
ListNode fast = head;
while(fast!=null&&fast.next!=null)
{
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
881.救生艇
///
/// 第 i 个人的体重为 people[i]，每艘船可以承载的最大重量为 limit。
/// 每艘船最多可同时载两人，但条件是这些人的重量之和最多为 limit。
/// 返回载到每一个人所需的最小船数。(保证每个人都能被船载)。
///
class LC881救生艇
{
public int NumRescueBoats(int[] people, int limit)
{
if (people == null || people.Length == 0) return 0;
Array.Sort<int>(people);
int res = 0;
int l = 0;
int r = people.Length - 1;
while(l<=r)
{
if (people[l] + people[r] <= limit)
l += 1;
r -= 1;
res += 1;
}
return res;
}
}
989数组形式的整数加法
public static List
{
int ans = 0;
for (int i = 0; i < A.Length; i++)
{
ans = ans * 10 + A[i];
}
ans += K;
List
while(ans>0)
{
res.Add(ans % 10);
ans /= 10;
}
res.Reverse();
return res;
}
——————————————————————————————————
class LC1456定长子串中元音最大的数目
{
///
/// 滑动窗口法
///
///
///
///
public int MaxVowels(string s, int k)
{
if (s == null || s.Length == 0||s.Length<k) return -1;
HashSet
int res = 0;
int count = 0;
for (int i = 0; i < k; i++)
{
if (set.Contains(s[i]))
count += 1;
}
res = Math.Max(res, count);
for (int i = k; i < s.Length; i++)
{
if (set.Contains(s[i - k]))
count -= 1;
if (set.Contains(s[i]))
count += 1;
res = Math.Max(res, count);
}
return res;
}
}