Leetcode

题目：判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。 示例 1: 输入: 121输出: true示例 2: 输入: -121输出: false解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。 示例 3: 输入: 10输出: false解释: 从右向左读, 为 01 。因此它不是一个回文数。进阶: 你能不将整数转为字符串来解决这个问题吗？ 来源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 解答一般方法：可以通过一个字符串简单的切片的使用来实现 class Solution(object): def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x<0: return False b = int(str(x)[::-1]) if b == x: return True return False 进阶方法：不转换为字符串 我们可以将数倒过来，然后将其判断相等 def isPalindrome(self, x): """ :type x: int :rtype: bool """ if x<0: return False b = x a = 0 while(x>=10): a = a*10 +x %10 #最后一位 x = x // 10 a = a*10 +x %10 if a == b: return True

题目：给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。 示例 1:输入: 123输出: 321 示例 2:输入: -123输出: -321 示例 3:输入: 120输出: 21 注意: 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−231, 231 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。 来源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 解答：class Solution(object): def reverse(self, x): """ :type x: int :rtype: int """ max0 = 2**31-1 min0 = -(2**31) symbol = True if x > max0 or x < min0: return 0 if x < 0: symbol = False x = -x int_x = str(x) raw = int_x[::-1] raw = int(raw) if raw > max0: return 0 if not symbol: return -raw return raw关键： ...

前言Weekly Contest 142的 拼车： 假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。 这儿有一份行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了你的第 i 次行程信息： 必须接送的乘客数量；乘客的上车地点；以及乘客的下车地点。这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。 请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所用乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。 示例1： 输入：trips = [[2,1,5],[3,3,7]], capacity = 4输出：false示例2： 输入：trips = [[2,1,5],[3,3,7]], capacity = 5输出：true示例3： 输入：trips = [[2,1,5],[3,5,7]], capacity = 3输出：true示例4： 输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11输出：true提示： 你可以假设乘客会自觉遵守 “先下后上” 的良好素质trips.length <= 1000trips[i].length == 31 <= trips[i][0] <= 1000 <= trips[i][1] < trips[i][2] <= 10001 <= capacity <= 100000解题思路本题难度为中等，主要是需要注意以下几点： ...

