算法进修Day-37

算法进修Day-37

73. 矩阵置零

难度：中等
题目要求
给定一个 _m_ x _n_ 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例1

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例2

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

题解

利用两个数组 $row$ 和 $col$ 来存入数值为0的位置的行和列，之后对数组进行遍历，将所在单位设为0

想法代码

class Solution
{public static void Main(String[] args){int[][] matrix ={new[] { 0, 1, 2, 0 },new[] { 3, 4, 5, 2 },new[] { 1, 3, 1, 5 }};Solution solution = new Solution();solution.SetZeroes(matrix);foreach (var i in matrix){foreach (var j in i){Console.Write(j+" ");}Console.WriteLine();}}public void SetZeroes(int[][] matrix){int index_x = 0;int index_y = 0;int count = 0;int[] row = new int[matrix.Length * matrix[0].Length];int[] col = new int[matrix.Length * matrix[0].Length];for (int i = 0; i < matrix.Length; i++){for (int j = 0; j < matrix[i].Length; j++){if (matrix[i][j] == 0){row[index_x] = i;col[index_y] = j;index_x++;index_y++;}}}while (count < index_x){for (int j = 0; j < matrix[0].Length; j++){matrix[row[count]][j] = 0;}count++;}count = 0;while (count < index_y){for (int j = 0; j < matrix.Length; j++){matrix[j][col[count]] = 0;}count++;}}
}

74.搜索二维数组

难度：中等
题目要求：
给你一个满足下述两条属性的 m x n 整数矩阵：

• 每行中的整数从左到右按非严格递增顺序排列。
• 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ，如果 target 在矩阵中，返回 true ；否则，返回 false 。

示例1

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出：true

示例2

输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出：false

题解

对当前数组的第一列进行遍历：

• 如果 $matrix[i][0]<target$ 那么，记录 $co{l}_{i}ndex=i-1$
• 如果 $matrix[i][0]==target$ ，直接返回$true$
• 如果 $matrix[matrix.Length-1][0]<target$，让 $co{l}_{i}ndex=matrix.Length-1$
• 如果 $co{l}_{i}ndex<0$，直接返回 $false$
• 如果 $matrix[co{l}_{i}ndex][i]==target$，返回 $true$，否则返回 $false$

想法代码

class Solution
{public static void Main(String[] args){Solution solution = new Solution();int[][] matrix ={new[] { 1, 3, 5, 7 },new[] { 10, 11, 16, 20 },new[] { 23, 30, 34, 60 }//new[]{1},//new[]{3}};int target = 30;Console.WriteLine(solution.SearchMatrix(matrix,target));}public bool SearchMatrix(int[][] matrix, int target){int col_index = 0;for (int i = 0; i < matrix.Length; i++){if (matrix[i][0] > target){col_index = i - 1;break;}if (matrix[i][0] == target){return true;}}if (matrix[matrix.Length-1][0] < target){col_index = matrix.Length - 1;}if (col_index < 0){return false;}for (int i = 0; i < matrix[0].Length; i++){if (matrix[col_index][i] == target){return true;}}return false;}
}

75. 颜色分类

难度：中等
题目要求：
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例1

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

示例2

输入：nums = [2,0,1]
输出：[0,1,2]

题解：

直接利用双指针进行解题，步骤如下：

• 定义 $inde{x}_{l}eft$ 和 $inde{x}_{r}ight$ 指针，分别置为0，对当前数组进行遍历
• 如果 $nums[i]=1$，交换当前位置和右指针的元素，右指针自增
• 如果 $nums[i]=0$，交换当前位置和左指针的元素，左指针自增
  • 如果 $inde{x}_{l}eft<inde{x}_{r}ight$，交换当前位置和右指针的元素（在父条件之后）
  • 左右指针自增
• 右指针到达数组末尾，遍历结束

想法代码

class Solution
{public static void Main(String[] args){Solution solution = new Solution();int[] nums = { 2, 0, 2, 1, 1, 0 };solution.SortColors(nums);foreach (int i in nums){Console.Write(i + " ");}}public void SortColors(int[] nums){int index_left = 0;int index_right = 0;for (int i = 0; i < nums.Length; i++){if (nums[i] == 1){Swap(nums, i, index_right);index_right++;}else if (nums[i] == 0){Swap(nums, i, index_left);if (index_left < index_right){Swap(nums,i, index_right);}index_left++;index_right++;}}}public void Swap(int[] nums, int index_left, int index_right){int temp = nums[index_left];nums[index_left] = nums[index_right];nums[index_right] = temp;}
}

76. 最小覆盖子串

难度：困难
题目要求：
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

示例1

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：“BANC”

示例2

输入：s = “a”, t = “a”
输出：“a”

示例3

输入：s = “a”, t = “aa”
输出：“”

题解

使用滑动窗口法，定义两个字典 $need$ 和 $window$，$need$ 内部存储 $t$ 的内容，$window$ 内部存储符合要求的内容
具体步骤如下：

• 对当前字符串 $s$ 进行遍历，让 $right$ 右移，直到 $right$ 指针第一次找到 $window$ 包含 $need$ 里的全部内容
• 将 $left$ 右移，直到找到下一个在 $need$ 内容里的元素，继续遍历重复上一步步骤
• 将内容比较，长度短的内容保存
• 当$right$ 遍历到字符串 $s$ 的最后一个内容的时候，遍历结束

返回最短的内容

想法代码

class Solution
{public static void Main(String[] args){Solution solution = new Solution();string s = "ADOBECODEBANC";string t = "ABC";Console.WriteLine(solution.MinWindow(s,t));}public string MinWindow(string s, string t){Dictionary<char,int> need = new Dictionary<char,int>();Dictionary<char,int> window = new Dictionary<char,int>();foreach (var a in t){if (need.ContainsKey(a)){need[a]++;}else{need.Add(a, 1);}}int left = 0;int right = 0;int start = 0;int count = 0;int len = Int32.MaxValue;while (right < s.Length){char c = s[right];right++;if (need.ContainsKey(c)){if (window.ContainsKey(c)){window[c]++;}else{window.Add(c, 1);}if (need[c] == window[c]){count++;}}while(count == need.Count){if (right - left < len){start = left;len = right - left;}char d = s[left];left++;if (need.ContainsKey(d)){if (window[d] == need[d]){count--;}window[d]--;}}}return len == Int32.MaxValue ? "" : s.Substring(start, len);}
}