@[TOC]
前言
:smiley: 大家好，我是writer桑，这是自己整理的 C# 做题记录，方便自己学习的同时分享出来，感谢支持。
03. 数组中重复的数字
找出数组中重复的数字。在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
代码实现：
public class Solution
{
public int FindRepeatNumber(int[] nums)
{
HashSet<int> set = new HashSet<int> { }; // 声明一个空的哈希表
foreach (int num in nums)
{
if (set.Contains(num)) // 重复包含直接返回
return num;
else
set.Add(num); // 无包含则添加
}
return 0;
}
}思路分析：
- 首先创建一个容器，遍历数组中的每个数字并检查容器中有无这个数字， 如果没有则直接放入元素， 如果有则证明这个元素是重复的可直接返回。
- 这里的容器推荐使用哈希表（HashSet）， 因为哈希表的查找效率很高，可以很好的提高整个算法的效率。
代码实现2：
public class Solution {
public int FindRepeatNumber(int[] nums) {
Array.Sort(nums); // 循环遍历
for (int i = 1; i < nums.Length; i++) // 对数组进行排序
{
if (nums[i] == nums[i - 1])
return nums[i];
}
return 0;
}
}思路分析：
- 对数组进行排序，for 循环从第二个元素开始遍历数组，如果与前一个元素相等则可以证明该元素是重复的。
- 因为需要多执行数组排序这一步，所以性能没有第一种解法高，推荐第一种解法。
04. 二维数组中的查找
在一个 n * m 的二维数组中，每一行都按照从左到右 非递减 的顺序排序，每一列都按照从上到下 非递减 的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30]]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
代码实现：
public class Solution {
public bool FindNumberIn2DArray(int[][] matrix, int target) {
if (matrix.Length == 0 || matrix == null) // 判断是否为空
return false;
int i = matrix.Length - 1;
int j = 0;
while (i >= 0 && j < matrix[0].Length)
{
if (matrix[i][j] > target)
i--;
else if (matrix[i][j] < target)
j++;
else
return true;
}
return false;
}
}思路分析：
- 将矩阵逆时针旋转 45° 并展开，可以发现类似于二叉搜索树， 那么从根节点开始搜索时，遇到比 target 大的元素就向左，反之则向右，以此来找到目标值 target 。
- 需要事先判断 matrix 是否为空，为空直接返回 false 。根据二叉搜索树的特性，选用矩阵的左下角的元素作为标志数 flag，若 flag > target ，则 target 一定在 flag 所在 行的上方, 若 flag < target ，则 target 一定在 flag 所在 列的右方，以此类推直到找到目标数 target 。
- 算法本身比较好理解，难点在于根据题目的描述找到突破口。
代码实现2：
public class Solution {
public bool FindNumberIn2DArray(int[][] matrix, int target) {
foreach (int[] arr in matrix)
{
if(arr.Contains(target)) // 包含直接返回true
{
return true;
}
}
return false;
}
}思路分析：
- 简单的循环输出，逐个数组进行判断有无包含目标数，有则直接返回 true 。当循环结束时，也即表示没有该目标数，返回 false 。
- 对比第一种解法，代码量更少， 但是因为每次都需要逐个遍历数组，所以性能较低，推荐第一种解法。
05. 替换空格
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例：
输入：s = "We are happy."
输出："We%20are%20happy."
代码实现：
public class Solution {
public string ReplaceSpace(string s) {
return string.Join("%20",s.Split(' '));
}
}思路分析：
- 使用 Split 方法指定空格 ' ' 进行分割，再利用 Join 方法指定 "%20" 进行连接， 然后直接返回即可。
- 这种解法很容易想到，而且代码量很少、很简洁，一行代码搞定。
代码实现2：
public class Solution {
public string ReplaceSpace(string s) {
StringBuilder res = new StringBuilder(); // 声明可变字符串
foreach(var c in s) // 循环遍历
{
if(c == ' ')
res.Append("%20");
else
res.Append(c);
}
return res.ToString();
}
}思路分析：
- 声明可变字符串 res 用于存放返回结果，for 循环遍历字符串 s 依次判断字符元素， 如果为空格 ' ' 则替换为"%20"放入 res , 如果不为空格则直接放入 res 中。循环结束则直接将 res 转换为字符串类型返回即可。
- 与第一种解法相比，这种解法更常见，代码量较多，两者在性能上差不多。
结语
:sunflower: 以上就是本次的做题记录啦，希望大家看完有所收获。同时希望大家多多支持，你们的支持就是笔者学习最大的动力！
