重要:指针的使用和二进制转换公式

发布于 2020-06-29  3.31k 次阅读


给你一个单链表的引用结点 head。链表中每个结点的值不是 0 就是 1。已知此链表是一个整数数字的二进制表示形式。
请你返回该链表所表示数字的 十进制值 。
示例 1:
输入:head = [1,0,1]
输出:5
解释:二进制数 (101) 转化为十进制数 (5)
解题思路:把head链表的数挨个取出,再使用二进制转换
方法一:
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
int getDecimalValue(struct ListNode* head){
    struct ListNode* a=head;
    int i=0,arr[50]={0},sum=0,j=0;
    while(a!=NULL){
        arr[i]=a->val;
        a=a->next;
        i++;
    }
    i=i-1;
    //转换成二进制;
    for(;i>=0;i--){
        sum=sum+(arr[i]*pow(2,j));
        j++;
    }//已完成;
    return sum;
}
优化版:
#define null 0
int getDecimalValue(struct ListNode* head){
struct ListNode *a=head;
int num=0;
while(a!=null){
num=num*2+a->val;
a=a->next;
}
return num;
}
最优解:位运算(移位,或)
思路:位运算
每取 1 位数字,将当前所有数位 左移 1 位
通过位运算 或 将取出数字存入最低位
int getDecimalValue(struct ListNode* head){
int res = 0;
for ( ; head; head = head->next)
res = (res << 1) | head->val;
return res;
}

她喜欢所以就做咯