Huahua’s Tech Road

花花酱 LeetCode 2023. Number of Pairs of Strings With Concatenation Equal to Target

By zxi on April 11, 2025

方法1: Brute Force

枚举所有的(nums[i], nums[j])组合，相加在和target比较。

时间复杂度：O(mn²) m为字符串的最长长度。
空间复杂度：O(m)

优化前 67ms, 49.3M

class Solution {

public:

int numOfPairs(vector<string>& nums, string target) {

const int n = nums.size();

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

if (i != j && nums[i] + nums[j] == target)

++ans;

return ans;

}

};

一些工程上的优化

用string_view作为参数类型，减少一次string copy
先比较长度，再判断内容。
string_view.substr 是O(1)时间，和直接用strncmp比较内容是一样的。

优化后 3ms, 12.88MB

class Solution {

public:

int numOfPairs(vector<string>& nums, string_view target) {

const int n = nums.size();

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = 0; j < n; ++j)

if (i != j

&& nums[i].size() + nums[j].size() == target.size()

&& target.substr(0, nums[i].size()) == nums[i]

&& target.substr(nums[i].size()) == nums[j])

++ans;

return ans;

}

};

花花酱 LeetCode 2016. Maximum Difference Between Increasing Elements

By zxi on April 11, 2025

数据规模 n <= 1000。O(n²) 的算法也是能过的。

方法1: Brute Force

双重循环枚举所有的(nums[i], nums[j])的组合。

时间复杂度：O(n²)
空间复杂度：O(1)

class Solution {

public:

int maximumDifference(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

for (int i = 0; i < n; ++i)

for (int j = i + 1; j < n; ++j)

ans = max(ans, nums[j] - nums[i]);

return ans ? ans : -1;

}

};

方法2: 空间换时间

使用prefix sum算法，预先计算num[i] ~ nums[n-1]的最大值，存储在right[i]中。

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {

public:

int maximumDifference(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

vector<int> right(n, nums.back());

for (int i = n - 2; i >= 0; --i)

right[i] = max(right[i + 1], nums[i]);

for (int i = 0; i < n; ++i)

ans = max(ans, right[i] - nums[i]);

return ans ? ans : -1;

}

};

方法3: Running Min

从左到右遍历，记录当前为止出现过最小的值。比较 nums[i] – 最小值和最优解。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {

public:

int maximumDifference(vector<int>& nums) {

const int n = nums.size();

int ans = 0;

int smallest = nums[0];

for (int i = 1; i < n; ++i) {

ans = max(ans, nums[i] - smallest);

smallest = min(smallest, nums[i]);

}

return ans ? ans : -1;

}

};

花花酱 LeetCode 2012. Sum of Beauty in the Array

By zxi on April 10, 2025

数据规模比较大，算法必须是O(n)的。

可以预先使用O(n)时间计算nums[0] .. nums[i]的最大值，存在left[i]中，以及nums[i] .. nums[n-1]的最小值存在right[i]中。然后再按题目的定义计算即可。

时间复杂度：O(n)
空间复杂度：O(n)

class Solution {

public:

int sumOfBeauties(vector<int>& nums) {

const int n = nums.size();

vector<int> left(n, nums[0]);

vector<int> right(n, nums.back());

for (int i = 1; i < n; ++i)

left[i] = max(left[i - 1], nums[i]);

for (int i = n - 2; i >= 0; --i)

right[i] = min(right[i + 1], nums[i]);

int ans = 0;

for (int i = 1; i < n - 1; ++i)

if (left[i - 1] < nums[i] && nums[i] < right[i + 1])

ans += 2;

else if (nums[i - 1] < nums[i] && nums[i] < nums[i + 1])

ans += 1;

return ans;

}

};

花花酱 LeetCode 2011. Final Value of Variable After Performing Operations

By zxi on April 10, 2025

C++ 也能写one-liner了。

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {

public:

int finalValueAfterOperations(vector<string>& operations) {

return accumulate(begin(operations), end(operations), 0, [](const auto s, const auto& op){

return s + (op[1] == '+' ? 1 : -1);

});

}

};

花花酱 LeetCode 1992. Find All Groups of Farmland

By zxi on April 10, 2025

已经告诉你所有的农田都是规整的矩形，题目难度一下子降低了。
对于每一个农田的左上角，找到它的宽度和高度即可。
然后把整个农田矩形标记为林地/非农田即可。

时间复杂度：O(m*n) 每个格子最多遍历3遍。
空间复杂度：O(1)

class Solution {

public:

vector<vector<int>> findFarmland(vector<vector<int>>& land) {

const int m = land.size();

const int n = land[0].size();

vector<vector<int>> ans;

for (int i = 0; i < m; ++i)

for (int j = 0; j < n; ++j) {

if (!land[i][j]) continue;

int w = 0;

int h = 0;

while (j + w < n && land[i][j + w]) ++w;

while (i + h < m && land[i + h][j]) ++h;

ans.push_back({i, j, i + h - 1, j + w - 1});

for (int p = 0; p < h; ++p)

for (int q = 0; q < w; ++q)

land[i + p][j + q] = 0; // mark as seen.

}

return ans;

}

};

Huahua's Tech Road

花花酱 LeetCode 2023. Number of Pairs of Strings With Concatenation Equal to Target

花花酱 LeetCode 2016. Maximum Difference Between Increasing Elements

花花酱 LeetCode 2012. Sum of Beauty in the Array

花花酱 LeetCode 2011. Final Value of Variable After Performing Operations

花花酱 LeetCode 1992. Find All Groups of Farmland