CTF of Z2BNS
0%

二进制链表转整数

发表于 更新于 分类于 ，
| 阅读次数： |
Valine：
本文字数： 691 阅读时长 ≈ 1 分钟

题目地址

难度：⭐

题目描述：

给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。

请你返回该链表所表示数字的 十进制值 。

示例1：

img

1
2
3
输入：head = [1,0,1]
输出：5
解释：二进制数 (101) 转化为十进制数 (5)

示例2：

1
2
输入：head = [0]
输出：0

示例3：

1
2
输入：head = [1]
输出：1

示例4：

1
2
输入：head = [1,0,0,1,0,0,1,1,1,0,0,0,0,0,0]
输出：18880

示例5：

1
2
输入：head = [0,0]
输出：0

提示：

  • 链表不为空。
  • 链表的结点总数不超过 30。
  • 每个结点的值不是 0 就是 1。
🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️解题过程🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️🙋‍♂️
解题过程：

思路：

把链表的每个结点的值存到vector容器tmp中，然后遍历tmp容器计算每一位转十进制的数值并相加。

c++代码：(执行用时4ms，击败49.61%，内存消耗8.7M，击败5.10%）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        vector<int> tmp;
        int result=0;
        //把链表结点的值存到tmp中
        while(head){
            tmp.push_back(head->val);
            head=head->next;
        }
        int n=tmp.size();
        //遍历二进制整数
        for(int i=0;i<n;++i){
            result+=tmp[i]*pow(2,n-i-1);
        }
        return result;
    }
};
💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎官 方 题 解💎💎💎💎💎💎💎💎💎💎💎💎💎💎💎
官方题解:

方法一：模拟

由于链表中从高位到低位存放了数字的二进制表示，因此我们可以使用二进制转十进制的方法，在遍历一遍链表的同时得到数字的十进制值。

c++代码：（执行8ms，击败80.33%，内存10.4M，击败5.12%）

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int getDecimalValue(ListNode* head) {
        ListNode* cur = head;
        int ans = 0;
        while (cur != nullptr) {
            ans = ans * 2 + cur->val;
            cur = cur->next;
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(N)$，其中 $N$是链表中的节点个数。
  • 空间复杂度：$O(1)$。
⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳总 结⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳⏳
总结：

我是想复杂了，直接像官方题解那样遍历链表同时得到十进制值就行了。

------------- THE END! THANKS! -------------