必须做的编码问题

2025年4月5日 | 阅读17分钟

在本文中，我们将介绍招聘人员经常询问的一些必做的编码问题。这些问题对于建立编程逻辑也很重要。我们将介绍编程和数据结构方面的每个问题。

1. 数组

a. Kadane's Algorithm

 / Function to find subarray with maximum sum
// arr: input array
// n: size of array
int maxSubarraySum(int arr[], int n){
    int sum=0;
    int maxi=INT_MIN;
    for(int i=0;i<n;i++){
        sum += arr[i];
        maxi=max(sum,maxi);
        if(sum<0)
            sum=0;       
    }
    return maxi;
}

b. 无额外空间合并

  // Function to merge two input arrays
// arr1[], arr2[]: input arrays
// n, m: size of arr1[] and arr2[] respectively
int nextGap(int gap) 
{ 
    if (gap <= 1) 
        return 0; 
    return (gap / 2) + (gap % 2); 
} 
void merge(int arr1[], int arr2[], int n, int m) 
{ 
    int i, j, gap = n + m; 
    for (gap = nextGap(gap); gap > 0; gap = nextGap(gap)) 
    { 
        for (i = 0; i + gap < n; i++) 
            if (arr1[i] > arr1[i + gap]) 
                swap(arr1[i], arr1[i + gap]);   
        for (j = gap > n ? gap-n : 0 ; i < n&&j < m; i++, j++) 
            if (arr1[i] > arr2[j]) 
                swap(arr1[i], arr2[j]);  
        if (j < m) 
        { 
            for (j = 0; j + gap < m; j++) 
                if (arr2[j] > arr2[j + gap]) 
                    swap(arr2[j], arr2[j + gap]); 
        } 
    } 
} 

c. 两个排序数组的并集

  Input: 
N = 5, arr1[] = {1, 2, 3, 4, 5}  
M = 3, arr2 [] = {1, 2, 3}
Output: 1 2 3 4 5
Explanation: Distinct elements including 
both the arrays are: 1 2 3 4 5.
Answer
#include <bits/stdc++.h>
using namespace std;
 // } Driver Code Ends
vector<int> findUnion(int arr1[], int arr2[], int n, int m)
{
    //Your code here
    //return vector with correct order of elements
    vector<int> ans;
    int i=0,j=0;
    if(arr1[i]>arr2[j]){
        ans.push_back(arr2[j]);
        j++;
    }
    else if(arr1[i]<arr2[j]){
        ans.push_back(arr1[i]);
        i++;
    }
    else{
        ans.push_back(arr1[i]);
            i++;
            j++;
    }
    while(i<n && j<m){
        if(arr1[i]==ans.back() && i>=0){
            i++;
            continue;
        }
        if(arr2[j]==ans.back() && j>=0){
            j++;
            continue;
        }
        if(arr1[i]<arr2[j]){
            ans.push_back(arr1[i]);
            i++;
        }
        else if(arr1[i]>arr2[j]){
            ans.push_back(arr2[j]);
            j++;
        }
        else{
            ans.push_back(arr1[i]);
            i++;
            j++;
        }
    }
    while(i<n){
        if(arr1[i]!=ans.back()){
            ans.push_back(arr1[i]);
        }
        i++;
    }
    while(j<m){
        if(arr2[j]!=ans.back()){
            ans.push_back(arr2[j]);
        }
        j++;
    }
    return ans;
}
// { Driver Code Starts.
int main() {	
	int T;
	cin >> T;	
	while(T--){	    
	    int N, M;
	    cin >>N >> M;	    
	    int arr1[N];
	    int arr2[M];	    
	    for(int i = 0;i<N;i++){
	        cin >> arr1[i];
	    }	    
	    for(int i = 0;i<M;i++){
	        cin >> arr2[i];
	    }	    
	    vector<int> ans = findUnion(arr1,arr2, N, M);
	    for(int i: ans)cout<<i<<' ';
	    cout << endl;	    
	}	
	return 0;
}  // } Driver Code Ends

