LeetCode_Nov_4th_Week

November 22nd : 384. 打乱数组
November 23rd : 859. 亲密字符串
November 24th : 423. 从英文中重建数字
November 25th : 458. 可怜的小猪
November 26th : 700. 二叉搜索树中的搜索
November 27th : 519. 随机翻转矩阵
November 28th : 438. 找到字符串中所有字母异位词

---

November 22nd : 384. 打乱数组

① In order from the number to be selected(The number of the array to shuffle)中随机选出一个,然后放入 $shuffle$ at the current position of the array,The position is moved back one by one,Also delete the selected numbers from the array to be shuffled,In this way, the scrambled array with equal probability can be obtained by one traversal operation.for the numbers in the original array,移动到第 $i$ 个位置的概率是$\frac{1}{n}$：

For deleting randomly selected elements in the array to be shuffled,A linked list data structure can be used,with a hash table,$O(1)$ Time complexity to find and delete numbers.

② ①ideas can be transformed,First copy the array to be shuffled as $shuffle$ 数组,再把 $shuffle$ 数组第 $i$ Swap numbers to a random position in the array.That is, think about from the way of arrangement $n!$ The scheme for selecting random numbers,$n!=n\ast (n-1)!$ 这里的 $n$ That is, you first select the number of types of the first element;然后 $(n-1)!$ It is the arrangement of other elements.So we have to choose a shuffling scheme,You can first wait for the probability $n$ Pick one of the elements as the first element;然后再对剩下的 $(n-1)$ elements are similarly selected.这样就相当于把 $n!$ 分成 $n$ 段,Choose one of the paragraphs first,里面有 $(n-1)!$ 个元素,我们把这 $(n-1)!$ divided into cases $(n-1)$ 段,Pick another at random,以此类推. Such a strategy can be done from $(n-1)!$ randomly selected.

//version 2②
class Solution {
    
public:
    Solution(vector<int>& nums) {
    
        Elements = nums;
    }
    
    vector<int> reset() {
    
        return Elements;
    }
    
    vector<int> shuffle() {
    
        vector<int> vShuffle = Elements;
        for(int i = 1; i < vShuffle.size(); ++i) {
    
            int r = rand() % (i + 1);
            swap(vShuffle[r], vShuffle[i]);
        }
        return vShuffle;
    }
private:
    vector<int> Elements;
};

---

November 23rd : 859. 亲密字符串

满足以下两个条件,Two strings are mutually intimate strings：
① The two strings have the same character frequency(The XOR method can be used,在$O(n)$Whether the calculation frequency is the same under the time complexity,但是步骤②The frequency number of characters is also required,So use the array count method);
② There are two positions where the characters corresponding to the two strings are inconsistent,Or both correspond to the same but the frequency of characters is greater than or equal to$2$;

时间复杂度$O(n+C)$,空间复杂度$O(C)$;根据数据规模,$O(n^2)$The amount of calculation is in $4\ast 10^8$,to time out,Violent methods do not pass.

class Solution {
    
public:
    bool buddyStrings(string s, string goal) {
    
        if(s.size() != goal.size()) return false;
        vector<int> cnt1 = vector<int>(26, 0);
        vector<int> cnt2 = vector<int>(26, 0);
        int chLocDiff = 0; //The number of different characters in the same position
        for(int i = 0; i < s.size(); ++i) {
    
            cnt1[s[i] - 'a']++;
            cnt2[goal[i] - 'a']++;
            if(s[i] != goal[i]) chLocDiff++;
        }
        bool hasSame = false; //Whether there is a frequency greater than 2的字符
        for(int i = 0; i < 26; ++i) {
    
        	//The same character has different frequencies,直接返回假
            if(cnt1[i] != cnt2[i]) return false;
            if(cnt1[i] > 1) hasSame = true;
        }
        //the same frequency,The different numbers are2,
        //or a different number0And the frequency is greater than 2character is true
        return chLocDiff == 2 || (hasSame && chLocDiff == 0);
    }
};

---

November 24th : 423. 从英文中重建数字

Count how often each letter appears in different numbers,Some specific numbers correspond to specific unique letters,These specific numbers are first determined based on the number of unique letters,Further infer the number of remaining digits.

class Solution {
    
public:
    string originalDigits(string s) {
    
        int dict[26] = {
    0};
        int nums[10] = {
    0};
        for(int i = 0; i < s.size(); ++i) dict[s[i]-'a']++;
        nums[0] = dict['z'-'a']; //zero,只有0含字母z
        nums[2] = dict['w'-'a']; //two,只有2含字母w
        nums[4] = dict['u'-'a']; //four,只有4含字母u
        nums[6] = dict['x'-'a']; //six,只有6含字母x
        nums[8] = dict['g'-'a']; //eight,只有8含字母g
        nums[3] = dict['h'-'a'] - nums[8]; //含h的只有3,8
        nums[5] = dict['f'-'a'] - nums[4]; //含f的只有4,5
        nums[7] = dict['v'-'a'] - nums[5]; //含v的只有5,7
        nums[9] = dict['i'-'a'] - nums[5] - nums[6] - nums[8]; //含i的只有5,6,8,9,And each contains only one
        nums[1] = dict['o'-'a'] - nums[0] - nums[2] - nums[4]; //含o的只有0,1,2,4,And each contains only one
        string ret = "";
        for(int i = 0; i < 10; ++i) 
            for(int j = 0; j < nums[i]; ++j) 
                ret += to_string(i);
        return ret;
    }
};

---

November 25th : 458. 可怜的小猪

可怜的小猪,可用$dp$,Mathematically better,可怜的小猪.

class Solution {
    
public:
    int poorPigs(int buckets, int minutesToDie, int minutesToTest) {
    
        int states = minutesToTest / minutesToDie + 1;
        int pigs = ceil(log(buckets) / log(states));
        return pigs;
    }
};

