どうにか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>…

一文字づつmapに入れて、後から1文字しか無いものを確認する class Solution { public: int firstUniqChar(string s) { unordered_map<char, int> m; for(int i=0; s.length()>i; i++){ if(m.find(s[i]) != m.end()){ m[s[i]] ++; } else{ m[s[i]]=1; } } for(int i =0;</char,>…

setを思いつければ簡単。 class Solution { public: int numUniqueEmails(vector<string>& emails) { set<string> num; for(string email: emails){ string checkedEmail; for(int i=0; email[i]!='@'; i++ ){ if(email[i] == '+'){ break; } else if(email[i] == '.'){ cont</string></string>…

最後に+1が必要だった。問題に二分木が書いてあって再帰をすぐに適応できた。 class Solution { public: int maxDepth(TreeNode* root) { if(!root){ return 0; } return max(maxDepth(root->left), maxDepth(root->right))+1; } };

setは重複を許可しないので、一意の値にしたいときに便利。 class Solution { public: vector<int> intersection(vector<int>& nums1, vector<int>& nums2) { set<int> s1; set<int> s2; for(auto val:nums1){ s1.insert(val); } for(auto val:nums2){ s2.insert(val); } vector<int> out; </int></int></int></int></int></int>…

一個ずつ順番に試すブルートフォースはすぐに思いついた。しかし、これだとO(n2)の時間がかかる。 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i</int></int>

一個ずつ順番に試すブルートフォースはすぐに思いついた。しかし、これだとO(n2)の時間がかかる。 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i</int></int>

一個ずつ順番に試すブルートフォースはすぐに思いついた。しかし、これだとO(n2)の時間がかかる。 class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { for(int i = 0; i</int></int>

heapは初めて使用した。以下のdiscussを読んで真似した。大きい方から3つを残すという発想はなかった。 https://leetcode.com/problems/kth-largest-element-in-a-stream/discuss/596093/C%2B%2B-solution-with-understandable-explaination class KthLarges…

stackに入れるのはすぐに思いつくが、取り出しでつまずいた。アドレスを意識できないと解けない問題だった。難易度はeasyだけど、自分はアドレスが意識できていないのがよくわかった。 /** * Definition for singly-linked list. * struct ListNode { * int …

最後にカッコが残った場合にどうすれば良いのかと思ったら、return emptyで良いのか。空ならtrue、残っていればfalse。 class Solution { public: bool isValid(string s) { stack<char> ch; for(int i = 0; s.length()>i; i++){ if(s[i] == '(' || s[i] == '[' ||</char>…

大学院の課題でif, forなどの制御構文と==などの比較演算子を使わずにfizzbuzzをかけというものが出た。成績が出たのでここにも記載する。 辞書型を使用して、3と5それぞれで割ったときの余りが0ならばFizzまたはBuzzを持ってきて、両方を連結するという方法…

きっかけ C++中心にソフトウェア開発をしていますが、最近Web系技術を使うことも増えてきました。しかしながら、Web系に関して社内では静的解析やコードフォーマットの統一はされていませんでした。私が担当になったこの機会に開発環境から揃えていこうと作…

tako-xyz.com

情報セキュリティの講義のまとめ DES : Data Encryption Standard ハードウェアでの実装に向いており、暗号化と複合がほぼ同じ処理。 鍵スケジュール部とデータ攪拌部からなる。データ攪拌部にFeistel構造を採用している。 AES : Advanced Encryption Standa…