前言Weekly Contest 142的 大样本统计： 我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 的采样个数。 我们以 浮点数 数组的形式，分别返回样本的最小值、最大值、平均值、中位数和众数。其中，众数是保证唯一的。 我们先来回顾一下中位数的知识： 如果样本中的元素有序，并且元素数量为奇数时，中位数为最中间的那个元素；如果样本中的元素有序，并且元素数量为偶数时，中位数为中间的两个元素的平均值。示例1： 输入：count = [0,1,3,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]输出：[1.00000,3.00000,2.37500,2.50000,3.00000]示例2： 输入：count = [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]输出：[1.00000,4.00000,2.18182,2.00000,1.00000]提示： count.length == 2561 <= sum(count) <= 10^9计数表示的众数是唯一的答案与真实值误差在 10^-5 以内就会被视为正确答案解题思路本地难度为中等，首先需要读懂题目意思，本题的入参数组count其实算是一个压缩数据后的数组。 我们对 0 到 255 之间的整数进行采样，并将结果存储在数组 count 中：count[k] 就是整数 k 的采样个数。简单来说就是，数组count的第k个元素就是k在压缩前的数组中出现count[k]个。以示例1的count为例 [0,4,3,2,2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]解压的过程如下： 第0个元素为0，则解压后的数组为[]第1个元素为4，则解压后的数组为[1,1,1,1]第2个元素为3，则解压后的数组为[1,1,1,1,2,2,2]第3个元素为2，则解压后的数组为[1,1,1,1,2,2,2,3,3]第4个元素为2，则解压后的数组为[1,1,1,1,2,2,2,3,3,4,4]......省略后续步骤搞清楚count的数据特征后，选择使用TreeMap对count进行处理，将有效数字及其出现个数存储起来（有效数字指的是count[k]不为0的元素）。根据就是根据题目要求分别处理以下指标： 最小值：TreeMap中第一个key最大值：TreeMap中最后一个key平均值：TreeMap的key之和除以value之和中位数： 计算出数组实际的元素个数（即value之和）根据元素个数的奇偶性，获取对应的值众数：出现次数最多的数字，即TreeMap中value最大的键值对的key实现代码 /** * 1093. 大样本统计 * * @param count * @return */ public double[] sampleStats(int[] count) { // 使用TreeMap有序存储数字及其出现次数 TreeMap<Integer, Integer> countMap = new TreeMap<>(); double[] result = new double[5]; // 总和 double sum = 0L; // 数字出现总次数 double total = 0L; // 最大出现次数 long maxTimes = 0; // 最小值 double min; // 最大值 double max; // 平均值 double average; // 中位数 double middle = 0; // 众数，出现次数最多的数字 double mode = 0; for (int i = 0; i < count.length; i++) { if (count[i] != 0) { countMap.put(i, count[i]); sum = sum + i * count[i]; total += count[i]; if (count[i] > maxTimes) { maxTimes = count[i]; mode = i; } } } min = countMap.firstKey().doubleValue(); max = countMap.lastKey().doubleValue(); average = sum / total; // 是否为奇数 boolean odd = total % 2 != 0; // 中位数索引 int middleIndex = (int) ((total - 1) / 2); int index = -1; Iterator<Map.Entry<Integer, Integer>> it = countMap.entrySet().iterator(); while (it.hasNext()) { Map.Entry<Integer, Integer> entry = it.next(); int num = entry.getKey(); int times = entry.getValue(); index += times; if (index > middleIndex) { middle = num; break; } else if (index == middleIndex) { if (odd) { middle = num; break; } else { middle = (num + it.next().getKey()) / 2.0; break; } } } result[0] = min; result[1] = max; result[2] = average; result[3] = middle; result[4] = mode; return result; }

D91 175. Combine Two Tables题目链接175. Combine Two Tables 题目分析这个题目比较简单，就是简单的连表查询。 思路以person表为出发点，于address表join。join依据是personId。 最终代码# Write your MySQL query statement belowSELECT person.FirstName, person.LastName, address.City, address.State FROM person LEFT JOIN address ON address.personId = person.personId若觉得本文章对你有用，欢迎用爱发电资助。

D89 653. Two Sum IV - Input is a BST题目链接653. Two Sum IV - Input is a BST 题目分析给定一个二叉树以及一个目标数字，判断能不能通过二叉树中任意两个节点的值相加得到。 思路思路1遍历的时候，先把节点存起来，并且与每一个值相加，判断是否等于所需值。 这个算法很明显效率比较低。 思路2遍历的时候，把自身作为键存进数组内。用isset函数判断与所求数字之差是否在数组内。存在既返回。否则，遍历子节点。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { protected $has = []; protected $hasResult = false; /** * @param TreeNode $root * @param Integer $k * @return Boolean */ function findTarget($root, $k) { if(is_null($root)){ return; } if(isset($this->has[$k-($root->val)])){ $this->hasResult = true; return $this->hasResult; } else{ $this->has[$root->val] = true; if(!$this->findTarget($root->left, $k)){ $this->findTarget($root->right, $k); } } return $this->hasResult; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

Implement next permutation, which rearranges numbers into thelexicographically next greater permutation of numbers.If such arrangement is not possible, it must rearrange it as thelowest possible order (ie, sorted in ascending order). The replacement must be in-place and use only constant extra memory. Here are some examples. Inputs are in the left-hand column and itscorresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1感觉属于那种数学找规律，然后把这个规律用程序表达，写的程序比较简单找到i满足nums[i]<nums[i+1];从{i-nums.length-1}中找到比nums[i]大且最小的，其余的按顺序排列 ...

前言Weekly Contest 141的 受标签影响的最大值： 我们有一个项的集合，其中第 i 项的值为 values[i]，标签为 labels[i]。 我们从这些项中选出一个子集 S，这样一来： |S| <= num_wanted对于任意的标签 L，子集 S 中标签为 L 的项的数目总满足 <= use_limit。返回子集 S 的最大可能的 和。 示例1： 输入：values = [5,4,3,2,1], labels = [1,1,2,2,3], num_wanted = 3, use_limit = 1输出：9解释：选出的子集是第一项，第三项和第五项。示例2： 输入：values = [5,4,3,2,1], labels = [1,3,3,3,2], num_wanted = 3, use_limit = 2输出：12解释：选出的子集是第一项，第二项和第三项。示例3： 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 1输出：16解释：选出的子集是第一项和第四项。示例4： 输入：values = [9,8,8,7,6], labels = [0,0,0,1,1], num_wanted = 3, use_limit = 2输出：24解释：选出的子集是第一项，第二项和第四项。提示： ...

前言Weekly Contest 141的 复写零： 给你一个长度固定的整数数组 arr，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。 注意：请不要在超过该数组长度的位置写入元素。 要求：请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。 示例1： 输入：[1,0,2,3,0,4,5,0]输出：null解释：调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]示例2： 输入：[1,2,3]输出：null解释：调用函数后，输入的数组将被修改为：[1,2,3]提示： 1 <= arr.length <= 100000 <= arr[i] <= 9解题思路本题十分简单，需要注意本题是一个原地算法，所以使用双指针法进行变量交换即可。大致逻辑如下： 遍历数组元素当前元素为0时，下一个元素赋值为0，并对数组进行左移，下一次遍历当前元素后2位的元素。否则正常遍历数组。实现代码 /** * 1089. 复写零 * @param arr */ public void duplicateZeros(int[] arr) { for (int i = 0; i < arr.length - 1;) { if (arr[i] == 0) {// 当前元素为0 // 记录下一个元素的值 int next = arr[i + 1]; // 将下一个元素设为0 arr[i + 1] = 0; for (int j = i + 2; j < arr.length; j++) { // 从当前索引后的第二个元素开始交换 int tmp = arr[j]; // 记录当前变量 arr[j] = next; // 将前一个位置的元素值赋给当前元素 next = tmp; // next指针记录当前元素 } i+=2; // 下一次遍历的是当前元素后2位的元素 }else{ ++i; // 正常遍历 } } }

LeetCode Notes - 1OverviewLeetCode - 141. Linked List Cycle - 环形链表LeetCode - 142. Linked List Cycle II - 环形链表LeetCode - 258. Add Digits - 数字推导（数字根）LeetCode - 461. Hamming Distance - 位运算LeetCode - 463. Island Perimeter - 常规计算141 - Linked List CycleDescriptionLeetCode - 141. Linked List CycleApproach 1 - Hash TableAnalysis使用哈希表解决，时间复杂度为 O(n)，空间复杂度为 O(n)。遍历链表，若遇到 Null，则 表明链表无环。若遍历的节点在哈希表中已存在，则表明链表有环。SolutionJavaScript/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } *//** * @param {ListNode} head * @return {boolean} */var hasCycle = function(head) { let nodesSeen = new Set(); if(head === null || head.next === null){ return false; } while(head !== null){ if(nodesSeen.has(head)){ return true; } else{ nodesSeen.add(head); } head = head.next; } return false;}; Java/** * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } */public boolean hasCycle(ListNode head) { Set<ListNode> nodesSeen = new HashSet<>(); while (head != null) { if (nodesSeen.contains(head)) { return true; } else { nodesSeen.add(head); } head = head.next; } return false;}Approach 2 - Two PointersAnalysis使用快慢指针解决，时间复杂度为 O(n)，空间复杂度为 O(1)。Use two pointers, walker and runner.Walker moves step by step.Runner moves two steps at time.If the Linked List has a cycle walker and runner will meet at some point.Ref ...

给定一个没有重复数字的序列，返回其所有可能的全排列。 示例: 输入: [1,2,3]输出:[ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]参考： /** * @param {number[]} nums * @return {number[][]} */var permute = function (nums) { result = [] nums.sort(function (a, b) { return a - b }) find(nums, []) return result};let result = []function find(nums, templateList) { if (nums.length == 0) { result.push(templateList.slice()) } for (let i = 0; i < nums.length; i++) { templateList.push(nums[i]) let copy = nums.slice() copy.splice(i, 1) find(copy, templateList) templateList.pop() }} ...

D87 705. Design HashSet题目链接705. Design HashSet 题目分析设计一个哈希类。 需要有add添加元素函数，contains判断元素存在的函数，remove移除元素函数。 思路这真的没什么好说的了…我把要存的值作为数组的键存储。 最终代码class MyHashSet { protected $values = []; /** * Initialize your data structure here. */ function __construct() { } /** * @param Integer $key * @return NULL */ function add($key) { $this->values[$key] = true; } /** * @param Integer $key * @return NULL */ function remove($key) { if(isset($this->values[$key])){ unset($this->values[$key]); } } /** * Returns true if this set contains the specified element * @param Integer $key * @return Boolean */ function contains($key) { return isset($this->values[$key]); }}/** * Your MyHashSet object will be instantiated and called as such: * $obj = MyHashSet(); * $obj->add($key); * $obj->remove($key); * $ret_3 = $obj->contains($key); */若觉得本文章对你有用，欢迎用爱发电资助。 ...

给定一个字符串 (s) 和一个字符模式 (p) ，实现一个支持 '?' 和 '*' 的通配符匹配。 '?' 可以匹配任何单个字符。 '*' 可以匹配任意字符串（包括空字符串）。 两个字符串完全匹配才算匹配成功。 说明: s 可能为空，且只包含从 a-z 的小写字母。 p 可能为空，且只包含从 a-z 的小写字母，以及字符 ? 和 *。示例 1: 输入:s = "aa" p = "a" 输出: false 解释: "a" 无法匹配 "aa" 整个字符串。示例 2: 输入: s = "aa"p = "*" 输出: true 解释: '*' 可以匹配任意字符串。示例 3: 输入: s = "cb" p = "?a" 输出: false 解释: '?' 可以匹配 'c', 但第二个 'a' 无法匹配 'b'。示例 4: ...

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。示例 1: 输入: num1 = "2", num2 = "3"输出: "6"示例 2: 输入: num1 = "123", num2 = "456"输出: "56088"说明： num1 和 num2 的长度小于110。num1 和 num2 只包含数字 0-9。num1 和 num2 均不以零开头，除非是数字 0 本身。不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。参考 /** * @param {string} num1 * @param {string} num2 * @return {string} */var multiply = function(num1, num2) { if(num1.charAt(0)==0||num2.charAt(0)==0){ return "0"; }var a,b,c,l=0 if(num1.length>=num2.length){ a=num1.split(""); b=num2.split("") }else{ b=num1.split(""); a=num2.split("") } c=[]; for(k=0;k<a.length+b.length;k++){ c[k]=0; } a=a.reverse(); b=b.reverse(); for(i=0;i<a.length;i++){ for(j=0;j<b.length;j++){ c[j+i]+=a[i]*b[j]; } } for(m=0;m<c.length;m++){ if(c[m]>9){ c[m+1]+=Math.floor(c[m]/10); c[m]%=10; } } c=c.reverse(); for(n=0;n<1;n++){ if(c[0]==0){c.splice(0,1);n--} return c.join("") }} ...

D86 748. Shortest Completing Word题目链接748. Shortest Completing Word 题目分析从给定的一个字符串中提取字符。从另一个给定的单词数组中，选择出所提取的字符在单词中出现次数相等或大于的单词。若出现次数相同，则返回第一个符合条件的单词。 假定结果必定存在。 思路先提取字符，转换成小写，并计算字符出现的次数。 遍历数组中的每一个单词，先计算单词中每个字符出现的次数。 同时，遍历前面计算的字符出现次数，若有任何一个字符没有在当前单词中没出现，那么可以抛弃当前单词。 若出现次数小于前面计算的出现次数，也可以排除。 若出现了符合的单词，先判断和原先保存的单词长度是否短。 短则覆盖，长则抛弃。 最终代码<?phpclass Solution { /** * @param String $licensePlate * @param String[] $words * @return String */ function shortestCompletingWord($licensePlate, $words) { $plateCounts = []; $licenseArray = str_split(strtolower($licensePlate)); foreach($licenseArray as $val){ if(($val>='a' && $val<='z')||($val>='A' && $val<='Z')){ if(!isset($plateCounts[$val])){ $plateCounts[$val] = 0; } $plateCounts[$val] += 1; } }; $match = null; foreach($words as $word){ $wordCounts = array_count_values(str_split($word)); $failed = false; foreach($plateCounts as $char => $amount){ if(!isset($wordCounts[$char])){ $failed = true; break; } if($amount > $wordCounts[$char]){ $failed = true; break; } } if(!$failed){ if(is_null($match)){ $match = $word; } else{ if(strlen($match)>strlen($word)){ $match = $word; } } } } return $match; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

You are given a string, s, and a list of words, words, that are all ofthe same length. Find all starting indices of substring(s) in s thatis a concatenation of each word in words exactly once and without anyintervening characters.Example 1: Input: s = "barfoothefoobarman", words = ["foo","bar"] Output:[0,9] Explanation: Substrings starting at index 0 and 9 are "barfoor"and "foobar" respectively. The output order does not matter, returning[9,0] is fine too. Example 2: ...

D85 242. Valid Anagram题目链接242. Valid Anagram 题目分析判断给定的两个单词是否同构。即，重新排列组合所出现的字母后得到另一个单词。 思路拆分成数组后，排序，再拼起来。判断是否相同。 最终代码<?phpclass Solution { /** * @param String $s * @param String $t * @return Boolean */ function isAnagram($s, $t) { $arrs = str_split($s); $arrt = str_split($t); sort($arrs); sort($arrt); return implode($arrs) === implode($arrt); } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

做有意思的题是要付出代价的，代价就是死活做不出来。一、题目接雨水： 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 1:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6二、我的答案思路1       前段时间有在看一个俄罗斯方块的代码，所以第一个思路是从下到上一层一层计算，先把数组中所有的数-1，然后去掉数组两端的-1，再统计数组中-1的个数，即为本层接的雨水。这种暴力解法应该是可行的，我并没有把思路落到纸上，各位感兴趣可以试一下。 思路2       接雨水嘛，两边比中间高就能接到，那么我只需要求出所有比左右两边高的点，他们两两组合就成一个可以接到水的坑，以原题中的示例1为例，下标为1，3，7，10的点就是我们所求。代码如下 /** * @param {number[]} height * @return {number} */var trap = function(height) { function fillister (arr) { let result = 0 let baseLine = arr[0] <= arr[arr.length - 1] ? arr[0] : arr[arr.length - 1] let difference for(let i = 0; i < arr.length; i++) { difference = baseLine - arr[i] difference > 0 ? result += difference : null } return result } let result = 0 let bigger, smaller, the_dot for(let begin = 0; begin < height.length; begin++) { bigger = (height[begin - 1] || 0) < height[begin] smaller = (height[begin + 1] || 0) < height[begin] if (smaller && bigger) { if (the_dot !== undefined) { result += fillister(height.slice(the_dot, begin + 1)) } the_dot = begin } } return result};       遍历参数数组height，只要符合条件，且不是第一个符合条件的点，就计算该点与之前点之间的积水。提交，答案错误。出错的测试用例为[5,1,2,1,5]。       原来按照上述思路，只计算了[5,1,2]和[2,1,5]两个小水洼，但是[5,1,2,1,5]本身就是个大水洼。意识到计算目标点的函数需要递归。       根据这个想法，我进行了大量的编码，因为这个递归调用的边界情况比较麻烦，而且越写越怀疑自己的思路，我始终觉得优秀的题解应该是简单的。这里只放出其中对我产生启发的一个片段。 ...

Given two integers dividend and divisor, divide two integers withoutusing multiplication, division and mod operator.Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero. Example 1: Input: dividend = 10, divisor = 3 Output: 3 Example 2: Input: dividend = 7, divisor = -3 Output: -2 Note: Both dividend and divisor will be 32-bit signed integers. The divisorwill never be 0. Assume we are dealing with an environment which couldonly store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your functionreturns 231 − 1 when the division result overflows.两个点需要注意1.这样设计到大数运算的又不能使用乘除法的肯定要使用移位符2.注意溢出的判断，这道题就适合更改输入条件，但要注意修改了原始输入值，是否影响后面的判断 ...

Implement strStr().Return the index of the first occurrence of needle in haystack, or -1if needle is not part of haystack. Example 1: Input: haystack = "hello", needle = "ll" Output: 2 Example 2: Input: haystack = "aaaaa", needle = "bba" Output: -1 Clarification: What should we return when needle is an empty string? This is a greatquestion to ask during an interview. For the purpose of this problem, we will return 0 when needle is anempty string. This is consistent to C's strstr() and Java's indexOf().需要注意边界条件，例如把正常逻辑全放到对haystack的循环体中，但haystack可能为空，逻辑将会走不到 ...

D84 371. Sum of Two Integers题目链接371. Sum of Two Integers 题目分析相加给定的两个数，但不能使用+或-运算符。 思路可以用二进制的与运算完成。此处用array_sum完成。 最终代码<?phpclass Solution { /** * @param Integer $a * @param Integer $b * @return Integer */ function getSum($a, $b) { return array_sum([$a,$b]); } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

设计你的循环队列实现。 循环队列是一种线性数据结构，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里，一旦一个队列满了，我们就不能插入下一个元素，即使在队列前面仍有空间。但是使用循环队列，我们能使用这些空间去存储新的值。你的实现应该支持如下操作：MyCircularQueue(k): 构造器，设置队列长度为 k 。Front: 从队首获取元素。如果队列为空，返回 -1 。Rear: 获取队尾元素。如果队列为空，返回 -1 。enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。isEmpty(): 检查循环队列是否为空。isFull(): 检查循环队列是否已满。 示例： MyCircularQueue circularQueue = new MycircularQueue(3); // 设置长度为 3circularQueue.enQueue(1);  // 返回 truecircularQueue.enQueue(2);  // 返回 truecircularQueue.enQueue(3);  // 返回 truecircularQueue.enQueue(4);  // 返回 false，队列已满circularQueue.Rear();  // 返回 3circularQueue.isFull();  // 返回 truecircularQueue.deQueue();  // 返回 truecircularQueue.enQueue(4);  // 返回 truecircularQueue.Rear();  // 返回 4来源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 /** * Initialize your data structure here. Set the size of the queue to be k. * @param {number} k */var MyCircularQueue = function(k) { // 存储数据 this.data = Array(k).fill(null); // 设置队列长度 this.maxSize = k; // 队列头尾指针 this.headPointer = 0; this.tailPointer = 0; // 当前使用空间 this.currentSize = 0;};/** * Insert an element into the circular queue. Return true if the operation is successful. * @param {number} value * @return {boolean} */MyCircularQueue.prototype.enQueue = function(value) { if(!this.isFull()){ this.data[this.tailPointer] = value; this.currentSize++; if(!this.isEmpty()){ this.tailPointer++; } return true; } return false;};/** * Delete an element from the circular queue. Return true if the operation is successful. * @return {boolean} */MyCircularQueue.prototype.deQueue = function() { if(this.currentSize!==0){ this.currentSize--; this.data[this.headPointer] = null; this.headPointer++; return true; } return false;};/** * Get the front item from the queue. * @return {number} */MyCircularQueue.prototype.Front = function() { console.log(this.isEmpty());; if(!this.isEmpty()){ return this.data[this.headPointer]; }else{ return -1; }};/** * Get the last item from the queue. * @return {number} */MyCircularQueue.prototype.Rear = function() { if(!this.isEmpty()){ return this.data[this.tailPointer-1]; }else{ return -1; }};/** * Checks whether the circular queue is empty or not. * @return {boolean} */MyCircularQueue.prototype.isEmpty = function() { return this.data.every(function(e){ return Object.prototype.toString.call(e)==="[object Null]"; })};/** * Checks whether the circular queue is full or not. * @return {boolean} */MyCircularQueue.prototype.isFull = function() { if(this.currentSize==this.maxSize){ return true; } return false;};/** * Your MyCircularQueue object will be instantiated and called as such: * var obj = new MyCircularQueue(k) * var param_1 = obj.enQueue(value) * var param_2 = obj.deQueue() * var param_3 = obj.Front() * var param_4 = obj.Rear() * var param_5 = obj.isEmpty() * var param_6 = obj.isFull() */多刷Leetcode，必成好青年！ ...

前言Weekly Contest 140的 Bigram 分词： 给出第一个词 first 和第二个词 second，考虑在某些文本 text 中可能以 "first second third" 形式出现的情况，其中 second 紧随 first 出现，third 紧随 second 出现。 对于每种这样的情况，将第三个词 "third" 添加到答案中，并返回答案。 示例1： 输入：text = "alice is a good girl she is a good student", first = "a", second = "good"输出：["girl","student"]示例2： 输入：text = "we will we will rock you", first = "we", second = "will"输出：["we","rock"]提示： 1 <= text.length <= 1000text 由一些用空格分隔的单词组成，每个单词都由小写英文字母组成1 <= first.length, second.length <= 10first 和 second 由小写英文字母组成解题思路本题需要注意以下两点： ...

D78 206. Reverse Linked List题目链接206. Reverse Linked List 题目分析给定一个链表，将其倒转过来。 思路我的思路是，把每一项存进数组作为栈。 遍历完成后，再逐个弹出即可。 最终代码<?php/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */class Solution { /** * @param ListNode $head * @return ListNode */ function reverseList($head) { $stack = []; while(true){ $stack[] = $head; $head = $head->next; if(is_null($head)){ break; } } $root = $head = array_pop($stack); while($stack){ $head->next = array_pop($stack); $head = $head->next; } $head->next = null; return $root; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D79 448. Find All Numbers Disappeared in an Array题目链接448. Find All Numbers Disappeared in an Array 题目分析给定一个1到n的数组，返回其中缺失的数字。 思路用range得出1到n的数字，再用array_diff和给定的数组计算差集。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @return Integer[] */ function findDisappearedNumbers($nums) { if(!$nums){ return []; } return array_diff(range(1,count($nums)),$nums); }}若觉得本文章对你有用，欢迎用爱发电资助。

D77 812. Largest Triangle Area题目链接812. Largest Triangle Area 题目分析给定一组坐标，返回能组成面积最大的三角形面积。 思路只能套for循环了。利用三边求面积公式得面积。 最终代码<?phpclass Solution { /** * @param Integer[][] $points * @return Float */ function largestTriangleArea($points) { $pointAmount = count($points); $max = -1; for($i=0;$i<=$pointAmount;$i++){ for($j=$i+1;$j<$pointAmount;$j++){ for($k=$j+1;$k<$pointAmount;$k++){ $p1 = $points[$i]; $p2 = $points[$j]; $p3 = $points[$k]; $area = abs($p1[0]*$p2[1]+$p2[0]*$p3[1]+$p3[0]*$p1[1]-$p1[0]*$p3[1]-$p2[0]*$p1[1]-$p3[0]*$p2[1])/2; if($area>$max){ $max = $area; } } } } return $max; }}若觉得本文章对你有用，欢迎用爱发电资助。

D83 169. Majority Element题目链接169. Majority Element 题目分析给定一个数组，返回其中出现次数超过一半的元素。 思路用array_count_values函数计算元素出现次数，用arsort逆序排序结果，输出第一个即可。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @return Integer */ function majorityElement($nums) { $values = array_count_values($nums); arsort($values); return key($values); } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

Given a sorted array nums, remove the duplicates in-place such thateach element appear only once and return the new length. Do not allocate extra space for another array, you must do this bymodifying the input array in-place with O(1) extra memory. Example 1: Given nums = [1,1,2], Your function should return length = 2, with the first two elements ofnums being 1 and 2 respectively. It doesn't matter what you leave beyond the returned length. Example2: ...

Given an array nums and a value val, remove all instances of thatvalue in-place and return the new length. Do not allocate extra space for another array, you must do this bymodifying the input array in-place with O(1) extra memory. The order of elements can be changed. It doesn't matter what you leavebeyond the new length. Example 1: Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements ofnums being 2. ...

Given a linked list, reverse the nodes of a linked list k at a timeand return its modified list.k is a positive integer and is less than or equal to the length of thelinked list. If the number of nodes is not a multiple of k thenleft-out nodes in the end should remain as it is. Example: Given this linked list: 1->2->3->4->5 For k = 2, you should return: 2->1->4->3->5 ...

D82 13. Roman to Integer题目链接13. Roman to Integer 题目分析将给定的罗马数字转换成阿拉伯数字。 思路用替换法。 要注意，先替换连续出现的那些。例如，比先替换I，要先替换III。 最终代码<?phpclass Solution { /** * @param String $s * @return Integer */ function romanToInt($s) { $ss = str_replace(['CM','CD','XC','XL','IX','IV','M','D','C','L','X','V','I'],[',900,',',400,',',90,',',40,',',9,',',4,',',1000,',',500,',',100,',',50,',',10,',',5,',',1,'],$s); return array_sum(array_filter(explode(',', $ss))); } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

Given a linked list, swap every two adjacent nodes and return itshead.You may not modify the values in the list's nodes, only nodes itselfmay be changed. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. public ListNode swapPairs(ListNode head) { ListNode trueHead=new ListNode(0); trueHead.next=head; ListNode cur=trueHead; while(cur.next!=null && cur.next.next!=null){ ListNode first=cur.next; ListNode second=cur.next.next; cur.next=second; first.next=second.next; second.next=first; cur=first; } return trueHead.next;}

Merge k sorted linked lists and return it as one sorted list. Analyzeand describe its complexity.Example: Input: [ 1->4->5, 1->3->4, 2->6 ] Output: 1->1->2->3->4->4->5->6要减小算法的复杂度，就要利用已知的条件，已知的条件就是已有的顺序。 public ListNode mergeKLists(ListNode[] lists) { ListNode trueHead=new ListNode(0); if(lists.length<=0) return trueHead.next; trueHead.next=lists[0]; for(int i=1;i<lists.length;i++){ ListNode cur=lists[i]; ListNode pre=trueHead; while(cur!=null){ while(pre.next!=null && pre.next.val<=cur.val) pre=pre.next; ListNode next=pre.next; ListNode curNext=cur.next; pre.next=cur; cur.next=next; cur=curNext; pre=pre.next; } } return trueHead.next;}我们一共会做k-1次合并，可以通过归并操作减少到logk次 public ListNode mergeKLists(ListNode[] lists) { if(lists.length<=0) return null; int len=1; while(len<=lists.length){ for(int i=0;i<lists.length-len;i=i+2*len){ ListNode left=lists[i]; ListNode cur=lists[i+len]; ListNode trueHead=new ListNode(0); trueHead.next=left; ListNode pre=trueHead; while(cur!=null){ while(pre.next!=null && pre.next.val<=cur.val) pre=pre.next; ListNode next=pre.next; ListNode curNext=cur.next; pre.next=cur; cur.next=next; cur=curNext; pre=pre.next; } lists[i]=trueHead.next; } len*=2; } return lists[0]; }

题目要求Given a non-empty 2D matrix matrix and an integer k, find the max sum of a rectangle in the matrix such that its sum is no larger than k.Example:Input: matrix = [[1,0,1],[0,-2,3]], k = 2Output: 2 Explanation: Because the sum of rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).Note:1. The rectangle inside the matrix must have an area > 0.2. What if the number of rows is much larger than the number of columns?现有一个由整数构成的矩阵，问从中找到一个子矩阵，要求该子矩阵中各个元素的和为不超过k的最大值，问子矩阵中元素的和为多少?注：后面的文章中将使用[左上角顶点坐标，右下角顶点坐标]来表示一个矩阵，如[(1,2),(3,4)]表示左上角顶掉坐标为(1,2)，右下角顶点坐标为(3,4)的矩阵。用S[(1,2),(3,4)]表示该矩阵的面积。顶点的坐标系以数组的起始点作为起点，向下为x轴正方向，向右为y轴正方向。 ...

题目要求Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.Follow up:What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?Example:// Init a singly linked list [1,2,3].ListNode head = new ListNode(1);head.next = new ListNode(2);head.next.next = new ListNode(3);Solution solution = new Solution(head);// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.solution.getRandom();要求从单链表中，随机返回一个节点的值，要求每个节点被选中的概率是相等的。 ...

Given n pairs of parentheses, write a function to generate allcombinations of well-formed parentheses.For example, given n = 3, a solution set is: [ "((()))", "(()())", "(())()", "()(())", "()()()" ]我们可以在每个index上确定上面状态带来的每个状态能引进的所有状态，可以看成是广度遍历。 public List<String> generateParenthesis(int n) { List<String> list=new ArrayList(); HashMap<String,int[]> map=new HashMap(); if(n<=0) return list; list.add("("); map.put("(",new int[]{1,1}); for(int i=2;i<=2*n;i++){ List<String> list1=new ArrayList(); HashMap<String,int[]> map1=new HashMap(); for(String s:list){ if(map.get(s)[0]>0){ list1.add(s+")"); map1.put(s+")",new int[]{map.get(s)[0]-1,map.get(s)[1]}); } if(map.get(s)[1]<n){ list1.add(s+"("); map1.put(s+"(",new int[]{map.get(s)[0]+1,map.get(s)[1]+1}); } } list=list1; map=map1; } return list;}递归的写法比较简单 ...

D81 520. Detect Capital题目链接520. Detect Capital 题目分析给定一个单词，判断其使用大写的方式正确与否。 思路如果给定单词是全大写或全小写的话，属于正确用法。 用array_count_values的结果和包含全大写或全小写的数组计算差集，结果为空集则说明为全大写或全小写。直接返回true即可。 除了全大写和全小写的情况外，只能出现首字母大写，其余字母小写的情况。 故我们把第一个字符排除掉，再判断剩余字母是否为全小写。判断方法与前面相同。 最终代码<?phpclass Solution { /** * @param String $word * @return Boolean */ function detectCapitalUse($word) { $wordArray = str_split($word); $uppercase = str_split('ABCDEFGHIJKLMNOPQRSTUVWXYZ'); $lowercase = str_split('abcdefghijklmnopqrstuvwxyz'); //all upper or lower case if(!array_diff_key(array_count_values($wordArray),array_flip($uppercase)) ||!array_diff_key(array_count_values($wordArray),array_flip($lowercase))){ return true; } //first letter whatever case, //rest of the string must be all lowercase array_shift($wordArray); if(!array_diff_key(array_count_values($wordArray),array_flip($lowercase))){ return true; } return false; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

Merge two sorted linked lists and return it as a new list. The newlist should be made by splicing together the nodes of the first twolists.Example: Input: 1->2->4, 1->3->4 Output: 1->1->2->3->4->4 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { ListNode trueHead=new ListNode(0); ListNode cur=trueHead; while(l1!=null || l2!=null){ if(l1==null){ cur.next=l2; l2=l2.next; }else if(l2==null){ cur.next=l1; l1=l1.next; }else if(l1.val<=l2.val){ cur.next=l1; l1=l1.next; }else{ cur.next=l2; l2=l2.next; } cur=cur.next; } return trueHead.next; }

D80 182. Duplicate Emails题目链接182. Duplicate Emails 题目分析写出 查找表中重复邮箱地址的SQL语句。 思路用GROUP BY把结果聚合，并用count函数计算出现次数。用having筛选出现次数大于1的结果即可。 最终代码# Write your MySQL query statement belowSELECT Email FROM Person group by Email having count(id)>1;若觉得本文章对你有用，欢迎用爱发电资助。

Given a string containing just the characters '(', ')', '{', '}', '['and ']', determine if the input string is valid.An input string is valid if: Open brackets must be closed by the same type of brackets. Openbrackets must be closed in the correct order. Note that an emptystring is also considered valid. Example 1: Input: "()" Output: true Example 2: Input: "()[]{}" Output: true Example 3: ...

Given a linked list, remove the n-th node from the end of list andreturn its head.Example: Given linked list: 1->2->3->4->5, and n = 2. After removing the second node from the end, the linked list becomes1->2->3->5. Note: Given n will always be valid. Follow up: Could you do this in one pass?链表操作的题，比较简单，主要主要Bug Free public ListNode removeNthFromEnd(ListNode head, int n) { int len=0; ListNode cur=head; while(cur!=null){ len++; cur=cur.next; } len=len-n; ListNode trueHead=new ListNode(0); trueHead.next=head; cur=trueHead; while(len>=1){ cur=cur.next; len--; } cur.next=cur.next.next; return trueHead.next;}上面的方法需要遍历两次链表也可以一次遍历出 ...

Given an array nums of n integers and an integer target, are thereelements a, b, c, and d in nums such that a + b + c + d = target? Findall unique quadruplets in the array which gives the sum of target.Note: The solution set must not contain duplicate quadruplets. Example: Given array nums = [1, 0, -1, 0, -2, 2], and target = 0. ...

第一题：计算二进制数两个1之间的间距题目： 我的思路英文翻译过来就是把数字化成二进制，计算两个1之间的最大间距。1000,1100,1010的最大间距分别是0,1,2.以此类推我的第一反应是大学数字逻辑课上的一个知识点，十进制转化为二进制——短除法！也就是说，在接收到输入的十进制数之后，利用短除法，转化为二进制数。转化的过程进行间距的计算虽然短除法先计算出来的是二进制低位的数，但是1010的间距从左往右数和从右往左数，结果是等价的实现如下：func BiggestGap(n int) int { distance,temp := 0,0 bValue := 0 for n,bValue = bDiv(n);bValue==0; { n,bValue = bDiv(n) } for (n>0) { n,bValue = bDiv(n) temp+=1 if bValue==1 { if temp>distance { distance=temp } temp = 0 } } return distance}func bDiv(n int)(remainder,bValue int){ if n%2 == 0 { return n/2,0 }else { return (n-1)/2,1 }}别人的思路看完题目，肯定是得自己先琢磨。琢磨完了，得学习学习别人是怎么分析的。先贴上别人的实现，源码是C++，我翻译成golang版本了别人家的版本：func BinaryDistance(n uint) int { var i uint distance,last:=0,-1 for i=0;i<32;i++{ if (n >> i) & 1 !=0 { if last>=0 { distance = max(distance,int(i)-last) } last = int(i) } } return distance}func max(numbers ...int) int{ max := 0 for _,num := range numbers{ if num>max { max=num } } return max}这个思路的关键点是 xxxxx0 & 000001的结果恒为零，xxxxx1 & 000001的结果恒为1（x的意思是为0或1）。有了这个计算基础之后，加上int类型默认是32位，借助移位运算符 >>，就能够判断二进制数的每一位是0还是1了最后这部分就没什么难度了，不断计算相邻两个1的距离，比之前保存的最大间距大，更新，小，丢弃，调整位置继续计算

题目要求Given an m x n matrix of non-negative integers representing the height of each unit cell in a continent, the "Pacific ocean" touches the left and top edges of the matrix and the "Atlantic ocean" touches the right and bottom edges.Water can only flow in four directions (up, down, left, or right) from a cell to another one with height equal or lower.Find the list of grid coordinates where water can flow to both the Pacific and Atlantic ocean.Note:The order of returned grid coordinates does not matter.Both m and n are less than 150.Example:Given the following 5x5 matrix: Pacific ~ ~ ~ ~ ~ ~ 1 2 2 3 (5) * ~ 3 2 3 (4) (4) * ~ 2 4 (5) 3 1 * ~ (6) (7) 1 4 5 * ~ (5) 1 1 2 4 * * * * * * AtlanticReturn:[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (positions with parentheses in above matrix).假设左上角的所有周围面积为太平洋，右下角的所有面积为大西洋。现在使用数组来表示一大片水域，其中数组的每一个位置上的元素代表某一个小水域的高度。假定水只能从高出流向低处，要求找出所有既可以流向太平洋也可以流向大西洋的水域。 ...

D75 706. Design HashMap题目链接706. Design HashMap 题目分析自行设计一个hashmap。 需要实现题目内指定的函数。 思路我觉得这个没什么好说的吧… 最终代码<?phpclass MyHashMap { /** * Initialize your data structure here. */ public $data = []; function __construct() { } /** * value will always be non-negative. * @param Integer $key * @param Integer $value * @return NULL */ function put($key, $value) { $this->data[$key] = $value; } /** * Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key * @param Integer $key * @return Integer */ function get($key) { return isset($this->data[$key])?$this->data[$key]:-1; } /** * Removes the mapping of the specified value key if this map contains a mapping for the key * @param Integer $key * @return NULL */ function remove($key) { unset($this->data[$key]); }}/** * Your MyHashMap object will be instantiated and called as such: * $obj = MyHashMap(); * $obj->put($key, $value); * $ret_2 = $obj->get($key); * $obj->remove($key); */若觉得本文章对你有用，欢迎用爱发电资助。 ...

看到这道题总觉得眼熟，做完之后恍然大悟，这不就是小学数学做的找规律一、题目Z 字形变换： 将一个给定字符串根据给定的行数，以从上往下、从左到右进行 Z 字形排列。比如输入字符串为 "LEETCODEISHIRING" 行数为 3 时，排列如下：L  C  I   RE T O E S  I  I   GE  D  H  N(这个字符排列看不懂的话推荐去看一下原题，原题的调整示例比较清晰)之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："LCIRETOESIIGEDHN"。请你实现这个将字符串进行指定行数变换的函数：string convert(string s, int numRows);示例 1:输入: s = "LEETCODEISHIRING", numRows = 3输出: "LCIRETOESIIGEDHN"示例 2:输入: s = "LEETCODEISHIRING", numRows = 4输出: "LDREOEIIECIHNTSG"二、我的答案       首先分析一下题目，输出内容就是重新排列之后的各行相加，那么问题变成按照题干规律排列，序号为n的字符在第几行。       在示例1中，LEETCODEISHIRING行数为3时，各个字符分别在1232-1232-1232-1232行，很明显应该存在某种规律，可以把字符串分成几组，然后每组按照这种规律push到不同行中，然后各行相加得出目标字符串，思路理清，代码如下 /** * @param {string} s * @param {number} numRows * @return {string} */var convert = function(s, numRows) { const perGroup = numRows > 1 ? (numRows - 2) * 2 + 2 : 1 const result = [] let i for(i = 0; i < numRows; i++) { result[i] = [] } for(i = 0; i < s.length; i++) { result[i % perGroup < numRows ? i % perGroup : numRows - (i % perGroup - numRows + 2)].push(s[i]) } let resultStr = '' result.forEach(item => { item.forEach(str => { resultStr += str }) }) return resultStr};       最后各行的数组都算出来了，转成字符串的操作想用的数组flat然后再join的，但是leetCode的编译环境好像不支持flat,就只能含泪用这种循环的方法了，最后运行用时击败88.52%，内存消耗击败33.66%，但是我不知道怎么降低内存消耗/捂脸 ...

前几天第一次在 Segmentfault 发文—JavaScript：十大排序的算法思路和代码实现，发现大家似乎挺喜欢算法的，所以今天再分享一篇前两个星期写的 Leetcode 刷题总结，希望对大家能有所帮助。 本文首发于我的blog 前言 今天终于刷完了 Leetcode 上的链表专题，虽然只有 31 道题（总共是 35 道，但有 4 道题加了锁）而已，但也陆陆续续做了两三个星期，严重跟不上原先计划啊。本来打算数据结构课程老师讲完一个专题，我就用 JS 在 Leetcode 做一个专题的。然而老师现在都讲到图了，而我连二叉树都还没刷 Orz（附上一张 AC 图，看着还是挺有成就感的嘛）。 先写一篇博客总结一下这阵子刷链表题的收获吧，有输入也要有输出。这里就不花篇幅介绍链表的一些基本概念了，不清楚的看官就自行谷歌一下吧，本文主要介绍一些常见的链表题和解题思路。文中提到的 Leetcode 题目都有给出题目链接以及相关解题代码，使用其他方法的解题代码，或者更多 Leetcode 题解可以访问我的GitHub 算法仓库。 正文缓存 不得不说使用数组 / map 来缓存链表中结点的信息是解决链表题的一大杀器，覆盖问题的范围包括但不限于：在链表中插入 / 删除结点、反向输出链表、链表排序、翻转链表、合并链表等，Leetcode 上 31 道链表绝大部分都可以使用这种方法解题。具体实现思路是先使用一个数组或者 map 来存储链表中的结点信息，比如结点的数据值等，之后根据题目要求对数组进行相关操作后，再重新把数组元素做为每一个结点连接成链表返回即可。虽然使用缓存来解链表题很 dirty，有违链表题的本意，而且空间复杂度也达到了 O(n)（即使我们常常用空间来换时间，不过还是能避免就避免吧），但这种方法的确很简单易懂，看完题目后几乎就可以马上动手不加思考地敲代码一次 AC 了，不像常规操作那样需要去考虑到很多边界情况和结点指向问题。 当然，并不是很提倡这种解法，这样就失去了做链表题的意义。如果只是一心想要解题 AC 的话那无妨。否则的话我建议可以使用数组缓存先 AC 一遍题，再使用常规方法解一次题，我个人就是这么刷链表题的。甚至使用常规方法的话，你还可以分别使用迭代和递归来解题，迭代写起来比较容易，而递归的难点在于把握递归边界和递归式，但只要理解清楚了的话，递归的代码写起来真的很少啊（后面会说到）。 先找道题 show the code 吧，不然只是单纯的说可能会半知半解。比如这道反转链表 II：反转从位置 m 到 n 的链表。如果使用数组缓存的话，这道题就很容易了。只需要两次遍历链表，第一次把从 m 到 n 的结点值缓存到一个数组中，第二次遍历的时候再替换掉链表上 m 到 n 的结点的值就可以了（是不是很简单很清晰啊，如果使用常规方法的话就复杂得多了）。实现代码如下： ...

D74 999. Available Captures for Rook题目链接999. Available Captures for Rook 题目分析在国际象棋中，“车”可以横向或竖向移动任意格子。 给定代表棋盘格子的二维数组，出现的大写字母代表白方，小写代表黑方。.代表空白格子。 返回白色车只走一次棋，有多少种吃法。 思路先从二维数组中找到白色车R。再往四个方向遍历。 在逐方向遍历时，遇到.时跳过，判断下一个格子。 如果遇到同为大写字母时，即遇到己方棋子时，停止遍历。 如果遇到小写字母时，可吃棋子数+1，并停止遍历。 如此遍历四个方向，最终返回可吃棋子数量即可。 最终代码<?phpclass Solution { /** * @param String[][] $board * @return Integer */ function numRookCaptures($board) { //首先要找到R $rowNum = -1; $colNum = -1; foreach($board as $rowNum => $row){ $colNum = array_search('R',$row); if($colNum !== false){ break; } } if($colNum===-1){ return 0; } $captureable = 0; //找到后往四个方向搜索 for($j=$colNum-1; $j>=0; $j--){ if($board[$rowNum][$j] == '.'){ continue; } if(strtoupper($board[$rowNum][$j]) == $board[$rowNum][$j]){ break; } if(strtolower($board[$rowNum][$j]) == $board[$rowNum][$j]){ $captureable++; break; } } for($j=$colNum+1; $j<8; $j++){ if($board[$rowNum][$j] == '.'){ continue; } if(strtoupper($board[$rowNum][$j]) == $board[$rowNum][$j]){ break; } if(strtolower($board[$rowNum][$j]) == $board[$rowNum][$j]){ $captureable++; break; } } for($i=$rowNum+1; $i<8; $i++){ if($board[$i][$colNum] == '.'){ continue; } if(strtoupper($board[$i][$colNum]) == $board[$i][$colNum]){ break; } if(strtolower($board[$i][$colNum]) == $board[$i][$colNum]){ $captureable++; break; } } for($i=$rowNum-1; $i>=0; $i--){ if($board[$i][$colNum] == '.'){ continue; } if(strtoupper($board[$i][$colNum]) == $board[$i][$colNum]){ break; } if(strtolower($board[$i][$colNum]) == $board[$i][$colNum]){ $captureable++; break; } } return $captureable; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

Given a string containing digits from 2-9 inclusive, return allpossible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) isgiven below. Note that 1 does not map to any letters. Example: Input: "23" Output: ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce","cf"]. Note: Although the above answer is in lexicographical order, your answercould be in any order you want. ...

D73 389. Find the Difference题目链接389. Find the Difference 题目分析给定两个字符串，其中一个字符串比另一个字符串在随机位置多一个字符。 返回多出来的字符。 思路用array_count_values计算字符串中字符出现的次数，对比两个字符串的字符出现次数。计算差集，返回差异部分即可。 最终代码<?phpclass Solution { /** * @param String $s * @param String $t * @return String */ function findTheDifference($s, $t) { $ss = array_count_values(str_split($s)); $tt = array_count_values(str_split($t)); $diff = array_diff_key($tt, $ss) + array_diff($tt, $ss) + array_diff_assoc($tt, $ss); return key($diff); }}若觉得本文章对你有用，欢迎用爱发电资助。

D72 349. Intersection of Two Arrays题目链接349. Intersection of Two Arrays 题目分析返回给定两个数组的交集。 思路这既然不是自己实现的话，直接用array_intersect就完事了。 最终代码<?phpclass Solution { /** * @param Integer[] $nums1 * @param Integer[] $nums2 * @return Integer[] */ function intersection($nums1, $nums2) { if(is_null($nums1)||is_null($nums2)){ return []; } return array_unique(array_intersect($nums1, $nums2)); }}若觉得本文章对你有用，欢迎用爱发电资助。

4:FindMedianSortedArraysThere are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)). You may assume nums1 and nums2 cannot be both empty. Example 1: nums1 = [1, 3]nums2 = [2]The median is 2.0Example 2: nums1 = [1, 2]nums2 = [3, 4]The median is (2 + 3)/2 = 2.5一、按时间复杂度O（m+n）解先来解释一下什么是中位数如下：[3，4，5] , 那么这组数的中位数就是4[3，4，5，6] , 那么这组数的中位数就是 （4+5）／2 = 4.5开始没有注意到时间复杂度，但按照O（m+n）解，也花了我不少时间，可能是很久没有接触算法的缘故。 ...

题目给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。 找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。 示例: X X X XX O O XX X O XX O X X运行你的函数后，矩阵变为： X X X XX X X XX X X XX O X X解释: 被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。 题解这道题我们拿到基本就可以确定是图的dfs、bfs遍历的题目了。题目中解释说被包围的区间不会存在于边界上，所以我们会想到边界上的o要特殊处理，只要把边界上的o特殊处理了，那么剩下的o替换成x就可以了。问题转化为，如何寻找和边界联通的o，我们需要考虑如下情况。 X X X XX O O XX X O XX O O X这时候的o是不做替换的。因为和边界是连通的。为了记录这种状态，我们把这种情况下的o换成#作为占位符，待搜索结束之后，遇到o替换为x（和边界不连通的o）；遇到#，替换回o(和边界连通的o)。 如何寻找和边界联通的o? 从边界出发，对图进行dfs和bfs即可。这里简单总结下dfs和dfs。 bfs递归。可以想想二叉树中如何递归的进行层序遍历。bfs非递归。一般用队列存储。dfs递归。最常用，如二叉树的先序遍历。dfs非递归。一般用stack。那么基于上面这种想法，我们有四种方式实现。 ...

D71 788. Rotated Digits题目链接788. Rotated Digits 题目分析当一个数字180度旋转后，不等于原来的数字，那么我们称它是一个好数字。 例如，数字0、1和8在旋转180度后，等于它本身。2和5旋转后为对方。6和9也是如此。而其他数字在旋转后不等于任何数字。 给定一个数字，返回从1到这个数字之间有多少个好数字。 思路用range函数生成1到给定数组之间的所有数组。 用array_filter函数对每一个数字进行一个操作。 对每一个数字，用str_split和array_count_values函数处理。 当包含3、4或7时，因为旋转180度后不等于任何数字，因此这个不是一个好数字。故直接返回false排除当前数字。 对数字2，转换成5。对可旋转的数字进行相同处理。 判断旋转后的数字是否等于原数字。不同则返回true保留当前数字，作为好数字。否则返回false，排除当前数字。 用count函数返回好数字的数量。 最终代码<?phpclass Solution { /** * @param Integer $N * @return Integer */ function rotatedDigits($N) { $all = range(1,$N); $good = array_filter($all, function($val){ $vs = str_split($val); $cnt = array_count_values($vs); if(isset($cnt[3]) || isset($cnt[4]) || isset($cnt[7])){ return false; } $newvs = array_map(function($va){ switch($va){ case 2: return 5; case 5: return 2; case 6: return 9; case 9: return 6; default: return $va; } },$vs); return intval(implode($newvs)) != $val; }); return count($good); }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

大部分玩前端的小伙伴，在算法上都相对要薄弱些，毕竟调样式、调兼容就够掉头发的了，哪还有多余的头发再去折腾。 确实在前端中需要使用到算法的地方是比较少，但若要往高级方向发展，算法的基本功就非常重要啦。对了，算法在面试中可是必考项啊，所以为了期望薪资，头发还是得做下牺牲呀。 有些小伙伴认为，刷了那些奇奇怪怪的算法题，可在工作中很少能直接派上用场，嗯，没错，所以学算法是件高延迟满足的事情。那么学算法，到底收获什么呢？我觉得通过练习算法，培养我们解决问题的潜意识才是最重要的。 学习算法，最直接有效的就是刷题，刷题有很多渠道，我比较推荐 LeetCode，它有国内和国外版，非常方便。现在网上有很多大牛都分享各自刷题的解法，但百读不如一练嘛，所以我也开个【来刷LeetCode】系列，由浅入深，分享我的解法和思路，因为我的解法肯定不是最棒的，所以还会在加上我觉得优秀的解法。 哔哔了这么多，我们现在开撸。代码略多，建议大家先点个赞（我就是来骗赞的~） 两数之和两数之和，题目描述如下： 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]我的思路这题，最暴力的解法就是逐个循环查找，但时间复杂度是 n*n ，太暴力的不适合我们。可以这么看，在遍历第一个值得时候，保留这个值与target的差，然后在下次遍历中，看看是不是与保留的差值相同，如果相同，那么就可以找到我们想要的结果了。画个简单的表格如下： 序号当前值差值027172这样一来，就需要记录差值，散列表这一数据结构就排上用场了，来看看百科关于散列表的介绍： 散列表（Hash table，也叫哈希表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。给定表M，存在函数f(key)，对任意给定的关键字值key，代入函数后若能得到包含该关键字的记录在表中的地址，则称表M为哈希(Hash）表，函数f(key)为哈希(Hash) 函数。而js中的对象就是基于哈希表结构，所以我们构造一个js对象即可，value是当前遍历到的值，key是其与目标值的差。 这是我的解法如下： /** * @param {number[]} nums * @param {number} target * @return {number[]} */var twoSum = function (nums, target) { let map = {}; let result = [] for (let index = 0;index <= nums.length;index++) { const val = nums[index]; if (map[val] !== undefined) { result.push(map[val], index); break; } const a = target - val; map[a] = index } return result;};// nums = [2, 6, 3, 15], target = 9// twoSum(nums,target)两数相加两数之和，题目描述如下： ...

D68 283. Move Zeroes题目链接283. Move Zeroes 题目分析给定一个整数数组，将值为0的元素移动到数组末尾，而不改动其他元素出现的顺序。 思路计算总共有多少个元素。 再在去0后的元素末尾填充0到计算出的数组长度。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @return NULL */ function moveZeroes(&$nums) { $total = count($nums); $nums = array_pad(array_filter($nums),$total,0); return $nums; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

Given an array nums of n integers and an integer target, find threeintegers in nums such that the sum is closest to target. Return thesum of the three integers. You may assume that each input would haveexactly one solution.Example: Given array nums = [-1, 2, 1, -4], and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).感觉与上一题类似，可以使用双指针避免无用的判断 ...

D67 485. Max Consecutive Ones题目链接485. Max Consecutive Ones 题目分析给定一个二进制数组（只含有0和1的数组），返回最长的1串。 思路逐个遍历，若为1则计数。遇到0则判断当前计数是否大于之前记录的最大数字，并置零。 返回最大数。 最终代码<?phpclass Solution { /** * @param Integer[] $nums * @return Integer */ function findMaxConsecutiveOnes($nums) { $max = 0; $current = 0; foreach($nums as $val){ if($val == 1){ $current++; if($current>$max){ $max = $current; } } else{ $current = 0; } } return $max; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目要求Given a root node reference of a BST and a key, delete the node with the given key in the BST. Return the root node reference (possibly updated) of the BST.Basically, the deletion can be divided into two stages:Search for a node to remove.If the node is found, delete the node.Note: Time complexity should be O(height of tree).Example:root = [5,3,6,2,4,null,7]key = 3 5 / \ 3 6 / \ \2 4 7Given key to delete is 3. So we find the node with value 3 and delete it.One valid answer is [5,4,6,2,null,null,7], shown in the following BST. 5 / \ 4 6 / \2 7Another valid answer is [5,2,6,null,4,null,7]. 5 / \ 2 6 \ \ 4 7假设有一棵二叉搜索树，现在要求从二叉搜索树中删除指定值，使得删除后的结果依然是一棵二叉搜索树。 ...

D65 892. Surface Area of 3D Shapes题目链接892. Surface Area of 3D Shapes 题目分析给定一个三维数组，返回所行程柱状体的表面积。 思路三维数组中，$arr[$i][$j]的值表示在该点上柱状体的高度。 因此，对每一个值，需要算做6份（1*1*1）的面积。但是，当上方或下方有块时，需要减去相应面积。 当相邻位置有方块时，需要减去相应表面积。当前柱体和相邻柱体都需要减去。但只减去两个柱体中，较矮的柱体的高度*2。 要记住，在两个方向上都需要做该判断。 最终代码<?phpclass Solution { /** * @param Integer[][] $grid * @return Integer */ function surfaceArea($grid) { $total = 0; $ys = count($grid); for($i = 0; $i<$ys; $i++){ $xs = count($grid[$i]); for($j = 0; $j<$xs; $j++){ $total += $grid[$i][$j]*4+2*($grid[$i][$j]!=0); if($i+1<$ys){ $total -= min($grid[$i][$j],$grid[$i+1][$j])*2; } if($j+1<$ys){ $total -= min($grid[$i][$j],$grid[$i][$j+1])*2; } } } return $total; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

题目要求Given an array which consists of non-negative integers and an integer m, you can split the array into m non-empty continuous subarrays. Write an algorithm to minimize the largest sum among these m subarrays.Note:If n is the length of array, assume the following constraints are satisfied:1 ≤ n ≤ 10001 ≤ m ≤ min(50, n)Examples:Input:nums = [7,2,5,10,8]m = 2Output:18Explanation:There are four ways to split nums into two subarrays.The best way is to split it into [7,2,5] and [10,8],where the largest sum among the two subarrays is only 18.将一个长度为n的正整数数组分割为m个非空的连续子数组，并分别计算每个子数组中所有元素的和。求一种分割方式，使得该分割方式生成的最大子数组和为所有分割方式中最小的。 ...

Write a function to find the longest common prefix string amongst anarray of strings.If there is no common prefix, return an empty string "". Example 1: Input: ["flower","flow","flight"] Output: "fl" Example 2: Input: ["dog","racecar","car"] Output: "" Explanation: There is nocommon prefix among the input strings. Note: All given inputs are in lowercase letters a-z.比较简单的一道题 按正向思维就可解 public String longestCommonPrefix(String[] strs) { if(strs.length<=0) return ""; List<Integer> list=new ArrayList(); for(String s:strs) list.add(s.length()); int min=Collections.min(list); StringBuilder builder=new StringBuilder(); for(int i=0;i<min;i++){ char c=strs[0].charAt(i); for(int j=1;j<strs.length;j++){ if(c!=strs[j].charAt(i)) return builder.toString(); } builder.append(c); } return builder.toString();}

D64 292. Nim Game题目链接292. Nim Game 题目分析假设你和朋友玩一个捡石头的游戏，你和朋友轮流拿1~3颗石头。拿到最后一颗石头的一方为剩方。第一轮由你开始捡石头。 同时假设你和你的朋友都足够聪明，每次都能采取最优策略。 现给定一个石头数量，判断你最终是否能取得胜利。 思路我们先从少一点开始推广到n个石头。 如果有1～3颗石头，因为规定了是你开始、还假设会采取最优策略，那么你是能获胜的。也即，对方不会在拿走石头后剩下1 假设有4颗石头。 你拿1颗，会剩下3颗。对方全拿，对方赢。 你拿2颗，会剩下2颗。对方全拿，对方赢。 你拿3颗，会剩下1颗。对方全拿，对方赢。 即，怎么拿都是你输。 假设有5颗石头。 你拿1颗，会剩下4颗。 对方拿走1颗，剩下3颗给你，你全拿，你赢。 对方拿走2颗，剩下2颗给你，你全拿，你赢。 对方拿走3颗，剩下1颗给你，你全拿，你赢。 你拿2颗，会剩下3颗。对方全拿，对方赢。 你拿3颗，会剩下2颗。对方全拿，对方赢。 因此，这一轮你会选择拿1颗，剩下4颗。 假设有6颗石头。 你拿1颗，会剩下5颗。 对方拿走1颗，剩下4颗给你，参考一开始就只有4颗的情况，对方赢。 对方拿走2颗，剩下3颗给你，你全拿，你赢。 对方拿走3颗，剩下2颗给你，你全拿，你赢。 你拿2颗，会剩下4颗。 对方拿走1颗，剩下3颗给你，你全拿，你赢。 对方拿走2颗，剩下2颗给你，你全拿，你赢。 对方拿走3颗，剩下1颗给你，你全拿，你赢。 你拿3颗，会剩下3颗。对方全拿，对方赢。 因此，这一轮你会选择拿2颗，剩下4颗。 假设有7颗石头。 你拿1颗，会剩下6颗。 对方拿走1颗，剩下5颗给你，参考一开始就只有5颗的情况，你赢。 对方拿走2颗，剩下4颗给你，对方赢。 对方拿走3颗，剩下3颗给你，你全拿，你赢。 你拿2颗，会剩下5颗。 对方拿走1颗，剩下4颗给你，对方赢。 对方拿走2颗，剩下3颗给你，你全拿，你赢。 对方拿走3颗，剩下2颗给你，你全拿，你赢。 你拿3颗，会剩下4颗。 对方拿走1颗，剩下3颗给你，你全拿，你赢。 对方拿走2颗，剩下2颗给你，你全拿，你赢。 对方拿走3颗，剩下1颗给你，你全拿，你赢。 因此，这一轮你会选择拿3颗，剩下4颗。 ...

题目要求You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.Follow up:What if you cannot modify the input lists? In other words, reversing the lists is not allowed.Example:Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)Output: 7 -> 8 -> 0 -> 7对以链表形式的两个整数进行累加计算。 ...

D62 976. Largest Perimeter Triangle题目链接976. Largest Perimeter Triangle 题目分析给定数字数组，任取三条边形成三角形，返回最大边长。 思路对给定的数组进行降序排序，使最大的数字在前面。 取最大的前三条，判断任两边之和是否大于第三边。 是则返回周长即可。 最终代码<?phpclass Solution { /** * @param Integer[] $A * @return Integer */ function largestPerimeter($A) { rsort($A); $length = count($A); for($i = 0; $i<$length-2; $i++){ if( ($A[$i] + $A[$i+1] > $A[$i+2]) && ($A[$i] + $A[$i+2] > $A[$i+1]) && ($A[$i+1] + $A[$i+2] > $A[$i]) ){ return $A[$i] + $A[$i+1] + $A[$i+2]; } } return 0; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D61 953. Verifying an Alien Dictionary题目链接953. Verifying an Alien Dictionary 题目分析给定一个单词数组和一个字符串，判断给定的数组是否满足给定字符串的顺序。 思路按给定字符串，替换成正常顺序的单词。 再判断sort之前和之后的数组是否相同。 最终代码<?phpclass Solution { /** * @param String[] $words * @param String $order * @return Boolean */ function isAlienSorted($words, $order) { $order = array_flip(str_split($order)); $alphas = str_split('abcdefghijklmnopqrstuvwxyz'); $words = array_map(function($val) use ($order, $alphas){ $chars = str_split($val); $word = []; foreach($chars as $char){ $word[] = $alphas[$order[$char]]; } return implode('', $word); }, $words); $originalWords = $words; sort($words); return $words == $originalWords; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

LeetCode 89. 格雷编码格雷编码是一个二进制数字系统，在该系统中，两个连续的数值仅有一个位数的差异。给定一个代表编码总位数的非负整数 n，打印其格雷编码序列。格雷编码序列必须以 0 开头。第一个数与最后一位数 也只差以为一位数 ‘首尾相连’ 所以又称为循环码或反射码 示例 1: 输入: 2输出: [0,1,3,2]解释:00 - 001 - 111 - 310 - 2对于给定的 n，其格雷编码序列并不唯一。例如，[0,2,3,1] 也是一个有效的格雷编码序列。00 - 010 - 211 - 301 - 1示例 2: 输入: 0输出: [0]解释: 我们定义格雷编码序列必须以 0 开头。 给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。 因此，当 n = 0 时，其格雷编码序列为 [0]。这题的难度主要是将给定的n转化为格雷编码 第一步 将n转变为格雷编码1=>['0','1']n = 101n = 20001--1110n = 3000001011010---110111101100分析上面的数字排列 我们可以注意到3点 以--为间隔上面的编码与下面的编码是轴对称的（除了第一位以外）后一个格雷编码 是以上一个为基础 做轴对称生成，并且前一半编码每项'0'+'xxx',后一半编码每项'1'+'xxx',每组的编码的长度为2^n先实现这部分逻辑 ...

D60 824. Goat Latin题目链接824. Goat Latin 题目分析给定一个句子，由大小写英文字母组成，以空格为单词的分割。 按以下规则修改单词： 如果一个单词以元音开头（即AEIOU），那么在这个单词末尾添加ma；如果不是以元音开头，那么将第一个字母移动到当前单词末尾，并在后面添加ma；在所有单词末尾再额外添加n个a。n为当前单词在句子中的次序，从1开始。即，在第1个单词按以上规则转换完成后，再加1个a。在第2个单词末尾加2个a，第3个加3个a，以此类推。思路首先，需要把句子分割成单词。用str_explode就可以实现。 分割后，判断首字母是否不是元音。 不是元音，则将第一个字母移到最后。 给字符串末尾添加ma。 给字符串末尾添加额外的n个a。 最终代码<?phpclass Solution { /** * @param String $S * @return String */ function toGoatLatin($S) { $words = explode(' ', $S); $newWords = []; foreach($words as $key => $word){ if(!in_array($word[0],['a','e','i','o','u','A','E','I','O','U'])){ $word .= $word[0]; $word = substr($word,1); } $word .= 'ma'.str_repeat('a', $key+1); $newWords[] = $word; } return implode(' ', $newWords); }}若觉得本文章对你有用，欢迎用爱发电资助。

D59 226. Invert Binary Tree题目链接226. Invert Binary Tree 题目分析反转二叉树。 思路类似反转两个变量，先把左右子树存进单独的变量，再相互覆盖左右子树。 并对子树进行相同的操作。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { /** * @param TreeNode $root * @return TreeNode */ function invertTree($root) { $left = $root->left; $right = $root->right; $root->left = $right; $root->right = $left; if($root->left){ $this->invertTree($root->left); } if($root->right){ $this->invertTree($root->right); } return $root; } }若觉得本文章对你有用，欢迎用爱发电资助。 ...

Given n non-negative integers a1, a2, ..., an , where each representsa point at coordinate (i, ai). n vertical lines are drawn such thatthe two endpoints of line i is at (i, ai) and (i, 0). Find two lines,which together with x-axis forms a container, such that the containercontains the most water.Note: You may not slant the container and n is at least 2. The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7].In this case, the max area of water (blue section) the container cancontain is 49.Example: ...

LeetCode 605. 种花问题假设你有一个很长的花坛，一部分地块种植了花，另一部分却没有。可是，花卉不能种植在相邻的地块上，它们会争夺水源，两者都会死去。 给定一个花坛（表示为一个数组包含0和1，其中0表示没种植花，1表示种植了花），和一个数 n 。能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。 示例 1: 输入: flowerbed = [1,0,0,0,1], n = 1输出: True示例 2: 输入: flowerbed = [1,0,0,0,1], n = 2输出: False注意:数组内已种好的花不会违反种植规则。输入的数组长度范围为 [1, 20000]。n 是非负整数，且不会超过输入数组的大小。我的思路总的来讲，这道题在leetCode 中不算难的，关键就是要有思路。下面是我自己做题时的分析。1. 在两边都是花 中间都是空地的情况下(关键前提) ，算出可以种花的最值。如[1,0,0,0,0,1]=>1 连续空地数 可种花的最值 0 => 0 1 => 0 2 => 0 3 => 1 4 => 1 5 => 2 6 => 2 7 => 3有感觉的老哥 ，估计已经有了想法，没错就是 parseInt((n - 1) / 2 ) = 可以种几颗 // (n为最近两个花 之间的空地数量)得出了这个结论 就基本完成了 但是还有2种特殊情况,以下是完整代码（战胜84%的js提交） ...

longest-substring-without-repeating-characters题目描述Given a string, find the length of the longest substring without repeating characters. 给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。 示例 1: 输入: "abcabcbb"输出: 3 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。示例 2: 输入: "bbbbb"输出: 1解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。示例 3: 输入: "pwwkew"输出: 3解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。 请注意，你的答案必须是 **子串** 的长度，"pwke" 是一个子序列，不是子串。<!--more--> 我的垃圾思路One刚开始想耍一些"小聪明"，看有没有巧妙的方法解决，当时用了类似于Node的前后'指针'的方式发现有线用例是过不了的后面用到了类似"滑窗"的方法，碰到重复字符则将滑窗宽度归零，且位置回到被重复字符的下一位置。但会出现死循环，因为没把之前被重复的字符remove掉 -- 后面发现只remove掉那个重复的字符的话，有些没有重复的字符在回退之后再次计算的时候，会发生混乱<font color=grey size=2>(回退后再次走到之前不重复的字符时候，因为hash表中已经在第一次put过了，所以这次一定会发生重复情况)</font>所以上面把滑窗归零的时候是真正的归零，包括存数据的hash表上面方法应该是 $ O(n^2) $ ,因为会发生例如abcdea在最后a发生重复，就会完全回退到b位置---so low ；提交记录耗时大概80+msTwo第二个方法是也两个指针类似滑窗， k指针一直前进，发生重复时j指针移动到被重复字符的下一位置，但是只能往右移动，不能回退将map<Character,Integer>中存放的之前被重复字符的value(即字符所在的索引)换为当前发生重复的字符位置 -- 不是被重复字符循环中一直保持max最大当有其中一个指针到达终点时，就可以退出了 ；由于j,k代表的都是索引，所以最后结果 为max+1Three第二种方法发现 k一直在++，其实就相当于for循环的 i++，所以就换成for循环了 -- 复杂度应该是 $ O(n) $Two和Three 提交的耗时6ms,占用内存35M--占用内存竟然超过了 100%的java用户ヽ(°◇° )ノ ...

Given an input string (s) and a pattern (p), implement regularexpression matching with support for '.' and '*'.'.' Matches any single character. '*' Matches zero or more of thepreceding element. The matching should cover the entire input string(not partial). Note: s could be empty and contains only lowercase letters a-z. p could beempty and contains only lowercase letters a-z, and characters like .or *. Example 1: ...

D58 693. Binary Number with Alternating Bits题目链接693. Binary Number with Alternating Bits 题目分析给定一个数字，返回其二进制形式中，0和1是否交替出现。 思路判断给定的数字是否为奇数。 若为奇数，那么最低位（即最右）会为1，那么会重复出现01串。 若为偶数，最低位为0，那么只能重复出现10串。 根据以上规则创建长度为给定数字二进制长度一半的01串，并转换为十进制。 判断转换后的数字是否等于给定的字符。 最终代码<?phpclass Solution { /** * @param Integer $n * @return Boolean */ function hasAlternatingBits($n) { $match = str_repeat($n%2==0?'10':'01',ceil(count(str_split(decbin($n)))/2)); return bindec($match) == $n; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目描述You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself. 给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 ...

D57 762. Prime Number of Set Bits in Binary Representation题目链接762. Prime Number of Set Bits in Binary Representation 题目分析对给定范围内的每个整数，返回其二进制形式下，数字1出现的次数为质数的次数。 例如11111，1出现了5次，5是质数。 再如10111，1出现了4次，4不是质数。 思路由于题目固定了范围为1~10^6，10^6次方为1千万。小于2^24。即最多只会出现24次1。 由于小于24的质数个数有限，我们直接写死24以内的质数。 对每一个数字，计算1出现的次数。再判断出现次数是否在这个质数数组内。 存在则符合题目要求的数字，否则不计入该数字。 最终代码<?phpclass Solution { /** * @param Integer $L * @param Integer $R * @return Integer */ function countPrimeSetBits($L, $R) { $primes = [2,3,5,7,11,13,17,19,23]; $nums = range($L,$R); $primeOnes = 0; foreach($nums as $num){ $ones = array_filter(str_split(decbin($num)), function($val){ return $val == '1'; }); if(in_array(count($ones),$primes)){ $primeOnes++; } } return $primeOnes; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D56 637. Average of Levels in Binary Tree题目链接637. Average of Levels in Binary Tree 题目分析返回每一层的平均值。 思路和前一篇相似。先保存每一层的值，再逐层计算平均值即可。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { /** * @param TreeNode $root * @return Float[] */ public $level = 0; public $values = []; function averageOfLevels($root) { $this->levelValues($root); $avg = []; foreach($this->values as $values){ $avg[] = array_sum($values)/count($values); } return $avg; } function levelValues($root){ if(is_null($root)){ return $this->values; } if(!isset($this->values[$this->level])){ $this->values[$this->level] = []; } $this->values[$this->level][] = $root->val; if($root->left){ $this->level++; $this->averageOfLevels($root->left); $this->level--; } if($root->right){ $this->level++; $this->averageOfLevels($root->right); $this->level--; } return $this->values; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

leetCode第一题普通解决思路将数组变量两次，相加判断是否等于传过来的值，如果等于，返回下标自己写的代码，如果有错误请指出，谢谢 package com.leetcode.firstquestion.one;import java.util.Arrays;/** * @program: test * @description: 两数之和 给定一个整数数组 nums 和一个目标值 target， * 请你在该数组中找出和为目标值的那 * 两个 整数，并返回他们的数组下标。 * @author: Mr.Yang * @create: 2019-05-08 09:20 **/public class Solution { public int[] twoSum(int[] nums, int target) { int[] ints = new int[2]; int indexOne=0; int indexTwo=0; boolean flag=false; for(int x=0;x<nums.length;x++){ for(int y=x+1;y<nums.length;y++){ if((nums[x]+nums[y])==target){ indexOne=x; indexTwo=y; flag=true; break; } } if(flag){ break; } } ints[0]=indexOne; ints[1]=indexTwo; return ints; } public static void main(String[] args) { int[] ints = {1, 2, 3, 4, 5, 6, 7, 8, 9}; Solution solution = new Solution(); int[] ints1 = solution.twoSum(ints, 9); System.out.println(Arrays.toString(ints1)); }}网上流传思路，使用HashMap来处理将数组的遍历值当作key（为了存取好处理，所以将数组的遍历值当作key），索引当作value来存储。 ...

题目描述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 示例: 给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]<!--more--> 我的垃圾思路One我能想到的只有一个循环去遍历每个数字，一个循环去匹配是否有符合的 -- O(n^2)首先想到暴力破解，两个for循环去找哪两个索引对应的值加起来等于target(当然这估计过不了关)但是想到了HashMap有个get方法效率很高，那么首先把数组中所有元素put到map中，将target - nums[i]作为key，索引index作为value，那么再写一个循环去遍历数组时候，判断起来就很方便了。直接用map.get(nums[i])，即可拿到对应的value，当value不为null的时候证明满足了nums[i] + nums[j] = target,也就是nums[i] = target - nums[j]。如上面示例的话，map中会存放的是map:{7:0, 2:1, -2:2, -6:3}然后再写一个循环去判断 int b = map.get(nums[i])不为空 且b != i时<font color=grey size=2>(因为当nums[0]==3，target==6就会得到[0,0]，很显然这是错误的，题目中提到了不能重复利用这个数组中同样的元素)</font>，即可break，[i,b]就是答案Two不过还是写个两个循环，能否写成一个循环呢？（根据提交的答案结果看来，两者差距不大） 那就是一个循环，边循环，边put到map中（key,value同上），循环过程中再去判断是否map已经contains这个nums[i]了，如果包含则满足了nums[i] = target - nums[j]，即可以break上面都将 $ O(n^2)->O(n) $ 我的垃圾代码package com.dasnnj.practice.simple;import java.util.Arrays;import java.util.HashMap;import java.util.Map;/** * Description <p> TODO: * 给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。 * 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。 * <p> * 示例: * <p> * 给定 nums = [2, 7, 11, 15], target = 9 * <p> * 因为 nums[0] + nums[1] = 2 + 7 = 9 * 所以返回 [0, 1]</p> * * @author DASNNJ <a href="mailto:dasnnj@outlook.com"> dasnnj@outlook.com </a> * @date 2019-04-28 15:38 */public class TwoSum { static int[] twoSum(int[] nums, int target) { //One /*//key为target-nums[i],value为index Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(target-nums[i],i); } int[] res = new int[2]; for (int i = 0; i < nums.length; i++) { Integer b; if ((b = map.get(nums[i])) != null && b != i) { res[0] = b; res[1] = i; break; } } return res; */ //Two //key为target-nums[i],value为index Map<Integer, Integer> map = new HashMap<>(); int[] res = new int[2]; for (int i = 0; i < nums.length; i++) { if (map.containsKey(nums[i])) { res[0] = map.get(nums[i]); res[1] = i; break; } map.put(target - nums[i], i); } return res; } public static void main(String[] args) { int[] nums = new int[]{2, 7, 11, 15}; System.out.println(Arrays.toString(TwoSum.twoSum(nums, 9))); }}

D55 429. N-ary Tree Level Order Traversal题目链接429. N-ary Tree Level Order Traversal 题目分析按层遍历N叉树。 思路以层数为键，塞入当前节点的值。 递归遍历即可。 最终代码<?php/*// Definition for a Node.class Node { public $val; public $children; @param Integer $val @param list<Node> $children function __construct($val, $children) { $this->val = $val; $this->children = $children; }}*/class Solution { /** * @param Node $root * @return Integer[][] */ public $level = 0; public $values = []; function levelOrder($root) { if(is_null($root)){ return $this->values; } if(!isset($this->values[$this->level])){ $this->values[$this->level] = []; } $this->values[$this->level][] = $root->val; foreach($root->children as $child){ $this->level++; $this->levelOrder($child); $this->level--; } return $this->values; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D54 937. Reorder Log Files题目链接937. Reorder Log Files 题目分析给定一个数组，每一个元素是一条“日志”。 每一条日志的第一个部分为一个标识符（ID）。 剩余部分为： 全为小写字母的字符串（称为字符日志） 或 全为数字的字符串（称为数字日志）。 给定的数组中确定会至少有一个字母。 重新排序这个数组，使得字符日志在前、数字日志在后。 并将字符日志按字母升序排序，数字日志按保持原来的顺序（即，出现的顺序）。 返回排序后的数组。 思路针对每一条日志： 首先，需要拆分ID和日志部分。 判断是字符日志还是数字日志，存入相应数组中。 遍历完成后，对字符日志进行排序。 在其后拼接数字日志数组，并返回即可。 最终代码<?phpclass Solution { /** * @param String[] $logs * @return String[] */ function reorderLogFiles($logs) { $letters = []; $digits = []; foreach($logs as $log){ $values = explode(' ',$log); $id = array_shift($values); $firstLetter = ord($values[0][0]) - ord('0'); if($firstLetter>=0 && $firstLetter<=9){ $digits[] = $log; } else{ $letters[implode(' ',$values)] = $log; } } ksort($letters); return $letters+$digits; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

题目要求A sequence of numbers is called a wiggle sequence if the differences between successive numbers strictly alternate between positive and negative. The first difference (if one exists) may be either positive or negative. A sequence with fewer than two elements is trivially a wiggle sequence.For example, [1,7,4,9,2,5] is a wiggle sequence because the differences (6,-3,5,-7,3) are alternately positive and negative. In contrast, [1,4,7,2,5] and [1,7,4,5,5] are not wiggle sequences, the first because its first two differences are positive and the second because its last difference is zero.Given a sequence of integers, return the length of the longest subsequence that is a wiggle sequence. A subsequence is obtained by deleting some number of elements (eventually, also zero) from the original sequence, leaving the remaining elements in their original order.Example 1:Input: [1,7,4,9,2,5]Output: 6Explanation: The entire sequence is a wiggle sequence.Example 2:Input: [1,17,5,10,13,15,10,5,16,8]Output: 7Explanation: There are several subsequences that achieve this length. One is [1,17,10,13,10,16,8].Example 3:Input: [1,2,3,4,5,6,7,8,9]Output: 2Follow up:Can you do it in O(n) time?扭动序列是指数组中的相邻两个元素的差保证严格的正负交替，如[1,7,4,9,2,5]数组中相邻两个元素的差为6,-3,5,-7,3，满足扭动序列的要求。现在要求从一个数组中，找到长度最长的扭动子序列，并返回其长度。 ...

D53 566. Reshape the Matrix题目链接566. Reshape the Matrix 题目分析给定一个二维数组，将它重新排列成r行c列的二维数组。 思路先把数据全部提出来，再用array_chunk函数重新分割数组。 最终代码<?phpclass Solution { /** * @param Integer[][] $nums * @param Integer $r * @param Integer $c * @return Integer[][] */ function matrixReshape($nums, $r, $c) { $values = []; foreach($nums as $items){ foreach($items as $item){ $values[] = $item; } } return count($values)/$c==$r?array_chunk($values, $c):$nums; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目要求Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.Find all the elements of [1, n] inclusive that do not appear in this array.Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space.Example:Input:[4,3,2,7,8,2,3,1]Output:[5,6]假设一个长度为n的整数数组，数组中的元素的值位于[1,n]区间中。问，该数组中有哪些[1,n]区间中的整数没有出现？ 思路和代码首先可以想到用另一个临时数组来记录每个元素出现的次数，则出现次数为零次的元素在数组中没有出现。代码如下： public List<Integer> findDisappearedNumbers(int[] nums) { int[] temp = new int[nums.length + 1]; for (int i = 0; i < nums.length; i++) { temp[nums[i]]++; } List<Integer> result = new ArrayList<>(); for (int i = 1; i < temp.length; i++) { if (temp[i] == 0) { result.add(i); } } return result; }但是这个实现违背了O(1)的空间复杂度（这里结果集不视为额外空间）。因此如何才能避免使用临时数组呢？其实我们可以利用原数组中元素相互调换的方式，将其转化为一个新的有序的数组。即从最左边开始，每遇到一个元素，就将其防止到元素的目标位置上，如在第0位上遇到元素i，则将位置i-1上的元素和位置0上的元素进行交换，并在此判断新的元素是否需要交换。如果当前元素无需进行交换，则指针右移一位。无需进行的场景是指当前元素已经出现在目标位置上了。 ...

题目要求Equations are given in the format A / B = k, where A and B are variables represented as strings, and k is a real number (floating point number). Given some queries, return the answers. If the answer does not exist, return -1.0.Example:Given a / b = 2.0, b / c = 3.0.queries are: a / c = ?, b / a = ?, a / e = ?, a / a = ?, x / x = ? .return [6.0, 0.5, -1.0, 1.0, -1.0 ].The input is: vector<pair<string, string>> equations, vector<double>& values, vector<pair<string, string>> queries , where equations.size() == values.size(), and the values are positive. This represents the equations. Return vector<double>.According to the example above:equations = [ ["a", "b"], ["b", "c"] ],values = [2.0, 3.0],queries = [ ["a", "c"], ["b", "a"], ["a", "e"], ["a", "a"], ["x", "x"] ]. The input is always valid. You may assume that evaluating the queries will result in no division by zero and there is no contradiction.已知一些字母之间的关系式，问是否能够计算出其它字母之间的倍数关系？如已知a/b=2.0 b/c=3.0问是否能够计算出a/c, b/a, a/e, a/a, x/x的值。如果无法计算得出，则返回-1。这里x/x的值因为在条件中无法获知x是否等于零，因此也无法计算其真实结果，也需要返回-1。 ...

Easy 020 Valid ParenthesesDescription:“()” "[]" "{}"三种括号匹配问题，判断参数字符串是否满足匹配要求如：“({[]})” true “[{})” falseNote:空串为trueMy Solution:括号匹配问题是栈的典型应用，遇到左括号，入栈，遇到右括号，看栈顶是否是相应的左括号，若不是，则false时间复杂度O(n)代码如下： public boolean isValid(String s) { if(s.length()==0){ return true; } Stack<Character> stack = new Stack<>(); for(char c:s.toCharArray()){ if(c == '(' || c == '{' || c == '['){ stack.push(c); }else if(stack.size()==0){ return false; } else if(c == ')' && stack.peek() == '('){ stack.pop(); }else if(c == ']' && stack.peek() == '['){ stack.pop(); }else if(c == '}' && stack.peek() == '{'){ stack.pop(); }else return false; } if(stack.size() == 0){ return true; } return false; }Fast Solution:

D52 496. Next Greater Element I题目链接496. Next Greater Element I 题目分析给定两个数组，其内元素不重复。 数组1是数组2的子集，返回每个在数组1中的元素在数组2对应位置以右最大的元素。 思路只能逐个遍历吧。 最终代码<?phpclass Solution { /** * @param Integer[] $nums1 * @param Integer[] $nums2 * @return Integer[] */ function nextGreaterElement($nums1, $nums2) { $result = []; foreach($nums1 as $key => $value){ $greater = -1; $start = false; for($i = 0; $i<count($nums2); $i++){ if($nums2[$i] == $value){ $start = true; } if($start && $nums2[$i]>$value){ $greater = $nums2[$i]; break; } } $result[] = $greater; } return $result; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D50 933. Number of Recent Calls题目链接933. Number of Recent Calls 题目分析这个题目说实在的，看得我一脸蒙蔽。 返回自3000毫秒到现在为止ping的次数（包括当前ping）。 调ping函数时，传入的参数t为当前ping的毫秒数。 思路其实是说，返回前3000毫秒内ping的次数。 把每次ping的毫秒数存起来，然后往回找3000毫秒内的ping。 即，给当前ping次数加1，直到当前毫秒数减前面ping的毫秒数大于3000。 最终代码<?phpclass RecentCounter { public $pings = []; public $head = 0; function __construct() { } function ping($t) { if(is_null($t)){ return null; } $this->pings[] = $t; while(($this->pings[count($this->pings)-1]-$this->pings[$this->head])>3000){ $this->head++; } return count($this->pings)-$this->head; }}/** * Your RecentCounter object will be instantiated and called as such: * $obj = RecentCounter(); * $ret_1 = $obj->ping($t); */ 若觉得本文章对你有用，欢迎用爱发电资助。 ...

D49 821. Shortest Distance to a Character题目链接821. Shortest Distance to a Character 题目分析给定一个字符串s和一个字符c。 返回字符串中每一个字符离给定的字符c的最短距离。 思路先用array_keys找到字符C在字符串S中的位置。 如果当前遍历到的位置是在下一个出现的字符C之前，那么直接相减下标即可得到距离。 否则，当当前下标大于上一个出现字符C的位置，且存在下一个字符C时，距离为两者中最小的那个。 当距离为0时，标记下一个要获取的C的位置。 最终代码<?phpclass Solution { function shortestToChar($S, $C) { $S = str_split($S); $keys = array_keys($S,$C); $distances = []; $prev = 0; foreach($S as $index => $char){ $dist = abs($keys[$prev] - $index); if($index > $keys[$prev] && isset($keys[$prev+1])){ $dist = min($index-$keys[$prev],$keys[$prev+1]-$index); if($dist == 0){ $prev++; } } $distances[] = $dist; } return $distances; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

905. Sort Array By Parity（easy）题目理解：一个数组中全是非负数，现在要我们把偶数放在前面，奇数放在偶数之后 首先想到的做法：声明一个新的vector，扫描A两遍，第一遍插入偶数，第二遍插入奇数，返回新的vector可能优化方向： 扫描一遍不分配新空间于是想到了新的做法：用两个指针标记位置，两个指针分别从前往后和从后往前扫描比较两个指针所指的数据有4种情况： 情况对应操作前奇后偶交换位置，i向后移，j向前移前偶后奇不用交换，i往后移，j往前移前后全是偶数不用交换，i往后移前后全是奇数不用交换，j往前移其实这种做法的本质就是利用两个指针在O(N)时间里达到了和之前扫描两次同样的效果，并且维护了原数组，就不用再分配新的空间了，这也是一种比较常用的做法。在实际代码里我对i，j移动的时机做了一些改动，结果是一样的，但是看起来可能更简单，也可以分成四种情况逐一用if...else if来写。accept代码 class Solution {public: vector<int> sortArrayByParity(vector<int>& A) { int i = 0, j = A.size() - 1; int n = A.size(); while (i < j) { if (A[i] % 2 != 0 && A[j] % 2 != 1) swap(A[i++], A[j--]); if (A[i] % 2 == 0) i++; if (A[j] % 2 == 1) j--; } return A; }}; ...

vector介绍我对vector的认识就是C++提供的包装好的数组，即对象的集合，一般来说，刷题过程中普通数组都可以用vector来代替，毕竟vector有很对简单用法并且不用考虑长度问题。因为是基础用法部分，就不深究vector和数组的区别以及vector的特性了，直接进入使用吧 本vector用法说明由于只是针对leetcode刷题所写的常用用法，所以内容可能比较简略，只是vector的部分内容。 声明虽然leetcode上自动包含了所有头文件，但是如果自己编程使用vector要加上头文件 #include <vector>再加上using namespace std;或者using std::vector;创建，复制vector<int> a; //创建一个空的vectorvector<int> a(n); //创建一个含有n个对象的vector， //此时数据已缺省构造产生，比如现在的数组里全是0vector<int> a(n, elem);//创建一个含有n个elem拷贝的vectorvector<int> a1(a2); //复制一个vectorvector<int> a1(begin, end); //这里的begin和end可以是另一个vector的迭代器 //会将[begin,end)范围内的数据复制过来关于最后一个用法有一个小坑可以注意一下，假设a2是一个含有4个int数据的vector，如果你是这样用的：vector<int> a1(a2.begin(), a2.begin()+3),那么a1中实际有3个对象；但如果你是这样用的：vector<int> a1(a2.begin(), a2.end()),那么a1中实际有4个对象。这是因为a2.end()实际上指向的并不是vector最后一个对象，而是最后一个对象的下一个位置。 一般来说，leetcode刷题过程中都不用手动释放vector内存，所以我也就不写了 访问数据a.begin() 返回指向首个对象的指针,也就是一般所说的迭代器a.end() 返回指向最后一个对象的下一个位置的指针a.begin()+1 返回指向首个对象的下一个对象的指针a.end()-1 返回返回指向最后一个对象的指针a.rbegin() 返回指向最后一个对象的指针，反向迭代器a.rend() 返回指向首个对象的前一个位置的指针，反向迭代器迭代器我个人觉得一开始不用深究，只需要知道他们是指向vector对象的指针即可反向迭代器很容易搞混。。可以不用，如果用的话要记住，rend和end分别在vector的两头 a.front() 返回首个对象的数据，和*a.begin()是一样的a.back() 返回最后一个对象的数据a.at(i) 返回编号i位置处的对象数据,会检查数据是否存在a[i] 返回编号i位置处的对象数据这里建议大家尽量使用a.at(i)来返回数据，因为会检查数据是否存在 插入a.push_back(i); //最简单的插入，直接向vector末尾加入一个数据a.insert(pos,elem); //向pos迭代器指向的对象前插入一个对象，注意是对象前a.insert(pos, n, elem); //向pos迭代器指向的对象前插入n个相同对象a.insert(pos, begin, end); //向pos迭代器指向的对象前插入[begin,end)之间的对象后三个函数都会返回新数据的位置 删除a.clear(); //删除所有对象a.pop_back(); //删除最后一个对象a.erase(pos); //删除pos迭代器对应的对象a.erase(begin, end); //删除[begin,end)之间的对象后两个函数会返回被删除数据的下一个位置 赋值a[1] = 1; //令编号1的对象数据为1a.assign(1, 1); //令a为{1}a.assign(begin,end); //把另一个迭代器[begin,end)中的数据赋值给a要注意第一行和第二行结果是完全不同的，assign函数有点类似复制函数，是对整体的操作 其它常用函数a.size() 返回vector中元素的个数a.empty() 返回vector是否为空，空返回1，不为空返回0a1.swap(a2); //交换a1,a2数据swap(a1, a2); //交换a1,a2数据，同上swap(a1[1], a1[2]); //交换a1的第2个数据和第3个数据 注意，是没有a1[1].swap(a1[2])这种用法的 ...

D48 985. Sum of Even Numbers After Queries题目链接985. Sum of Even Numbers After Queries 题目分析给定一个初始数组A，再给定一个二维操作数组Q。 操作数组里的每一个值是一个数组。其第一个值代表要添加的数。第二个值代表需要操作的数字在数组A中的下标。 也即，需要对A[Q[1]]加A[Q[0]。 结果中第i个元素的结果为，当执行第i步时，数组A中偶数元素的和。 思路这题如果每一步都array_sum的话时间开销会很大，所以采取的方案是先计算初始数组中偶数的和。 再在每一步计算的过程中，判断当前位置是否为偶数。 若为偶数，那么表明在最初已经计算过偶数和了，那么把它从偶数和中减去。 判断相加了第0个元素后，是否为偶数。是则加进偶数和中。 修改原数组A用于后面计算。 把每一步的偶数和记录下来，以便最后返回。 最终代码<?phpclass Solution { /** * @param Integer[] $A * @param Integer[][] $queries * @return Integer[] */ function sumEvenAfterQueries($A, $queries) { $evens = array_filter($A,function($val){ return $val%2==0; }); $total = array_sum($evens); $sums = []; foreach($queries as $query){ if($A[$query[1]]%2 == 0){ $total -= $A[$query[1]]; } if(($A[$query[1]]+$query[0])%2==0){ $total += $query[0] + $A[$query[1]]; } $sums[] = $total; $A[$query[1]] += $query[0]; } return $sums; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D47 868. Binary Gap题目链接868. Binary Gap 题目分析给定一个数字，计算其二进制表示中，出现的两个1最大距离。 思路当然是先转换成二进制了。再进行遍历。 当只有一个1时，返回0。因为只有一个1是没办法比较距离的。 逐个遍历每位。每位都给距离+1。 当出现1时，判断当前距离是否大于记录的最大值。是则覆盖。再把距离置零。 最后判断当只有一个1时，直接返回0。否则返回所记录的最大距离。 最终代码<?phpclass Solution { public $max = 0; function binaryGap($N) { $bin = decbin($N); $chars = str_split($bin); $len = 0; $max = 0; $ones = 0; foreach($chars as $key=>$char){ $len++; if($char == '1'){ $ones++; if($len>$max){ $max = $len; } $len = 0; } } return $ones>1?$max:0; }}若觉得本文章对你有用，欢迎用爱发电资助。

D46 893. Groups of Special-Equivalent Strings题目链接893. Groups of Special-Equivalent Strings 题目分析称一个字符串中，互换第奇数位（或偶数位）形成的新单词与原单词为特殊相等。 给定一个字符串数组A，计算该数组中有多少个独立的特殊相等词。 例如，单词abcd和cbad 为特殊相等词。也与adcb和cdab特殊相等。 思路先把字符串分割成数组，把第偶数个字符和第奇数个字符分别存放。 再对偶数字符数组和奇数字符数组进行排序。 接下来用分隔符拼接这两个数组。使得对任何一个特殊相等的词都有同一个值。把拼接后的字符串作为键存入数组中。（作为值存进去的话需要去重） 计算数组中的元素个数即可。 最终代码<?phpclass Solution { function numSpecialEquivGroups($A) { $words = []; foreach($A as $b){ $odd = $even = []; $chars = str_split($b); foreach($chars as $key=>$char){ if($key%2==0){ $odd[] = $char; } else{ $even[] = $char; } } sort($odd); sort($even); $words[implode('',$odd).'/'.implode('',$even)] = true; } return count($words); } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。

D45 872. Leaf-Similar Trees题目链接872. Leaf-Similar Trees 题目分析如果一个二叉树的左节点的后辈节点之和等于右节点的后辈节点，那么称该树为子节点相似树（直译的）。 思路直接遍历左节点和右节点，遍历完判断左右节点之间是否相等即可。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { function leafSimilar($root1, $root2) { $v1 = []; $this->sumVal($root1, $v1); $v2 = []; $this->sumVal($root2, $v2); return $v1 == $v2; } function sumVal($node, &$val){ if($node->left){ $this->sumVal($node->left,$val); } if($node->right){ $this->sumVal($node->right, $val); } if(!$node->left && !$node->right){ $val[]= $node->val; } return $val; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

1. Two SumGiven an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0, 1].一、两遍循环，暴力破解代码如下 function twoSum($nums, $target) { for($i=0;$i<count($nums); $i++){ for($j=$i+1; $j<count($nums); $j++){ $sum = $nums[$i]+$nums[$j]; if($target == $sum){ return array($i,$j); } } } }时间复杂度 O(n^2 ) ...

D44 590. N-ary Tree Postorder Traversal题目链接590. N-ary Tree Postorder Traversal 题目分析后序遍历，这题也是比较基础的题目了。 思路先遍历子节点，再遍历根节点。 最终代码<?php/*// Definition for a Node.class Node { public $val; public $children; @param Integer $val @param list<Node> $children function __construct($val, $children) { $this->val = $val; $this->children = $children; }}*/class Solution { public $val = []; /** * @param Node $root * @return Integer[] */ function postorder($root) { if(!$root){ return $this->val; } foreach($root->children as $child){ $this->postorder($child); } $this->val[] = $root->val; return $this->val; }}若觉得本文章对你有用，欢迎用爱发电资助。 ...

D42 559. Maximum Depth of N-ary Tree题目链接559. Maximum Depth of N-ary Tree 题目分析此题和上一题思路一样。只是不是二叉树。而是正常的树。 思路略 最终代码<?phpclass Solution { public $max = 0; public $level = 0; function maxDepth($root) { if($root){ $this->level++; if($this->level>=$this->max){ $this->max = $this->level; } } if($root->children){ foreach($root->children as $child){ $this->maxDepth($child); } } if($root){ $this->level--; } return $this->max; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目要求Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.Design an algorithm to serialize and deserialize a binary search tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary search tree can be serialized to a string and this string can be deserialized to the original tree structure.The encoded string should be as compact as possible.Note: Do not use class member/global/static variables to store states. Your serialize and deserialize algorithms should be stateless.将二叉搜索树序列化和反序列化，序列化是指将树用字符串的形式表示，反序列化是指将字符串形式的树还原成原来的样子。 ...

104. Maximum Depth of Binary Tree题目链接104. Maximum Depth of Binary Tree 题目分析返回给定的二叉树有多少层。 思路每下一级，层树+1，并记录到类属性level中。并判断是否大于已知最深层树。 最终代码<?php/** * Definition for a binary tree node. * class TreeNode { * public $val = null; * public $left = null; * public $right = null; * function __construct($value) { $this->val = $value; } * } */class Solution { public $max = 0; public $level = 0; /** * @param TreeNode $root * @return Integer */ function maxDepth($root) { if($root){ $this->level++; } if($this->level>=$this->max){ $this->max = $this->level; } if($root->left){ $this->maxDepth($root->left); } if($root->right){ $this->maxDepth($root->right); } $this->level--; return $this->max; } } 若觉得本文章对你有用，欢迎用[爱发电](https://afdian.net/@skys215)资助。