【解题报告】力扣 第 283 场周赛

文章目录

一、Excel 表中某个范围内的单元格

1、算法：字符串处理

  直接用 STL 的 string + vector，处理起来很方便，因为数字和字母都只有一位，所以直接下标索引获取对应范围。

2、源码

classSolution{public:
    vector<string>cellsInRange(string s){
        vector<string> ret;for(char i = s[0]; i <= s[3];++i){for(char j = s[1]; j <= s[4];++j){
                string ans;
                ans.push_back(i);
                ans.push_back(j);
                ret.push_back(ans);}}return ret;}};

二、向数组中追加 K 个整数

1、算法：排序 + 等差数列公式

  将原数组排完序后，计算相邻两个数中间没有出现过的数字的个数

gap

，和

k

进行比较，如果比

k

小，则计算中间的等差数列和加到结果中，并且执行

k -= gap

；否则就是剩下的

k

个等差数列的和，加到结果中即可。
  可以在数组最后加上一个非常大的数字，从而减少最后一堆数字的特殊判断。

2、源码

classSolution{longlongmax(longlong a,longlong b){return a > b ? a : b;}public:longlongminimalKSum(vector<int>& nums,int k){longlong ans =0;longlong maxv =0;longlong start =1;longlong pre =0, gap;sort(nums.begin(), nums.end());
        nums.push_back(2100000000);for(int i =0; i < nums.size();++i){
            gap = nums[i]- pre -1;if(gap ==-1)continue;if(k > gap){
                k -= gap;
                ans +=((pre +1)+(nums[i]-1))* gap /2;}else{
                ans +=((pre +1)+ pre + k )* k /2;
                k =0;break;}
            
            pre = nums[i];}return ans;}};

三、根据描述创建二叉树

1、算法：模拟 + 二叉树

  直接模拟创建父结点和子结点，把树建起来即可。如果是子结点，可以标记一下，这样最后如果没有标记过的结点，就一定是树根，直接返回即可。

2、源码

classSolution{public:
    TreeNode*createBinaryTree(vector<vector<int>>& descriptions){int i;int deg[100001];memset(deg,-1,sizeof(deg));
        TreeNode* nodes[100001];memset(nodes,NULL,sizeof(nodes));for(i =0; i < descriptions.size();++i){int p = descriptions[i][0];int c = descriptions[i][1];int l = descriptions[i][2];if(nodes[p]==NULL){
                nodes[p]=newTreeNode();
                nodes[p]->val = p;
                nodes[p]->left =NULL;
                nodes[p]->right =NULL;}if(nodes[c]==NULL){
                nodes[c]=newTreeNode();
                nodes[c]->val = c;
                nodes[c]->left =NULL;
                nodes[c]->right =NULL;}if(l ==0){
                nodes[p]->right = nodes[c];}else{
                nodes[p]->left = nodes[c];}
            deg[c]=1;if(deg[p]!=1){
                deg[p]=0;}}for(i =1; i <=100000;++i){if(!deg[i]){return nodes[i];}}returnNULL;}};

四、替换数组中的非互质数

1、算法：暴力链表

  直接把所有元素串联到链表里，然后从左往右枚举相邻两个数是否可以合并，合并后删掉一个结点，如果某次枚举没有发现任何可以合并的数，则跳出循环。
  数据会卡超时，所以可以随机一个因子，如果命中则从后往前建立链表，否则从前往后，水过去了。

2、源码

struct Node {int val;
    Node *next;Node(){
        next =NULL;}};intgcd(int a,int b){return!b ? a :gcd(b, a%b);}intlcm(int a,int b){return a /gcd(a, b)* b;}/*
-1 -> a -> b -> c -> NULL

*/voidvectorReverse(vector <int>& a){int i;int len = a.size();for(i =0; i < len/2;++i){int tmp = a[i];
        a[i]= a[len-i-1];
        a[len-i-1]= tmp;}}classSolution{public:
    vector<int>replaceNonCoprimes(vector<int>& nums){int xrandm =(rand()%2);if(xrandm)vectorReverse(nums);
        Node *head =newNode();
        Node *now = head;
        head->val = nums[0];Primes();int i;for(i =1; i < nums.size();++i){
            Node *nd =newNode();
            nd->val = nums[i];
            now->next = nd;
            now = now->next;}bool flag =true;while(flag){
            now = head;
            flag =false;while(now && now->next){int g =gcd(now->val, now->next->val);if(g ==1){
                    now = now->next;}else{
                    now->val = now->val / g * now->next->val;
                    now->next = now->next->next;
                    flag =true;}}}
        vector <int> ans;
        now = head;while(now){
            ans.push_back(now->val);
            now = now->next;}if(xrandm)vectorReverse(ans);return ans;}};