代码随想录算法训练营第6天 | 242. 有效的字母异位词 | 349. 两个数组的交集 | 202. 快乐数 | 1. 两数之和

242. 有效的字母异位词

题意

两个字符串中每个字符的出现次数是否一样

解

hash

bool isAnagram(char* s, char* t) {
    int array[30];

    memset(array, 0, sizeof(int) * 30);

    for (int i = 0; s[i] != '\0'; i++) {
        array[s[i] - 'a']++;
    }

    for (int i = 0; t[i] != '\0'; i++) {
        array[t[i]-'a']--;
    }

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

    return true;
}

349. 两个数组的交集

题意

找出两个数组中重复的数字

解

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
    int hash[1005];
    int i, k = 0;
    int *ans = (int *)malloc(sizeof(int) * (1005));

    memset(hash, 0, sizeof(int) * (1005));
    memset(ans, 0, sizeof(int) * (1005));

    for (i = 0; i < nums1Size; i++) {
        hash[nums1[i]] = 1;
    }

    for (i = 0; i < nums2Size; i++) {
        if (hash[nums2[i]] == 1) {
            ans[k++] = nums2[i];
            hash[nums2[i]] = 0;
        }
    }

    *returnSize = k;

    return ans;
}

leetcode返回数组时, 注意要给返回的数组指定长度

202. 快乐数

题意

一个整数的各位平方和如果最后为1, 就是快乐数. 如果不是快乐数, 就会一直循环下去

解

看的题解
非快乐数的平方会陷入一个循环中, 由于会重复出现, 所以和就会出现快慢相撞

int getsum(int n) {
    int sum = 0;

    while (n) {
        sum += (n%10) * (n%10);
        n /= 10;
    }

    return sum;
}

bool isHappy(int n) {
    int slow, fast;
    slow = fast = n;

    do {
        slow = getsum(slow);
        fast = getsum(getsum(fast));
    } while (slow != fast);

    return fast == 1;
}

1. 两数之和

题目链接

题意

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

解

看的题解

• 什么时候使用哈希法，当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法。

• 因为本题，我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> map;
        
        for (int i = 0; i < nums.size(); i++) {
            auto iter = map.find(target - nums[i]);
            if (iter != map.end()) {
                return {iter->second, i};
            }

            map.insert(pair<int, int> (nums[i], i));
        }

        return {};
    }
};