avatar

[笔记]初级算法-数组问题总结Ⅱ

加一

给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。

最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外,这个整数不会以零开头。

示例 1:

输入: [1,2,3]

输出: [1,2,4]

解释: 输入数组表示数字 123。

示例 2:

输入: [4,3,2,1]

输出: [4,3,2,2]

解释: 输入数组表示数字 4321。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// 倒序加1
public class Solution {
public int[] PlusOne(int[] digits) {
int len = digits.Length;
for(int i = len - 1; i >= 0; i--)
{
digits[i]++;
digits[i] %= 10;
if(digits[i] != 0)
return digits;
}
digits = new int[len + 1];
digits[0] = 1;
return digits;
}
}

移动零

给定一个数组 nums,编写一个函数将所有 0 移动到数组的末尾,同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]

输出: [1,3,12,0,0]

说明:

必须在原数组上操作,不能拷贝额外的数组。
尽量减少操作次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 置零
public class Solution {
public void MoveZeroes(int[] nums) {
for(int i = 0, lastZero = 0; i < nums.Length; i++)
{
if(nums[i] != 0)
{
nums[lastZero] = nums[i];
if(i != lastZero)
{
nums[i] = 0;
lastZero++;
}
}
}
}
}

置零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// 交换
// 把遇到的所有不非零的向前放
public class Solution {
public void MoveZeroes(int[] nums) {
int i = 0;
int zero = 0;
while(i < nums.Length)
{
if(nums[zero] != 0)
{
int temp = nums[i];
nums[i] = nums[zero];
nums[zero] = temp;
zero++;
}
i++;
}
}
}

交换

两数之和

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
// 暴力法,遍历搜索
public class Solution {
public int[] TwoSum(int[] nums, int target) {
for(int i = 0; i < nums.Length; i++)
{
int find = target - nums[i];
for(int j = i + 1; j < nums.Length; j++)
{
if(nums[j] == find)
return new int[]{i,j};
}
}
return new int[]{};
}
}

// 哈希表(对于key是int型的,用Dictionary速度更快)
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Hashtable h = new Hashtable();
for(int i = 0; i < nums.Length; i++)
{
int find = target - nums[i];
if(h.ContainsKey(find))
return new int[]{ (int)h[find], i};
h[nums[i]] = i;
}
return new int[]{};
}
}

public class Solution {
public int[] TwoSum(int[] nums, int target) {
var dic = new Dictionary<int,int>();
for(int i = 0; i < nums.Length; i++)
{
int find = target - nums[i];
if(dic.ContainsKey(find))
return new int[]{dic[find], i};
// 注意这里要先判断是否已经存在同样的键
else if(!dic.ContainsKey(nums[i]))
dic.Add(nums[i], i);
}
return new int[]{};
}
}

有效的数独

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。

数独图

上图是一个部分填充的有效的数独。

数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

示例 1:

输入:

1
2
3
4
5
6
7
8
9
10
11
[
["5","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]

输出: true

示例 2:

输入:

1
2
3
4
5
6
7
8
9
10
11
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]

输出: false

解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。

但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

说明:

一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 ‘.’ 。
给定数独永远是 9x9 形式的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
public bool IsValidSudoku(char[][] board)
{
if (board==null || board.Length==0 )
{
return false;
}
Dictionary<char, int>[] row = new Dictionary<char, int>[9];//行
Dictionary<char, int>[] col = new Dictionary<char, int>[9];//列
Dictionary<char, int>[] box = new Dictionary<char, int>[9];//宫
//初始化哈希表
for (int i = 0; i < 9; i++)
{
row[i] = new Dictionary<char, int>();
col[i] = new Dictionary<char, int>();
box[i] = new Dictionary<char, int>();
}
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
//当前没有字符 抬走 下一个
if (board[i][j].Equals('.'))
{
continue;
}
//计算宫的索引
int k = i / 3 * 3 + j / 3;
//当前元素对应的行集合,列集合,宫集合,都不重复
if (!row[i].ContainsKey(board[i][j]) && !col[j].ContainsKey(board[i][j]) && !box[k].ContainsKey(board[i][j]))
{
row[i].Add(board[i][j],i);
col[j].Add(board[i][j],j);
box[k].Add(board[i][j],k);
}
else {
return false;
}
}
}
return true;
}
}

旋转图像

给定一个 n × n 的二维矩阵表示一个图像。

将图像顺时针旋转 90 度。

说明:

你必须在原地旋转图像,这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。

示例 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
给定 matrix 
[
[1,2,3],
[4,5,6],
[7,8,9]
],

原地旋转输入矩阵,使其变为:
[
[7,4,1],
[8,5,2],
[9,6,3]
]

示例 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
给定 matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

原地旋转输入矩阵,使其变为:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
1
2
3
4
5
public class Solution {
public void Rotate(int[][] matrix) {

}
}
文章作者: Daachun
文章链接: http://daachun.com/2020/03/09/算法笔记/笔记-初级算法-数组问题总结Ⅱ/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 NGGames | 造梦者
打赏
  • 微信
    微信
  • 支付宝
    支付宝

评论