This morning, I suddenly wanted to brush up on the problem on LeetCode, and here it is… So this is a plain brush notes.
Of course, I am prepared to first liver simple questions, here is just my own writing some knowledge missing record and tips!
Don’t say much, bring it to you ~
The first question
The sum of two Numbers
The subject content
Given an integer array nums and an integer target, find the two integers in the array whose sum is target and return their array indices.
You can assume that there is only one answer for each input. However, the same element in the array must not appear repeatedly in the answer.
You can return the answers in any order.
Here are two functions that will be used
-
The containsKey method of map
1. Map is a set of key and value pairs.
2. The containsKey (key) method in the map is to check whether the key exists in the map. Return true if it exists, false otherwise.
3. Examples:
Determine if there is a 1 in the array, and if so, return the 1 and its location
public class twoSum{ public static int[] num(int[] nums){ Map<Integer,Integer> map = new HashMap<>(); for(int i=0; i<nums.length; i++){ if(map.containsKey(1)){ return new int[] {map.get(i),i}; } map.put(nums[i],i); } return nums; } public static void main(String[] args){ int a[] = new int[2]; a[0]=1; a[1]= 2; int b[] = num(a); for(int i = 0; i<2; i++){ System.out.println(b[i]); }}}Copy the code-
The put method of map
When we call put, we first determine if the hashMap array is an empty array,
(1) If the value is null, perform initialization and check whether the value of key is null.
(2) If null, store the corresponding value in the array at subscript 0,
(3) Calculate the hash value of the key and calculate the subscript.
(4) Traverse the linked list corresponding to the subscript and match the hash value and key value.
If so, override, returning the old value
If it does not exist, add a new one and return NULL
If the capacity of the elements in the array exceeds the threshold, the expansion will be triggered. The expansion is to put the source array into a temporary array, obtain the length of the old array, multiply the length of the old array by 2 to obtain the length of the new array, and create a new array. Save the data from the temporary array into the expanded array by recalculating the following table.
Answer to the problem solving
(Two solutions are given.)
// class Solution { // public int[] twoSum(int[] nums, int target) { // int temp; // int[] indexs = new int[2]; // Map<Integer , Integer> map = new HashMap<>(); // for(int i = 0; i < nums.length; i++){ // temp = target - nums[i]; // if(map.containsKey(temp)){ // indexs[1] = i; // indexs[0] = map.get(temp); // } // map.put(nums[i],i); // } // return indexs; // } // } class Solution{ public int[] twoSum(int[] nums,int target){ for(int i = 0; i<nums.length; i++){ for(int j = i+1; j<nums.length; j++){ if(target == nums[i] + nums[j]) return new int[] {i,j}; } } return new int[] {}; }}Copy the codeThe second question
Integer inversion
The subject content
Give you a 32-bit signed integer x and return the result of reversing the numeric portion of x.
If the reversed integer exceeds the range of 32 bit signed integers [−231, 231 − 1], 0 is returned.
Assume that the environment does not allow the storage of 64-bit integers (signed or unsigned).
(simple) so directly out of the example:
Enter: x = 123
Output: 321
Result = (result*10 +x % 10)Copy the codeEasy and fast!!
Answer to the problem solving
class Solution { public int reverse(int x) { int result = 0; while(x ! = 0){ int temp = result; result = (result * 10) + (x % 10); x /= 10; if(result / 10 ! = temp){ return 0; } } return result; }}Copy the codeThe third question
palindrome
The subject content
Given an integer x, return true if x is a palindrome; Otherwise, return false.
Palindromes are integers that are read in the same order (from left to right) and in the same order (from right to left). For example, 121 is a palindrome, while 123 is not.
It’s different from integer inversion
The key to this question is to save the data for later comparison
Everything else is similar to the last problem.
Answer to the problem solving
class Solution { public boolean isPalindrome(int x) { if(x < 0){ return false; } int result = 0; int t = x; while( t ! = 0){ //int temp = result; result = result *10 + t % 10; t /= 10; // if(result / 10 ! = temp){ // return false; // } } return result == x; }}Copy the codeThe fourth question
Convert Roman numerals to integers
The subject content
Roman numerals contain the following seven characters: I, V, X, L, C, D and M.
I 1 V 5 X 10 L 50 C 100 D 500 M 1000 The Roman numeral 2 is written II. Let’s write 12 as XII, which is X plus II. 27 write XXVII, XX + V + II.
In Roman numerals, the smaller number is usually placed to the right of the larger number. But there are exceptions. For example, instead of writing IIII for 4, I would write IV. The number 1 is to the left of the number 5, which is equal to the large number 5 and the number 4 is obtained by reducing the number 1. Similarly, the number 9 is represented as IX. This particular rule only applies in the following six cases:
I can be placed to the left of V (5) and X (10) to represent 4 and 9. X can be placed to the left of L (50) and C (100) to represent 40 and 90. C can be placed to the left of D (500) and M (1000) to represent 400 and 900.
Answer to the problem solving
class Solution {
public int romanToInt(String s) {
s = s.replace("IV","a");
s = s.replace("IX","b");
s = s.replace("XL","c");
s = s.replace("XC","d");
s = s.replace("CD","e");
s = s.replace("CM","f");
int sum = 0;
for(int i = 0; i < s.length();i++){
sum += getValue(s.charAt(i));
}
return sum;
}
public int getValue(char c){
switch(c){
case 'I': return 1;
case 'V': return 5;
case 'X': return 10;
case 'L': return 50;
case 'C': return 100;
case 'D': return 500;
case 'M': return 1000;
case 'a': return 4;
case 'b': return 9;
case 'c': return 40;
case 'd': return 90;
case 'e': return 400;
case 'f': return 900;
}
return 0;
}
}
Copy the codeThis is I see a big guy to write, the idea is novel can cow!! Can oneself good good study this kind of train of thought, after accomplish draw inferences from other cases!!
This problem first converts the special Roman character into an integer (for later calculation), and then writes a function that determines the character type and gives the value with the Switch statement to do the math.
The fifth problem
Longest common prefix
The subject content
Write a function to find the longest common prefix in an array of strings.
Returns an empty string “” if no common prefix exists.
So here are the functions that we’re going to use
Str.substring (0, str.length()-1)
- SubString is a method of String in the format:
public String substring(int beginIndex, int endIndex)
Copy the codeReturns a new string that is a substring of the string.
The substring starts at the specified beginIndex and ends at the index endIndex – 1. Therefore, the length of the substring is endIndex-BeginIndex.
The use of the String. IndexOf (STR)
- The indexOf() method returns the first occurrence of a specified string value in the string.
StringObject.indexOf(searchvalue.fromindex)
Copy the codeSearchvalue required. Specifies the string value to be retrieved.
Fromindex This parameter is an integer. Specifies the position in the string where the search begins. Its legitimate 3 values are 0 to negative 1.
Tip:
(1) The indexOf() method is case-sensitive!
(2) If the string value to be retrieved does not appear, the method returns -1.
(3) int indexOf(int ch) returns the indexOf the first occurrence of the specified character in this string.
(4) int indexOf(int ch, int fromIndex)
(5) int indexOf(String STR) returns the indexOf the first occurrence of the specified substring in this String.
(6) int indexOf(String STR, int fromIndex) return the indexOf the first substring in this String.
Answer to the problem solving
class Solution { public String longestCommonPrefix(String[] strs) { if(strs.length == 0){ return ""; } String str = strs[0]; for(int i = 1; i < strs.length; i++){ while(strs[i].indexOf(str)! =0){ str = str.substring(0,str.length()-1); } } return str; }}Copy the codeOk ~ today to write these five questions, although there is also a reference to the big guy’s ideas and code, but the harvest is still full!
LeetCode brush topic link put below!
Keep on refueling duck!
LeetCode is a technology growth platform beloved by geeks around the world (leetcode-cn.com)