這周抽了點時間寫了這3道題，其實發現，中等題目與簡單題目，都是相對比較簡單的。有些中等的也還好，現在還是感覺困難的比較有意思，哈哈。
第十一題：盛最多水的容器
解題思路：
從最開始看到題目，其實就如同找到最大值一樣，面積不就是底×高，高為min（x,y）.t為兩個下標距離
從傳統遍歷的話，設置I，j，這樣的話時間複雜度為O(n^2).但是找到最大值的例子可是O（n），
於是便想t在最大的時候是確定的，數組確定下來後。不妨左右開始記錄下標，向中間進攻。
於是這就是雙指針法，專門用來確定邊界的一些問題。
當 x <= y ,我們移動y 為y1: 由min(x,y) == x; t移動一下，為t1 < t;
當 y1 <= y, min(x, y1) <= min(x, y)
當 y1 > y min(x,y1) == x == min(x,y)
面積 s = min(x,y1)*t1 <= min(x,y)*t1 < min(x,y)*t;
所以移動大的數據，得到的結果比開始的小，所以不能移動大的，
當移動小的，x <= y 我們移動小的x 為x1,由min(x,y) == x t移動一下，為t1 < t;
當 x1 <= x min(x1, y) <= min(x, y) 結果當然比這個小了，
只有 x1 > x的時候 面積才不缺定，才有可能比較大，這個不就是記錄最大值問題，
遍歷下來也就是線性的 O(n);
int maxArea(vector<int>& height) {
int l = 0, r = height.size() - 1;
int ans = 0;
while (l < r) {
int area = min(height[l], height[r]) * (r - l);
ans = max(ans, area);
if (height[l] <= height[r]) {
++l;
}
else {
--r;
}
}
return ans;
}
void testmaxArea()
{
vector<int> height = {1,8,6,2,5,4,8,3,7};
int data = maxArea(height);
cout << "the height is " << data << endl;
}輸出結果：
the height is 49第十二題：整數轉羅馬數字
解題思路：
當出現這樣的情況的時候，就單獨這樣的題目，一個轉化成另一個的時候，可以想到hashmap
規定後，做除法，匹配對應的字母，就可以了，時間複雜度O（1）
也是貪心算法，採用最大方式來表示。
string intToRoman(int num) {
int values[] = { 1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1 };
string reps[] = { "M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I" };
string res;
for (int i = 0; i < 13; i++) //這裏不使用圖裏的count了，一遍一遍來就行了
while (num >= values[i])
{
num -= values[i];
res += reps[i];
}
return res;
}第十三題：羅馬數字轉整數
上個題目是相互轉換，採用打表方式，也就是hashmap，典型的費空間省時間。題目比較簡單 主要考慮的是
通過觀察我們發現，只有在遇到特殊情況時，兩個字符中左邊的字符小於右邊的字符，
且等於右邊的字符代表的數減左邊字符代表的數。 比如 CM 等於 1000 - 100，XC 等於 100 - 10；
int romanToInt(string s) {
int result = 0;
map<char, int> luomab = {
{ 'I',1 },
{ 'V',5 },
{ 'X',10 },
{ 'L',50 },
{ 'C',100 },
{ 'D', 500 },
{ 'M', 1000 }
};//初始化哈希表
for (int i = 0; i < s.length(); i++)
{
if (luomab[s[i]] < luomab[s[i + 1]])
result -= luomab[s[i]];
else
{
result += luomab[s[i]];
}
}
return result;
}
void testromanToInt()
{
string s = "MCMXCIV";
int data = romanToInt(s);
cout << s <<" is "<< data << endl;
}輸出結果：
結果：
MCMXCIV is 1994
題目相對比較簡單吧，要注意點細節，能解決問題才是本能。週一沒有寫成，慢慢來吧，爭取學習到更多的東西。每天都有進步的感覺十分充實。一起加油。
