303. Range Sum Query - Immutable
This question is a very clever question.It requires us to reduce the time required for calculation.We need to pay attention to two points.
- At most
10^4calls will be made tosumRange. 1 <= nums.length <= 10^4
We know use sum to count the result.But if left=0 and right=nums.length-1,the time is n,and the number of calculations is n.So the time is $n^2$.It is easy to time to.But it does not prevent us from writing this kind of code.
Solution1
class NumArray1 {
int[] array;
public NumArray1(int[] nums) {
array = nums;
}
public int sumRange(int left, int right) {
int result = 0;
for (int i = left; i <= right; i++) {
result += array[i];
}
return result;
}
}But let's think about it carefully.Why we spend a lot of time,because we spend a lot of time on count the result.Can we spend time on make the array?Because it is only used once.
So i came up with designing an array.It's elements store the sum of the previous elements of nums.We can get the difference between the left and right range by subtracting its elements.
Solution2
class NumArray2 {
int[] array;
public NumArray2(int[] nums) {
int n = nums.length + 1;
array = new int[n];
//array[i+1] is the previous elements of nums[0] to nums[i]
for (int i = 0; i < nums.length; i++) {
array[i + 1] = array[i] + nums[i];
}
}
public int sumRange(int left, int right) {
//array[right+1]=nums[0]+...+nums[right] array[left+1]=nums[0]+...+nums[left]
//array[right+1]-array[left+1]=nums[right]-...-nums[left]
return array[right + 1] - array[left];
}
}326. Power of Three
This question is the same as question 231. Power of Two.It also has two solutions.The first solution is universal solution to judge whether is a remainder.
Solution1
public boolean isPowerOfThree(int n) {
if (n <= 0) {
return false;
}
while (n > 1) {
if (n % 3 == 0) {
n /= 3;
} else {
return false;
}
}
return true;
}The second solution is a very clever solution.We know that n is in the range of int.So the largest power of 3 in int is 1162261467.We can directly judge whether this number is a divisor of 1162261467
Solution2
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}338. Counting Bits
This is a very interesting problem.We have two solutions.But their core idea are all bit operation.First,let us consider how to calculate the number of 1 in a binary number.
We can use & operation.
public static int bitCount(int n){
int count = 0;
while(n != 0){
n = n & (n - 1);
count++;
}
return count;
}So we can traverse the n,get each number of 1.But this solution time is $O(nlogn)$,space is $O(1)$
Solution1
public int[] countBits(int n) {
//make the result array
int[] result = new int[n + 1];
//result[0] default is 0
for (int i = 1; i <= n; i++) {
//record the current number
int j = i;
//calculate the number of 1
int a = i;
int count = 0;
while (a != 0) {
a = a & (a - 1);
count++;
}
//record into array
result[j] = count;
}
return result;
}Let's think about why the time is $O(nlogn)$.Because we have to recalculate the 1 in each number.How can we avoid this situation?We know power of two only have 1 1.
- 1=1
- 2=1
- 3=2
- 4=1
- 5=2
- 6=2
- 7=3
- 8=1
How can we judge whether the number is power of two?You must know the question 231. Power of Two.
- if
(i&(i-1))==0.So this number is power of two.The number of1is 1.And let this numberbit=1 result[i]=result[i-bit]+1
So this solution time has became $O(n)$
Solution2
public int[] countBits(int n) {
int[] result = new int[n + 1];
int bit = 0;
for (int i = 1; i <= n; i++) {
//judge the number whether is power of two
if ((i & (i - 1)) == 0) {
bit = i;
}
//the main code
result[i] = result[i - bit] + 1;
}
return result;
}342. Power of Four
This question is a very easy question.It has a same solution with 326. Power of Three.You can read it in my Blog.
Solution1
public boolean isPowerOfFour(int n) {
if (n <= 0) {
return false;
}
while (n > 1) {
if (n % 4 == 0) {
n /= 4;
} else {
return false;
}
}
return true;
}But this question is very similar with question 231. Power of Two.You can read my Blog LeetCode EasyTopic Notes7.
As we all know 4 is the power of 2.So if it is a power of 2,it must be a power of 4.But how about number 8.It isn't the power of 4 but it is the power of 2.
- $4\div3=1...1$
If there is a number is power of 2 and not the power of 4,just like 8.It can be written by $n=4^x\times2$
- $8=4\times2$
- $8\div3=(4\div3)\times2=2...2$
So the remainder of this number divided by 3 must be 2 instead of 1
Solution2
public boolean isPowerOfFour(int n) {
return n > 0 && (n & (n - 1)) == 0 && n % 3 == 1;
}344. Reverse String
This is a very easy question.We just need use two pointers can solve it.
Solution
public void reverseString(char[] s) {
int head = 0, tail = s.length - 1;
//swap the head and the tail,until they are meeting
while (head <= tail) {
char temp = s[head];
s[head] = s[tail];
s[tail] = temp;
head++;
tail--;
}
}345. Reverse Vowels of a String
This is an upgraded version of 344. Reverse String.If you want to solve this question,you must understand that question.This question the main idea is determine whether a letter is a vowel.And we must notice a situation.,.If we still move two pointers.There will be a cross-border situation.
Solution
public String reverseVowels(String s) {
int head = 0, tail = s.length() - 1;
//we can change the string,so we change it into a char array
char[] array = s.toCharArray();
//use two pointer
while (head < tail) {
//make this judgement head < tail is to avoid ",." cross-border situation
while (head < tail && vowele(array[head])) {
head++;
}
while (head < tail && vowele(array[tail])) {
tail--;
}
if (head >= tail) {
break;
}
//swap the two pointers
char swap = array[head];
array[head] = array[tail];
array[tail] = swap;
head++;
tail--;
}
return new String(array);
}
/**
* determine whether a letter is a vowel
*/
private boolean vowele(char ch) {
return !(ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u' || ch == 'A' || ch == 'E'
|| ch == 'I' || ch == 'O' || ch == 'U');
}349. Intersection of Two Arrays
This question is a easy question,We can use two solutions to solve it.The first thing that comes to mind must be HashSet.We can use two HashSet to store each elements.
Solution1
public int[] intersection(int[] nums1, int[] nums2) {
HashSet<Integer> hashSet1 = new HashSet<>();
HashSet<Integer> hashSet2 = new HashSet<>();
//add elements into hashSet1
for (int i : nums1) {
hashSet1.add(i);
}
for (int i : nums2) {
//exclude elements not included
if (hashSet1.contains(i)) {
hashSet2.add(i);
}
}
int[] result = new int[hashSet2.size()];
int index = 0;
//take all elements in hashSet2 into array
for (Integer integer : hashSet2) {
result[index++] = integer;
}
return result;
}The second solution we can use sort.So the two nums will change.
- 1 1 2 2
- 2 2
If the current element is the same as another element,and not the same as the previous element in the answer array.So is the new element.If one party is smaller than the other,update the data.
Solution2
public int[] intersection(int[] nums1, int[] nums2) {
//sort the two nums
Arrays.sort(nums1);
Arrays.sort(nums2);
//because the result length must be less than or equal to the nums2 or nums1
int index1 = 0, index2 = 0, n = 0;
while (index1 < nums1.length && index2 < nums2.length) {
//if are equal
if (nums1[index1] == nums2[index2]) {
//and not the same as the previous element,just updata
if (n == 0 || nums1[index1] != nums2[n - 1]) {
nums2[n++] = nums1[index1];
}
index1++;
index2++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
index1++;
}
}
//copy the same length of result
return Arrays.copyOfRange(nums2, 0, n);
}350. Intersection of Two Arrays II
This question is the update version of question 349. Intersection of Two Arrays.But it is also a easy problem.This question the best solution i think is use HashMap.As we all know HashMap has <Key,Value>.A element can be regarded as a key.The number of times it appears is the value.When it appears in another array,we just need --.Make its value greater than 0,we can get the minimum number of occurrences.
Solution
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> hashMap1 = new HashMap<>();
for (int i : nums1) {
//if is the first time appear,just give a default value of 1
if (!hashMap1.containsKey(i)) {
hashMap1.put(i, 1);
} else {
//plus the value 1
hashMap1.put(i, hashMap1.get(i) + 1);
}
}
//length of calculation result
int n = 0;
for (int i : nums2) {
//if have the same key,and value > 0,just add into the result array
if (hashMap1.containsKey(i) && hashMap1.get(i) > 0) {
nums2[n++] = i;
hashMap1.put(i, hashMap1.get(i) - 1);
}
}
return Arrays.copyOfRange(nums2, 0, n);
}367. Valid Perfect Square
This question is also a Binary Search question.But one thing it needs to pay attention to is that it may cross the boundary.If an out-of-bounds occurs,the wrong answer will be returned.
Solution
public boolean isPerfectSquare(int num) {
//1 is true
if (num == 1) {
return true;
}
//use long to store the calculation result
long head = 2, tail = num;
while (head <= tail) {
long mid = head + (tail - head) / 2;
if (mid * mid > num) {
tail = mid - 1;
} else if (mid * mid < num) {
head = mid + 1;
} else {
return true;
}
}
return false;
}