d. 缺失数字序列

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);
cin.tie(NULL)
int missing_number(int a[],int n)
{
	int sum=0;
	for(int i=0;i<n-1;i++)
		sum += a[i];
	int missing = (n*(n+1))/2 - sum;
	return missing;
}
int main()
{
	int n;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n-1;i++)
		cin >> a[i];
	cout << missing_number(a,n) << endl;
}

e. 最长递增子序列

 import java.util.*;
import java.io.*;
class Longest_Increains_Subsquence {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-- > 0){
		    int n = sc.nextInt();
		    int[] arr = new int[n];
		    for(int i = 0; i<n; i++){
		        arr[i] = sc.nextInt();
		    }
		    int l = LIS(arr, n);
		    System.out.println(l);
		}
	}	
	public static int LIS(int[] arr, int n){
	    int[] mat = new int[n];
	    
	    for (int i = 0; i < n; i++ ) 
               mat[i] = 1; 	    
	    for(int i = 1; i<n; i++){
	        for(int j = 0; j<i; j++){
	            if( arr[i] > arr[j] && mat[i] <= mat[j] ){
	                mat[i] = mat[j] + 1;
	            }
	        }
	    }
	    int max = 1;
	    for ( int i = 0; i < n; i++ ) 
            if ( max < mat[i] ) 
              max = mat[i]; 
        return max; 
	}
}

f. 数组中缺失的数字

 import java.util.*;
class MissingNumber {
	public static void main (String[] args) {
		Scanner sc = new Scanner(System.in);
	    int t = sc.nextInt();
	    while(t-- > 0){
	        int n = sc.nextInt();
	        int[] arr = new int[n];
	        for(int i = 0; i<n-1; i++){
	            arr[i] = sc.nextInt();
	        }
	        System.out.println(missing(arr, n));
	    }
	}
	public static int missing(int[] arr, int n){
	    int total = (n * (n+1))/2;
	    for(int i = 0; i<n-1; i++){
	        total -= arr[i];
	    }
	    return total;	    
	}
}

g. 盛水问题

  #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	fast_io;
	if(fopen("input.txt", "r"))
	{
		freopen("input.txt", "r", stdin);
		freopen("output.txt","w",stdout);
	}
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		int a[n+5];
		for(int i=0;i<n;i++)
			cin >> a[i];
		int l[n+5],r[n+5];
		l[0] = a[0];
		for(int i=1;i<n;i++)
			l[i] = max(a[i],l[i-1]);

		r[n-1] = a[n-1];
		for(int i=n-2;i>=0;i--)
			r[i] = max(a[i],r[i+1]);
		int ans = 0;
		for(int i=0;i<n;i++)
			ans += min(l[i],r[i]) - a[i];
		cout << ans << endl;
	}
}

h. 巧克力分配问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n,k;
		cin >> n;
		int a[n];
		int mn = INT_MAX;
		for(int i=0;i<n;i++)
		{
			cin >> a[i];
		}
		cin >> k;
		sort(a,a+n);
		for(int i=0;i<n;i++)
		{
			if( (i+k-1 ) < n && (a[i+k-1] - a[i]) < mn )
				mn = a[i+k-1] - a[i];
		}
		cout << mn << endl;
	}
} 	

2. 分治算法

a. 迭代二分查找

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int binary_search_iterative(int a[],int l,int h,int x)
{
	while(l<=h)
	{
		int mid = (l+h)/2;
		if(a[mid] == x)
			return mid;
		else if(a[mid] > x)
			h = mid-1;
		else
			l = mid+1;
	}
	return -1;
}
int main()
{
	int n,x;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];
	cin >> x;
	int idx = binary_search_iterative(a,0,n-1,x);
	if(idx==-1)
		cout << "Element not found!"<<endl;
	else
		cout << "Element found at index " << idx+1<<endl;

}

b. 递归二分查找

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int binary_search_recursive(int a[],int l,int h,int x)
{
	if(l<=h)
	{
		int mid = (l+h)/2;
		if(a[mid] == x)
			return mid;
		else if(a[mid] > x)
			return binary_search_recursive(a,l,mid-1,x);
		else
			return binary_search_recursive(a,mid+1,h,x);
	}
	return -1;
}
int main()
{
	int n,x;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];
	cin >> x;
	int idx = binary_search_recursive(a,0,n-1,x);
	if(idx==-1)
		cout << "Element not found!"<<endl;
	else
		cout << "Element found at index " << idx+1<<endl;
}

