leetcode.ipynb

{
  "nbformat": 4,
  "nbformat_minor": 0,
  "metadata": {
    "colab": {
      "name": "leetcode.ipynb",
      "provenance": [],
      "authorship_tag": "ABX9TyOpb1TuHIEnHmBfiD7CW3GM",
      "include_colab_link": true
    },
    "kernelspec": {
      "name": "python3",
      "display_name": "Python 3"
    }
  },
  "cells": [
    {
      "cell_type": "markdown",
      "metadata": {
        "id": "view-in-github",
        "colab_type": "text"
      },
      "source": [
        "<a href=\"https://colab.research.google.com/github/sweetpand/Algorithms/blob/master/leetcode.ipynb\" target=\"_parent\"><img src=\"https://colab.research.google.com/assets/colab-badge.svg\" alt=\"Open In Colab\"/></a>"
      ]
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "QJBvd0NT0Akb",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "intervals = [[1,3],[2,6],[8,10],[15,18]]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "J08tO_GG0RaE",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def merge(intervals):\n",
        "    out = []\n",
        "    for i in sorted(intervals, key=lambda i: i.start):\n",
        "        if out and i.start <= out[-1].end:\n",
        "            out[-1].end = max(out[-1].end, i.end)\n",
        "        else:\n",
        "            out += i,\n",
        "    return out"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "aLV2E1Ll0wPA",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "class Solution(object):\n",
        "    def merge(self, intervals):\n",
        "        \"\"\"\n",
        "        :type intervals: List[Interval]\n",
        "        :rtype: List[Interval]\n",
        "        \"\"\"\n",
        "        intervals.sort(key = lambda x: x.start)\n",
        "        i = 1\n",
        "        while i < len(intervals):\n",
        "            if intervals[i].start <= intervals[i-1].end:\n",
        "                intervals[i-1].end = max(intervals[i-1].end, intervals[i].end)\n",
        "                intervals.pop(i)\n",
        "            else:\n",
        "                i += 1\n",
        "        return intervals"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "mkwXzi531FYp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from typing import List\n",
        "class Solution:\n",
        "    def singleNumber(self, nums: List[int]) -> int:\n",
        "        return 2*sum(set(nums-sum(nums)))\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "m_lx4l791ySH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        ""
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "IGyTZ9rr1NxF",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\n",
        "def containsDuplicate(self, nums):\n",
        "  return not len(set(nums)) == len(nums)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "4Mq7U6vu2SIM",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def containsNearbyDuplicate(self,nums:List[int], k:int) -> bool:\n",
        "  d = {}\n",
        "  t = 0\n",
        "  for i in range(len(nums)):\n",
        "    t = nums\n",
        "    if not t in d or i - d[t] > k:\n",
        "      d[t] = i\n",
        "    else:\n",
        "      return True\n",
        "    return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "N0-h587Um1Lr",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from typing import List\n",
        "def removeDuplicates(self, nums: List[int]) -> int:\n",
        "    for i in range(len(nums)-1, 0, -1):\n",
        "      if nums[i]==nums[i-1]:\n",
        "        nums.pop(i)\n",
        "    return len(nums)"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "zjTwOkwCn2DJ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from typing import List\n",
        "def removeDuplicates(self, nums: List[int]) -> int:\n",
        "  i = 0\n",
        "  for n in nums:\n",
        "    if i < 2 or n > nums[i-2]:\n",
        "      nums[i] = n\n",
        "      i+=1\n",
        "    return i "
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "ofBf28rx7RvI",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "nums = [1,2,3,1]"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "7u8fYGXj7jrq",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "k = 3"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "y0LCuqM-7oPO",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "t = 0"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "nQyd1IQCoQrp",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "from typing import List \n",
        "def containsNearbyAlmostDuplicate(self, nums, k, t):\n",
        "        \"\"\"\n",
        "        :type nums: List[int]\n",
        "        :type k: int\n",
        "        :type t: int\n",
        "        :rtype: bool\n",
        "        \"\"\"\n",
        "\n",
        "        if k == 0 or (t==0 and len(nums)== len(set(nums))): \n",
        "            return False             \n",
        "        from collections import deque, defaultdict\n",
        "        myList = deque(maxlen=k+1)\n",
        "        myDict = defaultdict(int)\n",
        "        i = 0\n",
        "        while i < len(nums):\n",
        "            v = nums[i]\n",
        "            thisMin = v - t\n",
        "            thisMax = v + t\n",
        "            if len(myList) > 0 and not (min(myList) > thisMax or max(myList)< thisMin):\n",
        "                for key in myDict.keys():\n",
        "                    if myDict[key] != -1 and key >= thisMin and key <= thisMax:\n",
        "                        return True\n",
        "            myDict[v] = i\n",
        "            myList.append(v)\n",
        "            if len(myList) > k:\n",
        "                remove = myList.popleft()\n",
        "                myDict[remove] = -1\n",
        "            i += 1\n",
        "        return False\n",
        "                 \n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "OEJhHYdM9uZZ",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def containsNearbyAlmostDuplicate(self, nums: List[int], k: int, t: int) -> bool:\n",
        "        if t < 0: return False\n",
        "        d = {}\n",
        "        for i, (n, b)  in enumerate(zip(nums, map(lambda x: x // (t + 1), nums))):\n",
        "            if b in d or min(n - d.get(b - 1, float('-inf')), d.get(b + 1, float('inf')) - n) <= t: return True\n",
        "            d[b] = n\n",
        "            if i >= k: del d[nums[i - k] // (t + 1)]\n",
        "        return False"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "g4eucqO4-BGH",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def splitArray(self, nums:List[int], m:int)-> int:\n",
        "  def cal_sub(largest):\n",
        "    curS, sub = 0, 1\n",
        "    for n in nums:\n",
        "      curS+=n\n",
        "      if curS > largest:\n",
        "        sub+=1\n",
        "        curS = n\n",
        "      return sub\n",
        "  l, r = max(nums), sum(nums)\n",
        "  while l<r:\n",
        "    mid = (l+r)//2\n",
        "    if cal_sub(mid)>m:\n",
        "      l=mid+1\n",
        "    else:\n",
        "      r = mid\n",
        "  return l\n"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "AmHlfj-a_KHh",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "def check(expression):\n",
        "  open_tup = tuple('({[')\n",
        "  close_tup = tuple(')}]')\n",
        "  map = dict(zip(open_tup, close_tup))\n",
        "  queue = []\n",
        "  for i in expression:\n",
        "    if i in open_tup:\n",
        "      queue.append(map[i])\n",
        "    elif i in close_tup:\n",
        "      if not queue or i != queue.pop():\n",
        "          return 'Unbalanced'\n",
        "    return 'Balanced'"
      ],
      "execution_count": 0,
      "outputs": []
    },
    {
      "cell_type": "code",
      "metadata": {
        "id": "jE3pQpkV-uW2",
        "colab_type": "code",
        "colab": {}
      },
      "source": [
        "\n"
      ],
      "execution_count": 0,
      "outputs": []
    }
  ]
}