---

November 26th : 700. 二叉搜索树中的搜索

没啥讲的,BSTThe concept has mastered words,挺简单的一道题.

class Solution {
    
public:
    TreeNode* searchBST(TreeNode* root, int val) {
    
        while(root) {
    
            if(root->val < val) root = root->right;
            else if(root->val > val) root = root->left;
            else return root;
        }
        return nullptr;
    }
};
/******************************************************************/
class Solution {
    
public:
    TreeNode* searchBST(TreeNode* root, int val) {
    
        while(root && root->val != val) {
    
			root = root->val > val ? root->left : root->right;
        }
        return root;
    }
};

---

November 27th : 519. 随机翻转矩阵

• $m,n$的值可以达到$10^4$,The time complexity and space complexity are very high if they are simulated using arrays;
• Use a hash table to store which subscripted matrix elements are set to$1$了,That is, the hash table is used to store changes in the record mapping relationship,If the matrix currently exists$k$个$1$,那么$mp$的$[m\ast n-k,m\ast n)$The mapping relationship corresponding to the key value of the range is the actual setting$1$The matrix subscript position of ;
• The range of values ​​for random subscripts is $[0,m\ast n-k)$范围,随着$k$（$1$的个数）越来越多,It also means that the scope is shrinking,Take a hash index within the range,and mapped to the actual matrix,Then replace the mapping to $m\ast n-k-1$的位置,At the same time, a hash table is used to record the changes of the mapping relationship,In this way, it can be ensured that the element values ​​of the matrix subscripts mapped to within the range are the same$0$;
• This space complexity and $filp$times are proportional,也即是$O(F)$,$F$是次数,详情见：随机翻转矩阵;

class Solution {
    
public:
   Solution(int m, int n) : m(m), n(n) {
    
       total = m * n;
   }
   
   vector<int> flip() {
    
       vector<int> ret; 
       //0到total-1A random number of first-order probability is taken among them
       int x = rand() % total;
       total--;
       //判断xWhether the mapping relationship has been changed,If yes, take itmp中真实值,If not, the mapping relationship has not changed
       if(mp.count(x)) ret = {
    mp[x]/m, mp[x]%n};
       else ret = {
    x/m, x%n};
       //更新x的映射关系,将其和total(m*n-k-1)的位置进行调换
       //If the boundary value is already theremp里,is changed to the real mapped value,若不在,则直接更改
       if(mp.count(total)) mp[x] = mp[total];
       else mp[x] = total;
       return ret;
   }
   
   void reset() {
    
   	   total = r*c;
       mp.clear();
   }
private:
   int m, n;
   int total;
   // Record which points are selected,And it points to its unselected value,可以用来输出
   unordered_map<int, int> mp;
};

---

November 28th : 438. 找到字符串中所有字母异位词

滑动窗口,Count the letter frequencies of strings and compare them.The XOR method also cannot solve the matching of strings with only one letter in even frequency.

//The wrong version of XOR,If you encounter such as"aa","bb"This will judge the same
class Solution {
    
public:
    vector<int> findAnagrams(string s, string p) {
    
        if(p.size() == 0) return {
    };
        int winXor = 0, pXor = 0;
        for(int i = 0; i < p.size(); ++i) {
    
            winXor ^= s[i];
            pXor ^= p[i];
        }
        vector<int> ret;
        if(winXor == pXor) ret.push_back(0);
        for(int i = 1; i <= s.size()-p.size(); ++i) {
    
            //cout << i << endl;
            winXor ^= s[i-1];
            winXor ^= s[i+p.size()-1];
            if(winXor == pXor) ret.push_back(i);
        }
        return ret;
    }
};
/*************************************************************************************/
//version1 Use a fixed-size array to store the frequency of each letter,The space complexity is certain
class Solution {
    
public:
    vector<int> findAnagrams(string s, string p) {
    
        if(s.size() < p.size()) return {
    };
        int l = 0, r = -1;
        vector<int> freq_s(26, 0), freq_p(26, 0), res;
        // Initialize code value
        for(int i = 0; i < p.size(); i++){
    
            freq_p[p[i]-'a']++;
            freq_s[s[++r]-'a']++;
        }
        if(freq_s == freq_p) res.push_back(l);
        // 固定长度的滑动窗口
        while(r < s.size()-1){
    
            freq_s[s[++r]-'a']++;
            freq_s[s[l++]-'a']--;
            if(freq_s == freq_p) res.push_back(l);
        }
        return res;
    }
};

/*************************************************************************************/
//version2 使用mapto store windows and p的字母频次,Just need to comparemap遍历一遍即可,更省空间和时间(Check out the efficiency)
class Solution {
    
public:
    vector<int> findAnagrams(string s, string p) {
    
        if(p.size() > s.size()) return {
    };
        map<char, pair<int, int>> mp;
        for(int i = 0; i < p.size(); ++i) {
    
            mp[s[i]].first++;
            mp[p[i]].second++;
        }
        vector<int> ret;
        bool flag = true;
        for(int i = 0; i < s.size()-p.size(); ++i) {
    
            for(auto it = mp.begin(); it != mp.end(); ++it) {
    
                if(it->second.first != it->second.second) {
    
                    flag = false;
                    break;
                }
            }
            if(flag) ret.push_back(i);
            else flag = true;
            mp[s[i]].first--;
            mp[s[i+p.size()]].first++;
        }
        for(auto it = mp.begin(); it != mp.end(); ++it) {
    
            if(it->second.first != it->second.second) {
    
                flag = false;
                break;
            }
        }
        if(flag) ret.push_back(s.size()-p.size());
        return ret;
    }
};