Statement: the title and figure are from Leecode: https://leetcode-cn.com/
Sword finger offer
3: Duplicate number in array
Title:
Solution ①: use additional array space. Execution time: 2 ms; Memory consumption: 46.1 MB
class Solution {
public int findRepeatNumber(int[] nums) {
//Create an array with length n and initialize 0
int[] sum=new int[nums.length];
//If the number appears, the corresponding subscript + 1;
int j=0;
for(int i=0;i<nums.length;i++){
j=nums[i]; //The value of the current subscript num
sum[j]++; //sum corresponding subscript + 1
if(sum[j]>1){ //Output the first subscript greater than 1
return j;
}
}
return 0; //There must be duplicate numbers, so we won't go to this step.
}
}
Problem solving ②: on the basis of the original array.
Refer to sword finger offer for ideas as follows:
The code is as follows: execution time: 0 ms; Memory consumption: 45.7 MB
public int findRepeatNumber(int[] nums) {
if(nums.length==2) return nums[0];
int tmp=0;
for(int i=0;i<nums.length;){
if(nums[i]==i){ //If the current index is equal to the current value, the next index is determined
i++;
}else{ //If the current index is not equal to the current value, it is compared with the value whose index is the current value
if(nums[i]==nums[nums[i]]){ //If equal, a duplicate number was found
// System.out.println("equal:"+nums[i]);
return nums[i];
}else{ //Exchange the values of the two positions and compare them again
tmp=nums[i];
nums[i]=nums[tmp];
nums[tmp]=tmp;
// System.out.println(i+"===>change:"+nums[i]+"--"+nums[nums[i]]+"--"+tmp);
//i + + will not be performed here. Continue to compare the current position until the current index = current value or duplicate numbers are found.
}
}
}
return 0;
}
05: replace spaces
subject
Please implement a function to replace each space in the string s with "% 20".
Solution 1: use the library function replace. Execution time: 0ms; Memory consumption 36 MB.
class Solution {
public String replaceSpace(String s) {
return s.replace(" ","%20");
}
}
Solution 2: traversal. Execution time: 0ms; Memory consumption 36.3 MB.
public String replaceSpace(String s) {
StringBuilder sb=new StringBuilder();
char c='a';
for(int i=0; i<s.length(); i++) {
c=s.charAt(i);
if(c == ' ') {
sb.append("%20");
}else {
sb.append(c);
}
}
return sb.toString();
}
10-II: frog jumping steps
Title:
A frog can jump up one step or two steps at a time. Find out how many jumping methods the frog can jump up an n-step.
The answer needs to take the module 1e9+7 (100000007). If the initial result is 100000008, please return 1.
Source: LeetCode
Link: https://leetcode-cn.com/problems/qing-wa-tiao-tai-jie-wen-ti-lcof
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Answer: execution time: 0 ms; Memory consumption: 34.8 MB
public int numWays(int n) {
if(n<=1) {
return 1;
}
int[] num=new int[n+1];
num[0]=1;
num[1]=1;
for(int i=2; i<=n; i++) {
num[i]=(num[i-1]+num[i-2])%1000000007;
}
return num[n];
12: Path in matrix
Title: give an m x n two-dimensional character grid board and a string word word. If word exists in the grid, return true; Otherwise, false is returned.
Words must be formed alphabetically by letters in adjacent cells, where "adjacent" cells are those horizontally or vertically adjacent. Letters in the same cell cannot be reused.
Problem solving: execution time: 6 ms; Memory consumption: 40.1 MB
class Solution {
public boolean exist(char[][] board, String word) {
if(word.length() == 0){
return true;
}
// Used to store the current cell usage
boolean[][] use=new boolean[board.length][board[0].length];
char[] w=word.toCharArray();
// Indicates the number of elements currently traversed, which is used to judge whether the cell is used
int num=1;
for(int i=0;i<board.length;i++) {
for(int j=0;j<board[0].length;j++) {
if(find(board,i,j,w,0,num,use)){
return true;
}
}
}
return false;
}
private boolean find(char[][] board,int i,int j,char[] c,int current,int num,boolean[][] use) {
// If the matching element is greater than or equal to the word length, it indicates that all matching is successful
if(current == c.length) {
return true;
}
// Index out of bounds character mismatch path already exists for this node
if(i >= board.length || j >= board[0].length || i < 0 || j < 0 || board[i][j] != c[current] || use[i][j]) {
return false;
}
// Match successful
use[i][j]=true;
num++;
current++;
// Traverse up, down, left and right
boolean result= find(board,i-1,j,c,current,num,use) || find(board,i+1,j,c,current,num,use)
|| find(board,i,j-1,c,current,num,use) || find(board,i,j+1,c,current,num,use);
use[i][j]=false;
return result;
}
}
15: Number of 1 in binary
Title: write a function. The input is an unsigned integer (in the form of binary string) and returns the number of digits with '1' in its binary expression (also known as Hamming weight).
Link: https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/
Answer: execution time: 0 ms; Memory consumption: 35.4 MB
public int hammingWeight(int n) {
int sum=0;
while(n != 0){
if((n&1) == 1){
sum++;
}
n>>>=1;
}
return sum;
}
22: the penultimate node in the lin k ed list
Title: enter a linked list and output the penultimate node in the linked list. In order to conform to the habit of most people, this question starts from 1, that is, the tail node of the linked list is the penultimate node.
For example, a linked list has six nodes. Starting from the beginning, their values are 1, 2, 3, 4, 5 and 6. The penultimate node of the linked list is a node with a value of 4.
Problem solving: execution time: 1 ms; Memory consumption: 36.2 MB
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode p1=head;
ListNode p2=head;
int distance=k;
// Let p1 and p2 be k nodes apart
while(p2 != null && distance != 0) {
p2=p2.next;
distance--;
}
// k is greater than the length of the linked list
if(distance != 0) {
return head;
}
// Keep the distance between p1 and p2. When p2 is null, the penultimate k is the linked list starting from p1
while(p2 != null) {
p1=p1.next;
p2=p2.next;
}
return p1;
}
}
24: reverse linked list
Title: define a function, input the head node of a linked list, reverse the linked list and output the head node of the inverted linked list.
Problem solving: execution time: 0 ms; Memory consumption: 38.3 MB
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null) {
return null;
}
ListNode p1=head;
if(p1.next == null) {
return p1;
}
ListNode p2=p1.next;
ListNode p3=p2.next;
p1.next=null; // The next node of the head node points to null
while(p3 != null) {
p2.next=p1;
// p1,p2,p3 move forward
p1=p2;
p2=p3;
p3=p2.next;
}
p2.next=p1;
return p2;
}
}
29: print matrix clockwise
Title: enter a matrix and print out each number in clockwise order from outside to inside.
Problem solving: execution time: 116 ms; Memory consumption: 40.5 MB
public int[] spiralOrder(int[][] matrix) {
if(matrix.length == 0) {
return new int[0];
}
int x=matrix.length;int y=matrix[0].length;
// Use a boolean array to store whether it has been printed
boolean[][] visited=new boolean[x][y];
int i=0,j=0,k=0;
int[] result=new int[x*y];
// Right - > bottom - > left - > Top
while(true) {
// towards the right
while(k<result.length && j<y) {
if(!visited[i][j]){
result[k++]=matrix[i][j];
visited[i][j++]=true;
}else{
break;
}
}
j--;i++;
// down
while(k<result.length && i<x) {
if(!visited[i][j]){
result[k++]=matrix[i][j];
visited[i++][j]=true;
}else{
break;
}
}
i--;j--;
// towards the left
while(k<result.length && j<y && i<x && i>=0 && j>=0) {
if(!visited[i][j]){
result[k++]=matrix[i][j];
visited[i][j--]=true;
}else{
break;
}
}
j++;i--;
// Up
while(k<result.length && j<y && i<x && i>=0 && j>=0) {
if(!visited[i][j]){
result[k++]=matrix[i][j];
visited[i--][j]=true;
}else{
break;
}
}
if(k == result.length) {
break;
}
i++;j++;
}
return result;
}
39: elements that appear more than half times in the array
Title: a number in the array appears more than half the length of the array. Please find out this number.
You can assume that the array is non empty and that there are always many elements in a given array.
Link: https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
Problem solving: execution time: 3 ms; Memory consumption: 44.3 MB
public int majorityElement(int[] nums) {
if(nums.length<3) return nums[0];
Arrays.sort(nums);
int current=nums[0];
int sum=0;
for(int i=0;i<nums.length;i++){
if(current == nums[i]){
sum++;
if(sum>(nums.length/2)){
return current;
}
}else{
current=nums[i];
sum=1;
}
}
return -1;
}
40: minimum k number
subject
Enter the integer array arr to find the minimum number of k. For example, if you enter 8 numbers: 4, 5, 1, 6, 2, 7, 3 and 8, the minimum 4 numbers are 1, 2, 3 and 4. (note that the numbers do not need to be de duplicated)
Solution 1: use the automatic sorting characteristics of TreeMap to store elements. Execution time: 45 ms; Memory consumption: 40 MB
public int[] getLeastNumbers(int[] arr, int k) {
if(arr.length ==0 || k == 0) {
return new int[0];
}
TreeMap<Integer,Integer> tm=new TreeMap<>();
for(int i=0; i<arr.length; i++) {
if(tm.containsKey(arr[i])){
tm.put(arr[i],tm.get(arr[i])+1);
} else {
tm.put(arr[i],1);
}
}
int[] result=new int[k];
int j=0;
for(Map.Entry<Integer, Integer> current:tm.entrySet()){
if(j == k){
break;
}
for(int i=0;i<current.getValue();i++){
if(j == k){
break;
}
result[j++]=current.getKey();
}
}
return result;
}
Solution 2: use quick sorting to sort first and then intercept. Execution time: 7 ms; Memory consumption: 39.7 MB
public int[] getLeastNumbers(int[] arr, int k) {
if(arr.length ==0 || k == 0) {
return new int[0];
}
quickSort(0,arr.length-1,arr);
return Arrays.copyOf(arr,k);
}
void quickSort(int low,int high,int[] arr) {
if(low>high) {
return;
}
int i=low;
int j=high;
int sign=arr[low];
while(i != j) {
while(arr[j] >= sign && i<j) {
j--;
}
if(j>i) {
arr[i]=arr[j];
i++;
}
while(arr[i] <= sign && i<j) {
i++;
}
if(i<j) {
arr[j]=arr[i];
j--;
}
}
arr[i]=sign;
quickSort(low,i-1,arr);
quickSort(i+1,high,arr);
}
42: maximum sum of consecutive subarrays
Title: enter an integer array. One or more consecutive integers in the array form a sub array. Find the maximum value of the sum of all subarrays. The required time complexity is O(n).
Link: https://leetcode-cn.com/problems/lian-xu-zi-shu-zu-de-zui-da-he-lcof/
Answer: execution time: 1 ms; Memory consumption: 45 MB
public int maxSubArray(int[] nums) {
int pre=0;
int max=nums[0];
for(int i=0;i<nums.length;i++){
int sum=0;
if(pre >= 0) {
sum=nums[i]+pre;
}else{
sum=nums[i];
}
max=Math.max(max,sum);
pre=sum;
}
return max;
}
47: the greatest value of gifts
**Title: * * there is a gift in each grid of an m*n chessboard, and each gift has a certain value (value greater than 0). You can start from the upper left corner of the chessboard to take the gifts in the grid, and move one grid to the right or down at a time until you reach the lower right corner of the chessboard. Given the value of a chessboard and the gifts on it, please calculate the maximum value of gifts you can get?
Solution: execution time: 2 ms; Memory consumption: 41 MB
public int maxValue(int[][] grid) {
int[] result=new int[grid[0].length+1];
for(int i=1;i<=grid.length;i++) {
for(int j=1;j<=grid[0].length;j++) {
result[j]=Math.max(result[j-1],result[j])+grid[i-1][j-1];
}
}
return result[grid[0].length];
}
50: the first letter that appears only once
subject
Find the first character in the string s that appears only once. If not, a single space is returned. S contains only lowercase letters.
Answer: execution time: 7 ms; Memory consumption: 38.4 MB
public char firstUniqChar(String s) {
if(s.length() == 0) {
return ' ';
}
if(s.length() == 1) {
return s.charAt(0);
}
char[] letter=new char[26];
for(int i=0; i<s.length(); i++) {
letter[s.charAt(i)-'a']++;
}
for(int i=0; i<s.length(); i++) {
if(letter[s.charAt(i)-'a'] == 1) {
return s.charAt(i);
}
}
return ' ';
}
}
53 - II: missing numbers in 0~n-1
Title: all numbers in an incremental sorting array with length n-1 are unique, and each number is in the range of 0 ~ n-1. Among the N numbers in the range 0 ~ n-1, there is only one number that is not in the array. Please find this number.
Answer: order is dichotomy. Running time 0 ms, memory consumption 38.7 MB
public int missingNumber(int[] nums) {
return getDefectNumber(nums,0,nums.length-1);
}
private int getDefectNumber(int[] nums,int low,int high) {
if((low+1) >= high) {
if(nums[low]+2 == nums[high]) {
return nums[low]+1;
} else if(nums[low] > low) {
return nums[low]-1;
} else {
return nums[high]+1;
}
}
// Judge which side of the left half and the right half is missing
int mid=(low+high)/2;
if(nums[mid] != mid) {
//In the left half
return getDefectNumber(nums,low,mid);
} else {
// In the right half
return getDefectNumber(nums,mid,high);
}
}
58-I: flip word order
Title: input an English sentence and flip the order of words in the sentence, but the order of characters in the word remains the same. For simplicity, punctuation is treated like ordinary letters. For example, if you enter the string "I am a student.", you will output "student. a am I".
Problem solving: the running time is 2 ms and the memory consumption is 38.4 MB
public String reverseWords(String s) {
char[] word=s.toCharArray();
StringBuilder sb=new StringBuilder();
int j=0;int k=0;int before=0;
for(int i=word.length-1;i>=0;) {
while(i >= 0 && word[i] == ' ') {
i--;
}
if(i >= 0 && before == 1) {
sb.append(" ".toString());
}
j=i;
while(i >= 0 && word[i] != ' ') {
i--;
}
// At this point [i+1,j] is a word
if(i >= 0) {
sb.append(s.substring(i+1,j+1));
}else if(j >= 0){
sb.append(s.substring(0,j+1));
}
before=1;
}
return sb.toString();
}
64: find 1 + 2 +... + n
subject
For 1 + 2 +... + n, it is required that keywords such as multiplication and division, for, while, if, else, switch, case and conditional judgment statements (A?B:C) cannot be used.
Answer: the running time is 0 ms and the memory consumption is 35.1 MB
public int sumNums(int n) {
return n*(n+1)>>1;
}
68: nearest common parent node of binary tree
Title: given a binary tree, find the nearest common ancestor of two specified nodes in the tree.
Link: https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/
Answer 1: the running time is 227 ms and the memory consumption is 39.4 MB
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
LinkedList<TreeNode> first=new LinkedList<>();
LinkedList<TreeNode> second=new LinkedList<>();
// 1. Query the path from the root node to the two target nodes
findPath(root,p,first);
findPath(root,q,second);
// 2. The last public node in the two paths is the nearest public parent node
return lastCommon(first,second);
}
/**
* Find the path from the root node to goal and store it in path
*/
private void findPath(TreeNode root,TreeNode goal,LinkedList<TreeNode> path) {
// Preorder traversal
if(root == null){
return;
}
path.add(root);
if(root == goal){
return; // Find path
}
if(path.peekLast() != goal) {
findPath(root.left,goal,path);
}
if(path.peekLast() != goal) {
findPath(root.right,goal,path);
}
if(path.peekLast() != goal) {
path.removeLast();
}
}
/**
* Find the node with equal path1 and path2, which is the public parent node
*/
private TreeNode lastCommon(LinkedList<TreeNode> path1,LinkedList<TreeNode> path2) {
TreeNode result=null;
int n=Math.min(path1.size(),path2.size());
for(int i=0;i<n;i++){
if(path1.get(i) == path2.get(i)) {
result=path1.get(i);
}
}
return result;
}
}
Answer 2: refer to the official solution. Running time 6 ms, memory consumption 40 MB
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
// If root is equal to p or q, return root; If root is null, null is returned
if(root == null || root == p || root == q) {
return root;
}
// Recursive left and right subtrees. If there is a node to look for, return
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
// If left=null, the target nodes are in the right subtree
if(left == null) {
return right;
}
// If right=null, the target nodes are in the left subtree
if(right == null) {
return left;
}
// If neither left nor right is null, the target node is the current root node.
return root;
}
}