기술나눔

한어Русский языкEnglishFrançaisIndonesianSanskrit日本語DeutschPortuguêsΕλληνικάespañolItalianoSuomalainenLatina

목차

[템플릿] 1차원 접두어 합

[템플릿] 2차원 접두어 합

배열의 중심 인덱스 찾기

self 이외의 배열의 곱

행렬 면적 합계

---

[템플릿] 1차원 접두어 합

무차별 대입 솔루션을 사용하면배열은 매번 총 q번 순회해야 합니다.,그래서시간 복잡도너무 높으므로 이번에는 접두어 합계 배열을 구성합니다.1-n 간격 내의 각 간격의 합은 다음과 같이 저장됩니다. , 처음 n개 항목이 필요하고 dp 접두사 및 배열의 ​​아래 첨자 위치에 직접 액세스해야 합니다. 코드는 아래와 같이 표시됩니다.

#include<iostream>
#include<vector>
using namespace std;
 
int main()
{
	// 读入数据
	int n, q; cin >> n >> q;
	// n + 1 添加了虚拟节点0
	vector<int> arr(n + 1); // 默认全部为0
	for (int i = 1; i <= n; i++)
		cin >> arr[i];
 
	// 预处理出一个前缀和数组
	vector<long long> dp(n + 1); // 防止溢出
	for (int i = 1; i <= n; i++)
		dp[i] = dp[i - 1] + arr[i];
 
	// 使用前缀和数组
	int l = 0, r = 0;
	while (q--)
	{
		cin >> l >> r;
		cout << dp[r] - dp[l - 1] << endl;
	}
	return 0;
}

---

[템플릿] 2차원 접두어 합

전처리접두사 합 행렬은 다음과 같습니다.(1, 1)에서 (i, j) 위치까지의 모든 요소의 합이 dp 배열에 존재합니다.면적 계산 방법, 최종 답을 찾기 위한 코드는 다음과 같습니다.

int main()
{
	// 读入数据
	int n, m, q; cin >> n >> m >> q;
	vector<vector<int>> arr(n + 1, vector<int>(m + 1));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			cin >> arr[i][j];
 
	// 预处理一个前缀和数组
	vector<vector<long long>> dp(n + 1, vector<long long>(m + 1)); // 防止溢出
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
 
	// 使用前缀和数组
	while (q--)
	{
		int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
		cout << dp[x2][y2] - dp[x2][y1 - 1] - dp[x1 - 1][y2] + dp[x1 - 1][y1 - 1] << endl;
	}
	return 0;
}

---

배열의 중심 인덱스 찾기

여기서 극단적인 경우를 참고하세요.n+1 공간 접두사 및 배열을 열 필요가 없습니다., 이 질문의 중앙 첨자로 사용해야 하는 요소가 원본 배열에 있기 때문입니다. 코드는 다음과 같습니다.

class Solution {
public:
	int pivotIndex(vector<int>& nums) {
		int n = nums.size();
		vector<int> f(n), g(n);
		// 预处理前缀和数组  从左向右
		for (int i = 1; i < n; i++)
			f[i] = f[i - 1] + nums[i - 1];
		// 预处理后缀和数组  从右向左
		for (int i = n - 2; i >= 0; i--)
			g[i] = g[i + 1] + nums[i + 1];
		for (int i = 0; i < n; i++)
		{
			if (g[i] == f[i])
				return i;
		}
		return -1;
	}
};

---

self 이외의 배열의 곱

의미는 이전 질문과 유사하지만 경계 케이스 f(0) 및 g(n-1)은 0이 아닌 1로 초기화되어야 한다는 점에 유의해야 합니다. 코드는 다음과 같습니다.

class Solution {
public:
	vector<int> productExceptSelf(vector<int>& nums) {
		int n = nums.size();
		vector<int> f(n), g(n), ret(n);
		// 处理边界情况
		f[0] = 1; g[n - 1] = 1;
		// 预处理前缀积数组  从左向右
		for (int i = 1; i < n; i++)
			f[i] = f[i - 1] * nums[i - 1];
		// 预处理后缀积数组  从右向左
		for (int i = n - 2; i >= 0; i--)
			g[i] = g[i + 1] * nums[i + 1];
		for (int i = 0; i < n; i++)
			ret[i] = f[i] * g[i];
		return ret;
	}
};

---

행렬 면적 합계

참고: 2차원 접두사 및 배열에는 하나의 행과 하나의 열이 더 있어야 합니다. 그렇지 않으면 범위를 벗어난 액세스가 발생합니다. 또한 위치와 일치하도록 dp 배열과 ans 배열 사이의 첨자를 조정해야 합니다. ans[ 0 ][ 0 ] 은 이 위치의 dp [ 1 ][ 1] 에 해당합니다. 코드는 아래와 같이 표시됩니다.

class Solution {
public:
	vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
		int m = mat.size(), n = mat[0].size();  // m 为行 n 为列
		// 预处理一个二维前缀和数组 dp
		vector<vector<int>> dp(m + 1, vector<int>(n + 1));
		for (int i = 1; i <= m; i++)
			for (int j = 1; j <= n; j++)
				dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + mat[i - 1][j - 1] - dp[i - 1][j - 1];
		// 存放答案的二维数组 ans
		vector<vector<int>> ans(m, vector<int>(n));
		for (int i = 0; i < m; i++)
		{
			for (int j = 0; j < n; j++)
			{
				int x1 = max(0, i - k) + 1, y1 = max(0, j - k) + 1;
				int x2 = min(m - 1, i + k) + 1, y2 = min(n - 1, j + k) + 1;
				ans[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
			}
		}
		return ans;
	}
};