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.

  1. At most 10^4 calls will be made to sumRange.
  2. 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=1
  2. 2=1
  3. 3=2
  4. 4=1
  5. 5=2
  6. 6=2
  7. 7=3
  8. 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 of 1 is 1.And let this number bit=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;
  }
Last modification:October 11th, 2021 at 10:13 am