My Personal Blog

Leetcode Q3

There are basically two options here

  1. O(n^3), loop through every possibility to find the longest substring
  2. Use a hashmap to indicate the position of each character. If a replicate character is encountered, and is contained in the current substring, current substring will be updated such that it will start from one character next to the previous one, curr count will be updated accordingly.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int lengthOfLongestSubstring(String s) {
        HashMap<Character, Integer> map = new HashMap<>();
        int longest = 0;
        int curr = 0;
        int prev = 0;
        for(int i=0; i < s.length(); i++){
            char c = s.charAt(i);
            if(map.get(c) != null && map.get(c) >= prev){
                prev = map.get(c);
                map.put(c, i);
                longest = Math.max(curr, longest);
                curr = i - prev;
                prev++;
            }else{
                map.put(c, i);
                curr++;
            }
        }
        longest = Math.max(curr, longest);
        return longest;
    }
}

leetcode Q2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/**
 * 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 dummy = new ListNode(0);
        ListNode curr = dummy;
        int carry = 0;
        
        while( l1 != null || l2 != null){
            int l1i = l1 != null ? l1.val : 0;
            int l2i = l2 != null ? l2.val : 0;
            int combine = (l1i + l2i) + carry;
            int newval = combine % 10;
            carry = combine / 10;
            
            ListNode tmp = new ListNode(newval);
            
            curr.next = tmp;
            curr = tmp;
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        
        if(carry != 0){
            curr.next = new ListNode(carry);
        }
            
        return dummy.next;
    }
}

Leetcode Q1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

Leetcode Q9

https://leetcode.com/problems/palindrome-number/description/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public boolean isPalindrome(int x) {
        if(x == 0)
            return true;
        if(x < 0)
            return false;
        long rev = 0;
        int val = x;
        int count = 0;
        while( val!= 0){
            rev = rev * 10 + val % 10;
            val /= 10;
            count++;
            if( rev > Integer.MAX_VALUE || rev < Integer.MIN_VALUE)
                return false;
        }
        int irev = (int)rev;
        while(x != irev){
            int shift = count * 10;
            int left = irev / shift;
            int right = x % 10;
            if( left != right)
                return false;
            x/= 10;
            irev /= shift;
            count--;
        }
        return true;
    }
}