leetcode解题思路分析（七十五）661 - 669 题

矫情吗；* 2023-01-21 09:24 20阅读 0赞

1.  图片平滑器  
    包含整数的二维矩阵 M 表示一个图片的灰度。你需要设计一个平滑器来让每一个单元的灰度成为平均灰度 (向下舍入) ，平均灰度的计算是周围的8个单元和它本身的值求平均，如果周围的单元格不足八个，则尽可能多的利用它们。

**直接遍历比起前缀和等做法实测效率更高**

class Solution { 
    public:
        vector<vector<int>> imageSmoother(vector<vector<int>>& M) { 
            int m = M.size(), n = M.front().size();
            vector<vector<int>> result(m, vector<int>(n));
            for (int i = 0; i < m; ++i)
            { 
                for (int j = 0; j < n; ++j)
                { 
                    int num = 0, sum = 0;
                    for (int _i = max(0, i-1); _i <= min(m-1, i+1); ++_i)
                    { 
                        for (int _j = max(0, j-1); _j <= min(n-1, j+1); ++_j)
                        { 
                            sum += M[_i][_j];
                            ++num;
                        }
                    }
                    result[i][j] = sum / num;
                }
            }
            return result;
        }
    };

1.  二叉树最大宽度  
    给定一个二叉树，编写一个函数来获取这个树的最大宽度。树的宽度是所有层中的最大宽度。这个二叉树与满二叉树（full binary tree）结构相同，但一些节点为空。

**其实就是层序遍历加了一个索引计算**

1.  奇怪的打印机  
    有台奇怪的打印机有以下两个特殊要求：  
    打印机每次只能打印同一个字符序列。  
    每次可以在任意起始和结束位置打印新字符，并且会覆盖掉原来已有的字符。  
    给定一个只包含小写英文字母的字符串，你的任务是计算这个打印机打印它需要的最少次数。

**动态规划求解：dp\[i\]\[j\]表示从第i个字符到第j个字符所需的最小打印次数。  
递推式如下：dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i\]\[j-1\] + 1, dp\[i\]\[m-1\] + dp\[m\]\[j\]);, 其中第m个字符与第j个字符相同。**

class Solution { 
    public:
        int strangePrinter(string s) { 
            if (s.size() == 0) return 0;
            //去除连续相同·字符
            int index = 0;
            string str;
            while(index < s.size()) { 
                char ch = s[index++];
                str += ch;
                while(index < s.size() && s[index] == ch) { 
                    index++;
                }
            }
            int n = str.size();
            //dp[i][j]表示从第i个字符到第j个字符（包括两端）需要的打印次数
            vector<vector<int>> dp(n+1, vector<int>(n+1, -1));
            return helper(1,n,dp,str);
        }
        int helper(int l, int r, vector<vector<int>>& dp, string& str) { 
            if (dp[l][r] != -1) return dp[l][r];
            if (l > r) return dp[l][r] = 0;
            int res = helper(l, r - 1, dp, str) + 1;
            for (int m = l; m < r; ++m) { 
                if (str[m-1] == str[r-1]) { 
                    res = min(res, helper(l, m - 1, dp, str) + helper(m, r - 1, dp, str));
                }
            }
            return dp[l][r] = res;
        }
    };

1.  非递减数列  
    给你一个长度为 n 的整数数组，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。

**很简单的遍历，唯一的坑是需要判定是否可以修改成非递减序列**

class Solution { 
    public:
        bool checkPossibility(vector<int> &nums) { 
            int n = nums.size(), cnt = 0;
            for (int i = 0; i < n - 1; ++i) { 
                int x = nums[i], y = nums[i + 1];
                if (x > y) { 
                    cnt++;
                    if (cnt > 1) { 
                        return false;
                    }
                    if (i > 0 && y < nums[i - 1]) { 
                        nums[i + 1] = x;
                    }
                }
            }
            return true;
        }
    };

1.  优美的排列2  
    给你两个整数 n 和 k ，请你构造一个答案列表 answer ，该列表应当包含从 1 到 n 的 n 个不同正整数，并同时满足下述条件：  
    假设该列表是 answer = \[a1, a2, a3, … , an\] ，那么列表 \[|a1 - a2|, |a2 - a3|, |a3 - a4|, … , |an-1 - an|\] 中应该有且仅有 k 个不同整数。  
    返回列表 answer 。如果存在多种答案，只需返回其中 任意一种 。

