网站对企业的好处,室内设计公司排名全球,淘宝c2c模式,营销型网站 易网拓算法进修Day-37
73. 矩阵置零
难度#xff1a;中等 题目要求 给定一个 _m_ x _n_ 的矩阵#xff0c;如果一个元素为 0 #xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
示例1 输入#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]] 输出#xff1a;[…算法进修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]] 题解 利用两个数组 r o w row row 和 c o l col 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 题解 对当前数组的第一列进行遍历 如果 m a t r i x [ i ] [ 0 ] t a r g e t matrix[i][0]target matrix[i][0]target 那么记录 c o l i n d e x i − 1 col_indexi-1 colindexi−1如果 m a t r i x [ i ] [ 0 ] t a r g e t matrix[i][0]target matrix[i][0]target 直接返回 t r u e true true如果 m a t r i x [ m a t r i x . L e n g t h − 1 ] [ 0 ] t a r g e t matrix[matrix.Length-1][0]target matrix[matrix.Length−1][0]target让 c o l i n d e x m a t r i x . L e n g t h − 1 col_indexmatrix.Length-1 colindexmatrix.Length−1如果 c o l i n d e x 0 col_index0 colindex0直接返回 f a l s e false false如果 m a t r i x [ c o l i n d e x ] [ i ] t a r g e t matrix[col_index][i]target matrix[colindex][i]target返回 t r u e true true否则返回 f a l s e false 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] 题解 直接利用双指针进行解题步骤如下 定义 i n d e x l e f t index_left indexleft 和 i n d e x r i g h t index_right indexright 指针分别置为0对当前数组进行遍历如果 n u m s [ i ] 1 nums[i]1 nums[i]1交换当前位置和右指针的元素右指针自增如果 n u m s [ i ] 0 nums[i]0 nums[i]0交换当前位置和左指针的元素左指针自增 如果 i n d e x l e f t i n d e x r i g h t index_leftindex_right indexleftindexright交换当前位置和右指针的元素在父条件之后左右指针自增 右指针到达数组末尾遍历结束 想法代码
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” 输出“” 题解 使用滑动窗口法定义两个字典 n e e d need need 和 w i n d o w window window n e e d need need 内部存储 t t t 的内容 w i n d o w window window 内部存储符合要求的内容 具体步骤如下 对当前字符串 s s s 进行遍历让 r i g h t right right 右移直到 r i g h t right right 指针第一次找到 w i n d o w window window 包含 n e e d need need 里的全部内容将 l e f t left left 右移直到找到下一个在 n e e d need need 内容里的元素继续遍历重复上一步步骤将内容比较长度短的内容保存当 r i g h t right right 遍历到字符串 s s 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){Dictionarychar,int need new Dictionarychar,int();Dictionarychar,int window new Dictionarychar,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);}
}
