LeetCode 3. Longest Substring Without Repeating Characters

LeetCode problem No.3.

No.2 is here. modalsoul.hatenablog.com

3. Longest Substring Without Repeating Characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/

Given a string, find the length of the longest substring without repeating characters.

Example

```Input: "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3. ```

Code

```object Solution {
def lengthOfLongestSubstring(s: String): Int = {
s.foldLeft((Seq.empty[Char], if(s.length > 0) 1 else 0)){ (z, c) =>
if(z._1.contains(c)) ((z._1 :+ c).dropWhile(n => n != c).tail, z._2)
else (z._1 :+ c, if(z._1.length + 1 > z._2) z._1.size + 1 else z._2)
}._2
}
}
```

Methods

• Read a character and make substring.
• If current substring has the same character, drop characters before the same character to take sub-substring that doesn't have the same character.
• if current substring does not have the same character, add a character at the end to current substring.
• Count longest substring length.
• `z:(Seq[Char], Int)`
• `z._1` is current substring.
• `z._2` is current longest substring length.
• `c:Char`
• `c` is the current character.

Results

All testcase passed, but it is not fast.

Runtime: 464 ms, faster than 47.37% of Scala online submissions for Longest Substring Without Repeating Characters. Memory Usage: 59.2 MB, less than 5.55% of Scala online submissions for Longest Substring Without Repeating Characters.

LeetCode 2問目

1問目はこれ modalsoul.hatenablog.com

このリストは、それぞれのノードに整数の各桁が逆順に格納されている

この整数の和を求め、リンクリストとして返却する

Examples

```Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.```

コードその１

```object Solution {
def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
def calc(l:ListNode):Int = {
var result = 0L
var hasNext = true
var c = l
var digit = 1
while(hasNext) {
result = c.x * digit + result
if(c.next == null) hasNext = false
c = c.next
digit = digit * 10
}
result
}
var sum = calc(l1) + calc(l2)
var head = new ListNode(_x = sum%10)
sum = sum/10
while(sum > 0) {
val next = new ListNode(_x = sum%10)
prev.next = next
prev = next
sum = sum/10
}
}
}
```

考えたこと

• リンクリストを数値に戻し、足し算する
• 足し算の結果をリンクリストへ変換する

これだとExampleのようなケースでは動くけど、リンクリストの長さが増えると動かない

コードその２

```object Solution {
def addTwoNumbers(l1: ListNode, l2: ListNode): ListNode = {
def run(a:ListNode, b:ListNode, acc:ListNode = null, prev:ListNode = null, carried:Boolean = false): ListNode = {
if(a == null && b == null) {
if (carried) prev.next = new ListNode(_x = 1)
acc
}
else {
val x = (if(a != null) a.x else 0) + (if(b != null) b.x else 0) + (if(carried) 1 else 0)
val node = new ListNode(_x = x%10)
if(acc == null) {
run(a.next, b.next, acc = node, prev = node, x > 9)
}
else {
prev.next = node
run(if(a == null) null else a.next, if(b == null) null else b.next, acc = acc, prev = node, x > 9)
}
}
}
run(l1, l2)
}
}
```

考えたこと

• リンクリストを辿る時点でその桁の足し算をしてしまう
• 桁の繰り上がり有る無しを持ち回す

こっちはすべてのテストケースをパスした

Runtime: 380 ms, faster than 99.59% of Scala online submissions for Add Two Numbers. Memory Usage: 58.2 MB, less than 78.57% of Scala online submissions for Add Two Numbers.

1. Two Sum

https://leetcode.com/problems/two-sum/

Intの配列が与えられるので、和が指定される値と等しくなる2つの数値のインデックスを返す

Example:

```Given nums = [2, 7, 11, 15], target = 9

Because nums + nums = 2 + 7 = 9,
return [0, 1].```

コードその１

