374. Guess Number Higher or Lower

This question is also a Binary Search question.We can notice one thing.1 <= pick <= n.So this question is search 1 between n.We can search their mid number.If is less than the target just need to update the head.If is bigger than the target just need to update the tail.

Solution

public int guessNumber(int n) {
    int head = 1, tail = n;
    while (head < tail) {
      int mid = head + (tail - head) / 2;
      //mid > n
      if (guess(mid) == -1) {
        tail = mid - 1;
      } else if (guess(mid) == 1) {
        //mid < n
        head = mid + 1;
      } else {
        //find the target
        return mid;
      }
    }
    //while head==tail
    return head;
  }

383. Ransom Note

This question is a little similar to 349. Intersection of Two Arrays We can also use HashMap. The number of occurrences of each letter corresponds to a value.And find all the letters that appear in the first string.

Solution1

public boolean canConstruct(String ransomNote, String magazine) {
    HashMap<Integer, Integer> hashMap = new HashMap<>();
    for (int i = 0; i < magazine.length(); i++) {
      int value = magazine.charAt(i) - 'a';
      //if is the first time appear,just set initial value
      if (!hashMap.containsKey(value)) {
        hashMap.put(value, 1);
      } else {
        //calculate the number of occurrences
        hashMap.put(value, hashMap.get(value) + 1);
      }
    }
    for (int i = 0; i < ransomNote.length(); i++) {
      int value = ransomNote.charAt(i) - 'a';
      //if don't include this letter,just return false
      if (!hashMap.containsKey(value)) {
        return false;
      } else {
        //the number of occurrences is less than the number of times needed
        if (hashMap.get(value) - 1 < 0) {
          return false;
        } else {
          hashMap.put(value, hashMap.get(value) - 1);
        }
      }
    }
    return true;
  }

But the efficiency of HashMap is not high,we can notice consist of lowercase English letters So we can use array to store the number of occurrences.This solution is simplified.But the core solution idea has not changed.

Solution2

public boolean canConstruct(String ransomNote, String magazine) {
    //26 letters
    int[] result = new int[26];
    for (int i = 0; i < magazine.length(); i++) {
      result[magazine.charAt(i) - 'a']++;
    }
    for (int i = 0; i < ransomNote.length(); i++) {
      if (result[ransomNote.charAt(i) - 'a'] == 0) {
        return false;
      } else {
        result[ransomNote.charAt(i) - 'a']--;
      }
    }
    return true;
  }

387. First Unique Character in a String

This question is very similar to 383. Ransom Note.If you understand that question,you can also solve this question easily.We can also use HashMap or ASCII to solve it.

Solution1

public int firstUniqChar(String s) {
    HashMap<Character, Integer> hashMap = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
      //count the number of occurrences
      hashMap.put(s.charAt(i), hashMap.getOrDefault(s.charAt(i), 0) + 1);
    }
    for (int i = 0; i < s.length(); i++) {
      //if the number is 1,just return the location of the letter
      if (hashMap.get(s.charAt(i)) == 1) {
        return i;
      }
    }
    return -1;
  }

Solution2

public int firstUniqChar(String s) {
    int[] result = new int[26];
    for (int i = 0; i < s.length(); i++) {
      //use ASCII table to judge the letter
      result[s.charAt(i) - 'a']++;
    }
    for (int i = 0; i < s.length(); i++) {
      //if the letter's occurrences is 1,just return the location of the letter
      if (result[s.charAt(i) - 'a'] == 1) {
        return i;
      }
    }
    return -1;
  }

389. Find the Difference

This question is similar to 136. Single Number.We can just traverse the string once.The main idea is XOR or use ASCII.We can set a value to store the difference between each of their elements.It is seems like commutative law of addition.Add the last element of T in the end.

Solution1

public char findTheDifference(String s, String t) {
    int result = 0;
    for (int i = 0; i < s.length(); i++) {
      //char - char the result is int
      result += t.charAt(i) - s.charAt(i);
    }
    //use ASCII table to get the letter
    return (char) (result + t.charAt(t.length() - 1));
  }

Solution2

public char findTheDifference(String s, String t) {
    int result = 0;
    for (int i = 0; i < s.length(); i++) {
      //use XOR,just like question 136
      result ^= s.charAt(i);
      result ^= t.charAt(i);
    }
    return (char) (result ^ t.charAt(t.length() - 1));
  }

392. Is Subsequence

This question is also a double pointer question.We can search from the head of s and t.If there are equal,just continue.

Solution

public boolean isSubsequence(String s, String t) {
    int i = 0, j = 0;
    while (i < s.length() && j < t.length()) {
      //if there are equal,just update the i
      if (s.charAt(i) == t.charAt(j)) {
        i++;
      }
      //j must update each time
      j++;
    }
    //verify that the value of i is equal to the length of s
    return i == s.length();
  }

401. Binary Watch

This question is not a easy question.When i thought about it for the first time,i have no idea.But i gradually discovered that this is an enumeration problem.We can use two HashMap to store hour and minute values separately.Then pair with the other party and verify that it meets the specifications.

Solution1

public List<String> readBinaryWatch(int turnedOn) {
    //make two HashMap to store hour and minutes values separately
    HashMap<Integer, List<String>> hashHour = new HashMap<>();
    HashMap<Integer, List<String>> hashMins = new HashMap<>();
    //such as hour : 1,2,4,8 only have one 1
    for (int i = 0; i < 12; i++) {
      int hours = numberOf1(i);
      hashHour.putIfAbsent(hours, new ArrayList<String>());
      hashHour.get(hours).add(i + "");
    }
    //count the minute,get the number of 1
    for (int i = 0; i < 60; i++) {
      int mins = numberOf1(i);
      hashMins.putIfAbsent(mins, new ArrayList<String>());
      //if the minute is 01,02,04,08
      if (i < 10) {
        hashMins.get(mins).add("0" + i);
      } else {
        hashMins.get(mins).add(i + "");
      }
    }
    ArrayList<String> result = new ArrayList<>();
    //if the hour's number of 1 is n,so minute's number of 1 is m-n
    for (int i = 0; i <= turnedOn; i++) {
      //non-existent situation,just continue
      if (!hashHour.containsKey(i) || !hashMins.containsKey(turnedOn - i)) {
        continue;
      }
      //enumeration method,paired with each other
      for (String s : hashHour.get(i)) {
        for (String s1 : hashMins.get(turnedOn - i)) {
          result.add(s + ":" + s1);
        }
      }
    }
    return result;
  }

  /**
   * count the number of 1 in binary
   */
  private int numberOf1(int num) {
    int count = 0;
    while (num != 0) {
      ++count;
      num &= (num - 1);
    }
    return count;
  }

But this question can also be enumerated directly without storing the result of enumeration.The idea of solving the problem as a whole is still the same.

Solution2

public List<String> readBinaryWatch(int turnedOn) {
    ArrayList<String> strings = new ArrayList<>();
    //hour
    for (int i = 0; i < 12; i++) {
      //minute
      for (int j = 0; j < 60; j++) {
        //if n + m = turnedOn
        if (numberOf1(i) + numberOf1(j) == turnedOn) {
          //judge the minute
          strings.add(i + ":" + ((j < 10) ? "0" + j : j));
        }
      }
    }
    return strings;
  }

  /**
   * count the number of 1 in binary
   */
  private int numberOf1(int num) {
    int count = 0;
    while (num != 0) {
      ++count;
      num &= (num - 1);
    }
    return count;
  }
Last modification:October 20th, 2021 at 10:29 am