3.数组中重复的数字

题目
牛客网
思路

  1. 刚开始看到这个题目时第一反应可能是利用两个循环，外循环遍历数组确定要找的重复值，内循环遍历接下来的数组寻找重复值。但这种方法的时间复杂度太大，效率太低。
  2. 仔细阅读题目可以看到数字的范围在0~(n-1)之间，也就是说若没有重复的数字，在长度为n的数组里将填充着0~(n-1)范围内所有的数，若有重复的数字，数组中0~(n-1)之间的数肯定填不满。由此可以在外部再创建一个数组，在遍历原数组的同时把原数组上的数字存储到新建数组对应下标当中，也就是新建数组上的数字和其下标的值是相同的。但这样时间复杂度虽然变成了O(n)但是空间复杂度也变成了O(n)。
  3. 利用思路2中所分析的特性，不创建新的数组，在原数组中进行数据的交换，具体就是从头开始遍历数组，取下标i，i 上的值为numbers[i]，将numbers[i]与数组下标为numbers[i]上的值交换，直到交换到i上的值等于i时进行下一个值遍历。这种方法能够让数组下标和对应的值相等，而且还不用开辟新的数组空间。时间复杂度为O(n)，空间复杂度为O(1)。
    在这里采用思路3最好。

Java

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
public class Solution {
	public int duplicate (int[] numbers) {
	
		// 遍历数组
		for (int i = 0;i < numbers.length;i++) {
		
			// 若数组上的值与其下标不相等
			if (numbers[i] != i) {
			
				// 如果遍历到的数与这个数对应的下标上的数相等就表示有重复的数，返回重复数
				if (numbers[i] == numbers[numbers[i]]) {
					return numbers[i];
				}
				
				// 将下标为i 和下标为numbers[i]上的值进行交换
				swap(numbers, i, numbers[i])；
			}
		}
		
		// 没有重复的数返回-1
		return -1;
	}
	
	private void swap(int[] numbers, int i, int j) {
		/**
		*功能：交换数组numbers中下标为i 和下标为j 中的值
		*/
		int t = numbers[i];
		numbers[i] = numbers[j];
		numbers[j] = t;
	}
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def duplicate(self , numbers: List[int]) -> int:

        for i in range(len(numbers)):
            
            if(numbers[i] != i):
                
                if numbers[i] == numbers[numbers[i]]:
                    return numbers[i]
                
                self.swap(numbers, i, numbers[i])
        
        return -1
    
    def swap(self, numbers, i, j):
        t = numbers[i]
        numbers[i] = numbers[j]
        numbers[j] = t

4.二维数组中的查找

题目
牛客网
思路
题目特点：给定的数组每一行和每一列中的值都是递增。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来快速地缩小查找区间，每次减少一行或者一列的元素。当前元素的查找区间为左下角的所有元素。

Java

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
public class Solution {
	public boolean find(int target, int[][] array) {
	
		// 如果数组为空，返回false
		if (array == null) {
			return false;
		}
		
		// 初始化横纵坐标值（二维数组右上角）
		int i = 0;
		int j = array[0].length - 1;
		
		// 当横纵坐标都满足边界范围内，进行循环查找
		while ((i != array.length) && (j != -1)) {
			if (target == array[i][j]) {
				return true;
			} else if (target < array[i][j]) {
				j--;
			} else if (target > array[i][j]) {
				i++;
			}
		}
		
		// 找不到，返回false
		return false;
	}
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def Find(self , target: int, array: List[List[int]]) -> bool:
        
        if (array == []):
            return False
        
        i = 0
        j = len(array[0]) - 1
        
        while ((i != len(array)) and (j != -1)):
            if (target == array[i][j]):
                return True
            elif (target < array[i][j]):
                j = j - 1
            elif (target > array[i][j]):
                i = i + 1
        
