某公司笔试编程题

本文主要是介绍某公司笔试编程题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

参加了某公司编程题，这些题都来自牛客网，记录总结吧！

一、蛇形矩阵

题目描述

蛇形矩阵是有1开始的自然数依次排列成的一个上三角矩阵.
接口说明

void GetResult(int Num, int* pResult);
输入参数:
int Num :输入的正整数N
输出参数:
int *pResult: 指向放蛇形矩阵的字符串指针指针指向的内存区域保证有效

样例输入:
4
样例输出:
1 3 6 10
2 5 9
4 8
7

分析

由于题目限定了使用int*数组来存储数据，我们希望根据样例找出坐标关系。
此时坐标矩阵为

0  1  2  3 
4  5  6  7
8  9  10 11
12 13 14 15

我们根据蛇形矩阵的特点，依次得出每次内循环的坐标：

0
4 1
8 5 2
12 9 6 3

比如当现在位于第3行，第一列时，对应绝对坐标为(i-j)*n +j-1 = (3-1)*4+1-1=9，那么要得到下一个坐标时，我们只需让绝对坐标整体减少一行即可：9-4=5=（3-2)*4+1-1，此时也对应了内循环中j的自增。
代码：

#include<cstdio>
#include <iostream>
using namespace std;void GetResult(int Num, int * pResult)
{int n = Num;int *arr = pResult;int number = 1;for (int i = 1; i <= n; i++){for (int j = 1; j <= i; j++){// cout<<((i - j) * n + (j - 1));*(arr + (i - j) * n + (j - 1)) = number++;}cout<<endl;}}int main()
{int n;while(cin >> n){int *ret = new int[n*n];GetResult(n, ret);for (int i = 0; i<n; i++){for (int j = 0; j<n - i; j++){cout << *(ret + i * n + j);if (j<n - i - 1)cout << ' ';}cout << endl;}delete []ret;
}return 0;}

该方法空间复杂度为O(n*n)，并不是最好的办法，后期可以优化。

二、字符串旋转

题目描述

对于一个字符串，和字符串中的某一位置，请设计一个算法，将包括i位置在内的左侧部分移动到右边，将右侧部分移动到左边。

给定字符串A和它的长度n以及特定位置p，请返回旋转后的结果。

测试样例：
"ABCDEFGH",8,4
返回："FGHABCDE"

方法一：
循环移位，每次循环右移一个字符，将最后一个字符放到字符开头。共移动p次。

方法二：
利用字符串的方法substr() 左右切割，然后组合即可。

标准库的string有一个substr函数用来截取子字符串。一般使用时传入两个参数，第一个是开始的坐标（第一个字符是0），第二个是截取的长度。

代码：

#include<string>
#include <iostream>
using namespace std;string rotateString(string A, int n, int p) {string s;for (int i = 0; i < n - p - 1; ++i) {char ch = A[n - 1];for (int j = n - 1; j >= 1; --j) {A[j] = A[j - 1];}A[0] = ch;}s = A;return s;
}string rotateString1(string str, int n, int p) {string leftStr = str.substr(0,p+1);string rightStr = str.substr(p+1,n);return rightStr+leftStr;
}
int main()
{string str = "ABCDEFGH";string s = rotateString(str,8,4);cout<<s<<endl;cout<<rotateString1(str,8,4)<<endl;return 0;}

三、字符串求子串次数。

题目描述

求子串在母串中出现的次数。

测试样例：
输入
aaaaaa
aa
返回：3

代码：

#include<iostream>
#include<string>using namespace std;int main(){string str;string substr;while(cin>>str>>substr){int start = 0;int count = 0;int len = str.length();int sublen = substr.length();while(start+sublen <=len){if(str.substr(start,sublen) == substr){count++;start += sublen;}else{start++;}}cout<<count<<endl;}return 0;
}

这篇关于某公司笔试编程题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---