LeetCode刷题——Day1

╰+攻爆jí腚メ 2022-03-28 05:13 195阅读 0赞

## **终于放假啦，寒假也要学习！这一系列的主题是LeetCode刷题，请春招赐我一个理想的实习吧！！！** ##

1、给定一个整数数组 `nums` 和一个目标值 `target`，请你在该数组中找出和为目标值的那 **两个** 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

**示例:**

给定 nums = [2, 7, 11, 15], target = 9
    
    因为 nums[0] + nums[1] = 2 + 7 = 9
    所以返回 [0, 1]

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement)) {
                return new int[] { map.get(complement), i };
            }
            map.put(nums[i], i);
        }
    throw new IllegalArgumentException("No two sum solution");
    }
    }

### **出错点：java数组的声明和赋值的方式** ###

2、给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

**示例：**

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
    输出：7 -> 0 -> 8
    原因：342 + 465 = 807

/**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode(int x) { val = x; }
     * }
     */
    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode dummyHead=new ListNode(0);//结果链表的头结点
            ListNode p=l1,q=l2,curr=dummyHead;//p、q最开始指向两个链表的第一个节点，然后每过一轮就都向后移一位，直到表尾
        int carry=0;//进位
            while(p!=null||q!=null){//从最低位开始相加，因为一个列表存储的最大值是9，所以carry只可能是0或者1
                int x =(p != null) ? p.val : 0;
                int y=(q!=null)? q.val:0;
                int sum=carry+x+y;
                carry=sum/10;
                curr.next=new ListNode(sum%10);
                curr=curr.next;
                if(p!=null) p=p.next;
                 if(q!=null) q=q.next;
            }
            if(carry>0){
    curr.next=new ListNode(carry);//如果最后的一位加完还有进位，就需要再新建一个节点，这个数字一定是1
            }
            return dummyHead.next;
        }
    }

### 出错点：对链表头节点的理解，它最初是指向链表第一个节点，作用是遍历链表，最开始的值就是第一个节点的值。 ###

3、给定一个字符串，请你找出其中不含有重复字符的 **最长子串 **的长度。

**示例 1:**

输入: "abcabcbb"
    输出: 3 
    解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

思路：用HashMap标记某个字符最晚出现的地方。用pre标记不重复的起始位置。当出现重复字符的时候，有下面几种情况，1）和2）.b可以合并。

1）原有重复字符正好是pre节点

2）原有重复字符不是pre节点

a）原有重复字符在pre节点之后（考虑字符串tmmznxt就是这种情况）

b）原有重复字符在pre节点之前

public class Solution {
        public int lengthOfLongestSubstring(String s) {
            int max = 0;
            int pre = 0;
            HashMap<Character,Integer> hm = new HashMap<>();
            for(int i = 0; i < s.length(); i++){
                char c = s.charAt(i);
                if(!hm.containsKey(c)){
                    hm.put(c,i);
                    max = Math.max(max,i - pre + 1);
                }
                else{
                    if(pre <= hm.get(c)){
                        max = Math.max(max,i - hm.get(c));
                        pre = hm.get(c) + 1;
                    }
                    else{
                        max = Math.max(max,i - pre + 1);
                    }
                    hm.replace(c,i);
                }
            }
            return max;
        }
    }

###    出错点：不能想当然，如果出错了可以跟着走一遍看看自己哪里考虑不周，只要没通过就一定是自己有错误，不是平台的问题，虽然我也是在找出错误以后才解除对平台编译器的怀疑的，哈哈，逃~~ ###