【2020.5.7今日のプログラミング】LeetCode 121&122.株を売買する最良のタイミング+LeetCode 94.ツリーの中順ループ(非再帰的実装)
LeetCode 121.株を売買する最良のタイミングI
単純題:配列が与えられ、そのi番目の要素は与えられた株のi日目の価格である.最大1つの取引(株を1回購入して売ること)しか許可されていない場合は、取得できる最大利益を計算するアルゴリズムを設計します.注意:株を買う前に 株を売ることはできません.例: 入力:[7,1,5,3,6,4]出力:5解釈:2日目(株価=1)に購入し、5日目(株価=6)に売却し、最大利益=6-1=5.利益は7-1=6ではなく、販売価格が購入価格より大きい必要があるため、注意してください.同時に、購入前に株を売ることはできません.メソッド:ダイナミックプランニング. cppコード実装: 時間複雑度:O(n) 空間複雑度:O(1) LeetCode 122.株式売買のベストタイミングII
単純題:配列が与えられ、そのi番目の要素は与えられた株のi日目の価格である.あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません). 例: 入力:[7,1,5,3,6,4]出力:7解釈:2日目(株価=1)に購入し、3日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.その後、4日目(株価=3)に購入し、5日目(株価=6)に売却し、この取引所は利益=6-3=3を得ることができる.方法:貪欲アルゴリズム(正直に言うとまだ貪欲アルゴリズムがよく分かりませんが、この問題は分かりました). cppコード実装: 時間複雑度:O(n) 空間複雑度:O(1) LeetCode 94.ツリーの中順ループ(非再帰)
中程度題:二叉木を与え、その中序遍歴を返す. 例: 入力:[1,null,2,3]出力:[1,3,2]方法:補助スタックを用いて非再帰中シーケンス遍歴を実現する. cppコード実装: 時間複雑度:O(n) 空間複雑度:O(n) 【最后に书きます】たくさん前に练习した问题を持ってきて见る时、やはり书けないで、とても伤つけて、しかし仕方がなくて、温故知新、绝えず练习を缲り返して、自分に绝えず熟知させます.毎日パソコンの前に座って頭が疲れて、みんな麻痺しています.今日は1日の雨がしとしとと降って、雨が降る时いつも感伤して、多くのことを考えます~~~
単純
class Solution
{
int maxProfit(vector<int>& prices)
{
if(prices.size() <= 1)
return 0;
int maxP = 0;
int minP = prices[0];
for(int i = 1; i < prices.size(); i++)
{
maxP = max(maxP, prices[i] - minP);
minP = min(minP, prices[i]);
}
return maxP;
}
};
単純
class Solution
{
int maxProfit(vector<int>& prices)
{
if(prices.size() <= 1)
return 0;
int maxP = 0;
for(int i = 1; i < prices.size(); i++)
{
int temp = prices[i] - prices[i - 1];
if(temp > 0)
maxP += temp;
}
return maxP;
}
};
中程度
class Solution
{
vector<int> inorderTraversal(TreeNode* root)
{
vector<int>res;
if(root == NULL)
return res;
stack<TreeNode*>st;
TreeNode* ptr = root;
while(!st.empty() || ptr != NULL)
{
while(ptr != NULL)
{
st.push(ptr);
ptr = ptr->left;
}
if(!st.empty())
{
ptr = st.top();
res.push_back(ptr->val);
st.pop();
ptr = ptr->right;
}
}
return res;
};
};