LeetCode_22_Apr_2nd_Week

April 11th : 357. 统计各位数字都不同的数字个数
April 12th : 806. 写字符串需要的行数
April 13th : 380. O(1) 时间插入、删除和获取随机元素
April 14th : 1672. 最富有客户的资产总量

---

April 11th : 357. 统计各位数字都不同的数字个数

This problem uses dynamic programming,因为数字范围为$1\sim 10^8$,而按照$4$Digit average calculation,If it is judged one by one, the time complexity is too large,所以要使用其他方法,such as mathematical methods.The actual solution to this problem is also the use of mathematical ideas,At the same time use the idea of ​​dynamic programming,Solve by numbers.

//version 1 使用dp数组,时间O(n),空间O(n)
class Solution {
    
public:
    int countNumbersWithUniqueDigits(int n) {
    
        if(0 == n) return 1;
        vector<int> dp(n+1);
        dp[0] = 1; dp[1] = 10; //数位0位则为1,1位则为10,作为dp初始状态
        for(int i = 2; i < n+1; ++i) //进行dpSolve digitally
            dp[i] = dp[i-1] + (dp[i-1] - dp[i-2]) * (10 - (i - 1));
            //dp[i]表示表示从1digital toiThe number of digits in which each digit of the digit is different,dp[i-1]和dp[i-2]同理
            //dp[i-1]-dp[i-2]表示i-1compared to numbersi-2The number of digits in which each additional digit is different,
            //And the digits of these numbers are alli-1位的,而iNumbers in which each digit of the digit is different are to be taken from these numbers
            //Add a digit number to generate,The number of digits added must be different from the digits in the previous digits,所以有
            //每个i-1The digits of the digits are formed by different digitsibit may have(10-(i-1))种选择,i-1means to remove itself
        return dp[n];
    }
};
/*****************************************************************************/
//version 2 复用dp变量,时间O(n),空间O(1)
class Solution {
    
public:
    int countNumbersWithUniqueDigits(int n) {
    
        if(0 == n) return 1;
        int dp0 = 1, dp1 = 10;
        for(int i = 2; i <= n; ++i) {
    
            int curDp = dp1 + (dp1-dp0)*(11-i);
            dp0 = dp1; dp1 = curDp;
        }
        return dp1;
    }
};

---

April 12th : 806. 写字符串需要的行数

There isn't much to say about this,The thing to watch out for is when the last row is just filled,The number of lines occupied at this time remains unchanged,And the character width occupied by the last line is $100$.

class Solution {
    
public:
    vector<int> numberOfLines(vector<int>& widths, string s) {
    
        int lines = 1, width = 0;
        int remain = 100;
        for(auto ch : s) {
    
            remain -= widths[ch-'a'];
            if(0 > remain) {
    lines++; remain = 100-widths[ch-'a'];}
            if(0 == remain) {
    lines++; remain = 100;}
        }
        if(100 == remain) return {
    lines-1, 100}; //The case where the last row just fills up
        else return {
    lines, 100 - remain}; //一般情形
    }
};

---

April 13th : 380. O(1) 时间插入、删除和获取随机元素

$O(1)$Time Complexity Implements lookup and deletion of numeric members in a class,With the help of the hash table, the constant time complexity of the value members can be searched and located.For random return, you can use random time,Remember to create a time seed,Avoid pseudo-random.

class RandomizedSet {
    
public:
    RandomizedSet() {
    
        srand((unsigned)time(NULL));
    }
    
    bool insert(int val) {
    
        if(indices.count(val)) return false;
        elements.emplace_back(val);
        indices[val] = elements.size()-1;
        return true;
    }
    
    bool remove(int val) {
    
    	//First determine whether the value already exists,没有则返回false
    	//有的话,First find the subscript of the deleted element,将vectorThe trailing value is placed in this position
    	//To update the hash comparison of the trailing value,Also overwrite and delete the value,调整vector大小
        if(indices.count(val)) {
    
            indices[elements[elements.size()-1]] = indices[val];
            elements[indices[val]] = elements[elements.size()-1];
            indices.erase(val);
            elements.resize(elements.size()-1);
            return true;
        }
        return false;
    }
    
    int getRandom() {
    
        return elements[rand()%elements.size()];
    }
private:
    vector<int> elements;
    unordered_map<int, int> indices;
};

/** * Your RandomizedSet object will be instantiated and called as such: * RandomizedSet* obj = new RandomizedSet(); * bool param_1 = obj->insert(val); * bool param_2 = obj->remove(val); * int param_3 = obj->getRandom(); */

---

April 14th : 1672. 最富有客户的资产总量

Simple traversal to solve.

//version 1
class Solution {
    
public:
    int maximumWealth(vector<vector<int>>& accounts) {
    
        vector<int> fortune(accounts.size());
        for(int i = 0; i < accounts.size(); ++i) 
            for(int j = 0; j < accounts[0].size(); ++j) 
                fortune[i] += accounts[i][j];
        int ret = 0;
        for(auto ele : fortune) ret = max(ret, ele);
        return ret;
    }
};
//version 2
class Solution {
    
public:
    int maximumWealth(vector<vector<int>>& accounts) {
    
        int ret = INT_MIN;
        for(auto& account : accounts)
            ret = max(ret, accumulate(account.begin(), account.end(), 0));
        return ret;
    }
};