1290. 二进制链表转整数

缺乏、安全感 2023-03-14 13:19 2阅读 0赞

# 题目来源 #

[LEETCODE][]

# 题目描述 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]

# 题目解析 #

## 使用栈 ##

class Solution {
        
        public int getDecimalValue(ListNode head) {
        
            Stack<Integer> stack = new Stack<>();
    
            while (head != null){
        
                stack.push(head.val);
                head = head.next;
            }
    
            // 链表非空
            int ans = stack.pop();
            int temp = 1;
            while (!stack.empty()){
        
                int i = stack.pop();
                temp = temp * 2;
                ans = ans + i * temp;
            }
    
            return ans;
        }
    }

递归实现：

/*
        * 1001
        *
        * 从后面往前面看：0 +  1* (2^0) + 0 * (2^1) + 0 * (2^3) + 1 * (2^4)
        * */
    class Solution {
        
        private  int size = 0;
        public  int getDecimalValue(ListNode head) {
        
            if(head == null){
        
                return 0;
            }
    
    
            int val = getDecimalValue(head.next);
            int sum =  val + head.val * (int) Math.pow(2, size);
            size++;
            return  sum;
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][20200624140620432.png]

## 模拟 ##

任意一个数，我们以三位数为例，比如一个三位数abc,它的十进制的值是等于a*100+b*10+ca∗100+b∗10+c  
但是如果用这种思想去求解这道题较为麻烦，我们需要用遍历的思想去考虑这个问题，因为我们需要去从表头到表尾去遍历这样一个二进制链表，那么，上面的公式如何用遍历的思想去实现呢？  
100a+10b+c=((10\*a+b)\*10)\*10+c100a+10b+c=((10∗a+b)∗10)∗10+c  
写成这种形式，就可以利用遍历和累加的方式一步一步计算，从而求解

class Solution {
        
        public int getDecimalValue(ListNode head) {
        
            int ans = 0;
            while (head != null){
        
                ans = ans * 2 + head.val;
                head = head.next;
            }
    
            return ans;
        }
    }

![在这里插入图片描述][2020051809095289.png]

[LEETCODE]: https://leetcode-cn.com/problems/convert-binary-number-in-a-linked-list-to-integer/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20230312/fac240be920241fc9229a37d9dfcc46c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20230312/4fde208857a24d7cbc8227b959f8e382.png
[20200624140620432.png]: /images/20230312/d2988115331c4a388027cd83242826ca.png
[2020051809095289.png]: /images/20230312/01bfb685893a46a29fb43e3969d86ea3.png