523_hash_table.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 771. Jewels and Stones\n",
    "\n",
    "You're given strings J representing the types of stones that are jewels, and S representing the stones you have.  Each character in S is a type of stone you have.  You want to know how many of the stones you have are also jewels.\n",
    "\n",
    "The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so \"a\" is considered a different type of stone from \"A\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def numJewelsInStones(J, S):\n",
    "        \"\"\"\n",
    "        :type J: str\n",
    "        :type S: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        J = set(J)\n",
    "        count = 0\n",
    "        for letter in S:\n",
    "            if letter in J:\n",
    "                count += 1\n",
    "        return count"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 500. Keyboard Row\n",
    "\n",
    "Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def findWords(words):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        row1 = {'q', 'w', 'e', 'r', 't', 'y', 'u', 'i', 'o', 'p'}\n",
    "        row2 = {'a', 's', 'd', 'f', 'g', 'h', 'j', 'k', 'l'}\n",
    "        row3 = {'z', 'x', 'c', 'v', 'b', 'n', 'm'}\n",
    "        r = []\n",
    "        for word in words:\n",
    "            if len(set(word.lower()) - row1) == 0 or len(set(word.lower()) - row2) == 0 or len(set(word.lower()) - row3) == 0:\n",
    "                r.append(word)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def findWords(words):\n",
    "        \"\"\"\n",
    "        :type words: List[str]\n",
    "        :rtype: List[str]\n",
    "        \"\"\"\n",
    "        row1='qwertyuiop'\n",
    "        row2='asdfghjkl'\n",
    "        row3='zxcvbnm'\n",
    "        r=[]\n",
    "        for i in words:\n",
    "            if set(i.lower()).issubset(set(row1)):\n",
    "                r.append(i)\n",
    "            elif set(i.lower()).issubset(set(row2)):\n",
    "                r.append(i)\n",
    "            elif set(i.lower()).issubset(set(row3)):\n",
    "                r.append(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### issubset"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 463. Island Perimeter (poor)\n",
    "\n",
    "You are given a map in form of a two-dimensional integer grid where 1 represents land and 0 represents water. Grid cells are connected horizontally/vertically (not diagonally). The grid is completely surrounded by water, and there is exactly one island (i.e., one or more connected land cells). The island doesn't have \"lakes\" (water inside that isn't connected to the water around the island). One cell is a square with side length 1. The grid is rectangular, width and height don't exceed 100. Determine the perimeter of the island."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def islandPerimeter(grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        def peri(grid, i, j):\n",
    "            n = 0\n",
    "            if i>0 and grid[i-1][j] == 0 or i == 0:\n",
    "                n += 1\n",
    "            if i<len(grid)-1 and grid[i+1][j] == 0 or i == len(grid)-1:\n",
    "                n += 1\n",
    "            if j>0 and grid[i][j-1] == 0 or j == 0:\n",
    "                n += 1\n",
    "            if j<len(grid[0])-1 and grid[i][j+1] == 0 or j == len(grid[0])-1:\n",
    "                n += 1\n",
    "            return n\n",
    "                \n",
    "        perimeter = 0\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                if grid[i][j] == 1:\n",
    "                    perimeter += peri(grid, i, j)\n",
    "        return perimeter"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def islandPerimeter(self, grid):\n",
    "        \"\"\"\n",
    "        :type grid: List[List[int]]\n",
    "        :rtype: int\n",
    "       \n",
    "        \"\"\"\n",
    "        ret = 0\n",
    "        rows, cols = len(grid), len(grid[0])\n",
    "        for i in range(rows):\n",
    "            for j in range(cols):\n",
    "                if grid[i][j]:\n",
    "                    ret += 4\n",
    "                    if j and grid[i][j - 1]:   # every per has been count twice before\n",
    "                        ret -= 2\n",
    "                    if i and grid[i - 1][j]:\n",
    "                        ret -= 2\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 290. Word Pattern\n",
    "\n",
    "Given a pattern and a string str, find if str follows the same pattern.\n",
    "\n",
    "Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 16,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def wordPattern(pattern, str):\n",
    "        \"\"\"\n",
    "        :type pattern: str\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        str = str.split(' ')\n",
    "        def check(pattern, str):\n",
    "            record = {}\n",
    "            for i in range(len(pattern)):\n",
    "                if pattern[i] not in record.keys():\n",
    "                    if str[i] not in record.values():\n",
    "                        record[pattern[i]] = str[i]\n",
    "                    else:\n",
    "                        return False\n",
    "                elif record[pattern[i]] != str[i]:\n",
    "                    return False\n",
    "            return True\n",
    "        if len(pattern) > len(str):\n",
    "            return False\n",
    "        elif len(str) > len(pattern):\n",
    "            return False\n",
    "        else:\n",
    "            return check(pattern, str)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 17,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def wordPattern(self, pattern, str):\n",
    "        \"\"\"\n",
    "        :type pattern: str\n",
    "        :type str: str\n",
    "        :rtype: bool\n",
    "        \"\"\"\n",
    "        p2i, w2i = {}, {}\n",
    "        words = str.split(' ')\n",
    "        if len(pattern) != len(words):\n",
    "            return False\n",
    "        for i in range(len(pattern)):\n",
    "            if p2i.get(pattern[i]) != w2i.get(words[i]):\n",
    "                return False\n",
    "            p2i[pattern[i]] = w2i[words[i]] = i\n",
    "        return True"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### haven't use .get() before"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 438. Find All Anagrams in a String (didn't come up with a solution)\n",
    "\n",
    "Given a string s and a non-empty string p, find all the start indices of p's anagrams in s.\n",
    "\n",
    "Strings consists of lowercase English letters only and the length of both strings s and p will not be larger than 20,100.\n",
    "\n",
    "The order of output does not matter."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 22,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def findAnagrams(s, p):   # runtime error\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        ls = len(s)\n",
    "        lp = len(p)\n",
    "        setp = set(p)\n",
    "        r = []\n",
    "        for i in range(ls - lp+1):\n",
    "            ns = s[i:i+lp]\n",
    "            if set(ns) == setp and all(ns.count(l) == p.count(l) for l in ns):\n",
    "                r.append(i)\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 23,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def findAnagrams(self, s, p):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type p: str\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        if s == \"\":\n",
    "            return []\n",
    "        output  = []\n",
    "        correctdict = dict()\n",
    "        tempdict = dict()\n",
    "        for i in s+p:\n",
    "            if i not in correctdict:\n",
    "                correctdict[i] = 0\n",
    "                tempdict[i] = 0\n",
    "            \n",
    "        for i in p:\n",
    "            correctdict[i] += 1\n",
    "                \n",
    "        for i in s[0:len(p)]:\n",
    "            tempdict[i] += 1\n",
    "        if tempdict == correctdict:\n",
    "            output.append(0)  \n",
    "            \n",
    "        for i in range(len(s) - len(p)):\n",
    "            tempdict[s[i]] -= 1\n",
    "            tempdict[s[i + len(p)]] += 1\n",
    "            if tempdict == correctdict:\n",
    "                output.append(i + 1)\n",
    "\n",
    "            \n",
    "\n",
    "                \n",
    "        return output"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 389. Find the Difference\n",
    "\n",
    "Given two strings s and t which consist of only lowercase letters.\n",
    "\n",
    "String t is generated by random shuffling string s and then add one more letter at a random position.\n",
    "\n",
    "Find the letter that was added in t."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def findTheDifference(s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        for i in set(t):\n",
    "            if i not in set(s) or t.count(i)>s.count(i):\n",
    "                return i"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findTheDifference(self, s, t):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :type t: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        return list(collections.Counter(t) - collections.Counter(s))[0]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 508. Most Frequent Subtree Sum （Above 100%, well done!）\n",
    "\n",
    "Given the root of a tree, you are asked to find the most frequent subtree sum. The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def findFrequentTreeSum(root):\n",
    "        \"\"\"\n",
    "        :type root: TreeNode\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        record = {}\n",
    "        def calsum(root, record):\n",
    "            if root == None:\n",
    "                return 0\n",
    "            s = root.val + calsum(root.left, record) + calsum(root.right, record)\n",
    "            if s in record.keys():\n",
    "                record[s] += 1\n",
    "            else:\n",
    "                record[s] = 1\n",
    "            return s\n",
    "        calsum(root, record)\n",
    "        if len(record) == 0:\n",
    "            return []\n",
    "        \n",
    "        sums = sorted(record.keys(), key = lambda x:record[x], reverse = True)\n",
    "        r = [sums[0]]\n",
    "        for s in sums[1:]:\n",
    "            if record[s] == record[sums[0]]:\n",
    "                r.append(s)\n",
    "            else:\n",
    "                break\n",
    "        return r"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 347. Top K Frequent Elements\n",
    "\n",
    "Given a non-empty array of integers, return the k most frequent elements.\n",
    "\n",
    "For example,\n",
    "Given [1,1,1,2,2,3] and k = 2, return [1,2]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def topKFrequent(nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        record = {}\n",
    "        for num in nums:\n",
    "            if num not in record.keys():\n",
    "                record[num] = 1\n",
    "            else:\n",
    "                record[num] += 1\n",
    "        return sorted(record.keys(), key = lambda x:record[x], reverse = True)[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 28,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def topKFrequent(self, nums, k):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :type k: int\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        from collections import Counter\n",
    "        c=Counter(nums).most_common()#这里返回的是[(),()……]是以频率降序排列的\n",
    "        res=[]\n",
    "        count=0\n",
    "        for i in c:\n",
    "            if count<k:\n",
    "                res.append(i[0])\n",
    "                count+=1\n",
    "            else:\n",
    "                break\n",
    "        return res"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "#### need to get familiar with collections and Counter in it."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 454. 4Sum II （exceed time limit, should use collections!）\n",
    "\n",
    "Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l] is zero.\n",
    "\n",
    "To make problem a bit easier, all A, B, C, D have same length of N where $0 \\le N \\le 500$. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most $2^{31} - 1$."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 31,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def fourSumCount(self, A, B, C, D):\n",
    "        a_b = collections.Counter(i + j for i in A for j in B); return sum(a_b[-k - l] for k in C for l in D if -k - l in a_b)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 648. Replace Words (poor, need to learn from the better solution)\n",
    "\n",
    "In English, we have a concept called root, which can be followed by some other words to form another longer word - let's call this word successor. For example, the root an, followed by other, which can form another word another.\n",
    "\n",
    "Now, given a dictionary consisting of many roots and a sentence. You need to replace all the successor in the sentence with the root forming it. If a successor has many roots can form it, replace it with the root with the shortest length.\n",
    "\n",
    "You need to output the sentence after the replacement."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [],
   "source": [
    "    def replaceWords(dict, sentence):\n",
    "        \"\"\"\n",
    "        :type dict: List[str]\n",
    "        :type sentence: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        dict = sorted(dict, key = lambda x:len(x))\n",
    "        words = sentence.split(' ')\n",
    "        for i in range(len(words)):\n",
    "            for root in dict:\n",
    "                if root == words[i][:len(root)]:\n",
    "                    words[i] = root\n",
    "        return ' '.join(words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def replaceWords(self, dt, sentence):\n",
    "        \"\"\"\n",
    "        :type dict: List[str]\n",
    "        :type sentence: str\n",
    "        :rtype: str\n",
    "        \"\"\"\n",
    "        trie = {}\n",
    "        for w in dt:\n",
    "            t = trie\n",
    "            for c in w:\n",
    "                if c not in t:  t[c] = {}\n",
    "                t = t[c]\n",
    "            t['#'] = w\n",
    "            \n",
    "        # result = []\n",
    "        \n",
    "#         for word in sentence.split():\n",
    "#             result.append(self.replace(word, trie))\n",
    "        \n",
    "#         return \" \".joinresult \n",
    "    \n",
    "#     OR\n",
    "        return  \" \".join([ self.replace(i, trie) for i in sentence.split() ])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 739. Daily Temperatures (run time exceed limit, learn from better solutions)\n",
    "\n",
    "Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.\n",
    "\n",
    "For example, given the list temperatures = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].\n",
    "\n",
    "Note: The length of temperatures will be in the range [1, 30000]. Each temperature will be an integer in the range [30, 100]."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 39,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "    def dailyTemperatures(temperatures):\n",
    "        \"\"\"\n",
    "        :type temperatures: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        \n",
    "        #find minm diff, minm index\n",
    "        \n",
    "        #using stack\n",
    "        n = len(temperatures)\n",
    "        stacks = []\n",
    "        warmer = [0 for i in range(n)]\n",
    "        stacks.append(n-1)\n",
    "        \n",
    "        for i in range(n-1,-1,-1):\n",
    "            \n",
    "            while len(stacks) != 0 and temperatures[i] >= temperatures[stacks[-1]]:\n",
    "                stacks.pop()\n",
    "            \n",
    "            if len(stacks) != 0:\n",
    "                warmer[i] = stacks[-1] - i  \n",
    "            \n",
    "            stacks.append(i)\n",
    "            #print(stacks)\n",
    "            \n",
    "            \n",
    "        return warmer"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 94. Binary Tree Inorder Traversal  (should be familiar with three types of traversals and the iterative and recursive mthod)\n",
    "\n",
    "Given a binary tree, return the inorder traversal of its nodes' values."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution_iterative:\n",
    "    def inorderTraversal(self, root):\n",
    "        ans, stack, node = [], [], root\n",
    "        while stack or node:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            node = stack.pop()\n",
    "            ans.append(node.val)\n",
    "            node = node.right\n",
    "        return ans\n",
    "\n",
    "\n",
    "class Solution_iterative2:\n",
    "    def inorderTraversal(self, root):\n",
    "        ans, stack = [], [(0, root)]\n",
    "        while stack:\n",
    "            seen, node = stack.pop()\n",
    "            if node is None:\n",
    "                continue\n",
    "            if not seen:\n",
    "                stack.extend([(0, node.right), (1, node), (0, node.left)])\n",
    "            else:\n",
    "                ans.append(node.val)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": []
  }
 ],
 "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
}