代碼隨想錄算法訓(xùn)練營第六天| 242.有效的字母異位詞 349. 兩個數(shù)組的交集 第202題. 快樂數(shù) 1.兩數(shù)之和

242.有效的字母異位詞

字母是否出現(xiàn)過:哈希法

常犯錯誤 : 包裝類的方法后面都要跟括號 eg : s.length()

? 字符串 s , 不能使用 s[i] , 要使用 s.charAt(i)

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] hash = new int[26];

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

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

        for(int i = 0; i < 26; i++){
            if(hash[i] != 0){
                return false;
            }
        }

        return true;
    }
}

349. 兩個數(shù)組的交集

數(shù)字是否出現(xiàn)過:哈希法

• 嚴(yán)格判空 : nums1 == null 數(shù)組對象不存在 , nums1.length == 0 數(shù)組對象存在但為空

? if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0)

• 聲明語句 : Set set1 = new HashSet<>();

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //HashSet方法
         if(nums1 == null ||nums1 .length == 0 || nums2 == null || nums2.length == 0){
            return new int[0];
         }

         Set<Integer> set1 = new HashSet<>();
         Set<Integer> relset = new HashSet<>();

         for(int i : nums1){
            set1.add(i);
         }

         for(int i : nums2){
            if(set1.contains(i)){
                relset.add(i);
            }
         }

         int[] result = new int[relset.size()];
         int j = 0;
         for(int i : relset){
            result[j++] = i;
         }
         return result;
    }
}

哈希數(shù)組方法

重點 : 如何去重 同時比較兩個數(shù)組某個值是否都大于0

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //數(shù)組方法
        int[] hash1 = new int[1002];
        int[] hash2 = new int[1002];

        for(int i : nums1){
            hash1[i]++;
        }
        for(int i : nums2){
            hash2[i]++;
        }
        
		//去重
        List<Integer> resList = new ArrayList<>();
        for(int i = 0; i < 1002; i++){
            if(hash1[i] > 0 && hash2[i] > 0){
                resList.add(i);
            }
        }

        int index = 0;
        int res[] = new int[resList.size()];
        for(int i : resList)
            res[index++] = i;
        return res;

    }
}

第202題. 快樂數(shù)

是否是循環(huán) : 是否出現(xiàn)過這個數(shù) 哈希法

• 如何取每個數(shù),并平方后累加 :

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

• 循環(huán)條件 : 因為只有兩種可能性 n == 1 或一直循環(huán)

? 我要記錄每個出現(xiàn)過的數(shù), 條件就是 沒出現(xiàn)過 且 不等于 1. 他在while中循環(huán), 他跳出循環(huán)時, 為1則是true, 否則是false

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        while(n != 1 && !record.contains(n)){
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }

    private int getNextNumber(int n){
        int sum = 0;
        while(n > 0){
            int temp = n % 10;
            sum += temp * temp;
            n = n / 10;
        }
        return sum;
    }
}

1.兩數(shù)之和

• 為什么用哈希? 把出現(xiàn)過的值都記錄下來,遍歷時,尋找與之相加為target的數(shù)是否出現(xiàn)過
• 為什么用map? 因為要查找該值是否出現(xiàn)過,且返回其下標(biāo) , 兩個值用map鍵值對
• map的key存什么? 存你要找的是否存在過的值
• map的基本用法:
  • 聲明 : Map<Integer, Integer> map = new HashMap<>();
  • 查找 : map.containsKey(temp)
  • 查找對應(yīng)的value : map.get(temp)
  • 添加 : map.put(nums[i], i)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] res = new int[2];
        if(nums == null || nums.length == 0){
            return res;
        }

        Map<Integer, Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            int temp = target - nums[i];
            if(map.containsKey(temp)){
                res[0] = i;
                res[1] = map.get(temp);
                break;
            }
            map.put(nums[i], i);
        }
        return res;
    }
}