**先按照这种最小最大数相邻的方法排列，每排一个，k自减1，当k减到1的时候，后面的排列方法只要按照升序的方法排列，就不会产生不同的差的绝对值，这种算法的时间复杂度是O(n)。而且巧妙的是如果k是奇数则从前面最小数开始，否则k是偶数是从后面最大数开始的。**

class Solution { 
    public:
        vector<int> constructArray(int n, int k) { 
            assert(n > 0 && k > 0);
            vector<int> res;
            int i = 1;
            int j = n;
            while (i <= j) { 
                if (k > 1) { 
                    // 按照交替i,j一小一大的方法生成前K-1个数
                    if (k % 2 != 0) { 
                        res.push_back(i);
                        i++;
                    } else { 
                        res.push_back(j);
                        j--;
                    }
                    k--;
                } else { 
                    // 按照生序的方法生成剩余排列
                    res.push_back(i);
                    i++;
                }
            }
    
            return res;
        }
    };

1.  乘法表中第K小的数

**思路：二分法  
1、找第k小，第k大一类的问题，一般情况下都是用二分来解决，那么二分法就需要找到二分的数据点以及比较方式  
2、当前乘法表中最小值肯定是1，最大值为m\*n，也就是我们这张表的最小和最大值，数据点找到  
3、比较方式，要找到第k小，那么我们在拿到mid数据点的时候，去看当前mid的位置，如果mid位置大于k，说明mid值太大，需要再次进行二分求解 4、问题来了，这个位置怎么找呢，假设mid位于指定行i，那么mid/i也就是mid元素的列的位置，如果列的位置大于列最大长度n，那么说明该行所有数据都小于mid，累加n即可如果不是呢，说明找到了正确的行，只需要mid/i列的位置也就是这一行小于mid的元素个数  
5、边界条件的处理是二分法中比较重要的，我们要找第k小，那么可以理解为假设当mid处于某个值时，满足了条件，我们需要锁定大值，也就是count>=k，去调整l的值不断逼近当l的值逼近到某个数据，使得条件再次满足时，就是循环条件结束的时候，这样可以保证l的值一定是在原列表中的，因为+1或-1都会导致条件不满足当然我们的>=条件也是不允许的，因为满足之后l值就被锁定了**

class Solution { 
    public:
        int findKthNumber(int m, int n, int k) { 
            int l = 1;
            int h = m * n;
    
            while(l < h) { 
                int mid = l + (h - l) / 2;
                // 查找比mid小的元素个数
                int count = 0;
                for (int i = 1; i <= m; i++) { 
                    count += (mid / i > n ? n : mid / i);
                }
                if (count >= k) { 
                    h = mid;
                } else { 
                    l = mid + 1;
                }
            }
            return l;
        }
    };

1.  修剪二叉搜索树  
    给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在\[low, high\]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。

**分别处理根，左边，右边即可**

/** * 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) {} * }; */
    /** * 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 { 
    public:
        TreeNode* trimBST(TreeNode* root, int low, int high) { 
            if(!root) return nullptr;
            //处理头结点，让root移动到[low，high]范围内，注意是左闭右闭
            while(root->val < low || root->val > high)
            { 
                if(root->val < low) root = root->right;//小于low往右走
                else root = root->left;                //大于high往左走
                if(root == nullptr) break;             //结束循环的条件
            }
            TreeNode* cur = root;
            //此时root已经在[low，high]范围内，处理左孩子元素小于low的情况
            while(cur != nullptr)
            { 
                while(cur->left && cur->left->val < low)
                { 
                    cur->left = cur->left->right;
                }
                cur = cur->left;
            }
            cur = root;
            //此时root已经在[low，high]范围内，处理右孩子大于high的情况
            while(cur != nullptr)
            { 
                while(cur->right && cur->right->val > high)
                { 
                    cur->right = cur->right->left;
                }
                cur = cur->right;
            }
            return root;
        }
    };