代码随想录算法训练营第五天｜242-349-202-1

LeetCode 242. 有效的字母异位词

Ver1:

public boolean isAnagram(String s, String t) {

        // new two arrays to count the number of each character in each string
        int[] sChars = new int[123];
        int[] tChars = new int[123];

        // full scan two strings and count
        for (int i = 0; i < s.toCharArray().length; i++) {
            sChars[s.charAt(i)]++;
        }

        for (int j = 0; j < t.toCharArray().length; j++) {
            tChars[t.charAt(j)]++;
        }

        // return if these two counter arrays are equal
        return Arrays.equals(sChars, tChars);
    }

Ver2:

public boolean isAnagram(String s, String t) {

      // better check the length of each string first
      if(s.length() != t.length()) {
          return false;
      }

      // better space usage
      int[] alphabet = new int[123];

      for (int i = 0; i < s.toCharArray().length; i++) {
          alphabet[s.charAt(i)]++;
          alphabet[t.charAt(i)]--;
      }

      return Arrays.equals(alphabet, new int[123]);
  	}

Ver3:

   public boolean isAnagram(String s, String t) {

   if(s.length() != t.length()) {
       return false;
   }

   //better space usage
   int[] alphabet = new int[26];

   for (int i = 0; i < s.length(); i++) {
       alphabet[s.charAt(i) - 'a']++;
       alphabet[t.charAt(i) - 'a']--;
   }

   for (int i = 0; i < alphabet.length; i++) {
       if (alphabet[i] != 0) {
           return false;
       }
   }
   return true;
}

这道题的难度不高，使用数组充当哈希表，记录每个字符串中各个字符的数量，但是一些小的细节方面的优化值得注意

1. 比如一开始脑子抽风了使用了s.toCharArray().length导致超时
2. 开辟了两个数组用于记录字符数量
3. 没有检查字符串长度
4. 对两个字符串分别遍历

进阶问题:如果字符串包含unicode字符怎么办？

可以使用hashmap，以字符为key，字符的数量为value，思路一致

LeetCode 349. 两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        int[] digit1 = new int[1001];
        int[] digit2 = new int[1001];
      
				// full scan each array and records the number
        for (int i = 0; i < nums1.length; i++) {
            digit1[nums1[i]]++;
        }

        for (int i = 0; i < nums2.length; i++) {
            digit2[nums2[i]]++;
        }
        
      	// if a number exists in both array then record it
        LinkedList<Integer> ans = new LinkedList<>();
        for (int i = 0; i < digit1.length; i++) {
            if(digit1[i] > 0 && digit2[i] > 0) {
                ans.add(i);
            }
        }
				
      	// change the list to an array
        int[] array = new int[ans.size()];
        for(int i = 0; i < ans.size(); i++) array[i] = ans.get(i);

        return array;
    }
}

因为本题限制了数组中包含的数字的范围，所以可以使用开两个数组的方法作为哈希表，如果数字范围更大一些，则应该考虑使用set。

LeetCode 202. 快乐数

class Solution {
    public boolean isHappy(int n) {

        HashSet<Integer> seen = new HashSet<>();

        while ( n != 1 && !seen.contains(n)) {
            seen.add(n);
            n = getNextNumber(n);
        }

        return n == 1;

    }

    private int getNextNumber (int n) {

        int res = 0;

        while ( n > 0) {
            int temp = n % 10;
            res += temp * temp;
            n /= 10;
        }

        return res;
    }
}

这道题还是蛮有意思的，一开始没有想明白结束循环的条件，后来才意识到，无限循环意味着重复出现的n，如此，将其加入set，利用set查询时间复杂度为O(1)的优势进行快速查询，如果数字已经check过，那么结束循环，或者数字为1，结束循环。

LeetCode 1.两数之和

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap <Integer, Integer> visited = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            if(visited.containsKey(target - nums[i])) {
                return new int[] {i, visited.get(target - nums[i])};
            }else {
                visited.put(nums[i], i);
            }
        }

        return null;
    }
}

两数之和用暴力法解决思路还是挺直接的，但是暴力法的复杂度太高了。双重遍历的复杂度为n^2，其原因是，对于每一个正在check的数字，搜寻target-nums[i]的开销太大，考虑使用set将已经check过的数字cache起来，并利用其查询O(1)的优势。