LeetCodeのStack解いてみた
解いたコード
- 前回に引き続きStackカテゴリの問題を解いてみた
- コーディング面接対策のために解きたいLeetCode 60問 | 新井康平
- C#で書いてます
Problem1
Solution
public class Solution { private Stack<char> Stack = new Stack<char>(); private Dictionary<char, char> Dictionary = new Dictionary<char, char>() { {')', '('}, {'}', '{'}, {']', '['}, }; public bool IsValid(string s) { try { // 1文字ずつよんでopen bracketであればstackに積む // close bracketであればstackから取り出し対応するものであれば処理を継続。そうでなければinvalidとする for (int i = 0; i < s.Length; i++) { if (this.Dictionary.ContainsValue(s[i])) { this.Stack.Push(s[i]); } else if (this.Dictionary.ContainsKey(s[i])) { char c = this.Stack.Pop(); if (c == this.Dictionary[s[i]]) { continue; } else { return false; } } } // 「{」のようなinputに対応するため if (this.Stack.Count > 0) { return false; } } catch (InvalidOperationException e) { // popしたときに空だったときのため return false; } return true; } }
Problem2
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode ReverseList(ListNode head) { if (head == null) { return head; } Stack<int> Stack = new Stack<int>(); ListNode current = head; while (current != null) { Stack.Push(current.val); current = current.next; } ListNode list = new ListNode(0); ListNode current1 = list; while (Stack.Count > 0) { int i = Stack.Pop(); current1.val = i; if (Stack.Count > 0) { current1.next = new ListNode(0); current1 = current1.next; } } current1.next = null; return list; } }
LeetCodeのLinkedList解いてみた
解いたコード
- @koheiarai94さんが挙げていた問題の中でLinkedListカテゴリの問題を解いてみた
- C#で書いてます
Problem1
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public bool HasCycle(ListNode head) { ListNode current = head; HashSet<ListNode> hashSet = new HashSet<ListNode>(); while (current != null) { if (hashSet.Add(current) == false) { return true; } current = current.next; } return false; } }
補足
- 公式の解答をみると別解があるらしい
- 私の解だとHashSetに要素の長さ分(Space complexity)格納することになるが(つまりO(n))、これをO(1)にできるらしい
- 一応そのコードを書いておく
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public bool HasCycle(ListNode head) { if (head == null) { return false; } ListNode slow = head; ListNode fast = head.next; while (fast != null && fast.next != null) { if (slow == fast) { return true; } slow = slow.next; fast = fast.next.next; } return false; } }
- なるほどなーこれは思いつかん
Problem2
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode DetectCycle(ListNode head) { ListNode current = head; HashSet<ListNode> hashSet = new HashSet<ListNode>(); while (current != null) { if (hashSet.Add(current) == false) { return current; } current = current.next; } return null; } }
Problem3
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode DeleteDuplicates(ListNode head) { ListNode currentListNode = head; while(currentListNode != null && currentListNode.next != null) { if (currentListNode.val == currentListNode.next.val) { currentListNode.next = currentListNode.next.next; } else { currentListNode = currentListNode.next; } } return head; } }
Problem4
Solution
/** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode DeleteDuplicates(ListNode head) { ListNode current = head; ListNode prev = new ListNode(0); ListNode ret = prev; ret.next = prev.next = current; while (current != null && current.next != null) { ListNode next = current.next; if (current.val == next.val) { while (next.next != null && next.val == next.next.val) { next = next.next; } prev.next = current = next.next; if (current == null) { return ret.next; } } else { prev = current; current = next; } } return ret.next; } }
fizzbuzzかいてみた
背景
- とある機会でfizzbuzzを書いたので改めて残しておく
fizzbuzzとは(説明不要だと思うが一応)
・1からnまでの数をプリントするプログラムを書け
・ただし3の倍数のときは数の代わりに｢Fizz｣と、5の倍数のときは｢Buzz｣とプリントし、3と5両方の倍数の場合には｢FizzBuzz｣とプリントすること
方針
コード
<?php class FizzBuzz { function __construct() { } const MAP = [ 3 => 'Fizz', 5 => 'Buzz', ]; public function main() { for ($i = 1; $i <= 15; $i++) { echo $this->fizzbuzz($i); } } private function fizzbuzz(int $i): string { $ret = ''; // 割り切れるものがあれば対応する文字列を出力 foreach(self::MAP as $k => $v) { if ($i % $k !== 0) { continue; } $ret .= $v; } // 割り切れるものがなければ入力数値を出力 if (!$ret) { $ret = $i; } $ret .= "\n"; return $ret; } } $fb = new FizzBuzz(); $fb->main();
