leetcode解题思路分析（九十二）804 - 810 题

待我称王封你为后i 2022-09-11 13:16 110阅读 0赞

1.  唯一的摩尔斯密码  
    给定一个单词列表，每个单词可以写成每个字母对应摩尔斯密码的组合。例如，“cab” 可以写成 “-.-…–…”，(即 “-.-.” + “.-” + “-…” 字符串的结合)。我们将这样一个连接过程称作单词翻译。  
    返回我们可以获得所有词不同单词翻译的数量。

class Solution { 
    public:
        int uniqueMorseRepresentations(vector<string>& words) { 
            set<string>ans;
            vector<string>mp={ ".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."};
            for(int i=0;i<words.size();i++){ 
                string tmp;
                for(int j=0;j<words[i].size();j++){ 
                    tmp+=mp[words[i][j]-'a'];
                }
                ans.insert(tmp);
            }
            return ans.size();
        }
    };

1.  C++对半分枚举+双指针  
    给定的整数数组 A ，我们要将 A数组 中的每个元素移动到 B数组 或者 C数组中。（B数组和C数组在开始的时候都为空）返回true ，当且仅当在我们的完成这样的移动后，可使得B数组的平均值和C数组的平均值相等，并且B数组和C数组都不为空。

class Solution { 
    public:
        vector<double> make(vector<double> nums){  // 枚举子序列的和
            int n = nums.size();
            vector<double> ans(1 << n);
            for(int i = 0; i < n; ++i){ 
                for(int j = 0; j < (1 << i); ++j){ 
                    ans[j + (1 << i)] = ans[j] + nums[i];
                }
            }
            return ans;
        }
        bool splitArraySameAverage(vector<int>& nums) { 
            int n = nums.size(), sum = 0;
            if(n == 1) return false; // 被坑了一下
            for(int& ev: nums) sum += ev;
            vector<double> dnums(n);
            for(int i = 0; i < n; ++i){ 
                dnums[i] = nums[i] - (double)sum / n;
            }
            // 获取所有子序列的和
            vector<double> left = make({ dnums.begin(), dnums.begin() + n / 2});
            vector<double> right = make({ dnums.begin() + n / 2, dnums.end()});
            // 先判断是否能独自构成答案，注意不能从0开始枚举，0表示不贡献任何元素
            for(int i = 1; i < left.size(); ++i){ 
                if(fabs(left[i]) < 1e-5) return true;
            }
            left.erase(left.begin()); left.pop_back(); // 删除全贡献和全不贡献的情况
            for(int i = 1; i < right.size(); ++i){ 
                if(fabs(right[i]) < 1e-5) return true;
            }
            right.erase(right.begin()); right.pop_back();
            sort(left.rbegin(), left.rend());
            sort(right.begin(), right.end());
            int l = 0, r = 0; // 双指针
            while(l < left.size() && r < right.size()){ 
                double ev = left[l] + right[r];
                if(fabs(ev) < 1e-5) return true;
                else if(ev > 0) l++;
                else r++;
            }
            return false;
        }
    };

1.  写字符串需要的行数  
    现在回答两个问题：至少多少行能放下S，以及最后一行使用的宽度是多少个单位？将你的答案作为长度为2的整数列表返回。

class Solution { 
    public:
        vector<int> numberOfLines(vector<int>& widths, string s) { 
            int ansLine=1;
            int add=0;
            for(int i=0;i<s.size();i++){ 
                if(add+widths[s[i]-'a']>100){ 
                    ansLine++;
                    add=widths[s[i]-'a'];
                }else add+=widths[s[i]-'a'];
            }
            return { ansLine,add};
        }
    };

1.  保持城市天际线  
    在二维数组grid中，grid\[i\]\[j\]代表位于某处的建筑物的高度。 我们被允许增加任何数量（不同建筑物的数量可能不同）的建筑物的高度。 高度 0 也被认为是建筑物。最后，从新数组的所有四个方向（即顶部，底部，左侧和右侧）观看的“天际线”必须与原始数组的天际线相同。 城市的天际线是从远处观看时，由所有建筑物形成的矩形的外部轮廓。 请看下面的例子。建筑物高度可以增加的最大总和是多少？

**求出每个位置对应的两个最值，取小值即可。贪心求解**

