문서 목록

경계는 모두 1의 최대 정사각형 크기

제목

코드

본위치가 포함되지 않은 누승수조

제목

코드

수조의partition조정

제목

코드

최단 경로 값

제목

코드

수조에 나타나지 않은 최소 정수

제목

코드

수 그룹 정렬 후 인접수의 최대 차이값

제목

코드

경계는 모두 1의 최대 정사각형 크기이다

제목.

N 을 정하다×N의 매트릭스 matrix는 이 매트릭스에서 0과 1 두 가지 값만 있고 최대 정사각형의 변의 길이를 되돌려줍니다.예: 0 1 1 1 1 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 테두리 전체가 1인 최대 사각형 크기는 4×4, 되돌아가다 4

코드

위치별 복잡성은 O(N4), 변경된 복잡성은 O(N3)

#include
#include
#include
using namespace std;

void setBorderMap(vector<vector<int>> &m, vector<vector<int>> &right, vector<vector<int>> &down)
{
	int row = m.size();
	int col = m[0].size();
	if (m[row - 1][col - 1] == 1)
	{
		right[row - 1][col - 1] = 1;
		down[row - 1][col - 1] = 1;
	}
	for (int i = row - 2; i >= 0; i--)
	{
		if (m[i][col - 1] == 1)
		{
			right[i][col - 1] = 1;
			down[i][col - 1] = down[i + 1][col - 1] + 1;
		}
	}
	for (int i = col - 2; i >= 0; i--)
	{
		if (m[row - 1][i] == 1)
		{
			right[row - 1][i] = right[row - 1][i + 1] + 1;
			down[row - 1][i] = 1;
		}
	}
	for (int i = row - 2; i >= 0; i--)
	{
		for (int j = col - 2; j >= 0; j--)
		{
			if (m[i][j] == 1)
			{
				right[i][j] = right[i][j + 1] + 1;
				down[i][j] = down[i + 1][j] + 1;
			}
		}
	}
}

bool hasSizeofBorder(int size, vector<vector<int>> right, vector<vector<int>> down)
{
	for (int i = 0; i < right.size() - size + 1; i++)
	{
		for (int j = 0; j < right[0].size() - size + 1; j++)
		{
			if (right[i][j] >= size && down[i][j] >= size && right[i + size - 1][j] >= size && down[i][j + size - 1] >= size)
				return true;
		}
	}
	return false;
}

int getMaxSize(vector<vector<int>> m)
{
	int row = m.size();
	int col = m[0].size();
	vector<vector<int>>right(row, vector<int>(col, 0));
	vector<vector<int>>down(row, vector<int>(col, 0));
	setBorderMap(m, right, down);
	for (int size = min(row, col); size > 0; size--)
	{
		if (hasSizeofBorder(size, right, down))
			return size;
	}
	return 0;
}

int main()
{
	int row, col;
	cin >> row >> col;
	vector<vector<int>>in(row, vector<int>(col, 0));
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
			cin >> in[i][j];
	}
	int res = getMaxSize(in);
	cout << res << endl;
	getchar();
	return 0;
}

본위 값을 포함하지 않는 누승수 그룹

제목.

성형수 그룹arr를 정하고 이 위치를 포함하지 않는 곱하기 그룹을 되돌려줍니다. 예를 들어arr=[2,3,1,4], [12,8,24,6], 즉 자신을 제외한 모든 위치의 곱하기입니다.소요 시간 복잡도 O(N);추가 공간의 복잡도는 O(1)이다.

코드

두 가지 방법 중 하나는 모든 곱셈을 얻은 후 제법을 하고 제법을 허락하지 않는 경우 두 번째 방법을 참고할 수 있다.

#include
#include
using namespace std;

int* multi1(int* arr, int len)
{
	if (arr == NULL || len < 2)
		return NULL;
	int cnt = 0;
	int all = 1;
	for (int i = 0; i < len; i++)
	{
		if (arr[i] != 0)
			all *= arr[i];
		else
			cnt++;
	}
	int* res = new int[len];
	for (int i = 0; i < len; i++)
		res[i] = 0;
	if (cnt == 0)
	{
		for (int i = 0; i < len; i++)
			res[i] = all / arr[i];
	}
	if (cnt == 1)
	{
		for (int i = 0; i < len; i++)
		{
			if (arr[i] == 0)
				res[i] = all;
		}
	}
	return res;
}

