1,LeetCode 344. Reverse string
subject
Write a function that inverts the input string. The input string is given in the form of character array char [].
Do not allocate additional space to another array. You must modify the input array in place and use the additional space of O(1) to solve this problem.
You can assume that all characters in the array are printable characters in the ASCII code table.
Xiaobian vegetable solution
public static void reverseString(char[] s) {
int n = s.length;
int middle = 0;
if (n%2 != 0){
//If it is an odd number, the 0 and N-1 exchanges, the 1 and n-2 exchanges until (n-1)/2-1
middle = (n-1)/2;
}else{
//If it is an even number, the 0 and n-1 exchanges, the 1 and n-2 exchanges, and all the way to n/2-1
middle = n/2;
}
int left = 0;
while (left < middle){
char temp = s[left];
s[left] = s[n-1-left];
s[n-1-left] = temp;
left++;
}
}
It's more and more handy. I have to brush it.
The boss points out the country
public static void reverseString(char[] s) {
int n = s.length;
for (int left = 0,right = n-1;left<right;left++,right--){
char temp = s[left];
s[left] = s[right];
s[right] = temp;
}
}
2,LeetCode 345. Inverts the vowels in a string
subject
Give you a string s, only invert all vowels in the string, and return the result string.
Vowels include 'a', 'e', 'i', 'o' and 'u' and may appear in both upper and lower case.
Xiaobian vegetable solution
public static String reverseVowels(String s) {
List<Character> list = new ArrayList<Character>() {{
add('a');
add('e');
add('i');
add('o');
add('u');
}};
char[] chars = s.toCharArray();
int lg = s.length();
int right = s.length();
//Traverse the first half of the string. If it is a vowel, find the last vowel in the right half, and then exchange.
//If not, it will not be processed.
for (int left = 0; left < lg / 2; left++) {
char e = 0;
if (list.contains(chars[left])) {
//Look for the last vowel in the right half
for (int j = right - 1; j >= 0; j--) {
e = chars[j];
if (list.contains(e)) {
right = j;
break;
}
}
//Swap leftmost and rightmost vowels
char temp = chars[left];
chars[left] = e;
chars[right] = temp;
}
}
return new String(chars);
}
It feels a little troublesome.
Improved version of small cooking solution
public static String reverseVowels(String s) {
String const_A_U = "aeiouAEIOU";
char[] chars = s.toCharArray();
int lg = s.length();
int right = s.length();
//Traverse the first half of the string. If it is a vowel, find the last vowel in the right half, and then exchange.
//If not, it will not be processed.
for (int left = 0; left < lg / 2; left++) {
char e = 0;
if (const_A_U.indexOf(chars[left])>=0) {
//Look for the last vowel in the right half
for (int j = right - 1; j >= 0; j--) {
e = chars[j];
if (const_A_U.indexOf(e)>=0) {
right = j;
break;
}
}
//Swap leftmost and rightmost vowels
char temp = chars[left];
chars[left] = e;
chars[right] = temp;
}
}
return new String(chars);
}
Although it's a little troublesome, it's good to have a clear idea. I feel I can submit it, but the prompt is wrong. Why?
The boss points out the country
public static String reverseVowels(String s) {
String const_AE = "aeiouAEIOU";
char[] chars = s.toCharArray();
int lg = s.length();
int left = 0;
int right = lg - 1;
//Traverse the first half of the string. If it is a vowel, find the last vowel in the right half, and then exchange.
//If not, it will not be processed.
while (left < right) {
//If it's not a vowel
while (left < lg && const_AE.indexOf(chars[left]) < 0) {
++left;
}
//If it's not a vowel
while (right > 0 && const_AE.indexOf(chars[right]) < 0) {
--right;
}
if (left < right) {
char temp = chars[left];
chars[left] = chars[right];
chars[right] = temp;
++left;
--right;
}
}
return new String(chars);
}
The boss's idea is the same as mine, but using double pointers to operate is obviously more intuitive and concise than my first half and second half.
3,LeetCode 349. Intersection of two arrays
subject
Given two arrays, write a function to calculate their intersection.
Xiaobian vegetable solution
public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
for (int j = 0; j < nums2.length; j++) {
if (nums1[i] == nums2[j]){
set.add(nums1[i]);
}
}
}
int[] arr = new int[set.size()];
int i = 0;
for (int s : set) {
arr[i] = s;
i++;
}
return arr;
}
Although the problem was solved and the submission was successful, I always felt that the dishes were heinous and not very satisfied.
The time complexity of small cooking solution is O(mn), that is, the traditional violent algorithm, which is not recommended.
Idea and algorithm
If you use a hash set to store elements, you can judge whether an element is in the set in the time of O(1)O(1), so as to reduce the time complexity.
First, use two sets to store the elements in two arrays respectively, and then traverse the smaller set to determine whether each element is in another set. If the element is also in another set, add the element to the return value. The time complexity of this method can be reduced to O(m+n)O(m+n).
The boss points out the country
public static int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set1 = new HashSet<>();
Set<Integer> set2 = new HashSet<>();
for (int i = 0; i < nums1.length; i++) {
set1.add(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
set2.add(nums2[i]);
}
return getIntersection(set1, set2);
}
public static int[] getIntersection(Set<Integer> set1, Set<Integer> set2) {
if (set1.size()>set2.size()){
return getIntersection(set2,set1);
}
Set<Integer> set = new HashSet<>();
for (Integer x : set1){
if (set2.contains(x)){
set.add(x);
}
}
int[] ret = new int[set.size()];
int i = 0;
for (Integer x : set){
ret[i++] = x;
}
return ret;
}
The code seems more cumbersome, but it is important to avoid multiple for loops.
The time complexity is different, and the execution time is significantly improved.
