LeetCode_22_Apr_2nd_Week

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

---

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

该题使用动态规划，因为数字范围为$1\sim 10^8$，而按照$4$位数字平均值计算，若是逐个数字判断则时间复杂度过大，所以要使用其他方法，如数学方法。而实际本题的解决思路也是使用数学思想，同时运用动态规划的思想，依照数位进行求解。

//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) //进行dp数位求解
            dp[i] = dp[i-1] + (dp[i-1] - dp[i-2]) * (10 - (i - 1));
            //dp[i]表示表示从1数位到i位数的各位数字都不同的数字的个数，dp[i-1]和dp[i-2]同理
            //dp[i-1]-dp[i-2]表示i-1位数相比i-2位数所多出的各位数字都不同的数字的个数，
            //且这些数字的位数都是i-1位的，而i位的各位数字都不同的数字均要从这些数字中
            //增添一个数位数字产生，而所增添的数位数字必须与之前数位中数字不同，所以有
            //每个i-1位的各位数字不同的数字形成i位的可能有(10-(i-1))种选择，i-1表示除去自身
        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. 写字符串需要的行数

这个没有太多可说的，需要注意的是当刚好将末行填满时的情况，此时所占行数不变，且末行所占的字符宽度是$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}; //末行刚好填满的情形
        else return {
    lines, 100 - remain}; //一般情形
    }
};

---

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

$O(1)$时间复杂度实现对类中数值成员的查找和删除，借助哈希表便可以实现对数值成员的常数时间复杂度的查找和定位。而随机返回则使用时间随机即可，要记得创建时间种子，避免伪随机。

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) {
    
    	//先判断是否已有该值，没有则返回false
    	//有的话，先将所删除元素的下标查出，将vector尾部数值放置该位置
    	//要对尾部数值的哈希对照进行更新，同时覆盖删除数值，调整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. 最富有客户的资产总量

简单遍历即可求解。

//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;
    }
};