Brush questions every day -- leetcode sword finger offer 3, 4, 5, 29, 50

Start preparing to find a job, target java development, learn java from 0, and update the experience of brushing questions every day.
Today, there are several basic arrays and matrices.

Duplicate number in sword finger offer3 array

All numbers in an array of length n are in the range of 0 to n-1. Some numbers in the array are repeated, but I don't know how many numbers are repeated, or how many times each number is repeated. Please find any duplicate number in the array.

The complexity of each question is only one number, which means the complexity of each question is o.
There is a detail in the title here. If all the numbers in the array are in the range of 0 to n-1, you can use in-situ replacement and directly use the original array as the hash table

class Solution {
    public int findRepeatNumber(int[] nums) {
    	int len = nums.length;
    	for(int i=0; i<len; i++){
    		while(nums[i]!=i){
    			if(nums[nums[i]]!=nums[i]) {
					int temp = nums[i];
					nums[i] = nums[temp];
					nums[temp] = temp;
				}else{
    				return nums[i];
				}
			}
		}
    	return -1;
    }
}

Searching in two-dimensional array of sword finger offer4

Given a two-dimensional array, each row is sorted incrementally from left to right, and from top to bottom.
Given a number, judge whether the number is in the two-dimensional array.

The array is incremented to the right and down, so it is difficult to do. When the target is greater than the current number, we don't know whether to the right or down. At this time, we need to change the direction to make one side increase and the other side decrease, so that we can easily get the results. Therefore, select the upper right corner or lower left corner. For example, the upper right corner decreases to the left and increases to the right. You only need to determine the moving direction according to the comparison with the size of the target.

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
    	int lenx = matrix.length;
    	if(lenx==0){
    		return false;
		}
    	int leny = matrix[0].length;
    	if(leny==0) return false;
    	int i = 0, j = leny-1;
    	while(i<lenx&&j>=0){
    		if(matrix[i][j]>target){
    			j--;
			}else if(matrix[i][j]<target){
    			i++;
			}else{
    			return true;
			}
		}
    	return false;
    }
}

Sword finger offer5 replaces space

Please implement a function to replace each space in the string s with "% 20".

It's a basic string type operation problem. As a java Xiaobai, it puzzles me.
In JAVA, string type is not operable, so you need to reconstruct string.
Summarizing the problem solution mainly includes two methods: one is to construct charArray and use string method to construct string, and the other is to construct string through StringBuilder method

class Solution {
    public String replaceSpace(String s) {
    	StringBuilder res = new StringBuilder();
    	for(Character c: s.toCharArray()){
    		if(c==' ') res.append("%20");
    		else res.append(c);
		}
    	return res.toString();
    }
}

Sword finger offer29 clockwise print matrix

Enter a matrix and print out each number in clockwise order from the outside to the inside

This question is not difficult. Set the upper, lower, left and right bounds and set the cycle. It should be noted that when the upper and lower bounds are the same and the left and right bounds are the same, only one-way printing is required.

class Solution {
    public int[] spiralOrder(int[][] matrix) {
    	if(matrix==null || matrix.length==0 || matrix[0].length==0){
    		return new int[0];
		}
    	int rows = matrix.length, columns = matrix[0].length;
    	boolean[][] visited = new boolean[rows][columns];
    	int total = rows * columns;
    	int[] order = new int[total];
    	int row = 0, column = 0;
    	int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    	int direction = 0;
    	for(int i=0; i<total; i++){
    		order[i] = matrix[row][column];
    		visited[row][column] = true;
    		int nextRow = row + directions[direction][0], nextColumn = column + directions[direction][1];
    		if (nextRow<0 || nextRow>=rows || nextColumn<0 || nextColumn>=columns || visited[nextRow][nextColumn]==true){
    			direction = (direction + 1) % 4;
			}
    		row += directions[direction][0];
    		column += directions[direction][1];
		}
    	return order;
    }
}

Sword finger offer50 is the first character that appears only once

Find the first character in the string s that appears only once. If not, a single space is returned. S contains only lowercase letters.

This question is very similar to the third question of sword finger offer, which is to construct a hash table. Of course, this is a string type, and the reading and writing of string type need to be considered.

class Solution {
    public char firstUniqChar(String s) {
    	int[] cnts = new int[128];
    	for(int i=0; i<s.length(); i++){
    		cnts[s.charAt(i)]++;
		}
    	for(int i=0; i<s.length(); i++){
    		if(cnts[s.charAt(i)]==1){
    			return s.charAt(i);
			}
		}
    	return ' ';
    }
}

Today, that's it. Because it's the first day, it's relatively simple, four easy and one mid. The main thing is to be familiar with the syntax of java. There are still many string type operations, which need to be studied carefully. Finally, I hope I can stick to it and update it.

Tags: Java Algorithm leetcode Interview

Posted by SFDonovan on Sat, 26 Mar 2022 02:38:15 +0300