c. 归并排序

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int merge(int a[],int l,int m,int h)
{
	int i,j,k,n1,n2;
	n1 = m-l+1;
	n2 = h-m;
	int L[n1],R[n2];
	for(int i=0;i<n1;i++)
		L[i] = a[i+l];
	for(int j=0;j<n2;j++)
		R[j] = a[j+m+1];
	i=0;
	j=0;
	k=l;
	while(i<n1 && j<n2)
	{
		if(L[i] <= R[j])
			a[k++] = L[i++];
		else
			a[k++] = R[j++];
	}
	while(i<n1)
		a[k++] = L[i++];

	while(j<n2)
		a[k++] = R[j++];
}
int merge_sort(int a[],int l,int h)
{
	if(l < h)
	{
		int m = (l+h)/2;
		merge_sort(a,l,m);
		merge_sort(a,m+1,h);
		merge(a,l,m,h);
	}
}
int main()
{
	int n;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];
	merge_sort(a,0,n-1);
	for(int i=0;i<n;i++)
		cout << a[i] << " ";
	cout << endl;
}

d. 快速排序

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int partition(int a[],int l,int h)
{
	int pivot = a[h];
	int i=l-1;
	for(int j=l;j<h;j++)
	{
		if(a[j] <= pivot)
		{
			i++;
			int temp;
			temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}
	int temp;
	i++;
	temp = a[h];
	a[h] = a[i];
	a[i] = temp;
	return i;
}
int quick_sort(int a[],int l,int h)
{
	if(l < h)
	{
		int pindex = partition(a,l,h);
		quick_sort(a,l,pindex-1);
		quick_sort(a,pindex+1,h);
	}
}
int main()
{
	int n;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];
	quick_sort(a,0,n-1);
	for(int i=0;i<n;i++)
		cout << a[i] << " ";
	cout << endl;
}

3. 贪心算法

a. 最小生成树 (MST)

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define PII pair<int,int> 
int spanningTree(vector <pair<int,int> > g[], int MAX)
{
	priority_queue<PII, vector<PII>, greater<PII> > Q;
	int min_cost = 0;
	int source = 1;
	int visited[MAX];
	for(int i=0;i<MAX;i++)
	    visited[i] = 0;
	Q.push(make_pair(min_cost,source));
	while(!Q.empty())
	{
	    PII temp = Q.top();
	    Q.pop();
	    int u = temp.second;
	    if(visited[u])
	        continue;
	    min_cost += temp.first;
	    visited[u] = 1;
	    for(int v=0;v<g[u].size();v++)
	    {
	        int x = g[u][v].second;
	        if(!visited[x])
	            Q.push(g[u][v]);
	    }
	}
	return min_cost;
}

b. 可能的最大数字

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n,s;
		cin >> n >> s;

		if(n*9 < s || s == 0)
			cout << -1 << endl;
		else
		{
			string num = "";
			for(int i=0;i<n;i++)
			{
				for(int j=9;j>=0;j--)
				{
					if(s >= j)
					{
						char c = ('0' + j);
						num  = num + c;
						s -= j;
						break;
					}
				}
			}
			cout << num << endl;
		}
	}
}

4. 排序

a. 冒泡排序

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int bubble_sort(int a[],int n)
{
	for(int i=0;i<n-1;i++)
	{
		for(int j=0;j<n-1-i;j++)
		{
			if(a[j] > a[j+1])
			{
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
	}
}
int main()
{

	int n;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];

	bubble_sort(a,n);
	for(int i=0;i<n;i++)
		cout << a[i] << " ";
	cout << endl;
}

b. 插入排序

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int insertion_sort(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		int temp = a[i];
		int j=i;
		while(j > 0 && temp < a[j-1])
		{
			a[j] = a[j-1];
			j--;
		}
		a[j]=temp;
	}
}
int main()
{
	int n;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];
	insertion_sort(a,n);
	for(int i=0;i<n;i++)
		cout << a[i] << " ";
	cout << endl;
}

