0661-0670

661. Image Smoother $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
 public:
  vector<vector<int>> imageSmoother(vector<vector<int>>& M) {
    const int m = M.size();
    const int n = M[0].size();

    vector<vector<int>> ans(m, vector<int>(n));

    for (int i = 0; i < m; ++i)
      for (int j = 0; j < n; ++j) {
        int ones = 0;
        int count = 0;
        for (int y = max(0, i - 1); y < min(m, i + 2); ++y)
          for (int x = max(0, j - 1); x < min(n, j + 2); ++x) {
            ones += M[y][x];
            ++count;
          }
        ans[i][j] = ones / count;
      }

    return ans;
  }
};

662. Maximum Width of Binary Tree $\star\star$

663. Equal Tree Partition $\star\star$

664. Strange Printer $\star\star\star$

665. Non-decreasing Array $\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
 public:
  bool checkPossibility(vector<int>& nums) {
    int j = -1;

    for (int i = 0; i + 1 < nums.size(); ++i)
      if (nums[i] > nums[i + 1]) {
        if (j != -1) return false;
        j = i;
      }

    return j == -1 || j == 0 || j == nums.size() - 2 ||
           nums[j - 1] <= nums[j + 1] || nums[j] <= nums[j + 2];
  }
};

666. Path Sum IV $\star\star$

667. Beautiful Arrangement II $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
 public:
  vector<int> constructArray(int n, int k) {
    vector<int> ans;

    for (int i = 0; i < n - k; ++i) ans.push_back(i + 1);

    for (int i = 0; i < k; ++i) {
      if (i % 2 == 0)
        ans.push_back(n - i / 2);
      else
        ans.push_back(n - k + (i + 1) / 2);
    }

    return ans;
  }
};

668. Kth Smallest Number in Multiplication Table $\star\star\star$

669. Trim a Binary Search Tree $\star$

670. Maximum Swap $\star\star$

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int maximumSwap(int num) {
    string s = to_string(num);
    unordered_map<char, int> map;

    for (int i = 0; i < s.length(); ++i) map[s[i]] = i;

    for (int i = 0; i < s.length(); ++i)
      for (char digit = '9'; digit > s[i]; --digit)
        if (map[digit] > i) {
          s[map[digit]] = s[i];
          s[i] = digit;
          return stoi(s);
        }

    return num;
  }
};