leetcode菜鸡斗智斗勇系列（1）---把一个链表中的二进制数字转换为一个整型数（int）

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;
}
};

巴特西

leetcode菜鸡斗智斗勇系列（1）---把一个链表中的二进制数字转换为一个整型数（int）

1.原题：

2.解题思路：

a.解题所需要的知识：

b.解题思路：

最新文章

热门文章