小白LeetCode 刷题记录（1-10）（待续）

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target. 给一个整数数组，找到两个数使得他们的和等于一个给定的数，返回这两个数的下标。

You may assume that each input would have exactly one solution, and you may not use the same element twice. 可以假设只有一组答案。

Given nums = [2, 7, 11, 15], target = 9, return [0, 1].

解题思路: 先遍历一遍数组,建立map数据，然后再遍历一遍，开始查找，找到则记录index。

JAVA:

public class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        int[] res = new int[2];
        for(int i = 0;i < nums.length; i++){
            map.put(nums[i],i);
        }
        for(int i =0;i<nums.length; i++){
            int t = target - nums[i];
            if(map.containsKey(t)&& map.get(t)!= i){
                res[0] = i;
                res[1] = map.get(t);
                break;
            }
        }
        return res;
        
    }
}

把两个for循环合并成一个。

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

学习知识点：

• HashMap 是一种键值对应的数据结构。是哈希表的Map接口(java.util.Map )的实现类。非同步，允许使用NULL。
• 根据键的HashCode值存储数据，具有很快的访问速度。
• HashMap 没有顺序。通过get()来获取value , put()来插入value, ontainsKey() 来检验对象是否存在，

2. Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. 给你两个非空的链表来表示两个非负整数。整数的每个数字倒序存储在链表的每个节点中。现在你需要写一个函数，将两个整数相加，并以链表的形式返回它们的和。

You may assume the two numbers do not contain any leading zero, except the number 0 itself. 你可以假设两个整数没有任何前导零，除非是零本身。

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

思路：
两个链表求和，先做一个大循环，对每一位进行操作。要考虑两个链表长度不一致的情况。

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        
        int sum = 0;
        while(c1!=null || c2!=null ){
            sum /= 10;
            if(c1!= null){
                sum+= c1.val;
                c1 = c1.next;
            }
            if(c2!=null){
                sum+= c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if(sum / 10 ==1)
            d.next = new ListNode(1);
        return sentinel.next;
    }
}

3. Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. 给定一个字符串，找出其没有重复字符的最大子序列的长度.

Given “abcabcbb”, the answer is “abc”, which the length is 3.
Given “bbbbb”, the answer is “b”, with the length of 1.
Given “pwwkew”, the answer is “wke”, with the length of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] map = new int[256];
        int j = 0;
        int i = 0;
        int ans = 0;
        
        for(i = 0; i < s.length(); i++){
            while(j < s.length() && map[s.charAt(j)]==0){
                map[s.charAt(j)] = 1;
                ans = Math.max(ans, j-i +1);
                j++;
            }
            map[s.charAt(i)]=0;
            
        }
        return ans;
    }
}

对现阶段的我来说太难，，，待续，，，，，，，，，，，