Convert Binary Number in a Linked List to Integer這道題在leetcode上面算作是“easy”，然而小生我還是不會做，于是根據大佬的回答來整理一下思路以便日后復習，
https://leetcode.com/problems/convert-binary-number-in-a-linked-list-to-integer/
1.原題：
Given head which is a reference node to a singly-linked list. The value of each node in the linked list is either 0 or 1. The linked list holds the binary representation of a number.Return the decimal value of the number in the linked list.
翻譯：Head是一個單鏈表的參考，每個鏈表的元素都是1或者0，鏈表的數字們組成起來代表一個二進制數字（比如說 [1，0，1]代表二進制的101），你需要回傳這個二進制所代表的十進制數字，
輸入輸出：
Input: head = [1,0,1]
Output: 5
這是單鏈表的定義:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
2.解題思路：
首先作為演算法題，大多數語言都可以用，作者這里習慣，用的是C++，
這道題考驗的主要是答題者對編程語言中二進制的了解，
a.解題所需要的知識：
二進制的101代表十進制的5，這是因為 4 + 1 = 5，這個不用說了吧，
而我們要注意的就是 “<<”，這個不是我們熟知的C++輸出符，而是指往左移，后面的數字是指左移1一位，假設ret是3，ret <<= 1 之后就會ret = 6，
|= 意思為：按位或后賦值，也就是給對應的二進制的數字的位置賦值，假設ret是7，ret |= 4之后ret仍然是7，因為7是0111，4是0100，注意這4這個位置已經有1了所以已經賦值了，因此結果不變，
head->val就是指鏈表里面的val，關于鏈表的定義可以參考：https://blog.csdn.net/slandarer/article/details/91863177
b.解題思路：
解題思路見注釋，非常通俗易懂，
參考答案：
class Solution {
public:
int getDecimalValue(ListNode* head) {
int ret = 0; //設定ret為0，
while(head) //在head都不為NULL的情況下繼續回圈
{
ret <<= 1;
//我們會把ret左移，所以說如果之前已經有一位1了.
//那就會被推到更高的位置,比如說之前為0001，那么現在就是0010
ret |= head->val;
//如果head->val是1，就給這一層賦值1，如果是0，就維持不變，
//例子：比如說之前我們已經得到了0010，現在如果為1，就是0011；如果是0，就是0010不變，
head = head->next;
//指向下一個鏈表元素，
}
return ret;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/45218.html
標籤：其他