class Solution { 
    public:
        int maxIncreaseKeepingSkyline(vector<vector<int>>& grid) { 
            int n = grid.size();
            int maxRow[n];
            int maxCol[n];
            memset(maxRow, 0, sizeof(maxRow));
            memset(maxCol, 0, sizeof(maxCol));
            for (int i = 0; i < n; ++i)
            { 
                for (int j = 0; j < n; ++j)
                { 
                    maxRow[i] = max(maxRow[i], grid[i][j]);
                    maxCol[j] = max(maxCol[j], grid[i][j]);
                }
            }
    
            // 再次遍历计算差值
            int res = 0;
            for (int i = 0; i < n; ++i)
            { 
                for (int j = 0; j < n; ++j)
                { 
                    res += min(maxRow[i], maxCol[j]) - grid[i][j];
                }
            }
            return res;
        }
    };

1.  分汤  
    有 A 和 B 两种类型的汤。一开始每种类型的汤有 N 毫升。需要返回的值： 汤A先分配完的概率 + 汤A和汤B同时分配完的概率 / 2。

**设 dp(i, j) 表示汤 A 和汤 B 分别剩下 i 和 j 份时，所求的概率值。状态转移方程为：  
dp(i, j) = 1/4 \* (dp(i - 4, y) + dp(i - 3, y - 1) + dp(i - 2, y - 2) + dp(i - 1, y - 3))**

class Solution { 
    public:
        double soupServings(int N) { 
            // 较大N，直接返回1.0
            if (N >= 4000)
            { 
                return 1.0;
            }
            // 换算25来归一化
            N = N/ 25 + (N %25 != 0);
            double** d = new double*[N+1];
            for (int i = 0; i <= N; ++i)
            { 
                d[i] = new double[N+1];
                memset(d[i], 0, sizeof(double)*(N+1));
            }
            for (int i = 0; i <= N; ++i)
            { 
                 for (int j = 0; j <= N; ++j)
                 { 
                     if (i > 0 && j > 0)
                     { 
                         d[i][j] = (d[max(i-4, 0)][j] + d[max(i-3, 0)][max(j-1,0)] + d[max(i-2, 0)][max(j-2,0)] + d[max(i-1, 0)][max(j-3,0)])*0.25;
                     }
                     else if (i <= 0 && j <= 0)
                     { 
                         d[i][j] = 0.5;
                     }
                     else if (i <= 0 && j > 0)
                     { 
                         d[i][j] = 1.0;
                     }
                 }
            }
    
            return d[N][N];
        }
    };

1.  情感丰富的文字  
    输入一组查询单词，输出其中可扩张的单词数量。

**双指针滑动即可**

class Solution { 
    public:
        int expressiveWords(string s, vector<string>& words) { 
            int ans=0;
            for(int i=0;i<words.size();i++){ 
                string &word=words[i];
                int cur1=0,cur2=0;
                bool flag=false;
                while(cur1<s.size()){ 
                    int j=cur1;
                    cur1++;
                    while(cur1<s.size()&&s[cur1]==s[j])cur1++;
                    int len1=cur1-j;
                    if(word[cur2]!=s[j]){ 
                        flag=true;
                        break;
                    }
                    int k=cur2;
                    cur2++;
                    while(cur2<word.size()&&word[cur2]==word[k])cur2++;
                    int len2=cur2-k;
                    if(len1<=2&&len1!=len2){ 
                        flag=true;
                        break;
                    }
                    else if(len1>=3&&len2>len1){ 
                        flag=true;
                        break;
                    }
                }
                if(cur2!=word.size())flag=true;
                if(flag==false)ans++;
            }
            return ans;
        }
    };

1.  黑板异或游戏  
    黑板上写着一个非负整数数组 nums\[i\] 。Alice 和 Bob 轮流从黑板上擦掉一个数字，Alice 先手。如果擦除一个数字后，剩余的所有数字按位异或运算得出的结果等于 0 的话，当前玩家游戏失败。 (另外，如果只剩一个数字，按位异或运算得到它本身；如果无数字剩余，按位异或运算结果为 0。）

**本题实际需要按情况分类讨论如何能够获胜，通过数学证明，最后可得。当且仅当以下两个条件至少满足一个时，Alice 必胜：数组 nums 的全部元素的异或结果等于 0；数组 nums 的长度是偶数**

class Solution { 
    public:
        bool xorGame(vector<int>& nums) { 
            if (nums.size() % 2 == 0) { 
                return true;
            }
            int xorsum = 0;
            for (int num : nums) { 
                xorsum ^= num;
            }
            return xorsum == 0;
        }
    };