sem06_dict/sem06_201.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Семинар 6"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 1: [камешки](https://leetcode.com/problems/jewels-and-stones/)\n",
    "\n",
    "У Дори в глубинах океана есть кучка камней. Часть камней из этой кучки драгоценные. Недавно она пересчитала все драгоценные и забыла сколько их. Чтобы больше не забывать, Дори решила написать на питоне функцию, которая будет считать камни за неё.\n",
    "\n",
    "Напишите на python функцию, которая принимает на вход список драгоценных камней $J$ и список камней, которые есть у Дори $S$. На выход функция возвращает число драгоценных камней в запасах Дори.\n",
    "\n",
    "__Примеры:__ \n",
    "\n",
    "> Input: J = \"aA\", S = \"aAAbbbb\" <br />\n",
    "Output: 3\n",
    "\n",
    "Тут драгоценными считаются камни a и A. У Дори есть камни aAAbbbb. Среди них три драгоценных, aAA.\n",
    "\n",
    ">Input: J = \"z\", S = \"ZZ\" <br />\n",
    "Output: 0\n",
    "\n",
    "Драгоценными мы считаем только камень z. У Дори два камня, оба обычные."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "### ╰( ͡° ͜ʖ ͡° )つ▬▬ι═══════  bzzzzzzzzzz\n",
    "# will the code be with you"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "3"
      ]
     },
     "execution_count": 62,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "S = \"aAAbbbb\"\n",
    "J = \"aA\"\n",
    "\n",
    "def slow_snones(J,S):\n",
    "    cnt = 0\n",
    "    for char in S:     # O(m*n)\n",
    "        if char in J:  # O(n)\n",
    "            cnt += 1\n",
    "    return cnt \n",
    "\n",
    "slow_snones(J,S)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# n - длина J\n",
    "# m - длина S\n",
    "\n",
    "# Сложность по времени: O(m*n)\n",
    "# Сложность по памяти:  O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 63,
   "metadata": {},
   "outputs": [],
   "source": [
    "def fast_snones(J,S):\n",
    "    cnt = 0\n",
    "    J_set = set(J)         # O(n)\n",
    "    for char in S:         # O(m*1)\n",
    "        if char in J_set:  \n",
    "            cnt += 1    \n",
    "    return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# n - длина J\n",
    "# m - длина S\n",
    "\n",
    "# Сложность по времени: O(m + n)\n",
    "# Сложность по памяти:  O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Дилемма: почти всегда можно ускорить асимптотическую работу кода, \n",
    "# если пожертвовать памятью и завести какую-нибудь дополнительную \n",
    "# структуру данных, которая нам помогает быстрее решать поставленную\n",
    "# задачу "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 2: тайные циклы и их сложности"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 35,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 35,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 42, -5, 0, 4]  # list \n",
    "4 in a   # Тайный цикл - O(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 36,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 36,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "b = {1, 42, -5, 0, 4}  # set\n",
    "4 in b  # Не цикл! Потому что set - хэш-таблица - O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 37,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 42, -5, 0, 4] \n",
    "\n",
    "b = set(a)  # превращение листа в set работает за O(n) \n",
    "4 in b      # O(1)\n",
    "\n",
    "# Итого: O(n) + O(1) = O(n + 1) = O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 40,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1"
      ]
     },
     "execution_count": 40,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = [1, 42, 42, -5, 0, 4] \n",
    "a.index(42)  # O(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 41,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "2"
      ]
     },
     "execution_count": 41,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a.count(42)  # O(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 43,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[4, 0, -5, 42, 42, 1]"
      ]
     },
     "execution_count": 43,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a[::-1]  # O(n) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[-5, 0, 1, 4, 42, 42]"
      ]
     },
     "execution_count": 44,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "sorted(a) # O(n*log n) - внутри sorted хитрый алгоритм "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 45,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Бывают функции глупые, которые работают влоб. \n",
    "# А бывают хитрые, внутри которых запакован какой-то алгоритм\n",
    "\n",
    "# Заглядывайте в документацию, чтобы понимать хитрая или влобая штука перед вами!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 3: [сумма двух](https://leetcode.com/problems/two-sum-ii-input-array-is-sorted)\n",
    "\n",
    "Дан массив из целых чисел `nums` и ещё одно целое число `target`.  Найдите все такие пары чисел из массива `nums`, которые в сумме дают число `target`. Выведите на экран их индексы. Одно и то же число использовать при подсчёте суммы дважды нельзя. Попытайтесь решить эту задачу максимально эффективно. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 64,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)]"
      ]
     },
     "execution_count": 64,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "z = 6\n",
    "\n",
    "ans = [ ]\n",
    "for item in x:\n",
    "    for jtem in x:\n",
    "        if item + jtem == z:\n",
    "            ans.append((item, jtem))\n",
    "ans  "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Сложность по времени:  O(n^2)\n",
    "# Сложность по памяти:   O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 65,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 5), (2, 4)]"
      ]
     },
     "execution_count": 65,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "z = 6\n",
    "\n",
    "n = len(x)\n",
    "\n",
    "ans = [ ]\n",
    "for i in range(n):\n",
    "    for j in range(i + 1, n) :\n",
    "        if x[j]+ x[i] == z:\n",
    "            ans.append((x[i], x[j]))\n",
    "ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Сложность по времени:  O( (n-1)*n/2 ) = O(n^2/2 - n/2) = O(n^2 - n)= O(n^2)\n",
    "# Сложность по памяти:   O(1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 67,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(1, 5), (2, 4), (3, 3), (4, 2), (5, 1)]"
      ]
     },
     "execution_count": 67,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "z = 6\n",
    "\n",
    "ans = [ ]\n",
    "\n",
    "x_set = set(x)\n",
    "for item in x:\n",
    "    if z - item in x_set:\n",
    "        ans.append((item, z-item))\n",
    "ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Сложность по времени:  O(n)\n",
    "# Сложность по памяти:   O(n)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 71,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)]"
      ]
     },
     "execution_count": 71,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x = [1, 2, 3, 4, 5, 6, 7, 8, 9]\n",
    "z = 6\n",
    "\n",
    "ans = [ ]\n",
    "\n",
    "# Если хочется сохранять не элементы, а индексы из массива\n",
    "x_dct = dict(zip(x, range(len(x))))\n",
    "\n",
    "for item in x:\n",
    "    if z - item in x_dct:\n",
    "        ans.append((x_dct[item], x_dct[z-item]))\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 4:  Пробелы\n",
    "\n",
    "Дана строка. Нужно удалить из неё пробелы без использования дополнительной памяти. \n",
    "\n",
    "```\n",
    "\"where   is         my       cookie\" -> \"where is my cookie\"\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(0, 'f'), (1, 'd'), (2, 's'), (3, 'd')]"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "list(enumerate('fdsd'))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[(5, 7), (10, 18), (21, 27)]"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = \"where   is         my       cookie\"\n",
    "\n",
    "idx = [ ]\n",
    "start = True\n",
    "ks, ke = 0,0\n",
    "\n",
    "for i,w in enumerate(text):\n",
    "    \n",
    "    if w == ' ' and start:\n",
    "        ks = i\n",
    "        start = False\n",
    "        \n",
    "    if w != ' ' and not start:\n",
    "        ke = i - 1\n",
    "        start = True\n",
    "        \n",
    "        idx.append((ks, ke))\n",
    "idx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'  '"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Цикл для удаления пробелов с конца!\n",
    "text[5:7]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'f'"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a = 'fff'\n",
    "b = a\n",
    "b = b[:1]\n",
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'fff'"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "'where is my cookie'"
      ]
     },
     "execution_count": 29,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "text = \"where   is         my       cookie\"\n",
    "\n",
    "def remove_spaces(text):\n",
    "    text_copy = text[::-1]\n",
    "\n",
    "    start = True\n",
    "    ks, ke = 0,0\n",
    "\n",
    "    n = len(text) - 1\n",
    "    for i,w in enumerate(text_copy):\n",
    "\n",
    "        if w == ' ' and start:\n",
    "            ks = n - i\n",
    "            start = False\n",
    "\n",
    "        if w != ' ' and not start:\n",
    "            ke = n - (i - 1)\n",
    "            start = True\n",
    "\n",
    "            text = text[:ke] + text[ks:]\n",
    "    return text\n",
    "\n",
    "remove_spaces(text)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# ┬─┬ ノ( ゜-゜ノ)\n",
    "\n",
    "# (╯° □°)╯︵ ┻━┻"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 5: палиндром\n",
    "\n",
    "Дана строчка `s`. Нужно проверить является ли она палиндромом. Палиндром - это число или текст, одинаково читающееся в обоих направлениях."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 47,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = 'abakaba'\n",
    "\n",
    "s == s[::-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 48,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Проблема такого решения - оно долгое! O(n) \n",
    "# Есть лишние действия!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 52,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 52,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Можно написать код выше в виде цикла:\n",
    "ans = True\n",
    "n = len(s) - 1\n",
    "\n",
    "for i in range(n):\n",
    "    if s[i] != s[n - i]:\n",
    "        ans = False\n",
    "ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a\n",
      "b\n",
      "a\n",
      "k\n"
     ]
    },
    {
     "data": {
      "text/plain": [
       "True"
      ]
     },
     "execution_count": 60,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "# Такой код по-прежнему работает за O(n)\n",
    "# Но он делает в 2 раза меньше действий O(n/2)\n",
    "s = 'abakfkaba'\n",
    "\n",
    "ans = True\n",
    "n = len(s) \n",
    "\n",
    "for i in range(n // 2):\n",
    "    print(s[i])\n",
    "    if s[i] != s[n - 1 - i]:\n",
    "        ans = False\n",
    "        break\n",
    "ans"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 6: сумма двух для разных массивов\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 72,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1, 4, 5, 6, -5, 0, 2]\n",
    "y = [5, 4, 3, -2, 4, 7, 0]\n",
    "goal = 6\n",
    "\n",
    "# Нужно написать быстрый код! "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 73,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Подумать :) "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Задачка 7: сумма трёх"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 74,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = [1, 4, 5, 6, -5, 0, 2]\n",
    "y = [5, 4, 3, -2, 4, 7, 0]\n",
    "z = [3, 4, 6, -3]\n",
    "goal = 6 # goal = z[i] + x[k] + y[j]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 75,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Подумать :)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "__Вопросы:__"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 84,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[['a', 'b', 2], ['c', 'd', 45], ['h', 'b', 3]]"
      ]
     },
     "execution_count": 84,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "s = [['h', 'b', 3], ['a', 'b', 2], ['c', 'd', 45]]\n",
    "\n",
    "x = sorted(s, key=lambda w: w[0])\n",
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 85,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['h', 'b', 3]"
      ]
     },
     "execution_count": 85,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x[2]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 86,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "[2, 45, 3]"
      ]
     },
     "execution_count": 86,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "[item[2] for item in x]"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "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.9.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}