問題
原文
Given
headwhich is a reference node to a singly-linked list. The value of each node in the linked list is either0or1. The linked list holds the binary representation of a number.Return the decimal value of the number in the linked list.
The most significant bit is at the head of the linked list.
Example 1:
Example 2:
Constraints:
- The Linked List is not empty.
- Number of nodes will not exceed
30.- Each node’s value is either
0or1.
内容
単方向連結リストheadが与えられます。各ノードの値は0,1で、バイナリ値のみです。
連結リストを10進数の値にして返してください。
最上位bitは連結リストの先頭です。
※正しくない可能性があります。
方針
・各要素を文字列にしたリストに変換後、連結してから10進数に変換
解答
解答1：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
class Solution: def getDecimalValue(self, head: ListNode) -> int: #リストを用意 list_int = [] #連結リストのノードがある限り処理を行う while head: #現ノードの値を文字列にしてリストに保持 list_int.append(str(head.val)) #連結リストの次のノードへ移る head = head.next #リスト内の各要素を結合して変数に保持 binary_val = ''.join(list_int) #10進数にして返す return int(binary_val,2) |
”.join(list_int)でリスト内の各要素を結合することができる
例：[“1″,”2″,”3”]であれば123になる
リスト内の各要素は文字列である必要があるため、list_intに保持するときにstr()で文字列に変換した。
解答2
|
1 2 3 4 5 6 7 8 9 |
class Solution: def getDecimalValue(self, head: ListNode) -> int: curr = head res = 0 while curr: res = res*2 res += curr.val curr = curr.next return res |
こっちはよくわからないので、コメントをここにメモ
ビットシフト・ビット演算をしている？
For those of you who don’t understand how the algorithm works, it is easier to visualize as it is done in binary.
Take For Example:
1101 -> 13Binary View
0000 * 2 # shift left
0000 + 1 # add bit0001 * 2 # shift left
0010 + 1 # add bit0011 * 2 # shift left
0110 + 0 # add bit0110 * 2 # shift left
1100 + 1 # add bit1101 # 13
Decimal View
0 * 2 # x2
0 + 1 # add bit1 * 2 # x2
2 + 1 # add bit3 * 2 # x2
6 + 0 # add bit6 * 2 # x2
12 + 1 # add bit13 # Answer
補足・参考・感想
参考
前：876. Middle of the Linked List
コメント