1. A blank filling question of Shang Tang (I think it can be changed to programming question)
#include <iostream>
using namespace std;
int count = 0;
void Perm(int a[], int k, int m) //Perm functions are used to solve permutation problems
{
int i;
if(k == m)
{
if(a[5] > a[0] && a[6] > a[1])
{
if(a[7] > a[2] && a[8] > a[3] && a[9] > a[4])
{
if(a[4] > a[3] && a[3] > a[2] && a[2] > a[1] && a[1] > a[0])
{
if(a[9] > a[8] && a[8] > a[7] && a[7] > a[6] && a[6] > a[5])
{
for(i = 0; i <= 4; i++)
cout << "[" <<a[i] << "]";
cout <<endl;
for(i = 5; i <= 9; i++)
cout << "[" << a[i] << "]";
cout <<endl;
cout << "-----------------" <<endl;
count++;
}
}
}
}
}
else
for(int i = k; i <= m; i++)
{
swap(a[k],a[i]);
Perm(a, k+1, m);
swap(a[k], a[i]);
}
}
template <class T>
void swap(T &a, T &b)
{
T temp = a;
a = b;
b = temp;
}
int main()
{
int a[10] = {5,4,3,2,1,6,7,8,9,10};
Perm(a, 0, 9);
cout << "Count:" << count <<endl;
return 0;
}If this problem can be solved by permutation algorithm, it will be much easier. After that, we can add restrictions to permutation algorithm.
2. The programming problem of cutting hundreds of words
#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;
int Asd(char *p, char *q, int sumlen, int len, int n)
{ //*p points to array, * q points to string
int i,j,flag,k = 0; //sumlen is the length of the array, len is the length of the input string, n is the column
for(j = 0; j < len; j++)
{
flag = 0;
for(i = 0; i < sumlen; i++)
{
if(p[i] == q[j] && j == 0)
{
flag = 1; //flag
}
if(p[i] == q[j] && (p[i-1] == q[j-1] || p[i+1] == q[j-1] || p[i-n] == q[j-1] || p[i+n] == q[j-1]))
{
flag = 1;
if(flag == 1 && j == len-1)
{
return 1;
}
}
}
if(flag == 0)
{
break;
return 0;
}
}
}
int main()
{
int i = 0,m,n,sum;
char *p;
char a;
string s1;
cin >> m >> n;
sum = m*n;
p = new char[sum]; //General operations, creating arrays
int j = sum;
while(j > 0) //input
{
cin >> a;
if(a >= 'A' && a <= 'Z' || a >= 'a' && a <= 'z')
{
p[i++] = a;
j--;
}
}
cin >> s1;
int strlength = s1.length();
const char *r = s1.data();
char *q = const_cast<char*>(r); //string to char*
int reasult = Asd(p, q, sum, strlength, n);
if(reasult == 1)
cout << "true" <<endl;
else
cout << "false" <<endl;
return 0;
}
It's good to understand the questions, it's not difficult as a whole. There is a section of code where string is converted to const char *, which can be avoided. I just want to use the following data() function to write this.
3.thoughtworks
#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
void Change(char *mat, int *asd, int q, int w);
void Display(char *mat, int x, int m)
{
int i;
for(i = 0; i < x; i++)
{
if(i%(2*m+1) == 0 && i > 0)
cout <<endl;
cout << "[" << mat[i] << "]" << " ";
}
}
void Initall(char *mat, int x)
{
int i;
for(i = 0; i < x; i++)//Initialization wall
{
mat[i] = 'W';
}
}
void Init(char *mat, int n, int m)
{
int i,j,k;
for(i = 1; i < 2*n+1; i = i+2)
{
for(j = 1; j < 2*m+1; j = j+2)
{
*(mat + i*(2*m+1) + j) = 'R';
}
}
}
void Input(char *mat, int q, int w)
{
char str[100] = "0,1 0,2;1,0 1,1;1,2 1,1;2,1 2,0;0,0 1,0;0,2 1,2;1,1 2,1;1,2 2,2;0,1 1,1";
char *p1 = str;
char *p2, *p3, *p4;
int asd[4] = {0};
int a,x,y,length,k = 0,i = 0;
printf("%s\n", str);
int len = strlen(str);
p2 = strtok(p1, ";");
while((len > 0) && (p2 = strtok(p1, ";")) != (char *)NULL)
{
p1 += strlen(p2) +1;
len -= strlen(p2) +1;
length = strlen(p2)+1;
while(length > 0 && (p3 = strtok(p2, " ")) != (char *)NULL)
{
p2 += strlen(p3) + 1;
length -= strlen(p3) + 1;
if (i == 4)
i = 0;
if (k == 4)
k = 0;
while((p4 = strtok(p3, ",")) != (char *)NULL)
{
a = atoi(p4);
asd[i++] = a;
p3 = (char *)NULL;
k++;
if (i == 4 && k == 4)//Determine when to transmit data
{
Change(mat, asd, q, w);
}
}
}
}
}
void Change(char *mat, int *asd, int q, int w)
{
int a,b,x,y;
int m,n;
a = asd[0];
b = asd[1];
x = asd[2];
y = asd[3];
if(a == x || b == y)//This is the relationship between the top, the bottom, the left and the right
{
if(a == x)//Row equality
{
m = 2*a+1;
if(b < y)
n = 2*b+2; //n is the converted column
else
n = 2*y+2;
*(mat + (m*(2*w+1)) + n) = 'R';
}
else//Column equality
{
n = 2*b+1;
if(a < y)
m = 2*(a)+2;
else
m = 2*(y)+2;
*(mat + (m*(2*w+1)) + n) = 'R';
}
}
else
{
cout << "Maze format error!" <<endl;
}
}
int main()
{
int n,m;//n is row, m is column
char *p;
cout << "Enter number of rows and columns:";
cin >> n >> m;
int x = (2*n+1)*(2*m+1);
p = new char[x];
Initall(p, x);
cout << "Output:" <<endl;
Init(p, n, m);
Input(p, n, m);
Display(p, x, m);
cout <<endl;
return 0;
}
This is the test code. As long as the input is modified as follows, the difficulty is the segmentation of strings (don't care about the amount of code and the complexity of time and space, and there's no intention to optimize when you do it).
4. Programming problems of Jingdong
#include <iostream>
#include <vector>
#include <algorithm>
#define N 20000
using namespace std;
int n_temp[N], temp_to[N], f_temp[N], res, temp_v;
int x[N], y[N];
int tot = 0, po, mtemp;
void fundfs(int u, int bu, int dis, int index_x, int index_y)
{
if (dis>mtemp) { mtemp = dis; po = u; }
for (int e = f_temp[u]; e; e = n_temp[e])
{
temp_v = temp_to[e];
if (temp_v != bu && (!((u == index_x && temp_v == index_y) || (u == index_y && temp_v == index_x))))
{
fundfs(temp_v, u, dis + 1, index_x, index_y);
}
}
}
void funcreate(int a, int b)
{
tot++;
n_temp[tot] = f_temp[a];
f_temp[a] = tot;
temp_to[tot] = b;
}
int main()
{
int n;
cin >> n;
for (int i = 0; i<n - 1; ++i)
{
cin >> x[i] >> y[i];
funcreate(x[i], y[i]);
funcreate(y[i], x[i]);
}
for (int i = 0; i<n - 1; ++i)
{
mtemp = 0; po = 0;
fundfs(x[i], 0, 0, x[i], y[i]);
fundfs(po, 0, 0, x[i], y[i]);
int tmp = mtemp; mtemp = 0; po = 0;
fundfs(y[i], 0, 0, x[i], y[i]);
fundfs(po, 0, 0, x[i], y[i]);
if (tmp*mtemp>res) res = tmp*mtemp;
}
cout << res << endl;
return 0;
}
I'm still reading the code written by Daniel on the Internet. (let's tidy up so much first, and keep updating)