c. 选择排序

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int selection_sort(int a[],int n)
{
	for(int i=0;i<n;i++)
	{
		int mn = a[i];
		int idx = i;
		for(int j=i;j<n;j++)
		{
			if(a[j] < mn)
			{
				mn = a[j];
				idx = j;
			}
		}
		int temp;
		temp = a[i];
		a[i] = a[idx];
		a[idx] = temp;
	}
}
int main()
{
	int n;
	cin >> n;
	int a[n+5];
	for(int i=0;i<n;i++)
		cin >> a[i];
	selection_sort(a,n);
	for(int i=0;i<n;i++)
		cout << a[i] << " ";
	cout << endl;
}

5. 字符串

a. 最长公共子串

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int LCStr(string s1,string s2,int m,int n)
{
	int dp[m+1][n+1];
	int result = 0;
	for(int i=0;i<=m;i++)
	{
		for(int j=0;j<=n;j++)
		{
			if(i==0 || j==0)
				dp[i][j] = 0;
			else if(s1[i-1] == s2[j-1])
			{
				dp[i][j] = dp[i-1][j-1] + 1;
				result = max(result,dp[i][j]);
			}
			else
				dp[i][j] = 0;
		}
	}
	return result;
}
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		string s1,s2;
		int m,n;
		cin >> m >> n;
		cin >> s1 >> s2;
		cout << LCStr(s1,s2,m,n) << endl;
	}}

b. 最长回文子串

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		string s;
		cin >> s;
		int l,h;
		int maxAns = -1;
		int start = -1,end=-1;
		int n = s.size();
		for(int i=1;i<n;i++)
		{
			//Even Length
			l = i-1;
			h = i;
			while(l >= 0 && h < n && s[l] == s[h])
			{
				if(h-l + 1 > maxAns)
				{
					maxAns = h-l+1;
					start = l;
					end = h;
				}
				l--;
				h++;
			}
			//Odd Length
			l=i-1;
			h=i+1;
			while(l >= 0 && h < n && s[l] == s[h])
			{
				if(h-l + 1 > maxAns)
				{
					maxAns = h-l+1;
					start = l;
					end = h;
				}
				l--;
				h++;
			}
		}
		if(maxAns == -1)
		{
		    start = 0;
		    end = 0;
		}
		for(int i=start;i<=end;i++)
			cout << s[i];
		cout << endl;
	}
}

c. 括号匹配检查器

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		string s;
		cin >> s;
		stack<char> st;
		int n = s.size();
		int flag = 1;
		for(int i=0;i<n;i++)
		{
			if(s[i] == '{' || s[i] == '(' || s[i] == '[')
				st.push(s[i]);
			else if(s[i] == '}')
			{
				if(!st.empty())
				{
					if(st.top() == '{')
						st.pop();
					else
				        flag = 0;
				} 
				else
				    flag = 0;
			}
			else if(s[i] == ')')
			{
				if(!st.empty())
				{
					if(st.top() == '(')
						st.pop();
					else
				        flag = 0;
				}
				else
				    flag = 0;
				
			}
			else if(s[i] == ']')
			{
				if(!st.empty())
				{
					if(st.top() == '[')
						st.pop();
					else
				        flag = 0;
				}
				else
				    flag = 0;
			}
		}
		if(st.empty() & flag)
			cout << "balanced" << endl;
		else
			cout << "not balanced" << endl;
	}
}

d. 变位词检查器

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		string s1,s2;
		cin >> s1 >> s2;
		int h[28] = {0},g[28] = {0};
		for(int i=0;i<s1.size();i++)
			h[s1[i]-'a']++;
		for(int i=0;i<s2.size();i++)
			g[s2[i]-'a']++;
		int flag = 1;
		for(int i=0;i<26;i++)
		{
			if(h[i] != g[i])
			{
				flag = 0;
				break;
			}
		}
		if(flag)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