int* multi2(int* arr, int len)
{
	if (arr == NULL || len < 2)
		return NULL;
	int* res = new int[len];
	for (int i = 0; i < len; i++)
		res[i] = 0;
	res[0] = 1;
	for (int i = 1; i < len; i++)
		res[i] = res[i - 1] * arr[i - 1];
	int tmp = 1;
	for (int j = len - 2; j >= 0; j--)
	{
		tmp *= arr[j + 1];
		res[j] *= tmp;
	}
	return res;
}

void print(int* arr, int len)
{
	for (int i = 0; i < len; i++)
		cout << arr[i] << " ";
	cout << endl;
}

int main()
{
	int len;
	cin >> len;
	int* input = new int[len];
	for (int i = 0; i < len; i++)
		cin >> input[i];
	int* res1 = new int[len];
	int* res2 = new int[len];
	res1 = multi1(input, len);
	res2 = multi2(input, len);
	print(res1, len);
	print(res2, len);
	getchar();
	return 0;
}

배열의 파티션 조정

제목.

질서정연한 수조를 주고 arr를 조정하여 이 수조의 왼쪽 부분에 중복된 요소가 없고 승차순이 없으며 오른쪽 부분의 질서가 있는지 보장할 필요가 없습니다.보충 제목: 하나의 수조arr를 정합니다. 그 중에서 0, 1, 2 세 개의 값만 포함할 수 있습니다. arr의 정렬을 실현하십시오.요구: 시간 복잡도 O(N), 추가 공간 복잡도 O(1).

코드

#include
using namespace std;

