Leetcode第283场周赛解题报告

AK了，但是排名还是低

6016. Excel 表中某个范围内的单元格

知识点：模拟
模拟进位

/**
 * @param {string} s
 * @return {string[]}
 */
var cellsInRange = function(s) {
    let [a,b] = s.split(":")
    const ans = []
    let now = a
    while(true) {
        console.log(now)
        ans.push(now)
        if(now===b) {
            break;
        }
        const cx = now.charCodeAt(1)
        let x = String.fromCharCode(cx+1)
        let offset = 0
        if(cx===(b.charCodeAt(1))) {
            x = String.fromCharCode(a.charCodeAt(1))
            offset = 1
        }
        now = String.fromCharCode(now.charCodeAt(0)+offset) + x
    }
    return ans
};

6017. 向数组中追加 K 个整数

知识点：模拟、数学
一开始写了一个for循环的解，直接超时了。
优化方法：区间内的数可以合并求解，即用等差数列求和公式计算给定区间的和

class Solution {
public:
    long long minimalKSum(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        long long ans = 0;
        long long last = 0;
        long long pos = 0;
        for(auto i:nums) {
            last+=1;
            while(last < i && pos < k) {
                long long t = min(i - last,k-pos);
                ans+=((last+last+t-1)*t)/2;
                pos+=t;
                last+=t;
            }
            if(pos>=k) break;
            last = i;
        }
        last+=1;
        long long t = k-pos;
        ans+=((last+last+t-1)*t)/2;
        return ans;
    }
};

6018. 根据描述创建二叉树

知识点：搜索
使用哈希表进行建图，然后找到一个入度为0的点，即根节点，然后进行搜索
对于每一个搜索的节点来说，找到存储的边表，非常常规的建树

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
private:
    unordered_map<int,int> in;
    unordered_map<int,pair<int,int>> out;
    TreeNode* search(int now){
        if(now==0) return 0;
        auto p = out[now];
        if(out.find(now)==out.end()) return new TreeNode(now);
        return new TreeNode(now,search(p.first),search(p.second));
    }
public:
    TreeNode* createBinaryTree(vector<vector<int>>& descriptions) {
        for(auto i:descriptions){
            in[i[1]]++;
            if(in.find(i[0])==in.end()) in[i[0]] = 0;
            if(i[2]==1) {
                out[i[0]].first = i[1];
            }else{
                out[i[0]].second = i[1];
            }
        }
        for(auto &[k,v]:in){
            if(v==0) return search(k);
        }
        return 0;
    }
};

6019. 替换数组中的非互质数

知识点：栈
一开始根据题意写了个模拟，即反复两两匹配，直到没有可以新合并的数为止。
后来发现每次重新扫描，都要重复匹配多次。
然而在合并过程中，合并完成的元素，其能够影响的范围也只有相邻的元素。
因此得到一次扫描完成算法：正向扫描，每次合并后向左查找元素，是否能继续合并，重复此过程直到没有元素可以合并为止

class Solution:
    def replaceNonCoprimes(self, nums: List[int]) -> List[int]:
        stps = 0
        lst = -1
        cnt = -1
        ans = []
        mask = [0] * len(nums)

        cnt = 0
        lstidx = -1
        st = []
        for i in range(len(nums)):
            if lstidx != -1:
                gc = math.gcd(nums[i], nums[lstidx])
                if gc > 1:
                    mask[lstidx] = 1
                    nums[i] = math.lcm(nums[i], nums[lstidx])
                    cnt += 1
                    ok = True
                    while ok and len(st) > 0:
                        top = st.pop()
                        if mask[top] == 1:
                            continue
                        gc = math.gcd(nums[i], nums[top])
                        if gc > 1:
                            mask[top] = 1
                            nums[i] = math.lcm(nums[i], nums[top])
                        else:
                            st.append(top)
                            ok = False
            if mask[i] == 0:
                lstidx = i
                st.append(i)
        
        for i in range(len(nums)):
            if mask[i]==0:
                ans.append(nums[i])
        return ans