e. 字符串去重

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	string s;
	getline(cin,s);
	while(t--)
	{
		int hash[260] = {0};
		string s;
		getline(cin,s);
		int n = s.size();
		for(int i=0;i<n;i++)
		{
			if(hash[s[i]] == 0)
			{
				cout << s[i];
				hash[s[i]]++;
			}
		}
		cout << endl;
	}
}

f. 字符串反转

#include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		string s;
		stack<string> st;
		cin >> s;
		string tmp;
		tmp="";
		int ctr=0;
		for(int i=0;i<s.size();i++)
		{
			if(s[i] != '.')
				tmp = tmp+s[i];
			else
			{
				st.push(tmp);
				tmp = "";
				ctr++;
			}
			if(i == s.size()-1)
			{
			    st.push(tmp);
				tmp = "";
				ctr++;
			}
		}
		ctr--;
		while(!st.empty())
		{
			cout << st.top() ;
			st.pop();
			if(ctr!=0)
			{
				cout << "." ;
				ctr--;
			} 
			
		}
		cout << endl;
	}
}

6. 图算法

a. 广度优先搜索

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
vector<int> graph[1005];
int visited[1005]={0};
int main()
{
	int V,E;
	cin >> V >> E;
	for(int i=0;i<E;i++)
	{
		int x,y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	int source;
	cin >> source;
	queue<int> q;
	q.push(source);
	while(!q.empty())
	{
		int x = q.front();
		cout << x << " ";
		visited[x] = 1;
		q.pop();
		for(int i=0;i<graph[x].size();i++)
		{
			int node = graph[x][i];
			if(!visited[node])
			{
				q.push(node);
			}
		}
	}
	cout << endl;
}

b. 深度优先搜索

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
vector<int> graph[1005];
int visited[1005]={0};
void dfs(int x)
{
	visited[x] = 1;
	cout << x << " ";
	for(int i=0;i<graph[x].size();i++)
	{
		int node = graph[x][i];
		if(!visited[node])
		{
			dfs(node);
		}
	}
}
int main()
{
	int V,E;
	cin >> V >> E;
	for(int i=0;i<E;i++)
	{
		int x,y;
		cin >> x >> y;
		graph[x].push_back(y);
		graph[y].push_back(x);
	}
	int source;
	cin >> source;
	dfs(source);
	cout << endl;
	
}

c. Dijkstra's 最短路径算法

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
#define PII pair<int,int>
void dijkstra(int graph[MAX][MAX], int s,int V)
{
    int INF = 1e6;
    priority_queue < PII ,vector<PII> , greater<PII> > pq;
    vector<int> dist(V, INF);
    pq.push(make_pair(0,s));
    dist[s] = 0;
    while(!pq.empty())
    {
       pair<int,int> node = pq.top();
       int u = node.second;
       pq.pop();
       
       for(int i=0;i<V;i++)
       {
           if(graph[u][i] > 0)
           {
               int v = i;
               int w = graph[u][i];
               if(dist[v] > dist[u] + w)
               {
                   dist[v] = dist[u] + w;
                   pq.push(make_pair(dist[v],v));
               }
           }
       }
    }
    for(int i=0;i<V;i++)
        cout << dist[i] << " ";
}

d. 到达目的地最短路径问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define PII pair<int,int> 
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int m,n;
		cin >> m >> n;
		int graph[m+5][n+5];
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
				cin >> graph[i][j];
		int p,q;
		cin >> p >> q;
		if(graph[0][0] == 0)
		{
			cout << -1 << endl;
			continue;
		}
		int visited[m+5][n+5];
		map< PII ,int> mp;
		memset(visited,0,sizeof(visited));
		int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
		priority_queue < pair < int , PII > , vector < pair < int , 
PII > > , greater < pair < int , PII > > >pq;
		pq.push(make_pair(0,make_pair(0,0))); 
		visited[0][0] = 1;
		mp[make_pair(0,0)] = 0; 
		int ans = -1; 
		while(!pq.empty())
		{
			pair < int , PII > temp;
			temp = pq.top();
			pq.pop();
			PII node = temp.S;
			int dist = temp.F;
			for(int i=0;i<4;i++)
			{
				int x = dir[i][0] + node.F;
				int y = dir[i][1] + node.S;
				PII newnode = make_pair(x,y);
				if(x >= 0 && x < m && y >=0 && y<n)
				{
					if(!visited[x][y] && graph[x][y])
					{
						visited[x][y] = 1;
						pq.push(make_pair(mp[node] + 1,newnode));
mp[newnode] = mp[node] + 1;		
}					
else if (mp.find(newnode) != mp.end())
{						
mp[newnode] = min(mp[node] + 1,mp[newnode]);
					}
				}
			}
		}
		if(mp.find(make_pair(p,q)) == mp.end())
		    cout << -1 << endl;
	    else
		    cout << mp[make_pair(p,q)] << endl;
	}
}