void swap(int* &arr, int index1, int index2)
{
	int tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

void leftUnique(int* arr, int len)
{
	if (arr == NULL || len < 2)
		return;
	int u = 0;
	int i = 1;
	while (i != len)
	{
		if (arr[i++] != arr[u])
			swap(arr, ++u, i - 1);
	}
}

void sort(int* &arr, int len)
{
	if (arr == NULL || len < 2)
		return;
	int left = -1;
	int index = 0;
	int right = len;
	while (index < right)
	{
		if (arr[index] == 0)
			swap(arr, ++left, index++);
		else if (arr[index] == 2)
			swap(arr, index, --right);
		else
			index++;
	}
}

int main()
{
	int len;
	cin >> len;
	int* in = new int[len];
	for (int i = 0; i < len; i++)
		cin >> in[i];
	leftUnique(in, len);
	for (int i = 0; i < len; i++)
		cout << in[i] << " ";
	cout << endl;
	getchar();
	return 0;
}

최단 경로 값

제목.

정형 매트릭스 matrix를 지정하면 하나의 네트워크를 표시하고 1은 길이 있고 0은 길이 없다. 모든 위치는 경계를 넘지 않으면 상하 좌우 네 방향이 있다. 왼쪽 상단에서 오른쪽 하단까지의 가장 짧은 통로 값을 구한다.예를 들어 matrix의 경우: 1 0 1 1 1 1 0 1 1 1 1 1 1 0 0 0 0 0 1 라우팅 루트 12 개 1로 구성되어 12로 돌아갑니다.

코드

#include
#include
#include
using namespace std;

void walkTo(int pre, int toR, int toC, vector<vector<int>> &m, vector<vector<int>>&mp, queue<int> &rQ, queue<int>&cQ)
{
	if (toR < 0 || toR >= m.size() || toC < 0 || toC >= m[0].size() || m[toR][toC] != 1 || mp[toR][toC] != 0)
		return;
	mp[toR][toC] = pre + 1;
	rQ.push(toR);
	cQ.push(toC);
}

int minPath(vector<vector<int>> m)
{
	if (m.size() < 1 || m[0].size() < 1 || m[0][0] != 1 || m[m.size() - 1][m[0].size() - 1] != 1)
		return 0;
	int res = 0;
	int row = m.size();
	int col = m[0].size();
	vector<vector<int>> mp(row, vector<int>(col, 0));
	mp[0][0] = 1;
	queue<int> rQ, cQ;
	int r = 0;
	int c = 0;
	rQ.push(r);
	cQ.push(c);
	while (!rQ.empty())
	{
		r = rQ.front();
		c = cQ.front();
		rQ.pop();
		cQ.pop();
		if (r == row - 1 && c == col - 1)
			return mp[r][c];
		walkTo(mp[r][c], r - 1, c, m, mp, rQ, cQ);
		walkTo(mp[r][c], r + 1, c, m, mp, rQ, cQ);
		walkTo(mp[r][c], r, c + 1, m, mp, rQ, cQ);
		walkTo(mp[r][c], r, c - 1, m, mp, rQ, cQ);
	}
	return res;
}

int main()
{
	int row, col;
	cin >> row >> col;
	vector<vector<int>>in(row, vector<int>(col, 0));
	for (int i = 0; i < row; i++)
	{
		for (int j = 0; j < col; j++)
			cin >> in[i][j];
	}
	int res = minPath(in);
	cout << res << endl;
	getchar();
	return 0;
}

배열에 나타나지 않는 최소 정수

제목.

무질서 성형 수조arr를 지정하여 수조에 나타나지 않은 최소 정수를 찾습니다.예:arr=[-1,2,3,4].돌아가다arr=[1,2,3,4], 5 반환;

코드

#include
using namespace std;

void swap1(int* &arr, int index1, int index2)
{
	int tmp = arr[index1];
	arr[index1] = arr[index2];
	arr[index2] = tmp;
}

int minNum(int* arr, int len)
{
	int l = 0;
	int r = len;
	while (l < r)
	{
		if (arr[l] == l + 1)
			l++;
		else if (arr[l] <= l || arr[l] > r || arr[arr[l] - 1] == arr[l])
			arr[l] = arr[--r];
		else
			swap1(arr, l, arr[l] - 1);
	}
	return l + 1;
}

int main()
{
	int len;
	cin >> len;
	int* input = new int[len];
	for (int i = 0; i < len; i++)
		cin >> input[i];
	int res = minNum(input, len);
	cout << res << endl;
	getchar();
	return 0;
}

그룹 정렬 후 인접수의 최대 차이

제목.

정렬된 두 수의 최대 차이를 되돌려주는 정형수 그룹arr를 지정합니다.rr=[9,3,1,10], 정렬 후 [1,3,9,10], 인접한 두 수 사이의 최대 삽입값은 6이고 6으로 되돌아오면 된다.만약 arr 길이가 N이라면, 요구 시간의 복잡도는 O (N) 이다.통 정렬 사상

코드

#include
#include
using namespace std;
int bucket(long num, long len, long Min, long Max)
{
	return (int)((num - Min) * len / (Max - Min));
}

int maxGap(int* arr, int len)
{
	if (arr == NULL || len < 2)
		return 0;
	int Min = INT_MAX;
	int Max = INT_MIN;
	for (int i = 0; i < len; i++)
	{
		Min = min(Min, arr[i]);
		Max = max(Max, arr[i]);
	}
	if (Min == Max)
		return 0;
	bool* hasNum = new bool[len + 1];
	int* maxs = new int[len + 1];
	int* mins = new int[len + 1];
	for (int i = 0; i <= len; i++)
	{
		hasNum[i] = false;
		maxs[i] = 0;
		mins[i] = 0;
	}

	int bid = 0;
	for (int i = 0; i < len; i++)
	{
		bid = bucket(arr[i], len, Min, Max);
		mins[bid] = hasNum[bid] ? min(mins[bid], arr[i]) : arr[i];
		maxs[bid] = hasNum[bid] ? max(maxs[bid], arr[i]) : arr[i];
		hasNum[bid] = true;
	}
	int res = 0;
	int lastMax = 0;
	int i = 0;
	while (i <= len)
	{
		if (hasNum[i++])
		{
			lastMax = maxs[i - 1];
			break;
		}
	}
	for (; i <= len; i++)
	{
		if (hasNum[i])
		{
			res = max(res, mins[i] - lastMax);
			lastMax = maxs[i];
		}
	}
	return res;
}

int main()
{
	int len; 
	cin >> len;
	int* input = new int[len];
	for (int i = 0; i < len; i++)
		cin >> input[i];
	int res = maxGap(input, len);
	cout << res << endl;
	getchar();
	return 0;
}