微派冬令营笔试题

算法题如下：

最小覆盖子串

我认为难以理解的部分为

//这个部分是在s中找到了包含所有t字符的一个子串，这个子串可能不是最小的，后续操作就是把这个变为最小

//检测当前窗口是否已经包含了t中的所有字符（包括数量）
        while(Right < s.Length){
			char c = s[Right];
            Right++;
            
            if(need.ContainsKey(c)){
				windows[c] = windows.ContainsKey(c):windows[c] + 1 : 1;//记录s中字符串的出现次数
                if(windows[c] == need[c])
                    Vaild++;
            }
        }

假设：

• s = "ADOBECODE"（源字符串）
• t = "ABC"（需要包含的字符）

need字典记录t中每个字符需要出现几次：

• need = {'A':1, 'B':1, 'C':1}（A需要1个，B需要1个，C需要1个）

初始状态：窗口为空，Valid = 0

第一次循环（Right=0，字符’A’）：

• ‘A’在need中存在 → 记录windows[‘A’]=1
• windows’A’== need’A’→ Valid从0变成1

第二次循环（Right=1，字符’D’）：

• ‘D’不在need中 → 直接跳过，Valid还是1

第三次循环（Right=2，字符’O’）：

• ‘O’不在need中 → 跳过，Valid还是1

第四次循环（Right=3，字符’B’）：

• ‘B’在need中存在 → windows[‘B’]=1
• windows’B’== need’B’→ Valid从1变成2

第五次循环（Right=4，字符’E’）：

• ‘E’不在need中 → 跳过，Valid还是2

第六次循环（Right=5，字符’C’）：

• ‘C’在need中存在 → windows[‘C’]=1
• windows’C’== need’C’→ Valid从2变成3

此时 Valid = 3且 need.Count = 3，说明窗口”ADOBEC”已经包含了t的所有字符！但是if(need.ContainsKey(c))减少了不需要的判断，上述过程是未简化的

完整的解题思路：

1. 使用两个哈希表：need记录 t中每个字符的出现次数，window记录当前窗口中各字符的出现次数

2. 使用双指针 left和 right表示滑动窗口的左右边界

3. 移动右指针扩大窗口，直到包含 t的所有字符

4. 然后移动左指针缩小窗口，寻找最小子串

5. 记录最小长度和起始位置

   • need[c]：字符c在目标字符串t中需要出现的次数
   • windows[c]：字符c在当前滑动窗口中实际出现的次数
   • Vaild：当前窗口中已满足需求数量的字符种类数

   完整代码

   public class Solution{
       public string MinWindow(string s, string t) {
   		if(s.Length == 0||t.Length == 0||s == null||t == null)
               return "";
           Dictionary<char,int> need = new Dictionary<char,int>();
           
       	//记录t中字符串出现的次数
           for(int i = 0;i < t.Length;i++){
               char c = t[i];
               if(need.ContainsKey(c)){
                   need[c] = need[c] + 1;
               }
               else{
                   need[c] = 1;
               }
           }
           //滑动窗口
           Dictionary<char,int> windows = new Dictionary<char,int>();
           int Left = 0; //双指针
           int Right = 0;
           int Vaild = 0;  //满足条件的字符个数,先找到最大的范围
           int Start = 0,maxLen = int.MaxValue; // 记录最小子串的起始位置和长度
           
           //- s = "ADOBECODEBANC"，t="ABC"
           //检测当前窗口是否已经包含了t中的所有字符（包括数量）
           while(Right < s.Length){
   			char c = s[Right];
               Right++;
               
               if(need.ContainsKey(c)){  //减少不需要的判断，优化性能
   				windows[c] = windows.ContainsKey(c)?windows[c] + 1 : 1;//记录s中字符串的出现次数
                   if(windows[c] == need[c]) //这个c不是索引，是字符
                       Vaild++;
               }
               
               //判断左侧窗口是否要收缩
               while(Vaild == need.Count){  //说明找到包含完整t的子串  如果有多个窗口也可以分割窗口，第一个找完后找第二个
                   //更新最小覆盖子串
                   if(Right - Left < maxLen){  //第一次是直接进去的，因为必然小于
                       Start = Left;
                       maxLen = Right - Left;
                   }
                   char d = s[Left];
                   Left++;
   
                   // 更新窗口数据，就是找到每个窗口的最小子串，最后进行比较
                   if (need.ContainsKey(d)) {//首先判断 在s中是否存在t字符，不存在这个直接窗口右移。
                       if (window[d] == need[d]) {//字符d在2个字典出现的次数是否相等
                           valid--;
                       }
                       window[d]--;     
                   }
               }
           }
           return maxLen == int.MaxValue?"":s.Substring(Start,maxLen);
       }
   }

最长递增子序列

使用动态规划求解

动态规划：

• dp[i]表示以 nums[i]结尾的最长递增子序列长度
• 对于每个位置 i，遍历之前的所有位置 j(0 ≤ j < i)
• 如果 nums[i] > nums[j]，则 dp[i] = Math.Max(dp[i], dp[j] + 1)
• 最终结果是 dp数组中的最大值

public class Solution {
    public int LengthOfLIS(int[] nums) {
        if(nums.Length == 0 || nums = null)
            return 0;
        
		int n = nums.Length;
        int[] dp = new int[n];  //以 nums[i]结尾的最长递增子序列长度
        int maxLen = 1;
        
        for(int i = 0;i < n;i++)//默认都是1，因为自身包含一个数字
            dp[i] = 1;
    	for(int i = 1;i < n;i++){
            for(int j = 0;j < i;j++){  
                if(nums[i] > nums[j])  //如果当前数大于它之前的数
                	dp[i] = Math.Max(dp[i],dp[j] + 1);
			}
            maxLen = Math.Max(maxLen,dp[i]);
        }
        return maxLen;
    }
}