Leetcode 3. Longest Substring Without Repeating Characters

解法1：

每次选取一个字符，从该字符开始往后遍历，存入HashSet中去，借助HashSet来判断是否重复出现，如果遇到重复字符，就结束循环，计算起始索引的长度，然后将HashSet清空，继续循环，再从第二个字符开始遍历，直到处理完所有字符。

此解法的时间复杂度是O(N^2)，最坏情况下时间复杂度是O(N^3)，因为HashSet的contains方法；空间复杂度是O(N)

解法2：

采用256大小的数组，利用

解法3：

滑动窗口算法。

此解法和上面的第一种解法有点类似，使用两个变量，一左一右，像窗口一样滑动，遇到重复值时，就将左边的一个字符从HashSet中移除，直到遍历完所有字符。

此解法的时间复杂度是O(N)，最坏情况下时间复杂度是O(N^2)，因为HashSet的contains方法；空间复杂度是O(N)。

解法如下：

如果使用hashset代替arraylist，速度会变快，arraylist应该可以保留substring

class Solution {

    public int lengthOfLongestSubstring(String s) {

        int left = 0;

        int right = 1;

        int n = s.length();

        int result = 1;

        ArrayList sl = new ArrayList();

        if (s.equals("")){

            System.out.println("empty string");

            return 0;

        }

        sl.add(s.charAt(0));

        while (left < n && right < n){

            char last = s.charAt(right);

            if (sl.contains(last)){

                left += sl.indexOf(last)+1;

                sl.subList(0, sl.indexOf(last)+1).clear();

            }

            sl.add(last);

            right += 1;

            result = Math.max(result, right-left);

        }

        

        return result;

    }

}

LeetCode 2. Add Two Numbers

思路与标准解法类似 

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode() {}

 *     ListNode(int val) { this.val = val; }

 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }

 * }

 */

class Solution {

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode l3 = new ListNode();

        ListNode curr = l3;

        int temp = 0;

        int val1 = 0;

        int val2 = 0;

        while (!(l1==null && l2==null)){

            if (l1==null){

                val1 = 0;

                val2 = l2.val;

            }

            else if (l2 == null){

                val1 = l1.val;

                val2 = 0;

            }

            else{

                val1 = l1.val;

                val2 = l2.val;

            }

            

            temp += val1 + val2;

            curr.val = temp %10;

            temp = temp/10;

            if (l1!=null) {l1 = l1.next;}

            if (l2!=null) {l2 = l2.next;}

            if (!(l1==null && l2==null && temp==0)){

                curr.next = new ListNode();

                curr = curr.next;

            }

        }

        if (temp == 1) {curr.val = temp;}

        return l3;

    }

}

LeetCode 307. Range Sum Query - Mutable

'''
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

The update(i, val) function modifies nums by updating the element at index i to val.
'''
#764ms, 15.8MB
class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums
     

    def update(self, i, val):
        """
        :type i: int
        :type val: int
        :rtype: None
        """
        self.nums[i] = val
     

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

LeetCode 200. Number of Islands

'''
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

'''
class Solution:
    def findANDsink(self, i, j):
        if self.grid[i][j] == '1':
            self.grid[i][j] = '0'
            if not i == 0:
                self.findANDsink(i-1, j)
            if i < self.n-1:
                self.findANDsink(i+1, j)
            if not j == 0:
                self.findANDsink(i, j-1)
            if j < self.m-1:
                self.findANDsink(i, j+1)
       
   
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid: return 0
       
        self.grid = grid
        self.n = len(grid)
        self.m = len(grid[0])
       
        i = 0
        j = 0
        self.count = 0
        for i in range(0, self.n):
            for j in range(0, self.m):
                if self.grid[i][j] == '1':
                    self.count += 1
                    self.findANDsink(i,j)
           
        return self.count

LeetCode 343. Integer Break

'''
Given a positive integer n, break it into the sum of at least two positive integers and maximize the product of those integers. Return the maximum product you can get.
'''
'''
first a few integers:
1: 0 (not available)
2: 1*1=1
3: 1*2=2
4: 2*2=4
5: 2*3=6
6: 3*3=9
7: 3*4=12

for n >= 4, can be break into 2s and 3s to max the product
proof:
if break into multiple numbers and one of it >= 5: it can be broken to get a larger product
so the max single number is 4, which is also 2*2   
   
'''

class Solution(object):
    def integerBreak(self, n):
        """
        :type n: int
        :rtype: int
        """
        if n == 1: return 0
        elif n == 2: return 1
        elif n == 3: return 2
        elif n == 4: return 4
        else:
            result = 1
            while n > 4:
                result *= 3
                n -=3
            result *= n
            return result

LeetCode 338. Counting Bits

'''
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array.
'''
'''
Solution;
when n = 2k: count(n) = n/2
when n = 2k+1: count(n) = count(n/2) +1
'''

#76ms, 16MB
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """
        if num == 0: return [0]
        elif num == 1: return [0,1]
       
        result = [0, 1]
        for i in range(2, num+1):
            if i%2 == 0:
                result.append(result[i/2])
            else:
                result.append(result[(i-1)/2]+1)
       
        return result

LeetCode 303. Range Sum Query - Immutable

'''
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Key is the calculation efficiency.
'''

class NumArray1(object):
#1088 ms, 15.3 MB
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.nums = nums

    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        return sum(self.nums[i:j+1])


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

class NumArray(object):
#144ms, 15.3MB
    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.list = []
        total = 0
        for i in nums:
            total += i
            self.list.append(total)
           
    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self.list[j]
        else:
            return self.list[j] - self.list[i-1]