力扣刷题：第二天

谁践踏了优雅 2023-09-26 11:11 8阅读 0赞

## 力扣刷题：第二天，有我的题解 ##

## 1.两数之和 ##

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

### 我的：就有点慢，最基础的思路时间复杂度`O(n2)`，力扣的第一个题解和我这个是一样的，下面的题解是第二种，要好很多 ###

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
             for (int i = 0; i < nums.length; i++) {
        
                 for (int j = i+1; j < nums.length; j++) {
        
                     if (nums[i]+nums[j]==target){
        
                         return new int[]{
        i,j};
                     }
                 }
             }
             return null;
        }
    }

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

### 题解：哈希表 ###

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

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
            for (int i = 0; i < nums.length; ++i) {
        
                // 为使用map集合什么快：
                //  map 数据量多的时候（size()>8） 改用 红黑树的 数据结构 在查找效率上十分突出
                //原理：
                // map 中的 containsKey（key）方法是判断该key在map中是否有key存在。如果存在则返回true。如果不存在则返回false。
                // 先找 target 减去 nums[i] 的 key 是否存在，他这里的key存的就是 数组nums的值
                if (hashtable.containsKey(target - nums[i])) {
        
                    return new int[]{
        hashtable.get(target - nums[i]), i};
                }
                // 没找到的话 就把 key 值 与 位置存入吗map集合中，供下次循环使用
                hashtable.put(nums[i], i);
            }
            return new int[0];
        }
    }

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

## 2.两数相加 ##

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

### 我的：贼6好吧 ###

> 思路：把链表中的数字变成字符串，再翻转一下，变成数字相加后再转成字符串，再翻转一下，然后一个个装入链表中
> 
> 做法：
> 
> 用StringBuilder来接收链表ListNode的值，然后使用StringBuilder的reverse()翻转，
> 
> 使用BigInteger把StringBuilder转成数字，为什么哈，是因为Interger、Long都接收不了很大的值，他的案例写道了25位以上的数字，Long最大只能接收19位数字，使用要使用BigInteger

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    import java.util.*;
    import java.math.BigInteger;
    class Solution {
        
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            //下面两个都是分别使用stringBuilder把链表中的数字加进去
            StringBuilder stringBuilder = new StringBuilder();
            while (l1!=null){
        
                stringBuilder.append(l1.val);
                l1=l1.next;
            }
            StringBuilder stringBuilder2 = new StringBuilder();
            while (l2!=null){
        
                stringBuilder2.append(l2.val);
                l2=l2.next;
            }
            
            // stringBuilder.reverse()，让字符串翻转得到我们需要相加的值
            BigInteger bigInteger = new BigInteger(stringBuilder.reverse().toString());
            BigInteger bigInteger1 = new BigInteger(stringBuilder2.reverse().toString());
            // String.valueOf(bigInteger.add(bigInteger1)) 相加后再转成字符串，翻转一下，得到字符串集合
            String[] split = new StringBuilder(String.valueOf(bigInteger.add(bigInteger1))).reverse().toString().split("");
            // listNode2相当于listNode的表头，listNode后面相加得到的值，都赋给listNode2
            ListNode listNode = new ListNode();
            ListNode listNode2 = listNode;
            // 一个个装入ListNode中
            for (String s : split) {
        
                listNode.next = new ListNode(Integer.parseInt(s));
                listNode = listNode.next;
            }
            // listNode2相当于listNode的表头，头结点是null，所以要下一个
            return listNode2.next;
        }
    }

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

### 题解：思路就是挨个（挨个的意思就是依次）判断是否进位 ###

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

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {
        
        //我们要理解 10进制（不管哪个进制）都是从最小位开始进位的，这里刚好可以从链表的头开始计算（因为按照题目的要求，链表的头部就是个位）
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        
            // 单项链表 ，tail一旦指向下一个节点就回不来了，所以需要我们一开始就让head执行tail，得到完整的链表（因为后续tail会变）
            ListNode head = null, tail = null;
            int carry = 0;
            //这俩为空就不用计算了
            while (l1 != null || l2 != null) {
        
                // 赋值（三元运算符）
                int n1 = l1 != null ? l1.val : 0;
                int n2 = l2 != null ? l2.val : 0;
                //先从个位相加，没有进位所以加零
                int sum = n1 + n2 + carry;
                    //为空的时候，给头结点设置值，这里只会执行一次，因为后面循环时head就不为空了
                if (head == null) {
        
                    //我举个例子 为什么这里要%10：以十进制 两位数举例
                    //   如果 n1 = 8 ， n2 = 9 那么第一次循环是个位相加 ，没有进位，所以carry=0，得到数字17，
                    // 那么这里的意思就是 向十位进 1（所以之后的操作是让 carry 等于 17 中的1，就是需要进位的数） 并且要把个位（7）放在链表中 
                    head = tail = new ListNode(sum % 10);
                } else {
        
                    //每次都给链表赋值，逻辑跟上述一样的
                    tail.next = new ListNode(sum % 10);
                    //指向下一个节点
                    tail = tail.next;
                }
                //这里就是指向前一位 进位的数
                carry = sum / 10;
                if (l1 != null) {
        
                    //不为空的话，指向下一个节点
                    l1 = l1.next;
                }
                if (l2 != null) {
        
                    //不为空的话，指向下一个节点
                    l2 = l2.next;
                }
            }
            if (carry > 0) {
        
                //计算完了之后，需要判断还要进位不，因为l1和l2为null跳出循环了，执行不到 int sum = n1 + n2 + carry; 这步操作了，要手动加一
                tail.next = new ListNode(carry);
            }
            //返回头
            return head;
        }
    }

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

[022622a0907a4e0ebe415f44d60be3aa.png]: https://img-blog.csdnimg.cn/022622a0907a4e0ebe415f44d60be3aa.png
[8cc2e2b1ced9481d96d347aa6c804794.png]: https://img-blog.csdnimg.cn/8cc2e2b1ced9481d96d347aa6c804794.png
[acfae227aa2e4b1397f280c71bc92d57.png]: https://img-blog.csdnimg.cn/acfae227aa2e4b1397f280c71bc92d57.png
[8fd9b1e887114024aa05cfa7a3adaf46.png]: https://img-blog.csdnimg.cn/8fd9b1e887114024aa05cfa7a3adaf46.png
[c2fe477f86464026b2c22b37739d2e79.png]: https://img-blog.csdnimg.cn/c2fe477f86464026b2c22b37739d2e79.png
[2606fa2b435244a8aee491bb2df331e8.png]: https://img-blog.csdnimg.cn/2606fa2b435244a8aee491bb2df331e8.png
[2285e7f0d9ce41928d6d02336d9720e8.png]: https://img-blog.csdnimg.cn/2285e7f0d9ce41928d6d02336d9720e8.png
[afdfcd1ced3f4ffbbad5d155b997abfd.png]: https://img-blog.csdnimg.cn/afdfcd1ced3f4ffbbad5d155b997abfd.png