院校机试刷题第三天：1393矩阵转置、1703最大字串和、1700判断回文数

一、1393矩阵转置

1.题目描述

2.解题思路

也是一道简单的过程模拟题，只需要把输入的行当成列输出即可，只需要将元素存储起来，遍历顺序先遍历列再遍历行输出就行了。

---------------------------------------------------------------------------------------------------------

对于矩阵转置问题，通常有以下几种做法：

1.方阵：原地转置a[i][j] = a[j][i]。

2.非方阵：定义一个新矩阵数组，依次遍历旧数组，让每一行转换为新矩阵的每一列b[i][j] = a[j][i]

3.代码

#include <iostream>
#include <vector>
using namespace std;int main() {int n;while(cin >> n) {vector<vector<int>> a(n, vector<int>(n, 0));for(int i = 0; i < n; i++) {for(int j = 0; j < n; j++) {cin >> a[i][j];}}for(int j = 0; j < n; j++) {for(int i = 0; i < n; i++) {cout << a[i][j] << ' ';}cout << endl;}}return 0;
}

二、1703最大字串和

1.题目描述

2.解题思路

这题代码随想录刷过，贪心算法。也就是依次遍历累加，如果前面的总和为负数，那么一定会拉低后面的元素的总和，所以可以直接抛弃掉此时的元素和，从后面那个元素开始重新计数。

但是要注意可能存在所有元素都是负数的情况，所以判断条件应该为：

sum + a[i] > a[i]

和力扣上不一样的点就在于要存储子串

3.代码

#include <iostream>
#include <vector>
using namespace std;int main() {int n;while(cin >> n) {vector<int> a(n, 0);for(int i = 0; i < n; i++) {cin >> a[i];}vector<int> result;vector<int> finalResult;int sum = 0;int maxSum = 0;for(int i = 0; i < n; i++) {if(sum + a[i] > a[i]) {sum += a[i];result.push_back(a[i]);if(sum > maxSum) {maxSum = sum;finalResult = result;}}else {sum = a[i];result.clear();result.push_back(a[i]);}}for(int i = 0; i < finalResult.size(); i++) {cout << finalResult[i] << ' ';}cout << endl;cout<< maxSum << endl;}return 0;
}

三、1700判断回文数

1.题目描述

2.解题思路

代码随想录也刷过，这题用栈求解，先把前一半入栈，然后依次出栈和后面的元素进行比对即可。

也可以用双指针求解，一个指前面，一个指后面，往中间逼近。

3.代码

#include <bits/stdc++.h>
using namespace std;void judge(string str) {int length = str.length();if(length < 1) {cout << "No"<< endl;return;}int mid = length / 2;stack<int> st;for(int i = 0; i < mid; i++) {st.push(str[i]);}int mid1;if(length % 2 == 1) mid1 = mid + 1;for(int i = mid1; i < length; i++) {int temp = st.top();st.pop();if(temp != str[i]) {cout << "No" << endl;return;}}cout << "Yes" << endl;return;
}int main() {string str;while(cin >> str) {judge(str);}return 0;
}