剑指 Offer 03. 数组中重复的数字
难度⭐
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3
coding
class Solution:
def findRepeatNumber(self, nums: List[int]) -> int:
hashset = set()
for num in nums:
if num not in hashset:
hashset.add(num)
else:
return num
return -1
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet<Integer> set = new HashSet<Integer>();
int repeat = -1;
for(int num:nums){
if(!set.add(num)){
repeat = num;
break;
}
}
return repeat;
}
}
剑指 Offer 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]
]
coding
当然还有暴力法
class Solution:
def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
if not matrix:
return False
#以右上角元素为起点
#target < 该元素 左移；否则 下移
x,y = 0,len(matrix[0])-1
while x<len(matrix) and y>=0:
if target == matrix[x][y]:
return True
elif target < matrix[x][y]:
y -= 1
else:
x += 1
return False
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix==null || matrix.length==0 || matrix[0].length==0){
return false;
}
int x=0, y=matrix[0].length-1;
while (x<matrix.length && y>=0){
int num = matrix[x][y];
if (num == target){
return true;
} else if (num < target){
x += 1;
} else{
y -= 1;
}
}
return false;
}
}
剑指 Offer 05. 替换空格
难度⭐
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
coding
class Solution:
def replaceSpace(self, s: str) -> str:
# return s.replace(" ","%20");
length = len(s)
new = [""]*length*3
index = 0
for char in s:
if char == " ":
new[index] = "%"
new[index+1] = "2"
new[index+2] = "0"
index += 3
else:
new[index] = char
index += 1
return "".join(new[:index+1])
class Solution {
public String replaceSpace(String s) {
// return s.replace(" ","%20");
int len = s.length();
char[] array = new char[len*3];
int index = 0;
for (int i=0;i<len;i++){
char c = s.charAt(i);
if (c==' '){
array[index++] = '%';
array[index++] = '2';
array[index++] = '0';
}
else{
array[index++] = c;
}
}
String news = new String(array,0,index);
return news;
}
}