111. Minimum Depth of Binary Tree

最大深度を求めるより全然難しい。左右どちらかが、なければもう一方を探索していく。

class Solution {
public:
    int minDepth(TreeNode* root) {
        if(!root)
        {
            return 0;
        }
        
        if (root->left == NULL) {
            return minDepth(root->right) +1 ;
        }
        if (root->right == NULL) {
            return minDepth(root->left) +1;
        }

        
        return min(minDepth(root->left), minDepth(root->right))+1;
    }
};

35. Search Insert Position

普通にサーチしたら下記の結果となったが、O(log n)で作れとあった。これだとO(n)である。バイナリサーチならば条件を満たすらしいので下に作成。

普通の

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        
        for(int i=0; len >i; i++){
            if(nums[i] == target)
            {
                return i;
            }
            else if(nums[i] > target){
                return i;                
            }
        }
        return len;
    }
};

バイナリサーチ

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();
        if(len == 0){
            return 0;
        }
        
        int low = 0;
        int hi = len -1;
        int mid;
        while(low <= hi){
            mid = (low + hi) / 2;
            if(nums[mid] == target)
            {
                return mid;
            }else if(nums[mid] < target)
            {
                low = mid +1;
            }
            else{
                hi = mid -1;
            }
        }
        return low;
    }
};

387. First Unique Character in a String

一文字づつmapに入れて、後から1文字しか無いものを確認する

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> m;
        
        for(int i=0; s.length()>i; i++){
            if(m.find(s[i]) != m.end()){
                m[s[i]] ++;
            }
            else{
                m[s[i]]=1;
            }             
        }
        
        for(int i =0; s.size()>i; i++){
            if(m[s.at(i)]==1){
                return i;
            }
        }
        return -1;
    }
};

929. Unique Email Addresses

setを思いつければ簡単。

class Solution {
public:
    int numUniqueEmails(vector<string>& emails) {        
        set<string> num;        
        for(string email: emails){
            string checkedEmail;            
            
            for(int i=0; email[i]!='@'; i++ ){
                if(email[i] == '+'){
                    break;
                }
                else if(email[i] == '.'){
                    continue;
                }
                else{
                    checkedEmail +=  email[i];
                }
            }
            int j = email.find('@');
            checkedEmail += email.substr(j, email.length()-j);
            num.insert(checkedEmail);
        }
        return num.size();
    }
};

104. Maximum Depth of Binary Tree

最後に+1が必要だった。問題に二分木が書いてあって再帰をすぐに適応できた。

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(!root){
            return 0;
        }
        return max(maxDepth(root->left), maxDepth(root->right))+1;
    }
};

349. Intersection of Two Arrays

setは重複を許可しないので、一意の値にしたいときに便利。

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1;
        set<int> s2;
        
        for(auto val:nums1){
            s1.insert(val);
        }
        
        for(auto val:nums2){
            s2.insert(val);
        }
        
        vector<int> out;
        
        for(auto val:s1){
            if(s2.find(val)!=s2.end()){
                out.push_back(val);
            }
        }
        return out;
    }
};

■

一個ずつ順番に試すブルートフォースはすぐに思いついた。しかし、これだとO(n²)の時間がかかる。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        for(int i = 0; i<nums.size()-1; i++){
            for(int j=i+1; j<nums.size(); j++){
                if(nums[i]+nums[j] == target){
                    return {i, j};
                }
            }
        }
        return {};
    }
};

https://leetcode.com/problems/two-sum/discuss/860427/Brute-force-Hash-Table-optimized-hash-table. 高速化で上記URLを真似した。unordered_mapのkeyを1、2、3のindexと考えてしまうが、値の方をindexとするように発想できるようにならなければ。

1. numsを前から見ていく
2. target-nums[i]になる要素があるか探す
3. 存在するならばそれのindexを返す
4. 存在しないならば、hashに保存し、次の値に行く

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