LeetCode笔记

LeetCode Online Website

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.
Example:

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

My Solution

// Time complexity : O(n^2)
public class Solution {
    public int[] twoSum(int[] nums, int target) {
        int[] result = {0,0};
        for(int i = 0 ; i < nums.length - 1; i++){ // notice the bound of i
            for(int j = i+1;j<nums.length;j++){
                if(nums[i]+nums[j] == target){
                    result[0] = i;
                    result[1] = j;
                    return result;
                }
            }
        }
        return result;
    }
}

Editorial Solution

// Time complexity : O(n)
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");
}

Add Two Numbers

You are given two linked lists representing two non-negative numbers. 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.

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

My Solution(I think it’s very terrible)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int carry = 0;
        if(l1==null&&l2==null){
            return null;
        }
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode head = new ListNode((l1.val+l2.val)%10);
        carry = (l1.val+l2.val)/10;
        ListNode node = head;
        while(l1.next!=null||l2.next!=null){
            if(l1.next == null){
                node.next = new ListNode((l2.next.val+carry)%10);
                carry = (l2.next.val+carry)/10;
                node = node.next;
                l2 = l2.next;
                continue;
            }
            if(l2.next == null){
                node.next = new ListNode((l1.next.val+carry)%10);
                carry = (l1.next.val+carry)/10;
                node = node.next;
                l1 = l1.next;
                continue;
            }
            node.next = new ListNode((l1.next.val+l2.next.val+carry)%10);
            carry = (l1.next.val+l2.next.val+carry)/10;
            node = node.next;
            l1 = l1.next;
            l2 = l2.next;
        }
        if(carry!=0){
            node.next = new ListNode(carry);
        }
        return head;
    }
}

Editorial Solution

public ListNode addTwoNumbers(ListNode l1, ListNode l2) { // Time complexity : O(\max(m, n))
    ListNode dummyHead = new ListNode(0);
    ListNode p = l1, q = l2, curr = dummyHead;
    int carry = 0;
    while (p != null || q != null) {
        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);
    }
    return dummyHead.next;
}

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:
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.

My Solution

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        StringBuilder sb = new StringBuilder();
        char c;
        int maxLength = 0;
        for(int i = 0; i < s.length(); i++){
            c = s.charAt(i);
            if(sb.indexOf(""+c) > -1){
                maxLength = maxLength > sb.length() ? maxLength : sb.length();
                sb.replace(0,sb.length(),sb.substring(sb.indexOf(""+c)+1,sb.length()));
                sb.append(""+c);
            }else{
                sb.append(""+c);
            }
        }
        return maxLength > sb.length() ? maxLength : sb.length();
    }
}

Editorial Solution

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int n = s.length(), ans = 0;
        Map<Character, Integer> map = new HashMap<>(); // current index of character
        // try to extend the range [i, j]
        for (int j = 0, i = 0; j < n; j++) {
            if (map.containsKey(s.charAt(j))) {
                i = Math.max(map.get(s.charAt(j)), i);
            }
            ans = Math.max(ans, j - i + 1);
            map.put(s.charAt(j), j + 1);
        }
        return ans;
    }
}