catalogue
Code part
Question 9
Give you an integer X. if x is a palindrome integer, return true; Otherwise, false is returned.
Palindromes are integers that are read in the same positive order (from left to right) and reverse order (from right to left). For example, 121 is palindrome, not 123.
Source: LeetCode
Link: https://leetcode-cn.com/problems/palindrome-number
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Code modified with reference to comments:
class Solution {
public boolean isPalindrome(int x) {
if (x < 0) return false;
else if (x == 0) return true;
else
{
int xorigion = x;
int X = 0;
while (x != 0)
{
X = X * 10 + x % 10;
x = x / 10;
}
if(X == xorigion) return true;
else return false;
}
}
}First, judge the special situation. For the rest, the number of palindromes is obtained through a while loop. Finally, judge return.
Question 13
Roman numerals contain the following seven characters: I, V, X, L, C, D, M.
Character = numeric value
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
For example, the Roman numeral 2 is written as {II, which is two parallel ones. 12 is written as ， XII, which is ， X + II. 27 is written as ， XXVII, which is ， XX + V + II.
Usually, the small Roman numerals are to the right of the large ones. However, there are also special cases. For example, 4 is not written as ＾ IIII, but ＾ IV. The number 1 is on the left of the number 5, and the number represented is equal to the value 4 obtained by subtracting the decimal 1 from the large number 5. Similarly, the number 9 is represented as {IX. This special rule applies only to 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 on the left of ＾ D (500) and ＾ M (1000) to represent ＾ 400 and ＾ 900.
Given a Roman numeral, convert it to an integer.
Source: LeetCode
Link: https://leetcode-cn.com/problems/roman-to-integer
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Your own code is a little long, but the time is 100% and the memory is 95%:
class Solution {
public int romanToInt(String s) {
char [] S = s.toCharArray();
int res = 0;
for(int i = 0 ; i < S.length ; i ++)
{
if((i+1)< S.length)
{
if(S[i] == 'I')
{
if(S[i+1] != 'V' && S[i+1] != 'X')
{
res += 1;
}
else if(S[i+1] == 'V')
{
res += 4;
i ++;
}
else if(S[i+1] == 'X')
{
res += 9;
i ++;
}
}
else if(S[i] == 'X')
{
if(S[i+1] != 'L' && S[i+1] != 'C')
{
res += 10;
}
else if(S[i+1] == 'L')
{
res += 40;
i ++;
}
else if(S[i+1] == 'C')
{
res += 90;
i ++;
}
}
else if(S[i] == 'C')
{
if(S[i+1] != 'D' && S[i+1] != 'M')
{
res += 100;
}
else if(S[i+1] == 'D')
{
res += 400;
i ++;
}
else if(S[i+1] == 'M')
{
res += 900;
i ++;
}
}
else if(S[i] == 'V') res += 5;
else if(S[i] == 'L') res += 50;
else if(S[i] == 'D') res += 500;
else if(S[i] == 'M') res += 1000;
}
else
{
if(S[i] == 'I') res +=1;
else if(S[i] == 'V') res += 5;
else if(S[i] == 'X') res += 10;
else if(S[i] == 'L') res += 50;
else if(S[i] == 'C') res += 100;
else if(S[i] == 'D') res += 500;
else if(S[i] == 'M') res += 1000;
}
}
return res;
}
}Using the idea of compiling principle, first judge two characters in a group (IV, IX, XL, XC, CD, CM), and then judge a single character.
Question 14
Write a function to find the longest common prefix in a string array.
Returns the empty string '' if there is no public prefix.
Violent recursive code after several times of repair:
class Solution {
public String longestCommonPrefix(String[] strs) {
int len = strs.length ;
String res;
if(len == 0) return "";
if(len == 1) return strs[0];
if(strs[0].length() == 0) return "";
char [] string1 , string2 , nextarray;
string1 = strs[0].toCharArray();
string2 = strs[1].toCharArray();
nextarray = new char[200];
for(int i = 0 ; i < 200 ; i++)
{
nextarray[i] = 'A';
}
int i = 0;
while(i < string1.length && i < string2.length && string1[i] == string2[i])
{
nextarray[i] = string1[i];
i ++;
}
String nextstring = new String(nextarray);
String [] tonext = new String[len-1];
tonext[0] = nextstring;
for(int j = 1 ; j < len -1 ; j ++)
{
tonext[j] = strs[j+1];
}
if(len == 2)
{
i = 0;
while(nextarray[i] != 'A') i ++;
nextstring = nextstring.substring(0,i);
return nextstring;
}
res = longestCommonPrefix(tonext);
return res;
}
}Judge the special situation first. Convert the first two strings to an array, declare and initialize the char array nextarray, which is used to store the prefix. Find the longest prefix of the first two strings and store them in the nextarray array. Declare the string nextstring, convert the nextaray array into a string, and store the nextstring string and the remaining strings in the string array tonext.
Judge if there are only two strings, return the current longest prefix.
Recursive.
Question 20
Given a string s that only includes' (',' ',' {','} ',' [','] ', judge whether the string is valid.
Valid strings must meet:
The left parenthesis must be closed with the same type of right parenthesis.
The left parentheses must be closed in the correct order.
Source: LeetCode
Link: https://leetcode-cn.com/problems/valid-parentheses
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Your own code is as follows, which can be solved by using stack:
class Solution {
public boolean isValid(String s) {
char[] S = s.toCharArray();
Stack<Character> stack = new Stack<Character>();
for(int i = 0 ; i < S.length ; i++)
{
if(S[i] == '(') stack.push(')');
else if(S[i] == '[') stack.push(']');
else if(S[i] == '{') stack.push('}');
else
{
if(stack.isEmpty() == true) return false;
else if(S[i] != stack.pop()) return false;
}
}
if(stack.isEmpty()) return true;
else return false;
}
}For each front bracket ((, [, {), put the other half of its corresponding bracket into the stack, so as to reduce the number of judgments during out of stack comparison.
Question 4
Given two positively ordered (from small to large) arrays of m and n, respectively, * nums1 and * nums2. Please find and return the median of these two positive arrays.
The time complexity of the algorithm should be O(log (m+n)).
Source: LeetCode
Link: https://leetcode-cn.com/problems/median-of-two-sorted-arrays
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Their own code is as follows. It is too long and there is much room for improvement:
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int len1 , len2;
len1 = nums1.length;
len2 = nums2.length;
int flag1 = (len1+len2)/2;;
int med1 = 0 , med2 = 0;
double med11 ,med22 , med = 0;
if(len1 == 0 && len2 ==0) return med;
if((len1+len2)%2 == 0) //even numbers
{
int i1 = 0 , i2 = 0;
for(int i = flag1 ; i >= 0 ; i--)
{
if(i != 0)
{
if(i1 == len1)
{
med1 = nums2[i2];
i2 ++;
}
else if(i2 == len2)
{
med1 = nums1[i1];
i1 ++;
}
else if(nums1[i1] > nums2[i2])
{
med1 = nums2[i2];
i2 ++;
}
else if(nums1[i1] <= nums2[i2])
{
med1 = nums1[i1];
i1 ++;
}
}
else if(i == 0)
{
if(i1 == len1)
{
med2 = nums2[i2];
i2 ++;
}
else if(i2 == len2)
{
med2 = nums1[i1];
i1 ++;
}
else if(nums1[i1] > nums2[i2])
{
med2 = nums2[i2];
i2 ++;
}
else if(nums1[i1] <= nums2[i2])
{
med2 = nums1[i1];
i1 ++;
}
}
}
med11 = (double)med1;
med22 = (double)med2;
med = (med11 + med22) / 2;
}
else //Odd number
{
int i1 = 0 , i2 = 0;
for(int i = flag1 ; i >= 0 ; i--)
{
if(i1 == len1)
{
med = nums2[i2];
i2 ++;
}
else if(i2 == len2)
{
med = nums1[i1];
i1 ++;
}
else if(nums1[i1] > nums2[i2])
{
med = nums2[i2];
i2 ++;
}
else if(nums1[i1] <= nums2[i2])
{
med = nums1[i1];
i1 ++;
}
}
}
return med;
}
}Judge the special situation first. Judge whether the sum of the lengths of the two arrays is even or odd, and operate separately. Even numbers need to take the middle two numbers to get the average value, and odd numbers need to take the middle one, that is, even numbers need to be taken
Small numbers and
Small numbers, and odd numbers need to be takenSmall numbers. Get the number through the for loop. In the loop, you need to first judge the cross-border situation.
Question 21
Merge the two ascending linked lists into a new} ascending linked list and return. The new linked list is composed of all nodes of a given two linked lists.
Own code:
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
if(list1 == null){return list2;}
if(list2 == null){return list1;}
ListNode root = new ListNode();
ListNode res = root;
while(list1 != null && list2 != null)
{
if(list1.val <= list2.val)
{
res.next = list1;
res = res.next;
list1 = list1.next;
}
else
{
res.next = list2;
res = res.next;
list2 = list2.next;
}
}
if(list1 == null && list2 != null)
{
res.next = list2;
}
else if(list2 == null && list1 != null)
{
res.next = list1;
}
return root.next;
}
}Judge the special situation first. Judge the val value of the original linked list and connect the smaller node to the target linked list. If one is used up, connect the other directly.
Question 15
Give you an array of n integers ， nums ， judge whether there are three elements a, b and c in ， so that ， a + b + c = 0? Please find all triples with sum 0 and no repetition.
Note: the answer cannot contain duplicate triples.
Source: LeetCode
Link: https://leetcode-cn.com/problems/3sum
The copyright belongs to Lingkou network. For commercial reprint, please contact the official authorization, and for non-commercial reprint, please indicate the source.
Refer to the modified code:
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();
int len = nums.length;
int a , b , c , j , k;
if(len < 3) {return res;}
if(len == 3 && nums[0]+nums[1]+nums[2] != 0) {return res;}
if(len == 3 && nums[0]+nums[1]+nums[2] == 0)
{
res.add(Arrays.asList(nums[0],nums[1],nums[2]));
return res;
}
Arrays.sort(nums);
for(int i = 0 ; i < len ; i++)
{
if(nums[i] > 0) {return res;}
if(i > 0 && nums[i] == nums[i-1]) {continue;}
a = nums[i];
j = i + 1;
k = len -1;
while(j < k)
{
b = nums[j];
c = nums[k];
if(a + b + c == 0)
{
res.add(Arrays.asList(a,b,c));
j ++;
k --;
while(j < k && j > i + 1 && nums[j] == nums[j-1]) {j ++;}
while(j < k && k < len -1 && nums[k] == nums[k+1]) {k --;}
}
else if(a + b + c > 0) {k--;}
else if(a + b + c < 0) {j++;}
}
}
return res;
}
}Judge the special situation first. Sort the array first. Use the for loop to traverse nums[i] in order to judge the special case. Use j and k to locate the array part after I and point to the beginning and end of this part respectively. Use the while loop to ensure that j always precedes k. Judge whether the sum of the three is equal to 0, and adjust the position of j and k according to the relationship with 0.
Add judgment to prevent repeated fetching.
java small knowledge part
Question 9
If there are special circumstances, judge it first.
Question 13
For arrays and linked lists, we should judge whether they are out of bounds.
+ =, - = is an operator, and no space is allowed in the middle.
Question 14
The array length is Length, the length of the string is length().
For string truncation:
nextstring = nextstring.substring(0,i);
Question 20
Various operations of stack:
Stack<Character> stack = new Stack<Character>(); //Stack declaration
stack.push(')'); //Push
stack.isEmpty() //Out of stack
stack.pop() //Judge stack emptyQuestion 4
In if judgment, judge the cross-border situation first, and then judge other situations.
Question 15
The data type is List, which means that List is composed of List, and the inner List is composed of int.
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList<>();How to add new data:
res.add(Arrays.asList(nums[0],nums[1],nums[2]));
Sorting method:
Arrays.sort(nums);