e. 洪水填充算法

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define PII pair<int,int>
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int m,n;
		cin >> m >> n;
		int graph[m+5][n+5];
		for(int i=0;i<m;i++)
			for(int j=0;j<n;j++)
				cin >> graph[i][j];
		int p,q,k;
		cin >> p >> q >> k;
		queue<PII> qu;
		qu.push(make_pair(p,q));
		int color = graph[p][q];
		graph[p][q] = k;
		while(!qu.empty())
		{
			PII node = qu.front();
			qu.pop();
			int dir[4][2] = {{0,1},{1,0},{-1,0},{0,-1}};
			for(int i=0;i<4;i++)
			{
				int x = dir[i][0] + node.F;
				int y = dir[i][1] + node.S;
				PII newnode = make_pair(x,y);
				if(x >= 0 && x < m && y >=0 && y<n)
				{
					if(graph[x][y] == color)
					{
						graph[x][y] = k;
						qu.push(make_pair(x,y));
					}
				}
			}
		}
		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				cout << graph[i][j] << " ";
			}
		}
		cout << endl;

	}
}

f. 检查路径是否存在

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
#define PII pair<int,int> 
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		cin >> n;
		int graph[n+5][n+5];
		PII source,goal;
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin >> graph[i][j];
				if(graph[i][j] == 1)
					source = make_pair(i,j);
				if(graph[i][j] == 2)
					goal = make_pair(i,j);
			}
		}
		int dir[4][2] = {{1,0},{0,1},{-1,0},{0,-1}};
		queue< PII > q;
		q.push(source);
		int visited[n+5][n+5];
		memset(visited,0,sizeof(visited));
		int flag = 0;
		while(!q.empty())
		{
			PII node = q.front();
			q.pop();
			visited[node.F][node.S] = 1;
			for(int i=0;i<4;i++)
			{
				int x = node.F + dir[i][0];
				int y = node.S + dir[i][1];
				if(graph[x][y] == 2)
				{
					flag = 1;
					break;
				}
				if(x >= 0 && x < n && y >= 0 && y < n)
				{
					if(graph[x][y]==3 
&& !visited[x][y])
					{
					q.push(make_pair(x,y));
					}
				}
			}
			if(flag)
				break;	
		}
		cout << flag << endl;
	}
}

7. 动态规划

a. 背包问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n,W;
		cin >> n;
		cin >> W;
		int wt[n+5];
		int val[n+5];
		for(int i=1;i<=n;i++)
		{
			cin >> val[i];
		}
		for(int i=1;i<=n;i++)
		{
			cin >> wt[i];
		}
		int K[n+1][W+1];
		for (int i = 0; i <= n; i++)
	    {
	       for (int w = 0; w <= W; w++)
	       {
	           if (i==0 || w==0)
	               K[i][w] = 0;
	           else if (wt[i] <= w)
	                 K[i][w] = max(val[i] + K[i-1][w-wt[i]],  K[i-1][w]);
	           else
	                 K[i][w] = K[i-1][w];
	       }
	    }
	    cout << K[n][W] << endl;

	}
}

