宁德时代 笔试（软开）

只有三道编程题

1.给一个数，如果为偶数可将该数除2，奇数可将该数加1或者减1，问将该数变为1需要多少步

递归+记忆化搜索 95% 不想改了

#include <bits/stdc++.h>
using namespace std;

unordered_map<int ,int> umap;
int process(int num){
	if(num==1)return 0;
	if(num%2==0){
		if(umap.count(num/2))return 1+umap[num/2];
		int cur = process(num/2);
		umap[num/2] = cur;
		return 1+cur;
	}
	else{
		int l , r;
		if(umap.count(num-1))l = umap[num-1];
		else{
			l = process(num-1);
			umap[num-1] = l;
		}
		if(umap.count(num+1))r = umap[num+1];
		else{
			r = process(num+1);
			umap[num+1] = r;
		}
		return 1+min(l , r);
	} 
}

int main(){
	long cur = 0;
	cin>>cur;
	umap[1] = 0;
	if(cur%2==0)cout<<1+process(cur/2);
	else cout<<1+min(process(cur-1) , process(cur+1));
	return 0;
}

2.给一组数，判断最长几乎有序子序列长度（子序列元素位置不需要连续，即可以删除某些元素）；几乎有序（不能出现三个连续的数x,y,z使得x>=y>=z）

类似单调栈的处理，不过给几乎有序加了一个判断 100%

#include <bits/stdc++.h>
using namespace std;

int process(vector<int> &vec , int l , int r){
	vector<int> dec(r-l+1);
	dec[0] = 0;
	for(int i = 1;  i<r-l+1 ; i++){
		if(vec[i+l]<=vec[l+i-1])dec[i] = 1+dec[i-1];
		else dec[i] = 0;
	}
	stack<int> stk;
	stk.push(vec[l]);
	int res = 1;
	bool flg = false;
	for(int i = 1 ; i<r-l+1 ; i++){
		int cur = vec[i+l];
		if(cur<stk.top()){
			if(!flg){
				stk.push(cur);
				flg = true;
			}
			else{
				stk.pop();
				stk.push(cur);
			}
		}
		else if(cur==stk.top()){
			if(!flg){
				stk.push(cur);
				flg = true;
			}
		}
		else {
			stk.push(cur);
			flg = false;
		}
		res = max(res , (int)stk.size());
	}
	return res;
}

int main(){
	int n , q;
	cin>>n>>q;
	vector<int> vec(n);
	for(int i = 0 ; i < n ; i++){
		cin>>vec[i];
	}
	int l , r;
	vector<int> res(q);
	for(int i = 0 ; i<q ; i++){
		cin>>l>>r;
		--l;
		--r;
		res[i] = process(vec , l , r);
	}
	for(int i = 0 ; i<q ; i++){
		cout<<res[i]<<endl;
	}
	return 0;
} 

3.给一个0/1矩阵，判断面积最大的矩形的位置，输出上边界行数，下边界行数，左边界列数，右边界列数

两个前缀和数组（行、列）一次枚举进行判断 0% 编译没过 （估计是输入不对 本地IDE样例按字符串输入没问题 每次都不给说怎么输入的 服了）

#include <bits/stdc++.h>
using namespace std;


int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	string str;
	getline(cin , str);
	vector<vector<int>> vec;
	vector<int> help;
	for(int i = 0 ; i<str.length() ; i++){
		int cur = str[i];
		if(cur=='0'){
			help.emplace_back(0);
		}
		if(cur=='1'){
			help.emplace_back(1); 
		}
		if(cur==']'&&str[i-1]!=']'){
			vec.emplace_back(help);
			help.clear();
		}
	}
	int n = vec.size() , m = vec[0].size();
	vector<vector<int>> row(n , vector<int>(m));
	for(int i = 0 ; i<n ; i++){
		if(vec[i][0])row[i][0] = 1;
		else row[i][0] = 0;
	}
	for(int i = 0 ; i<n ; i++){
		for(int j = 1 ; j<m ; j++){
			if(vec[i][j])row[i][j] = row[i][j-1]+1;
			else row[i][j] = 0;
		}
	}
	vector<vector<int>> col(n , vector<int>(m));
	for(int i = 0 ; i<m ; i++){
		if(vec[0][i])col[0][i] = 1;
		else col[0][i] = 0;
	}
	for(int j = 0 ; j<m ; j++){
		for(int i = 1 ; i<n ; i++){
			if(vec[i][j])col[i][j] = col[i-1][j]+1;
			else col[i][j] = 0;
		}
	}
	int data = 0;
	vector<int> res(4);
	for(int i = 0 ; i<n ; i++){
		for(int l = 0 ; l<m ; l++){
			if(row[i][l]==0)continue;
			int cur = col[i][l];
			for(int r = l ; r<m ; r++){
				if(row[i][r]==0)break;
				cur = min(cur , col[i][r]);
				data = max(data , cur*(r-l+1));
				if(data==cur*(r-l+1)){
					res[0] = i-cur+1;
					res[1] = i;
					res[2] = l;
					res[3] = r;
				}
			}
		}
	}
	string s = "[";
	for(int i = 0 ; i<4 ; i++){
		s += to_string(res[i]);
		s += ',';	
	}
	s.pop_back();
	s += ']';
	cout<<s; 
	return 0;
}