2021-09-01から1ヶ月間の記事一覧
どうにかreverseを使えないかと思ったが自力では考えつかなかった。 https://leetcode.com/problems/reverse-string-ii/discuss/1354754/C%2B%2B-oror-Easy-Solution-oror-91 場合分け class Solution { public: string reverseStr(string s, int k) { int n…
シンプルではあるが難しい https://leetcode.com/problems/maximum-number-of-occurrences-of-a-substring/discuss/457717/Simple-Sliding-Window-C%2B%2B-Solution class Solution { public: int maxFreq(string s, int maxLetters, int minSize, int maxSi…
下記を見てsetを使う方法とsliding windowを使う方法を学んだ。 https://leetcode.com/problems/longest-substring-without-repeating-characters/discuss/1275071/C%2B%2B-oror-100-faster-Simple-approach-with-two-methods set class Solution { public: …
stackで貯めていき、stackのtopと同じ文字がきたら、popする。 '''cpp class Solution { public: string removeDuplicates(string s) { stackst; for(char i:s) { if(st.size() == 0) { st.push(i); } else if(i == st.top()) { st.pop(); } else { st.push(…
substrで切り取って、一文字目を足せば良いのか https://leetcode.com/problems/rotate-string/discuss/947059/C%2B%2B-or-Simple-Solution-or-Faster-than-100 class Solution { public: bool rotateString(string s, string goal) { int len = goal.size()…
Sliding Windowを用いた方法 s1をソート sliding window法を用いて、s1の長さ分だけs2の文字をソートしていく https://leetcode.com/problems/permutation-in-string/discuss/1385457/Very-Easy-C%2B%2B-Solution class Solution { public: bool checkInclus…
sortを使う方法 '''cpp class Solution { public: bool isAnagram(string s, string t) { sort(s.begin(), s.end()); sort(t.begin(), t.end()); if(s ==t){ return true; } else{ return false; } } }; unordered_mapに入れてから比較 class Solution { pub…
stringにまつわるコーディング試験を行うことになったのでやってみる。 class Solution { public: void reverseString(vector<char>& s) { vector<char> reverseS; for(int i = s.size()-1; i>=0; i-- ) { reverseS.push_back(s[i]); } s= reverseS; } }; Runtime: 53 ms</char></char>…
nums[i]が0でないときに、nums[i]より前にある0といれかえる class Solution { public: void moveZeroes(vector<int>& nums) { int swapObj=0; for(int i=0;i</int>
targetSumの値からtreeの値をrootから引いていく。0になったときにその下にノードがなければtrue。 class Solution { public: bool hasPathSum(TreeNode* root, int targetSum) { if(root == nullptr){ return false; } targetSum = targetSum-root->val; if…
与えられた配列の中心をルートにする 左側にルートより小さい値、右側に大きな値の枝を作る 1-2を繰り返す 参考1 https://qiita.com/mhiro216/items/49d244dd9da1d6e6f70d 参考2 https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/…
kadane algorithmの応用で行けました class Solution { public: int maxProfit(vector<int>& prices) { int maxPro = INT_MIN; int temPro = 0; int minBuyPrice =INT_MAX; for(int i= 0; i <prices.size(); i++) { minBuyPrice = min(prices[i], minBuyPrice); temPro=max(temPro, prices[i]-minBuyPrice); if(temPro>maxPro) { max…</prices.size();></int>
https://leetcode.com/problems/maximum-subarray/ 与えられた値を1つずつ足していき、最も大きな値を選ぶ総当りは思いついたが、O(ｎ2)で遅い。 部分配列をO(ｎ)で計算するKadane Algorithm というアルゴリズムがあるようでした。 Kadaneのアルゴリズム—（…
root1,2のどちらかが存在しない場合はもう一方のTreeNodeを返し、両方のTreeNodeが存在しない場合は0を、そして両方のTreeNodeが存在する場合は数値を足す class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(!root1 &&…
最大深度を求めるより全然難しい。左右どちらかが、なければもう一方を探索していく。 class Solution { public: int minDepth(TreeNode* root) { if(!root) { return 0; } if (root->left == NULL) { return minDepth(root->right) +1 ; } if (root->right …
普通にサーチしたら下記の結果となったが、O(log n)で作れとあった。これだとO(n)である。バイナリサーチならば条件を満たすらしいので下に作成。 普通の class Solution { public: int searchInsert(vector<int>& nums, int target) { int len = nums.size(); if</int>…
