⑴ 103. leetcode笔记(1~60)
d1
https://leetcode-cn.com/problems/two-sum
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
【hashmap存储】
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
【奇偶判断】
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
【双循环贪心】
d2
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
输入: 121
输出: true
【折半比较】
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。
注意:
假设字符串的长度不会超过 1010。
示例：
输入:
"abccccdd"
输出:
7
【集合更新与判空】(add remove, 放入可回文的字符，无重复)
给你一个字符串 s 和一个字符规律 p ，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。
'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 **整个 **字符串 s 的，而不是部分字符串。
说明:
【正则包与结果项】
d3
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
示例:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
【新计数索引】
给定一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
【while val存在】
实现 strStr() 函数：
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。
示例:
输入: haystack = "hello", needle = "ll"
输出: 2
【str.index(p)】
d4
【分支递归乘数】
给定一个整数数组 nums，求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和，包含 i, j 两点。
给定 nums = [-2, 0, 3, -5, 2, -1]，求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
【缓存和】
给定一个二进制数组，你可以最多将 1 个 0 翻转为 1，找出其中最大连续 1 的个数。
输入：[1,0,1,1,0]
输出：4
解释：翻转第一个 0 可以得到最长的连续 1。
当翻转以后，最大连续 1 的个数为 4。
【最近0的出现位置】
d5
对于一个 正整数，如果它和除了它自身以外的所有正因子之和相等，我们称它为“完美数”
输出: True
解释: 28 = 1 + 2 + 4 + 7 + 14
【折平根比较】
修改一个数，则变成非递减数列，输出True
【嵌套条件分支】
123456789101112...求出第N个数字对应的单字符数值
【while True中的数量级t和求解条件m】
d6
列表中存在最大长度为k的两个相等的数，则返True
给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j，使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。如输入: nums = [1,2,3,1], k = 3， 输出: true
【集合表示滑动窗口】
【双指针追踪】
两个数不是同一个数，存在某数2倍数的一个数则返回True
【判双零】
d7
两个数值型字符串，相加后返回结果字符串
【while中低位进位】
求节点与其祖先之间的最大差，如：
【左右递归dfs返回最大差】
一排人领糖果, 相邻的人rating高的获得较多糖，每人都有糖果。
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？如输入: [1,0,2], 输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
【左右规则】
d8
返回链表中倒数第k个节点值
【双指针追踪】
是否平衡二叉树，即任意一个节点其两颗子树的高度差不超过一。
【递归返回是否平衡和树高】
【三重while中低位进位】
d9
删除链表中的节点
【制造伪头结点】
之字形层次遍历二叉树，如:
【递归含层数的层次遍历与折返判断】
如果一个数的左边数组和与右边数组和相等，则返回此中间数的索引。
【从左累加与总和比较】
d10
输出二叉树的镜像， 如：
【制造临时节点的自身递归】
自底向上遍历二叉树，如：
【递归层次遍历】
【含hashmap[depth]的dfs递归】
d11
返回除法结果，不越界[-2**31， 2**31-1]
【正负/零划分】
一个数的二进制表示中1的个数
【带奇偶判断的逐右移位】
移除所有值为val的节点，返回链表。如输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
【含有目标比较的自身递归】
d12
实现int sqrt(int x)函数
【牛顿迭代】
【两次判空与全存在的各自相加】
求出根到叶子节点路径总和为固定值的所有路径集
【目标递减下叶子和当前更新的路径和与目标值的比较】
d13
数组中是否有独一无二的出现次数
【hashmap计数与值数组判重】
给定一个无序的整数数组，找到其中最长上升子序列的长度。如输入: [10,9,2,5,3,7,101,18]
输出: 4 ，解释: 最长的上升子序列是 [2,3,7,101]，它的长度是 4。
【双循环动态规划】
【递归判断】
d14
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。
注意你不能在买入股票前卖出股票。如输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。
【最低股价与最大利润同时更新】
输入一个整型数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。
要求时间复杂度为O(n)。如输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6, 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
【max0 sum0初始索引0赋值，与sum0>0判断】
给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。如输入: n = 12
输出: 3 ，解释: 12 = 4 + 4 + 4
【动态规划双循环解背包问题】
d15
统计所有小于非负整数 n 的质数的数量。如输入: 10
输出: 4，解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
【筛去法】
找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。如输入: n = 10
输出: 12， 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
【三指针动态规划】
给定一个整数数组 prices，其中第 i 个元素代表了第 i 天的股票价格 ；非负整数 fee 代表了交易股票的手续费用。
你可以无限次地完成交易，但是你每次交易都需要付手续费。如果你已经购买了一个股票，在卖出它之前你就不能再继续购买股票了。
返回获得利润的最大值。如输入: prices = [1, 3, 2, 8, 4, 9], fee = 2
输出: 8，解释: 能够达到的最大利润:
在此处买入 prices[0] = 1
在此处卖出 prices[3] = 8
在此处买入 prices[4] = 4
在此处卖出 prices[5] = 9
总利润: ((8 - 1) - 2) + ((9 - 4) - 2) = 8.
【买入卖出的动态规划】
d16
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
如输入: [7,1,5,3,6,4]
输出: 7
解释:
在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出,
这笔交易所能获得利润 = 5-1 = 4 。
随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出,
这笔交易所能获得利润 = 6-3 = 3 。
【同leet714 多次买卖的动态规划】
是否是相同的树
【同空、不同空判断后的自身递归】
不特定根节点和叶子节点，返回路径总和为固定值的路径数
【自身递归与dfs递归】
d17
找出右边的值小于当前值的数的个数：
使用线段树构建左右子树，并从右到左计算前面的数小于当前值的数的个数，最终返回依次进入结果数组的list的倒置值。
【list复制法】
将遍历到的前两个和数都去掉，双重遍历T(n)= O(n)
规范的路径表示写法转换为最简路径
【栈进栈出，判断'' '.' '..'()】
d18
【复制字符库，逐次后移匹配库起始点】
按要求分一个数组为m份，求其中子数组的最大值中最小一个
【二分查找、设定子数组最大的和mid作划分节点】
【二分思想，拆分数组递归】(不用判断平衡)
d19(52%)
两个字符串对应位置移动总次数在指定步数内(ascii值的差)，求字符串的最大可变换长
【滑窗记录更新最初位置、不断更新当前滑窗内移动步数最小值】
⑵ leetcode算法
*最近在做一些 leetcode 的算法题，我会将自己做过的算法题记录下来以供大家参考，如果查找不方便请看 油猴插件实现网站左侧目录生成。
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例：
解答：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。
注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。
示例：
提示：
解答：
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例：
说明:
解答：
给定一个整数数组，判断是否存在重复元素。
如果任意一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例：
解答：
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例：
解答：
给定两个数组，编写一个函数来计算它们的交集。
示例：
说明：
进阶:
解答：
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
示例：
解答：
给定一个数组 nums ，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
说明:
给定一个整数数组 nums 和一个目标值 target ，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例：
解答：
判断一个 9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数独部分空格内已填入了数字，空白格用 '.' 表示。
示例：
说明:
解答：
给定一个 *n *× *n* 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。 请不要 使用另一个矩阵来旋转图像。
示例：
解答：
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须 原地修改输入数组 、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例：
解答：
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例：
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
解答：
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
示例：
解答：
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
长度一样，包含的字母都一样，每个字符出现的频率也一样，只是顺序不同而已，这就属于异位词，
示例：
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
解答：
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明 ：本题中，我们将空字符串定义为有效的回文串。
示例：
解答：
请你来实现一个 atoi 函数，使其能将字符串转换成整数。
首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。接下来的转化规则如下：
注意 ：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换，即无法进行有效转换。
在任何情况下，若函数不能进行有效的转换时，请返回 0 。
提示 ：
示例：
解答：
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始) 。如果不存在，则返回 -1 。
示例：
说明:
当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。
对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符
解答：
“外观数列”是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。前五项如下：
1 被读作 "one 1" ("一个一") , 即 11 。
11 被读作 "two 1s" ("两个一") , 即 21 。
21 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211 。
给定一个正整数 n（1 ≤ n ≤ 30），输出外观数列的第 n 项。
注意 ：整数序列中的每一项将表示为一个字符串。
示例：
解答：
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 "" 。
示例：
说明:
所有输入只包含小写字母 a-z 。
解答：
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 -- head = [4,5,1,9]，它可以表示为:
示例：
说明：
解答：
给定一个链表，删除链表的倒数第 n 个节点，并且返回链表的头结点。
示例：
说明：
给定的 n 保证是有效的。
进阶：
你能尝试使用一趟扫描实现吗？
解答：
反转一个单链表。
示例：
解答：
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例：
解答：
请判断一个链表是否为回文链表。
示例：
解答：
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1 ，则在该链表中没有环。
示例：
解答：
给定一个二叉树，找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明 : 叶子节点是指没有子节点的节点。
示例：
给定二叉树 [3,9,20,null,null,15,7] ，
返回它的最大深度 3 。
解答：
给定一个二叉树，判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征：
示例：
解答：
给定一个二叉树，检查它是否是镜像对称的。
例如，二叉树 [1,2,2,3,4,4,3] 是对称的。
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
解答：
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树： [3,9,20,null,null,15,7] ,
返回其层次遍历结果：
解答：
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例：
给定有序数组: [-10,-3,0,5,9] ,
一个可能的答案是: [0,-3,9,-10,null,5] ，它可以表示下面这个高度平衡二叉搜索树：
解答：
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
说明:
示例:
解答：
你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, ..., n] ，你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例：
解答：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意 ：给定 n 是一个正整数。
示例：
解答：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意 ：你不能在买入股票前卖出股票。
示例：
解答：
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
解答：
你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。
给定一个代表每个房屋存放金额的非负整数数组，计算你在不触动警报装置的情况下，能够偷窃到的最高金额。
示例：
解答：
打乱一个没有重复元素的数组。
示例：
解答：
设计一个支持 push ， pop ， top 操作，并能在常数时间内检索到最小元素的栈。
示例：
解答：
写一个程序，输出从 1 到 n 数字的字符串表示。
示例：
解答：
统计所有小于非负整数 n 的质数的数量。
示例：
解答：
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例：
解答：
罗马数字包含以下七种字符: I ， V ， X ， L ， C ， D 和 M 。
例如，罗马数字 2 写做 II ，即为两个并列的 1 。 12 写做 XII ，即为 X + II 。 27 写做 XXVII , 即为 XX + V + II 。
通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII ，而是 IV 。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX 。这个特殊的规则只适用于以下六种情况：
示例：
解答：
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为 汉明重量 ）。
示例：
提示：
⑶ 猪喝毒水 信息熵
事情的起因是有这么一道题：
25桶水其中一桶有毒，猪喝水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
看到这个题，我直接就使用了二分法，25桶直接分成12桶+12桶+1桶，然后12分6，6分3，3分1，最终计算结果是需要5头猪，反过来理解，也就是 ，现在就25桶水，当然答案是5头猪。然而我这个答案是错的……
网络了一下，发现是一道leecode题目，正确答案是2。解法也很容易理解，这里借用网络到的一张图来帮助理解，如果我下面的解释没看懂，也可以去看一下博主原文： [leetcode]——哪桶水有毒
如图，把25桶水分成5行5列，派两头猪，一个逐行喝( 注意是一次性喝掉这一行的5桶水的混合物 )，一个逐列喝。以逐列的猪为例，15分钟后死了说明毒水在第1列，如果活着就继续去喝第2列，然后分别等到30、45、60分钟观察是否死亡来锁定是哪一列，如果60分钟还没死，说明前面4列都没毒水，那么用排除法就知道毒水只能在第5列。逐行猪同理，最终只要锁定了行列数，那么交叉点必然是毒水所在位置。
可以观察到，这种解法的关键是，一头猪充分利用了15分钟的间隔，在1个小时内直接辨明了5大桶水(实际是5桶混合水)是否有毒。如果题目改成是10分钟的间隔呢，那1个小时就能辨明7桶水了。此时7的2次方是49，仍然需要2头猪。
再扩展一下，仍然是15分钟间隔，但总共是1000桶水呢？实际上，一头猪只能辨明5，两个维度只能是5乘以5，再来一头，就是5的3次方；很容易发现，问题实际变成求5的多少次方能大于1000，答案易得是5头猪。其实这时候5的5次方是3125，也就是说即使是3000桶水，5头猪也是够的。
再扩展一下，如果是15分钟间隔，但要求是15分钟搞定，而不是一个小时呢？这时候会发现，15分钟结束后，猪只有两个状态，要么死要么活。也就是每一行或每一列实际上只能放2桶水。那么 问题就变成2的多少次方大于25，哎，此时的答案和我刚开始使用的二分法是完全一致的。这个时候，我才意识到，我的二分法，实际上不需要1小时，仅仅15分钟就能搞定辨明毒水的目的。因为题目中说了，每桶水是无限多的，那我可以先按二分的思路，把25桶水全部都拆好，然后一声令下，5头猪同时上去喝对应的分组，当然是15分钟后就知道结果了。
然而事情到现在，才刚刚开始……比如这个知乎3万赞的回答：
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？ - 苗华栋的回答 - 知乎
作者上来就丢出信息熵的定义和公式：
然后用这公式一顿计算，把我看懵逼了。这里建议先通过别的链接，来补一下基础知识。
参考 信息熵是什么？ - 运筹之学的回答 - 知乎
信息熵，信息熵，怎么看怎么觉得这个“熵”字不顺眼，那就先不看。我们起码知道这个概念跟信息有关系。而它又是个数学模型里面的概念，一般而言是可以量化的。所以，第一个问题来了： 信息是不是可以量化？
起码直觉上而言是可以的，不然怎么可能我们觉得有些人说的废话特别多，“没什么信息量”，有些人一语中的，一句话就传达了很大的信息量。
有些事情本来不是很确定，例如明天股票是涨还是跌。如果你告诉我明天NBA决赛开始了，这两者似乎没啥关系啊，所以你的信息对明天股票是涨是跌带来的信息量很少。但是假如NBA决赛一开始，大家都不关注股票了没人坐庄股票有99%的概率会跌，那你这句话信息量就很大，因为本来不确定的事情变得十分确定。
而有些事情本来就很确定了，例如太阳从东边升起，你再告诉我一百遍太阳从东边升起，你的话还是丝毫没有信息量的，因为这事情不能更确定了。
所以说信息量的大小跟事情不确定性的变化有关。
一，跟事情的可能结果的数量有关；二，跟概率有关。
先说一。例如我们讨论太阳从哪升起。本来就只有一个结果，我们早就知道，那么无论谁传递任何信息都是没有信息量的。当可能结果数量比较大时，我们得到的新信息才有潜力拥有大信息量。
二，单看可能结果数量不够，还要看初始的概率分布。例如一开始我就知道小明在电影院的有15*15个座位的A厅看电影。小明可以坐的位置有225个，可能结果数量算多了。可是假如我们一开始就知道小明坐在第一排的最左边的可能是99%，坐其它位置的可能性微乎其微，那么在大多数情况下，你再告诉我小明的什么信息也没有多大用，因为我们几乎确定小明坐第一排的最左边了。那么，怎么衡量不确定性的变化的大小呢？怎么定义呢？这个问题不好回答，但是假设我们已经知道这个量已经存在了，不妨就叫做信息量，那么你觉得信息量起码该满足些什么特点呢？
那有什么函数能满足上面四个条件呢？
负的对数函数，也就是-log（x）！底数取大于1的数保证这个函数是非负的就行。前面再随便乘个正常数也行。
a. 为什么不是正的？因为假如是正的，由于x是小于等于1的数，log（x）就小于等于0了。第一个特点满足。
b. 咱们再来验证一下其他特点。三是最容易的。假如x是一个概率，那么log（x）是连续依赖于x的。donec。
四呢？假如有n个可能结果，那么出现任意一个的概率是1/n，而-log(1/n)是n的增函数，没问题。
d。最后验证二。由于-log(xy) = -log(x) -log(y)，所以也是对的。学数学的同学注意，这里的y可以是给定x的条件概率，当然也可以独立于x。By the way，这个函数是唯一的（除了还可以多乘上任意一个常数），有时间可以自己证明一下，或者查书。
ok，所以我们知道一个事件的信息量就是这个事件发生的概率的负对数。最后终于能回到信息熵。信息熵是跟所有可能性有关系的。每个可能事件的发生都有个概率。信息熵就是平均而言发生一个事件我们得到的信息量大小。所以数学上，信息熵其实是信息量的期望。（表达式参考其它答案或者看下面）
参考 信息熵是什么？ - D.Han的回答 - 知乎
赌马比赛里，有4匹马{A,B,C,D},获胜概率为{1/2,1/4,1/8,1/8}。接下来，让我们将哪一匹马获胜视为一个随机变量X。
假定我们需要用尽可能少的二元问题来确定随机变量 X 的取值。例如：问题1：A获胜了吗？问题2：B获胜了吗？问题3：C获胜了吗？最后我们可以通过最多3个二元问题，来确定X的取值，即哪一匹马赢了比赛。
那么很容易计算，在这种问法下，为确定X取值
当我们使用上述的信息熵公式，是这样的：
-1/2*log(1/2) + -1/4*log(1/4) + -1/8*log(1/8) + -1/8*log(1/8)
这里很容易计算结果，比如： -1/2*log(1/2) = -1/2 * (log1 - log2) = 1/2 * log2 = 1/2 ，最终结果就是：
1/2+1/2+3/8+3/8 = 7/4
可以发现，信息熵公式计算结果与之前计算是一致的。在二进制计算机中，一个比特为0或1，其实就代表了一个二元问题的回答。也就是说，在计算机中，我们给哪一匹马夺冠这个事件进行编码，所需要的平均码长为1.75个比特。
很显然，为了尽可能减少码长，我们要给发生概率较大的事件，分配较短的码长 。这个问题深入讨论，可以得出霍夫曼编码的概念。
扩展阅读可以参考 H264系列九 热力学熵 信息熵 哈夫曼编码 哥伦布编码 ，在这篇文章里，也有一个很有意思的例子：
我要抛一次骰子，在观测到结果之前，骰子六个面向上都有可能，而且概率完全一样（都是1/6).这时，这一事件的信息熵为 。这个结果用之前的信息熵公式也很好计算，相当于累加6次 -1/6*log(1/6) ，即 -log(1/6)=-(log1-log6)=log6 ，注意这个算法在之后算猪喝毒水时也会用到。
现在万能的女神给了我一个提示，这次骰子的结果一定是偶数，于是可能的结果由6种降低为3种，事件的熵也就变成了 。也就是说，当我得到提示后，对于事件结果的不确定性降低了。我们把信息熵降低的量规定为信息量I。上面那条提示对我的信息量是 ，正好是1比特，相当于对一个完全未知的命题做一次是非判断需要的信息量。而如果我要得到唯一确定的结果，P(x)就必须等于1，此时的信息熵为零。我们需要得到的信息量就是原本的熵 。
看到这里，聪明的你一定已经可以自己总结出另一个金光闪闪的结论：信息就是负熵。需要特别注意的是，这句话里的“熵”指而且仅指信息熵，试图将这个结论扩大到热力学熵的解释往往都缺乏足够的事实基础，并且含义也经常是含混的。
是时候回到知乎3万赞的回答了： 1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？ - 苗华栋的回答 - 知乎
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用15分钟内找到这桶毒水，至少需要几头猪？
首先，”1000桶水其中有一桶有毒“这个随机变量X的信息熵为： -(1/1000)*log(1/1000) 累加1千次。这个很容易理解吧，毒水出现在任意一桶之中是个等概率事件，累加起来的结果就是：
-log(1/1000) = log 1000 约等于9.966
1只猪喝水以后的要么活着，要么死去，一共有两种状态，所以”1只猪喝完水以后的状态“这个随机变量Y的信息熵为
n只猪喝完水会有2的n次方种状态，即"n只猪喝完水以后的状态"这个随机变量Y的信息熵为
所以，按照题目要求，如果至少需要n头猪能够找到这桶毒水，那么随机变量Y的信息熵必须要大于随机变量X的信息熵，也就是H(Y) >= H(X) ，也就是 n >= 9.966，即 n = 10
当我们用信息熵算出来了n的最小值以后，我们就可以坚信，理论上n=10一定是最优解，任何想方设法想找到小于10的值都是徒劳的。
其实，上面的信息熵计算的简化版本可以写成如下更好理解的形式 ，同样可以解得 n = 10 ，虽然形式简单，但我们一定要记住它背后的原理是信息熵。
至于到底采用什么方案，这涉及到术的层面，即使我们暂时想不到，我们也会有努力的方向，并且知道努力的边界在哪里，不会做类似寻找永动机的事情。
1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？
1000桶水其中有一桶有毒，和第一个问题相同，仍然是9.966。但是，猪的信息熵不同了。我们可以想象一下，一只猪在一个小时内会有几种状态？
可见，1只猪1个小时以后会有5种状态，所以”1只猪1个小时后的状态“这个随机变量Z的信息熵为
n只猪1个小时后会有 5的n次方 种状态，即"n只猪1个小时以后的状态"这个随机变量Y的信息熵为
所以，按照题目要求，如果至少需要n头猪能够找到这桶毒水，那么随机变量Y的信息熵必须要大于随机变
量X的信息熵，也就是H(Y) >= H(X) ，也就是 n >= 9.966 / 2.3219 = 4.292，即 n = 5
事实上，对于 n = 5来说，不仅可以检测1000桶水，甚至检测3000桶水都是没有问题的。有兴趣的童鞋
可以试着计算一下。
到此，香农给了我们一个理论极限，但是具体的方案还是需要我们自己进行构造。得出n=5是依靠我们的
理论功底，而得出具体的方案就是我们的工程水平了。
还是知乎3万赞的作者，参考 香农的信息论究竟牛在哪里？ - 苗华栋的回答 - 知乎 ，老习惯，这里只介绍思路，具体方案看作者原文。
12个外表相同的球中有1个坏球，它的重量比其它11个好球要轻，现在有一台没有砝码的天平，问至少称几次能确保找出这个坏球？
我们可以思考一下，一个天平称量1次后会有3种结果：
所以“天平称量1次后的结果”这个随机变量Z的信息熵是
如果将上述式子简化，即
12个外表相同的球中有1个坏球，它的重量和其它11个球不同，现在有一台没有砝码的天平，问至少称几次能确保找出这个坏球？
这个问题和前面那个问题的不同之处在于不知道这个坏球的轻重。这对信息熵来说跟前面的已知坏球是轻的相比有什么影响呢？
如果有2个球放在天平两侧。如果已知坏球比较轻，当天平不平衡时，我就可以立刻知道坏球是轻的那一侧。而当不知道坏球是轻还是重时，如果天平不平衡，我无法判断坏球是重的那一侧还是轻的那一侧，我只能够知道坏球要么是轻的那一个，要么是重的那一个。所以，在不知道坏球是轻还是重时，每次测量多了一个坏球是轻还是重的不确定性。在上题的基础上，在最高位增加一位表示球的轻重。其中0表示轻，1表示重，如下表所示。于是虽然12个球，但是因为多了一个轻重的不确定性，所以变成24种状态。
于是“12个外表相同的球中确定1个不知轻重的球”这个随机变量X的信息熵为
而“天平称量n次后的结果”这个随机变量Y的信息熵没有变，因为天平每次还是只能确定三种状态，所以
同样，H(Y) >= H(X) ，即 n >= 2.893，即 n = 3可见，前面那道题并没有充分发挥天平的信息优势，3次还能测出不知轻重的坏球。这就是理论武装头脑的好处，先找到答案，再去想方案。这种自顶向下的思考方式的好处就是我们在思考方案之前有了目标，也有了努力的方向，而不是无头苍蝇一样。
如果看了文章开头1000桶水找毒药那道题的童鞋可能会发现，这道题的解题思路几乎是照搬那道题的解题思路，虽然表面上是不同类型的题目，但我们要像香农祖师爷学习，透过题目的表象直穿本质。
这两道题目的底层逻辑都是信息熵，当我们掌握了理论工具以后，人之间的差距就在于是否有足够的能力将现实问题抽象成数学或者其他问题，然后用我们熟知的理论工具去解决它。在这一点上，就和解方程式是一样的。解方程本身非常简单，难点是如何将现实的问题抽象成表达式，定义变量，列出方程式。关于这一点详细的陈述在我的另一篇文章 《数学思维在生活中有多大用处？》 中有更详细的描述。
参考 1000桶水，其中一桶有毒，猪喝毒水后会在15分钟内死去，想用一个小时找到这桶毒水，至少需要几头猪？ - PlanarG的回答 - 知乎
考虑这样一个过程：假设现在给你两个数a,b，只允许你进行一次比较，将这两个数从小到大排序。你心想这个问题不是非常简单吗，直接拿这两个数比较一次，哪个数小哪个就排在前面。
我们来分析一下这个看似简单的问题的本质是什么。
如果我们只能进行一次比较，那么根据这一次比较，我们能够得到的信息实际上只有两种：要么第一个数较小，要么第二个数较小。而两个数最终从小到大的关系也只有两种情况：要么是 a,b ，要么是b,a 。也就是说，我们能够根据这一次比较的结果建立一个结果-最终排列的双射关系，每一种比较的结果都唯一地对应最终的一种大小关系。
现在考虑上面那个问题的升级版：如果现在给你四个数a,b,c,d 能否通过 4 次比较给它们从小到大排序？答案是否定的。因为通过四次比较我们能得到的信息最多只有2的4次方，即16种。而这4个数的排列一共有4！=24种。因此不可能将询问的结果与最终排列一一对应，我们就证明了 4 不可能是答案的下界。
我们再升级一次，考虑给n个数排序的情况。如果我们在最终的方案中使用了k次比较，那么可能得到的信息有2的k次方种，而n个数的排列有n!种。要建立结果-最终排列的双射关系，必须满足 即：
现在让我们用信息论的角度思考一下原问题。 1000桶水，只有一桶有毒，换言之，可能的答案只有 1000种。
每头猪在中毒之后 15分钟内死去，那么我们可以从每头猪获得的信息一共有5种：在[0,15) [15,30) [30,45) [45,60)中的哪一个时间段死去，或者最终存活下来。如果最终有k只猪，我们能获得的信息就有 种，换言之，k需要满足 ，即 ，因此 k的下界为 5。
⑷ 【leetcode C语言实现】面试题 02.05-链表求和
给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。
示例：
输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：假设这些数位是正向存放的，请再做一遍。
示例：
输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912
当两个整数相加时，从个位开始，依次将两个数的对应位置进行相加，将所得结果的个位数作为相加后对应位置的结果，若有进位将进位的值在更高一位进行相加。此处两个数是以链表存储，同样的思路，依次将两个数的对应位置进行相加，并将所得结果保存到一个链表中。
运行结果：
⑸ C C++ leetcode 总是说编译错误，关键我连第77行都没有，只有那么几行……
leetcode都不能自己定义主函数的
需要你构造一个Solution的类
77行redefine的main恰好就是leetcode用来测试你写的Solution的main函数
⑹ LeetCode 力扣官方题解 - 1020. 飞地的数量
题目描述
给你一个大小为 m x n 的二进制矩阵 grid，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。
一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。
返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。
示例 1：
示例 2：
提示：
根据飞地的定义，如果从一个陆地单元格出发无法移动到网格边界，则这个陆地单元格是飞地。因此可以将所有陆地单元格分成两类：第一类陆地单元格和网格边界相连，这些陆地单元格不是飞地；第二类陆地单元格不和网格边界相连，这些陆地单元格是飞地。
我们可以从网格边界上的每个陆地单元格开始深度优先搜索，遍历完边界之后，所有和网格边界相连的陆地单元格就都被访问过了。然后遍历整个网格，如果网格中的一个陆地单元格没有被访问过，则该陆地单元格不和网格的边界相连，是飞地。
代码实现时，由于网格边界上的单元格一定不是飞地，因此遍历网格统计飞地的数量时只需要遍历不在网格边界上的单元格。
代码
Java
C#
C++
C
Python3
Golang
JavaScript
复杂度分析
也可以通过广度优先搜索判断每个陆地单元格是否和网格边界相连。
首先从网格边界上的每个陆地单元格开始广度优先搜索，访问所有和网格边界相连的陆地单元格，然后遍历整个网格，统计飞地的数量。
代码
Java
C#
C++
C
Python3
Golang
JavaScript
复杂度分析
除了深度优先搜索和广度优先搜索的方法以外，也可以使用并查集判断每个陆地单元格是否和网格边界相连。
并查集的核心思想是计算网格中的每个陆地单元格所在的连通分量。对于网格边界上的每个陆地单元格，其所在的连通分量中的所有陆地单元格都不是飞地。如果一个陆地单元格所在的连通分量不同于任何一个网格边界上的陆地单元格所在的连通分量，则该陆地单元格是飞地。
并查集的做法是，遍历整个网格，对于网格中的每个陆地单元格，将其与所有相邻的陆地单元格做合并操作。由于需要判断每个陆地单元格所在的连通分量是否和网格边界相连，因此并查集还需要记录每个单元格是否和网格边界相连的信息，在合并操作时更新该信息。
在遍历网格完成并查集的合并操作之后，再次遍历整个网格，通过并查集中的信息判断每个陆地单元格是否和网格边界相连，统计飞地的数量。
代码
Java
C#
C++
C
Python3
Golang
JavaScript
复杂度分析
BY /
本文作者：力扣
⑺ 为什么LeetCode上C的解法很少
leetcode不支持C语言原因如下：
1、在ViewController.h添加事件代理和数据源代理<UICollectionViewDataSource,UICollectionViewDelegate>。
2、在ViewController.m创建UICollectionView。需要使用UICollectionViewFlowLayout来创建，使用方法- (instancetype)initWithFrame:(CGRect)frame collectionViewLayout:(UICollectionViewLayout *)layout;如果只用普通的init方法，是实现不了的。
4、代理授权并添加至视图。
self.collectionView.delegate = self;
self.collectionView.dataSource = self;
[self.view addSubview:self.collectionView];
把UICollectionViewCell添加到UICollectionView内
1、注册CollectionViewCell，添加cell需要在这里实现。方法：- (void)registerClass:(Class)cellClass forCellWithReuseIdentifier:(NSString *)identifier;
2、添加代理方法
//定义展示的UICollectionViewCell的个数
-(NSInteger)collectionView:(UICollectionView *)collectionView numberOfItemsInSection:(NSInteger)section;