```object Solution {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
def index(n1:Int, arr:Array[Int]):Option[Int] = {
val res = arr.indexWhere(_ + n1 == target) + 1
if(res != 0) Some(res) else None
}

def run(nums:Array[Int], offset:Int = 0):Array[Int] = {
case Some(n2) => Array(offset, n2 + offset)
case _ => run(nums.tail, offset + 1)
}
}
run(nums)
}
}
```

解説

def index(n1:Int, arr:Array[Int]):Option[Int]

`Seq.indexWhere`の戻り型を`Int`から`Option[Int]`へ変換するためのもの

`Seq.indexWhereOption:Option[Int]`のようなメソッドがあれば良かったんだが。。

def run(nums:Array[Int], offset:Int = 0):Array[Int]

`index`の結果をパターンマッチして、Someの場合に解発見、Noneの場合再帰する

tailを遡るたびにindexが進むので、その回数をoffsetで持ち回る

コードその2

```object Solution {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
val map = nums.zipWithIndex.toMap
nums.zipWithIndex.foldLeft(Array.empty[Int]){(z, n) =>
if(!z.isEmpty) z
else {
val t = target - n._1
map.get(t).fold(z){ x => if(x != n._2) Array(n._2, x) else z}
}
}
}
}
```

解説

• n番目の値のインデックスとn番目の値をtargetから引いた値のインデックスが解になる
• 値とインデックスのマップを生成

これでO(n)

コードその3

```object Solution {
def twoSum(nums: Array[Int], target: Int): Array[Int] = {
nums.zipWithIndex.foldRight((Map.empty[Int, Int], Array.empty[Int])) { (n, z) =>
if(!z._2.isEmpty) z
else {
val (map, acc) = z
val (num, index) = n
(map + n, map.get(target - num).fold(acc){ x => if(x != index) Array(index, x) else acc})
}
}._2
}
}
```

解説

• 基本的な考え方はコードその2と同じ
• 値とインデックスのマップ生成時に、和がtargetになる値の有無をチェックする

Luhnアルゴリズムによる誤り検出

Luhnアルゴリズムについてちょっと話題に上がったので書いてみる

Luhnアルゴリズム1

クレジットカード番号やIMEI番号の検証に使われているアルゴリズム

• 任意の1桁の間違いや隣接する桁の数字の順序間違いを検出できる
• 09 から 90 （または逆）という間違いは検出できない
• 同じ数字が2つ連続する場合の間違いも10種類のうち4種類までは検出できる
• 22 ⇔ 55、33 ⇔ 66、44 ⇔ 77 は検出できない

IMEI番号は電話のキーパッド*#06#と入力すると表示される

検証手順

• 右端のチェックディジットを1番目として、偶数番目の桁を2倍にする。
• 2倍にしていない桁も含め、各数字の総和を求める（2倍にした桁が2桁になった場合は、それぞれを別々の数字として加える）。
• この総和の下1桁が0なら（つまり、10で割り切れる場合）、この番号はLuhnアルゴリズムでは正しく、そうでない場合は正しくない。

これをScalaで実装してみた

Raspberry Pi Zeroで車載機をDIYしたときのアレコレとその先

↑の記事のなかで、Raspberry Pi Zero WHを使った車載機を作ったときのアレコレを書いてみます

使ったもの

9軸センサー

`FaBo9Axis_MPU9250`モジュールをPython3系で使ったときに、`MPU9250.py``print "~"``Syntax Error`になってハマったのはモニョッたぜ。。

GPS

みちびき4機対応のファームアップデートしないとなー

Bluetooth

セキュリティのON/OFFを判定するのに、Bluetoothバイスのスキャンを使った

ほんとうはBLEのBeaconタグを使うつもりだったけど、間に合わず

BLE Beaconを受信するところがなんかうまくいかなかったので、もうちょっと調べたい

スピーカー

システム音声を再生するのに使った

ほんとうに音量が控えめ、悟りを開きそうになるくらい耳を澄まさないと聞こえない。。

物理ボタン

Raspberry Piをいじる上で、物理ブート/シャットダウンボタンはほんとうに役に立った

スイッチはトグルタイプに変えたさある

使いたいもの

電子ペーパー

