LeetCode: Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A = [1,1,1,2,2,3],

Your function should return length = 5, and A is now [1,1,2,2,3].

Solution:

public class Solution {
    public int removeDuplicates(int[] A) {
        int count = 0;
        int value = Integer.MIN_VALUE;
        int i = 0;
        int len = A.length;
        while (i<len)
        {
            if (A[i]==value)
                count++;
            else
            {
                count = 1;
                value = A[i];
            } 
            if(count>2)
                moveToEnd(A,i,--len);
            else
                i++;
        }
        return len;
    }
    
    private void moveToEnd(int[]A, int pos1, int end)
    {
        for(int i= pos1; i<end; i++)
            swap(A, i, i+1);
    }
    
    private void swap (int[] A, int pos1, int pos2)
    {
        int temp = A[pos1];
        A[pos1] = A[pos2];
        A[pos2] = temp;
    }
}

LeetCode (Python): Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution:

# Definition for a  binary tree node
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    # @param p, a tree node
    # @param q, a tree node
    # @return a boolean
    def isSameTree(self, p, q):
        if p == None and q == None:
            return True
        if p == None or q == None:
            return False
        if p.val != q.val:
            return False
        solution = self.isSameTree(p.left, q.left)
        solution = solution and self.isSameTree(p.right, q.right)
        return solution

LeetCode: Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.

Solution:

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p== null && q== null)
            return true;
        if(p== null || q== null)
            return false;
        if(p.val!=q.val)
            return false;
        boolean solution = isSameTree(p.left, q.left);
        solution = solution && isSameTree(p.right, q.right);
        return solution;
    }
}

LeetCode (Python): Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

Solution:

class Solution:
    # @return an integer
    def lengthOfLongestSubstring(self, s):
        lastRepeating = -1
        longestSubstring = 0
        positions = {}
        for i in range(0, len(s)):
            if s[i] in positions and lastRepeating<positions[s[i]]:
                lastRepeating = positions[s[i]]
            if i-lastRepeating > longestSubstring:
                longestSubstring = i-lastRepeating
            positions [s[i]]=i
        return longestSubstring

LeetCode (Python): Restore IP Addresses

Given a string containing only digits, restore it by returning all possible valid IP address combinations.

For example:
Given "25525511135",

return ["255.255.11.135", "255.255.111.35"]. (Order does not matter)

Solution:

class Solution:
    # @param s, a string
    # @return a list of strings
    def restoreIpAddresses(self, s):
        solution = [] 
        self.restoreIpAddressesRec(s,0,0,[],solution)
        return solution
    
    def restoreIpAddressesRec(self, s, index, octets, tempSolution, solution):
        if len(s)-index<4-octets:
                return
        if len(s)-index>3*(4-octets):
                return  
        if octets==4:
            if index== len(s):
                tempSolution.pop()
                solution.append("".join(tempSolution))
                tempSolution.append('.')
            return
        for size in range(1,4):
            if s[index]=='0' and size>1:
                break
            if int(s[index:index+size])>255:
                break
            tempSolution.append(s[index:index+size])
            tempSolution.append('.')
            self.restoreIpAddressesRec(s,index+size,octets+1,tempSolution, solution)
            tempSolution.pop()
            tempSolution.pop()

Leetcode (Python): Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

class Solution:
    # @param prices, a list of integer
    # @return an integer
    def maxProfit(self, prices):
        solution = 0
        for i in range (1, len(prices)):
            if prices[i]>prices[i-1]:
                solution += (prices[i]-prices[i-1])
        return solution

Leetcode: Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

Solution:

public class Solution {
    public int maxProfit(int[] prices) {
        int benefit =0;
        for(int i=1; i<prices.length; i++)
            if(prices[i]>prices[i-1])
                benefit += (prices[i]-prices[i-1]);
        return benefit;
    }
}