        return False

5.替换空格

题目
牛客网
思路
创建一个全新的字符串或者字符列表，然后再遍历输入的字符串，当遍历到的值不是空格时把遍历到的字符填充到新的字符串中，若是空格则把”%20”填入到新字符串中。

注：在Java中要掌握String、StringBuffer、StringBuilder类之间的关系和这些类中常用的方法。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
	public String replaceSpace (String s) {
	
		// 创建一个StringBuffer对象用来操作字符串
		StringBuffer stringBuffer = new StringBuffer();
		
		// 遍历字符串并对新字符串赋值
		for (int i = 0;i < s.length();i++) { 
		
			// 如果遍历到了空格字符，则把"%20"加入新字符串中
			if (s.charAt(i) == ' ') {
				stringBuffer.append("%20");
			}
			// 否则把原字符加入到新字符串中
			else {
				stringBuffer.append(s.charAt(i));
			}
		}
		
		// 返回新字符串对象的字符串
		return stringBuffer.toStirng();
	}
}

Python3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
	def replaceSpace(self, s: str) -> str:
	
		# 创建一个空字符串列表
		result_str = []
		
		# 遍历字符串并赋值到字符列表
		for str_char in str:
		
			# 如果遍历到字符串为' '则将'%20'加入到字符串列表
			if str_char == ' ':
				result_str.append('%20')
			else:
				result_str.append(str_char)
		
		# 将字符串列表拼成字符串并返回
		return ''.join(result_str)

29.顺时针打印矩阵

题目
牛客网
思路
方法：边界模拟法
这道题就是一个简单的模拟，我们想象有一个矩阵，从第一个元素开始，往右到底后再往下到底后再往左到底后再往上，结束这一圈，进入下一圈螺旋。

注：循环结束的条件是（左边界值>右边界值）或者（上边界值>下边界值），每次遍历完都得压缩边界并比较边界是否越界。

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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
       
       // 初始化集合
        ArrayList<Integer> res = new ArrayList<Integer>();
        
        // 若输入数组为空的情况
        if (matrix.length == 0) {
            return res;
        }
        
        // 初始化四个边界
        int up = 0;
        int down = matrix.length - 1;
        int left = 0;
        int right = matrix[0].length - 1;
        
        // 循环遍历二维数组直到边界重合
        while ((up <= down) && (left <= right)) {
            
            // 上边界从左到右
            for (int i = left;i <= right;i++) {
                res.add(matrix[up][i]);
            }
            
            up++;
            
            if (up > down) {
                break;
            }
            
            // 右边界从上到下
            for (int i = up;i <= down;i++) {
                res.add(matrix[i][right]);
            }
            
            right--;
            
            if (left > right) {
                break;
            }
            
            // 下边界从右到左
            for (int i = right;i >= left;i--) {
                res.add(matrix[down][i]);
            }
            
            down--;
            
            if (up > down) {
                break;
            }
            
            // 左边界从下到上
            for (int i = down;i >= up;i--) {
                res.add(matrix[i][left]);
            }
            
            left++;
            
            if (left > right) {
                break;
            }
        }
        
        // 返回数组集合
        return res;
    }
}

50.第一个只出现一次的字符位置

题目
牛客网
思路
统计频率可以建立一个哈希表，遍历字符串的同时，统计每个字符出现的频率，然后再从头遍历一次字符串，在哈希表中查看每个字符串的频率，找到第一个只出现一次的字符串，返回位置，如果没找到返回-1即可。

注：难点在于怎么建立字符键与出现次数的hashmap。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
import java.util.HashMap;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        
        // 新建hashmap
        HashMap<Character, Integer> mp = new HashMap<>();
        
        // 遍历字符串，找到不同字符出现的次数
        for (int i = 0;i < str.length();i++) {
            mp.put(str.charAt(i), (mp.getOrDefault(str.charAt(i), 0) + 1));
        }
        
        // 根据字符键从hashmap中查找次数
        for (int i = 0;i < str.length();i++) {
            if (mp.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        
        return -1;
    }
}