やっぱりスピーカーとLEDランプ以外の出力が欲しい

けれど、消費電力の都合上ディスプレイは厳しそうなんで、電子ペーパー使ってみたいですね

フリップドットディスプレイ

フリップドットディスプレイつけたいんですが、気軽に手に入るのないですかね？

多謝

Raspberry Pi Zeroについて

GPIOのピン、どうやっても並びを覚えられなくて、どっちから数えて何番目だっけ？ってとき、このページのハードウェア図は何度も参照しました

この場を借りて感謝

Raspberry Pi Zero WHで、 BLE Beaconを送信する＆Bluetoothデバイス名を変更する

Raspberry Pi Zero WHは、Bluetooth4.0/BLE(Bluetooth Low Energy)が使えるので、Beaconの送信をしてみた

Bluez

LinuxオフィシャルなBluetoothスタックのBluezを使います

Bluez-ibeaconのインストール

```cd /usr/local/src
sudo git clone https://github.com/carsonmcdonald/bluez-ibeacon.git
cd bluez-ibeacon/bluez-beacon/
sudo make
```

Usage

```cd bluez-ibeacon/bluez-beacon/
./ibeacon
```

Beaconの送信

```sudo ./ibeacon 200 67567567567567567567567567567567 1 1 -29
```
param value
UUID 67567567567567567567567567567567
majer number 1
minor number 1

※ パラメータはこれを参考に設定

Bluetoothデバイス名の変更

Beaconを受信できたけど、デバイス名が機械的で認識しずらいので、名前を変更する

/etc/machine-info

`/etc/machine-info`を作成し、以下の内容を記述する

`PRETTY_HOSTNAME=device-name`

Bluetooth serviceのrestart

```sudo invoke-rc.d bluetooth restart
```

確認 バイス名が任意の名前に変更できた

GPS受信機キット 配線

Raspberry Pi Zero GPSモジュール
5V 5V
GND GND
RxD TxD
TxD RxD
なし 1PPS とても基本的なことなんですが、RxDとTxDはクロスさせて接続します。これを間違えて、位置情報が取れず何度も設定を見直し、時間を無駄にしてしまった。。※ 上の写真は間違えた状態です

シリアルの有効化

raspi-config

```sudo raspi-config
```
• P5 Interfacing Options
• P6 Serial
• YES

で、Finish

```> ls /dev/serial*
/dev/serial0
```

/dev/serial0があることを確認

/boot/cmdline.txt

```sudo vi /boot/cmdline.txt
```

もとの`/boot/cmdline.txt`から、`console=serial0,115200`の記述を削除する

```# dwc_otg.lpm_enable=0 console=tty1 console=serial0,115200 root=PARTUUID=b7e00398-02 rootfstype=ext4 elevator=deadline fsck.repair=yes rootwait modules-load=dwc2,g_ether
dwc_otg.lpm_enable=0 console=tty1 root=/dev/mmcblk0p2 rootfstype=ext4 elevator=deadline fsck.repair=yes rootwait quiet splash plymouth.ignore-serial-consoles```

リブート

`sudo reboot`

動作確認

pyserialのインストール

シリアルモジュールをインストール

```pip install pyserial
```

repl

```~\$ python
Python 3.6.6 (default, Oct  7 2018, 12:22:23)
[GCC 6.3.0 20170516] on linux
>>> import serial
>>> s = serial.Serial('/dev/serial0', 9600, timeout=10)
'\$GPGGA,154327.000,,,,,0,1,,,M,,M,,*4F\r\n'
```

なにか値が取得できた

NMEA0183

モジュールから得られるデータは、NMEA0183に準拠したフォーマットになっている NMEA 0183 - Wikipedia

micropyGPS

repl

```Python 3.6.6 (default, Oct  7 2018, 12:22:23)
[GCC 6.3.0 20170516] on linux
>>> import serial
>>> from micropyGPS import MicropyGPS
>>> my_gps = MicropyGPS(9, 'dd')
>>> s = serial.Serial('/dev/serial0', 9600, timeout=10)