LeetCode刷题记录本

LeetCode刷题记录本

两数之和

难度：简单

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题思路

可以看到题目给的前提条件是每种输入都只会对应一个答案，但是数组中的同一个元素不能使用两边，这样我们可以通过循环数组，然后将数组元素的值作为key，坐标作为value存储到map中。

循环遍历过程中，用target减去当前元素的值，获取差值。然后去map中获取这个插值，如果可以获取到，就将这两个坐标存储到返回的数组里面进行返回。

实现代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] returnIntArray = new int[2];
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            int result = target - num;
            if (map.containsKey(result)) {
                returnIntArray[1] = i;
                returnIntArray[0] = map.get(result);
            } else {
                map.put(num, i);
            } 
        }
        return returnIntArray;
    }
}

我尝试遍历两个单项列表，将其转换为int，然后将两个int进行相加（简称为sum），最后将这个sum转换为string，然后遍历这个string，将其每一个值存储到一个ListNode中，然后组装成一个单项列表。但是在实际运行测试过程中，leetCode提交的时候，如果给传入了一个比较长的单项列表作为参数，可能int的长度就直接溢出了，导致结果不对。因为无法规定listnode的长度要求，就算是换成long也有可能移除，所以这个方案不可靠

新的方案

0、定义一个node head，再定义一个end，end指向head，定义一个进位数量carry

1、判断两个单项列表（下面简称l1,l2），如果两个都为空就算是遍历完了，但是只要有一不为空，那么就继续遍历，只是两外一个的node的val永远都是0了。

2、获取l1+l2的值

3、因为可能上一次计算的结果是大于十的，是要进位的，所以这两位的最终计算结果逻辑应该是：l1+l2+carry

4、那新的carry就是(l1+l2+carry)/10，当前的sum结果是(l1+l2+carry)%10

5、将end.next指向新建的node，node的val设置为sum

6、将end指针指向新建的node（end = end.next)

7、判断一下l1和l2是否为空，如果不为空，分别将其指向自己的下一个节点

8、当完成遍历的时候，可能最后一位的和的结果大于10，所以需要判断一下最终的carry是否大于0，如果大于0，需要再end的下一个节点，指向一个新的节点，节点值就是carry

9、由于我们刚开始创建的head的值为0，但是实际结果中我们不需要0这个节点，所以我们返回结果为head.next

实现代码

/**
 * 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 head = new ListNode(0);
        ListNode end = head;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y + carry;
            // 判断和的结果是否大于10
            carry = sum / 10;
            // 获取无论结果是否大于10，最终的这一位的数字是多少
            sum = sum % 10;
            // 组装列表
            end.next = new ListNode(sum);
            end = end.next;
            // 判断是否还需要继续next
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        // 判断最终位计算是否超过了10
        if (carry > 0) {
            end.next = new ListNode(carry);
        }
        return head.next;
    }
}

无重复字符的最长子串

难度：中等

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

示例

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

解题思路

定义一个map用来存储字符和长度位置，value值为字符位置+1，+1表示从字符位置后一个才开始不重复
定义不重复子串的开始位置start，结束为end
随着end不断的遍历向后，会遇到和start，end区间内字符相同的情况，此时将字符作为key，获取其value值，更新start，此时start,end区间内不存在重复字符
无论是否更新start都会更新其map数据结构和ans
时间复杂度O(n)

实现代码

public int lengthOfLongestSubstring(String s) {
    int ans = 0;
    Map<Character, Integer> map = new HashMap<>();
    for (int start = 0, end = 0; end < s.length(); end++) {
        Character c = s.charAt(end);
        if (map.containsKey(c)) {
            start = Math.max(start, map.get(c));
        }
        ans = Math.max(ans, end - start + 1);
        map.put(c, end + 1);
    }
    return ans;
}