13. Roman to Integer
题目描述：
罗马数字包含以下七种字符：I， V， X， L，C，D 和 M。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：
I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。
给定一个罗马数字，将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: C = 100, L = 50, XXX = 30, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
思路：
这个要用到map数据结构，还要判断有没有左减的情况
代码
class Solution {
public:
int romanToInt(string s) {
map<char,int> m;
m.insert(make_pair('I',1));
m.insert(make_pair('V',5));
m.insert(make_pair('X',10));
m.insert(make_pair('L',50));
m.insert(make_pair('C',100));
m.insert(make_pair('D',500));
m.insert(make_pair('M',1000));
int res = 0;
for(int i=0; i<s.size(); )
{
if(m[s[i]] < m[s[i+1]]) // 左减
{
res += m[s[i+1]]-m[s[i]];
i+=2;
}
else
{
res += m[s[i]];
++i;
}
}
return res;
}
};
566. 重塑矩阵
题目描述
在MATLAB中，有一个非常有用的函数 reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。
给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。
重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。
如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。
示例 1:
输入:
nums =
[[1,2],
[3,4]]
r = 1, c = 4
输出:
[[1,2,3,4]]
解释:
行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。
示例 2:
输入:
nums =
[[1,2],
[3,4]]
r = 2, c = 4
输出:
[[1,2],
[3,4]]
解释:
没有办法将 2 * 2 矩阵转化为 2 * 4 矩阵。 所以输出原矩阵。
思路
这个题没什么难的
代码
class Solution {
public:
vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) {
if(r*c!=nums.size()*nums[0].size())
return nums;
vector<int> tmp;
for(int i = 0;i<nums.size();i++)
{
for(int j = 0;j<nums[0].size();j++)
tmp.push_back(nums[i][j]);
}
vector<int> ret[r];
vector<vector<int> > rett;
int count = 0;
for(int i = 0;i<tmp.size();i++)
{
if(count<c)
{
ret[i/c].push_back(tmp[i]);
count++;
}
else
{
ret[i/c].push_back(tmp[i]);
count=1;
}
}
for(int i = 0;i<r;i++)
rett.push_back(ret[i]);
return rett;
}
};
637. Average of Levels in Binary Tree
题目描述：
给定一个非空二叉树, 返回一个由每层节点平均值组成的数组.
示例 1:
输入:
3
/
9 20
/
15 7
输出: [3, 14.5, 11]
解释:
第0层的平均值是 3, 第1层是 14.5, 第2层是 11. 因此返回 [3, 14.5, 11].
思路
这个是树的层次遍历，要借助队列。其中，我们定义两个指针，now，last，来标记是否为一层的数据。结束循环的标志是队列为空的时候。
代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<double> averageOfLevels(TreeNode* root) {
queue<TreeNode*> q;
double result = 0;
int count = 0;
q.push(root);
TreeNode* now=root;
TreeNode* last = root;
vector<double> ret;
while(!q.empty())
{
if(now!=last)
{
result += now->val;
count++;
if(now->left)
q.push(now->left);
if(now->right)
q.push(now->right);
q.pop();
now = q.front();
}
else
{
result += now->val;
count ++;
if(now->left)
q.push(now->left);
if(now->right)
q.push(now->right);
q.pop();
now = q.front();
last = q.back();
ret.push_back(result/count);
result = 0.0;
count = 0;
}
}
return ret;
}
};
