524_linked_list_math.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 206. Reverse Linked List (important for staring)\n",
    "\n",
    "Reverse a singly linked list."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "# Definition for singly-linked list.\n",
    "# class ListNode(object):\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution(object):\n",
    "    def reverseList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        current = head\n",
    "        pre = None\n",
    "        while current:\n",
    "            tempt = current.next\n",
    "            current.next = pre\n",
    "            pre = current\n",
    "            current = tempt\n",
    "        return pre"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 21. Merge Two Sorted Lists\n",
    "\n",
    "Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        current = None\n",
    "        head = current = ListNode(0)\n",
    "        while l1 or l2:\n",
    "            if not l1:\n",
    "                current.next = l2\n",
    "                break\n",
    "            elif not l2:\n",
    "                current.next = l1\n",
    "                break\n",
    "            else:\n",
    "                if l1.val <= l2.val:\n",
    "                    current.next = ListNode(l1.val)\n",
    "                    l1 = l1.next\n",
    "                else:\n",
    "                    current.next = ListNode(l2.val)\n",
    "                    l2 = l2.next \n",
    "                current = current.next\n",
    "        return head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def mergeTwoLists(self, l1, l2):\n",
    "        \"\"\"\n",
    "        :type l1: ListNode\n",
    "        :type l2: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res = ListNode(-1)\n",
    "        pre = res\n",
    "        while(l1 and l2):\n",
    "            if l1.val <= l2.val:\n",
    "                pre.next = l1\n",
    "                l1 = l1.next\n",
    "            else:\n",
    "                pre.next = l2\n",
    "                l2 = l2.next\n",
    "            pre = pre.next\n",
    "        if(l1):\n",
    "            pre.next = l1\n",
    "        if(l2):\n",
    "            pre.next = l2\n",
    "        return res.next"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 141. Linked List Cycle (didn't come up with a solution)\n",
    "\n",
    "Given a linked list, determine if it has a cycle in it.\n",
    "\n",
    "Follow up:\n",
    "Can you solve it without using extra space?"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution_recursive(object):\n",
    "    def hasCycle(self, head):\n",
    "        return head is not None and self.check(head, head.next)\n",
    "\n",
    "    def check(self, slow, fast):\n",
    "        if fast is None or fast.next is None:\n",
    "            return False\n",
    "        if fast == slow:\n",
    "            return True\n",
    "        return self.check(slow.next, fast.next.next)\n",
    "\n",
    "\n",
    "class Solution_iterative(object):\n",
    "    def hasCycle(self, head):\n",
    "        slow = fast = head\n",
    "        while fast and fast.next:\n",
    "            slow = slow.next\n",
    "            fast = fast.next.next\n",
    "            if slow == fast:\n",
    "                return True\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 203. Remove Linked List Elements (There is not big difference between the runtime)\n",
    "\n",
    "Remove all elements from a linked list of integers that have value val."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def removeElements(self, head, val):\n",
    "        new_head = ListNode(0)\n",
    "        new_head.next = head\n",
    "        slow, fast = new_head, head\n",
    "        while fast:\n",
    "            if fast.val != val:\n",
    "                slow.next.val = fast.val\n",
    "                slow = slow.next\n",
    "            fast = fast.next\n",
    "        slow.next = None\n",
    "        return new_head.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def removeElements(self, head, val):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :type val: int\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        p = head\n",
    "        while p and p.val==val:\n",
    "            p = p.next\n",
    "        head = p\n",
    "        pre = None\n",
    "        while p:\n",
    "            if p.val==val:\n",
    "                pre.next  = p.next\n",
    "            else:\n",
    "                pre = p\n",
    "            p = p.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 328. Odd Even Linked List (Not explicit)\n",
    "\n",
    "Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.\n",
    "\n",
    "You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def oddEvenList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        n = 1\n",
    "        if head == None:\n",
    "            return head\n",
    "        if head.next == None:   # only one node\n",
    "            return head\n",
    "        else:\n",
    "            even = head.next\n",
    "            head2 = even  # record the start of the even linked list\n",
    "            if even.next == None:   # only two nodes\n",
    "                return head\n",
    "            else:\n",
    "                odd = even.next  # odd list start from the third one\n",
    "                head.next = odd\n",
    "                even.next = odd.next\n",
    "        while even.next:\n",
    "            even = even.next\n",
    "            odd.next = even.next\n",
    "            if not odd.next:\n",
    "                break\n",
    "            else:\n",
    "                odd = odd.next\n",
    "                even.next = odd.next     \n",
    "        odd.next = head2\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def oddEvenList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        cur1 = odd = ListNode(1)\n",
    "        cur2 = even = ListNode(1)\n",
    "        while head:\n",
    "            cur1.next = head\n",
    "            cur1 = cur1.next \n",
    "            head = head.next \n",
    "            if head:\n",
    "                cur2.next = head\n",
    "                cur2 = cur2.next \n",
    "                head = head.next \n",
    "        cur1.next = even.next \n",
    "        cur2.next = None \n",
    "        \n",
    "        return odd.next "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 367. Valid Perfect Square (not so easy, many methods to learn)\n",
    "\n",
    "Given a positive integer num, write a function which returns True if num is a perfect square else False."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://leetcode.com/problems/valid-perfect-square/discuss/130010/Python-4-Methods-with-time-testing"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solving with Bitwise trick."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    " def BitwiseTrick(self, num):\n",
    "       root = 0\n",
    "       bit = 1 << 15\n",
    "       \n",
    "       while bit > 0 :\n",
    "           root |= bit\n",
    "           if root > num // root:    \n",
    "               root ^= bit                \n",
    "           bit >>= 1        \n",
    "       return root * root == num"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Using Newton's Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def NewtonMethod(self, num):\n",
    "        r = num\n",
    "        while r*r > num:\n",
    "            r = (r + num/r) // 2\n",
    "        return r*r == num"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Math Trick for Square number is 1+3+5+ ... +(2n-1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def Math(self, num):\n",
    "        i = 1\n",
    "        while (num>0):\n",
    "            num -= i\n",
    "            i += 2       \n",
    "        return num == 0"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Binary Search Method"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def BinarySearch(self, num):\n",
    "        left = 0\n",
    "        right = num\n",
    "        \n",
    "        while left <= right:\n",
    "            mid = left + (right-left)//2\n",
    "            if  mid ** 2 == num:\n",
    "                return True\n",
    "            elif mid ** 2 > num:\n",
    "                right = mid -1\n",
    "            else:\n",
    "                left = mid +1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Linear Method (Naive) - For comparison"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def Linear(self, num):\n",
    "        i = 1\n",
    "        while i ** 2 <= num:\n",
    "            if i ** 2 == num:\n",
    "                return True\n",
    "            else:\n",
    "                i += 1\n",
    "        return False"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "I test these five methods with for i in range(100000): function(i), and get results as below.\n",
    "\n",
    "Time for Bitwise's Method : 0.45249104499816895\n",
    "\n",
    "Time for Newton's Method : 0.3492701053619385\n",
    "\n",
    "Time for Math's Method : 2.641957998275757\n",
    "\n",
    "Time for Binary Search's Method : 1.5031492710113525\n",
    "\n",
    "Time for Linear's Method : 17.613927125930786"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 413. Arithmetic Slices (well down!)\n",
    "\n",
    "A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 18,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def numberOfArithmeticSlices(self, A):\n",
    "        \"\"\"\n",
    "        :type A: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        flag = 0\n",
    "        count = 0\n",
    "        if len(A) <= 2:\n",
    "            return count\n",
    "        A[0] = A[1] - A[0]\n",
    "        for i in range(1, len(A)-1):\n",
    "            A[i] = A[i+1] - A[i] \n",
    "            if A[i] != A[flag]:\n",
    "                if i - flag >= 2:\n",
    "                    count += (i - flag) * (i - flag - 1)/2\n",
    "                flag = i\n",
    "        if len(A) - flag -1 >= 2:\n",
    "            count += (len(A) - flag -1) * (len(A) - flag -2)/2\n",
    "        return count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 171. Excel Sheet Column Number\n",
    "\n",
    "Given a column title as appear in an Excel sheet, return its corresponding column number."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def titleToNumber(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ref = {'A': 1, 'B': 2, 'C':3, 'D':4, 'E':5, 'F':6, 'G':7, 'H':8, 'I':9, 'J':10, 'K':11, 'L':12, 'M':13, 'N':14, 'O':15,\n",
    "               'P':16, 'Q':17, 'R':18, 'S': 19, 'T':20, 'U':21, 'V':22, 'W':23, 'X':24, 'Y':25, 'Z':26}\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            count += ref[s[i]] * 26**(len(s) - i - 1)\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution(object):\n",
    "    def titleToNumber(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        i = 0\n",
    "        res = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            p = len(s)-1 - i\n",
    "            res += (ord(s[p]) - 64) * pow(26, i)\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "use pow(), ord()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 9. Palindrome Number\n",
    "\n",
    "Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'123445'"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "class Solution(object):\n",
    "    def isPalindrome(self, x):\n",
    "        \"\"\"\n",
    "        :type x: int\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        if x < 0:\n",
    "            return False\n",
    "        elif x == 0:\n",
    "            return True\n",
    "        else:\n",
    "            x = str(x)\n",
    "            return x[::-1] == x"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 670. Maximum Swap (well done)\n",
    "\n",
    "\n",
    "Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 34,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def maximumSwap(num):\n",
    "        \"\"\"\n",
    "        :type num: int\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        num = list(str(num))\n",
    "        for i in range(len(num)-1):\n",
    "            if num[i] == max(num[i:]):    # find the one that is not the maximum\n",
    "                continue\n",
    "            else:\n",
    "                flag = i\n",
    "                for j in range(i+1, len(num)):    # find the biggest one after i to swap them\n",
    "                    if int(num[j]) >= int(num[flag]):  # it's very interesting to use >= instead of > here\n",
    "                        flag = j   # need to swap, find the maximum after i+1\n",
    "                num[i], num[flag] = num[flag], num[i]\n",
    "                break\n",
    "        return int(''.join(num))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}