D5.ipynb

{
 "cells": [
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": "# 代码随想录算法训练营第五天｜242.有效的字母异位词  349. 两个数组的交集 202. 快乐数 1. 两数之和  ",
   "id": "e279aac39b88f511"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 哈希表理论基础 \n",
    "\n",
    "建议：大家要了解哈希表的内部实现原理，哈希函数，哈希碰撞，以及常见哈希表的区别，数组，set 和map。  \n",
    "\n",
    "什么时候想到用哈希法，当我们遇到了要快速判断一个元素是否出现集合里的时候，就要考虑哈希法。  这句话很重要，大家在做哈希表题目都要思考这句话。 \n",
    "\n",
    "文章讲解：https://programmercarl.com/%E5%93%88%E5%B8%8C%E8%A1%A8%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html  \n",
    "\n"
   ],
   "id": "fc6b1ba1766d861d"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 242.有效的字母异位词 \n",
    "\n",
    "建议： 这道题目，大家可以感受到 数组 用来做哈希表 给我们带来的遍历之处。 \n",
    "\n",
    "题目链接：https://leetcode.com/problems/valid-anagram/description/\n",
    "文章讲解/视频讲解： https://programmercarl.com/0242.%E6%9C%89%E6%95%88%E7%9A%84%E5%AD%97%E6%AF%8D%E5%BC%82%E4%BD%8D%E8%AF%8D.html  \n"
   ],
   "id": "c63333b652ddb777"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "思路：用一个数组来做哈希表，这个数组的索引是字符，值是字符出现的次数。  \n",
    "先遍历第一个字符串，把字符出现的次数记录到数组中；再遍历第二个字符串，把字符出现的次数减去。最后判断数组是否全为0。"
   ],
   "id": "d28eb102cdaac9e8"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-09T03:34:41.877181Z",
     "start_time": "2024-07-09T03:34:41.873171Z"
    }
   },
   "cell_type": "code",
   "source": [
    "class Solution:\n",
    "    def isAnagram(self, s: str, t: str) -> bool:\n",
    "        hashTable = [0] * 26\n",
    "        for i in s:\n",
    "            #并不需要记住字符a的ASCII，只要求出一个相对数值就可以了\n",
    "            hashTable[ord(i) - ord('a')] += 1\n",
    "        for j in t:\n",
    "            hashTable[ord(j) - ord('a')] -= 1\n",
    "        for k in hashTable:\n",
    "            if k:\n",
    "                #数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。\n",
    "                return False\n",
    "        return True"
   ],
   "id": "70bd0cc6d372beee",
   "outputs": [],
   "execution_count": 3
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 349. 两个数组的交集 \n",
    "\n",
    "建议：本题就开始考虑 什么时候用set 什么时候用数组，本题其实是使用set的好题，但是后来力扣改了题目描述和 测试用例，添加了 0 <= nums1[i], nums2[i] <= 1000 条件，所以使用数组也可以了，不过建议大家忽略这个条件。 尝试去使用set。 \n",
    "\n",
    "题目链接/文章讲解/视频讲解：https://programmercarl.com/0349.%E4%B8%A4%E4%B8%AA%E6%95%B0%E7%BB%84%E7%9A%84%E4%BA%A4%E9%9B%86.html  \n"
   ],
   "id": "35722043e065776f"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "第一想法：建立一个大小为两个数组中最大值+1的数组，然后遍历两个数组，第一个数组对应的位置为1，第二个数组只填在为1的位置，重赋值为2，过程中去重。最后遍历这个数组，如果是2，就加入到结果中。  \n",
    "问题：如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。  \n",
    "更好的方法：使用集合set去重，然后求交集。  \n",
    "缺点：占用空间比数组大，而且速度要比数组慢，set把数值映射到key上都要做hash计算的。"
   ],
   "id": "3cfea2e41f1a3025"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "Java代码：\n",
    "```java\n",
    "import java.util.HashSet;\n",
    "import java.util.Set;\n",
    "\n",
    "class Solution {\n",
    "    public int[] intersection(int[] nums1, int[] nums2) {\n",
    "        if (nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0) {\n",
    "            return new int[0];\n",
    "        }\n",
    "        Set<Integer> set1 = new HashSet<>();\n",
    "        Set<Integer> resSet = new HashSet<>();\n",
    "        //遍历数组1\n",
    "        for (int i : nums1) {\n",
    "            set1.add(i);\n",
    "        }\n",
    "        //遍历数组2的过程中判断哈希表中是否存在该元素\n",
    "        for (int i : nums2) {\n",
    "            if (set1.contains(i)) {\n",
    "                resSet.add(i);\n",
    "            }\n",
    "        }\n",
    "      \n",
    "        //方法1：将结果集合转为数组\n",
    "\n",
    "        return resSet.stream().mapToInt(x -> x).toArray();\n",
    "}\n",
    "```"
   ],
   "id": "bcf42581e56a9a98"
  },
  {
   "metadata": {
    "ExecuteTime": {
     "end_time": "2024-07-09T04:06:42.948118Z",
     "start_time": "2024-07-09T04:06:42.935622Z"
    }
   },
   "cell_type": "code",
   "source": [
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:\n",
    "        array = [0] * (max(max(nums1), max(nums2)) + 1)\n",
    "        #由于题目已经限定了nums1[i], nums2[i] <= 1000，所以可以直接设定数组大小为1001\n",
    "        output = []\n",
    "        for i in nums1:\n",
    "            array[i] = 1\n",
    "        for j in nums2:\n",
    "            if array[j]:\n",
    "                array[j] = 2\n",
    "        for k in range(len(array)):\n",
    "            if array[k] is 2:\n",
    "                output.append(k)\n",
    "        return output"
   ],
   "id": "d0ff438abd4cbf59",
   "outputs": [
    {
     "data": {
      "text/plain": [
       "dict"
      ]
     },
     "execution_count": 9,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "execution_count": 9
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 202. 快乐数 \n",
    "\n",
    "建议：这道题目也是set的应用，其实和上一题差不多，就是 套在快乐数一个壳子 \n",
    "\n",
    "题目链接/文章讲解：https://programmercarl.com/0202.%E5%BF%AB%E4%B9%90%E6%95%B0.html  \n"
   ],
   "id": "6a72f23ef8a33e51"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "注意循环条件： \n",
    "> Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.   \n",
    "\n",
    "需要记录每次计算的结果，如果出现重复的结果，就说明进入了循环，返回False：使用HashSet。  \n",
    "链接中有多种实现方式，可以回看。"
   ],
   "id": "748550809e3caa5d"
  },
  {
   "metadata": {},
   "cell_type": "code",
   "outputs": [],
   "execution_count": null,
   "source": [
    "class Solution:\n",
    "   def isHappy(self, n: int) -> bool:\n",
    "       record = set()\n",
    "       while n not in record:\n",
    "           record.add(n)\n",
    "           new_num = 0\n",
    "           n_str = str(n)\n",
    "           for i in n_str:\n",
    "               new_num+=int(i)**2\n",
    "           if new_num==1: return True\n",
    "           else: n = new_num\n",
    "       return False"
   ],
   "id": "e369f45ac205dd59"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "## 1. 两数之和 \n",
    "\n",
    "建议：本题虽然是 力扣第一题，但是还是挺难的，也是 代码随想录中 数组，set之后，使用map解决哈希问题的第一题。 \n",
    "\n",
    "建议大家先看视频讲解，然后尝试自己写代码，在看文章讲解，加深印象。 \n",
    "\n",
    "题目链接/文章讲解/视频讲解：https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html \n"
   ],
   "id": "f642acd178461929"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 什么时候使用哈希法：\n",
    "当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就要第一时间想到哈希法"
   ],
   "id": "5c56e73a0cd0acd8"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "### 四个重点：\n",
    "- 为什么会想到用哈希表\n",
    "- 哈希表为什么用map\n",
    "- 本题map是用来存什么的\n",
    "- map中的key和value用来存什么的"
   ],
   "id": "8dae0ce1118efe52"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "本题中我们不仅要知道元素有没有遍历过，还要知道这个元素对应的下标，需要使用 key value结构来存放，key来存元素，value来存下标，那么使用map正合适  \n",
    "这道题目中并不需要key有序，选择unordered_map 效率更高  \n",
    "map中的存储结构为 {key：数据元素，value：数组元素对应的下标}  \n",
    "__核心思路__：遍历每个元素，看看target - nums[i]是否在map中，如果在，返回下标，否则把当前元素存入map中"
   ],
   "id": "4a87617f83a82ec3"
  },
  {
   "metadata": {},
   "cell_type": "markdown",
   "source": [
    "java代码：\n",
    "```java\n",
    "import java.util.HashMap;\n",
    "//使用哈希表\n",
    "public int[] twoSum(int[] nums, int target) {\n",
    "    int[] res = new int[2];\n",
    "    if(nums == null || nums.length == 0){\n",
    "        return res;\n",
    "    }\n",
    "    Map<Integer, Integer> map = new HashMap<>();\n",
    "    for(int i = 0; i < nums.length; i++){\n",
    "        int temp = target - nums[i];   // 遍历当前元素，并在map中寻找是否有匹配的key\n",
    "        if(map.containsKey(temp)){\n",
    "            res[1] = i;\n",
    "            res[0] = map.get(temp);\n",
    "            break;\n",
    "        }\n",
    "        map.put(nums[i], i);    // 如果没找到匹配对，就把访问过的元素和下标加入到map中\n",
    "    }\n",
    "    return res;\n",
    "}\n",
    "```"
   ],
   "id": "d46fdf25993fc321"
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "initial_id",
   "metadata": {
    "collapsed": true
   },
   "outputs": [],
   "source": [
    "class Solution:\n",
    "    def twoSum(self, nums: List[int], target: int) -> List[int]:\n",
    "        records = dict()\n",
    "\n",
    "        for index, value in enumerate(nums):  \n",
    "            if target - value in records:   # 遍历当前元素，并在map中寻找是否有匹配的key\n",
    "                return [records[target- value], index]\n",
    "            records[value] = index    # 如果没找到匹配对，就把访问过的元素和下标加入到map中\n",
    "        return []"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}