Code Caprice Algorithm Training Camp Day 6 | 242. Valid anagrams, 349. Intersection of two arrays, 202. Happy numbers, 1. Sum of two numbers

242. Effective anagrams

Solution and idea

Because the string is composed of lowercase letters, the total number of lowercase letters is 26, which is limited, so the data can be saved by numerical value. If the length of the string is unknown, you can consider using set,list, etc. to save it. You need to see the question for details. What is it.

Use two for loops to traverse the two strings respectively. The first one adds value to the value through traversal, and the second one does the opposite, subtracting the value. If the last value is 0, it means that the addition and subtraction are offset. The two Strings are anagrams.

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] nums = new int[26];
        for(int i = 0; i < s.length(); i++){
            nums[s.charAt(i) - 'a'] ++;
        }
        for(int i = 0; i < t.length(); i++){
            nums[t.charAt(i) - 'a'] --;
        }
        for(int i = 0; i < nums.length; i++){
            if(nums[i] != 0){
                return false;
            }
        }
        return true;
    }
}

349. Intersection of Two Arrays

Solution and idea

The title requires that each element in the output result must be unique, and the order of the output result is not considered. Set is deduplicated and does not need to sort the data, which is efficient. Therefore, we can use Set to save data through a for loop Save the nums1 data, and then traverse nums2 through the for loop. The contains method of the set itself checks whether the value of nums2 is stored in set1, and if so, saves it in set2, and finally converts it into a value and returns it.

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> set1 = new HashSet<>();
        Set<Integer> set2 = new HashSet<>();
        for(int i = 0; i < nums1.length; i++ ){
            set1.add(nums1[i]);
        }
        for(int i = 0; i < nums2.length; i++ ){
            if(set1.contains(nums2[i])){
                set2.add(nums2[i]);
            }
            
        }
        return  set2.stream().mapToInt(x -> x).toArray();
    }
}

202. Happy Numbers

Solution and idea

If this number is not a happy number, there must be repetitions during the cycle, so that the cycle can continue. You can use Set to save the number of each cycle, and use the contains method to judge whether this number is already in the Set, and this number is not Equal to 1, it means that it has been repeated, not a happy number. When the loop returns 1, it means the number is a happy number.

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

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

1. The sum of two numbers

Solution and idea

Because the result is to return the subscript of two numbers, it is necessary to save this number and its subscript at the same time. At this time, it is better to use Map to save it. For this question, we need to give an element to judge whether this element appears However, if present, returns the subscript of this element. Then to determine whether an element appears, this element will be used as a key, so the element in the array is used as a key, and the key corresponds to the value, and the value is used to store the subscript.

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] = map.get(temp);
                res[1] = i;
                break;
            }
            map.put(nums[i],i);
        }   
        return res;   
    }
}

Tags: Algorithm data structure leetcode

Posted by David03 on Thu, 09 Feb 2023 19:41:05 +0530