b. 最长公共子序列

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int LCS(string s1,string s2)
{
    int n1 = s1.size(), n2 = s2.size();
    int dp[n1+1][n2+1];
    for (int i=0;i<=n1;i++)
    {
        for(int j=0;j<=n2;j++)
        {
            if(i == 0 || j == 0)
            {
                dp[i][j] = 0;
            }
            else if(s1[i-1] == s2[j-1])
            {
                dp[i][j] = dp[i-1][j-1] + 1;
            }
            else
            {
                dp[i][j] = max(dp[i][j-1],dp[i-1][j]);
            }
        }
    }
    return dp[n1][n2];
}
int main()
{
    string s1,s2;
    cin >> s1 >> s2;
    cout << LCS(s1,s2) << endl;

}

c. 盒子堆叠问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
bool cmp(vector<int> a,vector<int> b)
{
    return a[1]*a[2] < b[1]*b[2] ;
}
int maxHeight(int height[],int width[],int length[],int n)
{
    vector < vector<int> > boxes;
    for(int i=0;i<n;i++)
    {
        vector<int> box1,box2,box3;
        int h,w,l;
        h = height[i];
        w = width[i];
        l = length[i];
        //box1
        box1.push_back(h);
        box1.push_back(min(w,l));
        box1.push_back(max(w,l));
        boxes.push_back(box1);
        //box2
        box2.push_back(w);
        box2.push_back(min(h,l));
        box2.push_back(max(h,l));
        boxes.push_back(box2);
        //box3
        box3.push_back(l);
        box3.push_back(min(h,w));
        box3.push_back(max(h,w));
        boxes.push_back(box3);
        
    }
    sort(boxes.rbegin(),boxes.rend(),cmp);
    n = boxes.size();
    int dp[n+5];
    for(int i=0;i<n;i++)
    {
        dp[i] = boxes[i][0];
    }
    for(int i=1;i<n;i++)
    {
        for(int j=0;j<i;j++)
        {
            if(boxes[i][1] < boxes[j][1] && boxes[i][2] < boxes[j][2] && dp[i] < dp[j] + boxes[i][0])
            {
                dp[i] = dp[j] + boxes[i][0];
            }
        }
    }
    int mxheight = -1;
    for(int i=0;i<n;i++)
    {
        mxheight = max(mxheight,dp[i]);
    }
    return mxheight;
    
}

d. 斐波那契数列

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{	
	int n;
	cin >> n;
	LL fib[n+5];
	fib[0] = 0;
	fib[1] = 1;
	for(int i=2;i<=n;i++)
		fib[i] = fib[i-1] + fib[i-2];

	for(int i=0;i<=n;i++)
		cout << fib[i] << " ";
	cout << endl;
}

e. 最大尺寸正方形子矩阵

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int M[100][100];
int max_size_submatrix(int m,int n)
{
    int dp[n][m],max_size=0;
    for(int i=0;i<m;i++)
    {
        dp[i][0] = M[i][0];
        max_size = max(dp[i][0],max_size);
    }
    
    for(int i=0;i<n;i++)
    {
        dp[0][i] = M[0][i];
        max_size = max(dp[0][i],max_size);
    }
    for(int i=1;i<m;i++)
    {
        for(int j=1;j<n;j++)
        {
            if(M[i][j] == 1)
            {
                dp[i][j] = min(dp[i-1][j-1],min(dp[i-1][j],dp[i][j-1])) + 1; 
                max_size = max(dp[i][j],max_size);
            }
            else
            {
                dp[i][j] = 0;
            }
        }
    }
    return max_size;
}
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i=0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            cin >> M[i][j];
        }
    }
    cout << max_size_submatrix(m,n)<<endl;
}

f. 可用路径数量

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define PII pair<int,int>
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n,m;
		cin >> n >> m;
		int dp[n+5][m+5];
		for(int i=0;i<n;i++)
			dp[i][0] = 1;
		for(int i=0;i<m;i++)
			dp[0][i] = 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];
		}
		cout << dp[n-1][m-1] << endl;
	}
}

g. 特殊键盘问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define PII pair<int,int>
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int N;
		cin >> N;
		int dp[N+5];
		for(int i=1;i<=min(N,6);i++)
			dp[i] = i;

		for(int i=7;i<=N;i++)
		{
			int ans = 0;
			for(int j=i-3;j>=1;j--)
			{
				int curr = (i-j-1)*dp[j];
				ans = max(ans,curr);
			}
			dp[i] = ans;
		}
		if (N > 75)
			cout << -1 << endl;
		else
			cout << dp[N] << endl;
	}
}

h. 最大加权路径问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int m,n;
		cin >>n;
		m = n;
		int path[m+5][n+5];
		int dp[m+5][n+5];

		for(int i=0;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				cin >> path[i][j];
				dp[i][j] = 0;
			}
		}
		for(int i=0;i<n;i++)
			dp[0][i] = path[0][i];

		for(int i=1;i<m;i++)
		{
			for(int j=0;j<n;j++)
			{
				if(j-1 >=0)
	dp[i][j] = path[i][j] + max(dp[i-1][j],dp[i-1][j-1]);
	if(j+1 < n)
	     dp[i][j] = max(dp[i][j],(path[i][j] + max(dp[i-1][j],dp[i-
1][j+1])));
			}
		}
		int ans =0;
		for(int i=0;i<n;i++)
		{
			ans = max(ans,dp[m-1][i]);
		}
		cout << ans << endl;

	}
}

i. 分段切割问题

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n;
		int x,y,z;
		cin>>n;
	    cin>>x>>y>>z;
	    int dp[n+1];
	    dp[0]=0;
	    for(int i=1;i<=n;i++){
	        dp[i]=INT_MIN;
	    }
	    for(int i=1;i<=n;i++){
	        if(x<=i)
	            dp[i]=max(dp[i],1+dp[i-x]);
	        if(y<=i)
	            dp[i]=max(dp[i],1+dp[i-y]);
	        if(z<=i)
	            dp[i]=max(dp[i],1+dp[i-z]);
	    }
	    cout<<dp[n]<<endl;
	}
}

j. 二项式系数

 #include <bits/stdc++.h>
using namespace std;
#define  LL long long
#define F first
#define S second
#define fast_io ios::sync_with_stdio(false);cin.tie(NULL)
int binomial_coeff(int n,int k)
{
	int dp[n+5][k+5];
	for(int i=0;i<=n;i++)
	{
		for(int j=0;j<=min(i,k);j++)
		{
			if(j == 0 || i == j)
				dp[i][j] = 1;
			else
				dp[i][j] = dp[i-1][j] + dp[i-1][j-1];
		}
	}
	return dp[n][k];
}
int main()
{
	int n,k;
	cin >> n >> k;
	cout << binomial_coeff(n,k) << endl;

}

下一主题定量分析类型

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

博客

必须做的编码问题

1. 数组

a. Kadane's Algorithm

b. 无额外空间合并

c. 两个排序数组的并集

d. 缺失数字序列

e. 最长递增子序列

f. 数组中缺失的数字

g. 盛水问题

h. 巧克力分配问题

2. 分治算法

a. 迭代二分查找

b. 递归二分查找

c. 归并排序

d. 快速排序

3. 贪心算法

a. 最小生成树 (MST)

b. 可能的最大数字

4. 排序

a. 冒泡排序

b. 插入排序

c. 选择排序

5. 字符串

a. 最长公共子串

b. 最长回文子串

c. 括号匹配检查器

d. 变位词检查器

e. 字符串去重

f. 字符串反转

6. 图算法

a. 广度优先搜索

b. 深度优先搜索

c. Dijkstra's 最短路径算法

d. 到达目的地最短路径问题

e. 洪水填充算法

f. 检查路径是否存在

7. 动态规划

a. 背包问题

b. 最长公共子序列

c. 盒子堆叠问题

d. 斐波那契数列

e. 最大尺寸正方形子矩阵

f. 可用路径数量

g. 特殊键盘问题

h. 最大加权路径问题

i. 分段切割问题

j. 二项式系数

相关帖子

全栈开发技术

Bash vs Zsh vs Fish

什么是防火墙身份验证

什么是 BlackArch

Arch 用户存储库

什么是潜在语义索引

设施管理的优缺点

信息技术的特征

Sketch-Up 中的动画

边缘路由器与核心路由器之间有什么区别？

订阅 Tpoint Tech