Leetcode

题目要求Given an n-ary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).For example, given a 3-ary tree: We should return its level order traversal:[ [1], [3,2,4], [5,6]] Note:The depth of the tree is at most 1000.The total number of nodes is at most 5000.对N叉树进行水平遍历，并输出每一行遍历的结果。 思路和代码这个和一般的水平遍历有所区别，因为它会记录每一行的水平遍历结果分别存在结果数组相应行。因此首先可以用水平遍历的通用解法，即队列的方式，进行解决： public List<List<Integer>> levelOrder(Node root) { List<List<Integer>> result = new ArrayList<List<Integer>>(); if(root != null) { LinkedList<Node> queue = new LinkedList<Node>(); queue.offer(root); //下一行的元素数量 int next = 1; List<Integer> levelOrderPerHeight = new ArrayList<Integer>(); while(!queue.isEmpty()) { next--; Node tmp = queue.poll(); levelOrderPerHeight.add(tmp.val); if(tmp.children != null && !tmp.children.isEmpty()) { for(Node child : tmp.children) { queue.offer(child); } } //当前行遍历完成，则更新当前行 if(next == 0) { result.add(levelOrderPerHeight); levelOrderPerHeight = new ArrayList<Integer>(); next = queue.size(); } } } return result; }上面的实现中使用next值来记录下一行的元素的个数。但是其实因为结果是采用List<List>的形式来记录的，也就是第i层的水平遍历的结果会记录于数组下标i-1的位置上。因此无需再用队列来额外存储每一行的水平遍历，可以直接通过递归将遍历结果插入到相应行的结果集中。 ...

写在前面今天的小李的目标是排序算法，果然还是要下手写才会更有体会，也更记得住。 认真做题的分割线第一题215. 数组中的第K个最大元素难度：中等在未排序的数组中找到第k个最大的元素。请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。示例 1: 输入: [3,2,1,5,6,4] 和 k = 2输出: 5示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4输出: 4说明:你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。 我的题解: def findKthLargest(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ num = quicksort(nums,0,len(nums)-1) return num[len(nums)-k] def quicksort(v,start,end): if start < end: i,j = start,end base = v[i] while i < j: while i < j and v[j] >= base: j -= 1 v[i] = v[j] while i < j and v[i] < base: i +=1 v[j] = v[i] v[i] = base quicksort(v,start,i-1) quicksort(v,j+1,end) return v ...

Easy 014 Longest Common PrefixDescription：find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". (注意要检查参数数组是否为空或==null)==Example==Input: ["flower","flow","flight"]Output: "fl"My Solution:for循环找出数组中最短的那个单词，以这个单词为基准，遍历其它单词看是否startswith这个最短的单词，如果有一项不符合，就将最短单词进行缩减，直至所有单词都startswith这个（可能被缩减后的）最短单词，或者最短单词被缩减至空字符串结束

Easy 009 Palindrome NumberDescription:Determine whether an integer is a palindrome. An integer is a palindrome when it reads the same backward as forward.==Example==123: true-123: false10: falseMy Solution:比较简单的一道题目，用取模取余的方法求翻转后的整数和原来的整数进行比较就行（不用完全翻转，翻转一半就可）（这已经是最快的方法了） public boolean isPalindrome(int x) { if (x<0 || (x!=0 && x%10==0)) return false; int rev = 0; while (x>rev){ rev = rev*10 + x%10; x = x/10; } return (x==rev || x==rev/10); }

Easy 013 Roman to IntegerDescription:将罗马字母的字符串转换为代表的整数Roman numerals are usually written largest to smallest from left to right. However, there are six instances where subtraction is used: I can be placed before V (5) and X (10) to make 4 and 9. X can be placed before L (50) and C (100) to make 40 and 90. C can be placed before D (500) and M (1000) to make 400 and 900.Symbol ValueI 1V 5X 10L 50C 100D 500M 1000My Solution:这题不难，用一个HashMap存罗马数字和具体数字的对应关系，然后遍历前后两两比较，该加加，该减减 ...

412. Fizz Buzz题目链接412. Fizz Buzz 题目分析这个题目也很简单。 从1逐个输出到给定数组，但逢3输出Fizz，逢5输出Buzz，逢15输出FizzBuzz。 思路没什么好说的了。用%整除判断能否被3、5分别整除或同时整除。然后替换要输出的内容即可。 最终代码<?phpclass Solution { function fizzBuzz($n) { $fb = []; $a = range(1,$n); foreach($a as $val){ if($val%3==0&&$val%5==0){ $fb[] = 'FizzBuzz'; continue; } if($val%3==0){ $fb[] = 'Fizz'; continue; } if($val%5==0){ $fb[] = 'Buzz'; continue; } $fb[] = (string)$val; }; return $fb; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目要求A sequence of number is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.For example, these are arithmetic sequence:1, 3, 5, 7, 97, 7, 7, 73, -1, -5, -9The following sequence is not arithmetic.1, 1, 2, 5, 7A zero-indexed array A consisting of N numbers is given. A slice of that array is any pair of integers (P, Q) such that 0 <= P < Q < N.A slice (P, Q) of array A is called arithmetic if the sequence:A[P], A[p + 1], ..., A[Q - 1], A[Q] is arithmetic. In particular, this means that P + 1 < Q.The function should return the number of arithmetic slices in the array A.Example:A = [1, 2, 3, 4]return: 3, for 3 arithmetic slices in A: [1, 2, 3], [2, 3, 4] and [1, 2, 3, 4] itself.将包含大于等于三个元素且任意相邻两个元素之间的差相等的数组成为等差数列。现在输入一个随机数组，问该数组中一共可以找出多少组等差数列。 ...

Easy 007 Reverse IntegerDescription：Given a 32-bit signed integer, reverse digits of an integer.Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−2^31,  2^31 − 1]. For the purpose of this problem, assume that your function returns 0 when the reversed integer overflows. ==Example==123→321 -123→-321 120→21My Solution：第一时间想到这是经典的取模取余运算，但是写的过程中遇到了很多问题QAQ（这么简单一题 基础做法：取一个整数的最后一位数字只要把这个整数 % 10就可以，要取除最后一位数字之外的其它数字只要 / 10int是没有长度函数的，需要转化成String才能使用长度函数用这个方法最大的难点在于用int类型时处理溢出问题，原本没有溢出的数字在进行翻转时很有可能溢出，最合适的方法是在处理过程中进行预判 假设翻转过程的中间值用res来保存，每次取下来的那个数字用pop来保存，overflow = 2147483646，underFlow = -2147483647已知当res * 10 + pop 会引起溢出时，res必定是 ≥ （max / 10）或 ≤ （min / 10）的，其中相等时对pop由要求根据上述条件在翻转时进行溢出预判Fast Solution：题目中要求的溢出条件其实是针对int型数据的，这题用Java来写的话其实可以用long类型

Easy 001 Two SumDescription:Given 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].My Solution:Fast Solution One:Fast Solution Two:

575. Distribute Candies题目链接575. Distribute Candies 题目分析给定一个偶数长度的数组，不同数字代表不同类型的糖果。 这一把糖果需要均分给两个人。计算最多能拿到多少种糖果。 思路最极端的情况，每一个都是不同的糖果。那么可以获得(数组长度除以2)种糖果。 若只有一种不同的糖果，那么最多能获得2种。此时，数组内不同元素的个数。 因此，只要从数组长度的一半和不同元素个数之间取最小值就好了。 最终代码<?phpclass Solution { function distributeCandies($candies) { return min(count(array_unique($candies)),count($candies)/2); }}若觉得本文章对你有用，欢迎用爱发电资助。

写在前面今天没有叨逼叨...但是又一次错过了竞赛...爱睡觉的小李...下周要上班，下下周一定要参加了（握拳 认真做题的分割线第一题1029. 两地调度公司计划面试2N人。第i人飞往 A 市的费用为 costsi，飞往 B 市的费用为 costsi。返回将每个人都飞到某座城市的最低费用，要求每个城市都有N人抵达。 示例： 输入：[[10,20],[30,200],[400,50],[30,20]]输出：110解释：第一个人去 A 市，费用为 10。第二个人去 A 市，费用为 30。第三个人去 B 市，费用为 50。第四个人去 B 市，费用为 20。最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。 提示： 1 <= costs.length <= 100costs.length 为偶数1 <= costsi, costsi <= 1000我的题解： class Solution(object): def twoCitySchedCost(self, costs): """ :type costs: List[List[int]] :rtype: int """ costs = sorted(costs,key = lambda x:abs(x[0] - x[1])) costs = costs[::-1] a,b = 0,0 n = len(costs) //2 res = 0 for i in costs: if a < n and b < n: if i[0] < i[1]: a += 1 res += i[0] else: b += 1 res += i[1] elif a<n: a += 1 res += i[0] else: b += 1 res += i[1] return res我的思路：参考了小江同学的思路（她的blog还在小黑屋...后续补上链接）和这位同学的思路。 ...

题目给定一个完美二叉树，其所有叶子节点都在同一层，每个父节点都有两个子节点。二叉树定义如下： struct Node { int val; Node *left; Node *right; Node *next;}填充它的每个 next 指针，让这个指针指向其下一个右侧节点。如果找不到下一个右侧节点，则将 next 指针设置为 NULL。 初始状态下，所有 next 指针都被设置为 NULL。 示例： 输入：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":null,"right":null,"val":4},"next":null,"right":{"$id":"4","left":null,"next":null,"right":null,"val":5},"val":2},"next":null,"right":{"$id":"5","left":{"$id":"6","left":null,"next":null,"right":null,"val":6},"next":null,"right":{"$id":"7","left":null,"next":null,"right":null,"val":7},"val":3},"val":1}输出：{"$id":"1","left":{"$id":"2","left":{"$id":"3","left":null,"next":{"$id":"4","left":null,"next":{"$id":"5","left":null,"next":{"$id":"6","left":null,"next":null,"right":null,"val":7},"right":null,"val":6},"right":null,"val":5},"right":null,"val":4},"next":{"$id":"7","left":{"$ref":"5"},"next":null,"right":{"$ref":"6"},"val":3},"right":{"$ref":"4"},"val":2},"next":null,"right":{"$ref":"7"},"val":1}解释：给定二叉树如图 A 所示，你的函数应该填充它的每个 next 指针，以指向其下一个右侧节点，如图 B 所示。题解方法一: 层序遍历使用层序遍历，遍历的时候把同层的节点连接起来； class Solution { public Node connect(Node root) { if (root == null) return null; Queue<Node> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); Node current = null; while (size > 0) { Node node = queue.poll(); if (node.right != null) queue.add(node.right); if (node.left != null) queue.add(node.left); node.next = current; current = node; size--; } } return root; }}方法二：递归递归的时候我们通常就分解为递归子问题和递归结束条件。 ...

Determine whether an integer is a palindrome. An integer is apalindrome when it reads the same backward as forward.Example 1: Input: 121 Output: true Example 2: Input: -121 Output: false Explanation: From left to right, it reads-121. From right to left, it becomes 121-. Therefore it is not a palindrome. Example 3: Input: 10 Output: false Explanation: Reads 01 from right to left.Therefore it is not a palindrome. ...

Implement atoi which converts a string to an integer. The function first discards as many whitespace characters as necessaryuntil the first non-whitespace character is found. Then, starting fromthis character, takes an optional initial plus or minus sign followedby as many numerical digits as possible, and interprets them as anumerical value. The string can contain additional characters after those that form theintegral number, which are ignored and have no effect on the behaviorof this function. ...

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and notthe value in the nodes.You should try to do it in place. The program should run in O(1) spacecomplexity and O(nodes) time complexity.https://leetcode.com/problems…# Definition for singly-linked list.# class ListNode:# def init(self, x):# self.val = x# self.next = Noneclass Solution: def oddEvenList(self, head: ListNode) -> ListNode: # If zero, one or two elements, then solved if head == None or head.next == None or head.next.next == None: return head # Two pointers p = head n = head.next t = None while n.next: # If there is even element if n.next.next: # Keep it for now for both n and p t = n.next.next m = p.next p.next = n.next p = p.next # Recover link for p and n p.next = m n.next = t n = n.next else: # Save and insert odd t = p.next p.next = n.next p = p.next p.next = t n.next = None return head ...

Given a sorted linked list, delete all nodes that have duplicatenumbers, leaving only distinct numbers from the original list.https://leetcode.com/problems…# Definition for singly-linked list.# class ListNode:# def init(self, x):# self.val = x# self.next = Noneclass Solution: def deleteDuplicates(self, head: ListNode) -> ListNode: # Two nodes: one to keep head, one to keep tail. ahead = phead = ListNode(’null’) # Two pointers: one to move ahead, one to monitor duplicates. p = None c = head # When move to end, terminate. while c: # At the beginning, simple move one step forward. if p == None: p = c # If p and c have different values, need to determine why. elif p.val != c.val: # If p and c are neighbors, p must be unique value. if p.next == c: phead.next = p phead = phead.next phead.next = None # p gets one step forward. p = c # If p and c are not neighbors, ignore nodes with p.val. else: p = c # c moves one step anyway. c = c.next # If p is not None (input not empty) and has next, collect last element. if p != None and p.next == None: phead.next = p return ahead.next ...

题目要求Given a non-empty string containing an out-of-order English representation of digits 0-9, output the digits in ascending order.Note:Input contains only lowercase English letters.Input is guaranteed to be valid and can be transformed to its original digits. That means invalid inputs such as “abc” or “zerone” are not permitted.Input length is less than 50,000.Example 1:Input: “owoztneoer"Output: “012"Example 2:Input: “fviefuro"Output: “45"一个非空的英文字符串，其中包含着乱序的阿拉伯数字的英文单词。如012对应的英文表达为zeroonetwo并继续乱序成owoztneoer。要求输入乱序的英文表达式，找出其中包含的所有0-9的数字，并按照从小到大输出。思路和代码首先将数字和英文表示列出来：0 zero1 one2 two3 three4 four5 five6 six7 seven8 eight9 nine粗略一看，我们知道有许多字母只在一个英文数字中出现，比如z只出现在zero中。因此对于这种字母，它一旦出现，就意味着该数字一定出现了。因此一轮过滤后可以得出只出现一次的字母如下：0 zero -> z1 one2 two -> w3 three4 four -> u5 five6 six -> x7 seven8 eight9 nine再对剩下的数字字母过滤出只出现一次的字母：1 one 3 three -> r5 five -> f7 seven -> s8 eight -> g9 nine最后对one和nine分别用o和i进行区分即可。因此可以得出如下代码： public String originalDigits(String s) { int[] letterCount = new int[26]; for(char c : s.toCharArray()) { letterCount[c-‘a’]++; } int[] result = new int[10]; //zero if((result[2] = letterCount[‘z’-‘a’]) != 0) { result[0] = letterCount[‘z’ - ‘a’]; letterCount[‘z’-‘a’] = 0; letterCount[’e’-‘a’] -= result[0]; letterCount[‘r’-‘a’] -= result[0]; letterCount[‘o’-‘a’] -= result[0]; } //two if((result[2] = letterCount[‘w’-‘a’]) != 0) { letterCount[’t’-‘a’] -= result[2]; letterCount[‘w’-‘a’] = 0; letterCount[‘o’-‘a’] -= result[2]; } //four if((result[4] = letterCount[‘u’-‘a’]) != 0) { letterCount[‘f’-‘a’] -= result[4]; letterCount[‘o’-‘a’] -= result[4]; letterCount[‘u’-‘a’] -= result[4]; letterCount[‘r’-‘a’] -= result[4]; } //five if((result[5] = letterCount[‘f’-‘a’]) != 0) { letterCount[‘f’-‘a’] -= result[5]; letterCount[‘i’-‘a’] -= result[5]; letterCount[‘v’-‘a’] -= result[5]; letterCount[’e’-‘a’] -= result[5]; } //six if((result[6] = letterCount[‘x’-‘a’]) != 0) { letterCount[’s’-‘a’] -= result[6]; letterCount[‘i’-‘a’] -= result[6]; letterCount[‘x’-‘a’] -= result[6]; } //seven if((result[7] = letterCount[’s’-‘a’]) != 0) { letterCount[’s’-‘a’] -= result[7]; letterCount[’e’-‘a’] -= result[7] * 2; letterCount[‘v’-‘a’] -= result[7]; letterCount[’n’-‘a’] -= result[7]; } //one if((result[1] = letterCount[‘o’-‘a’]) != 0) { letterCount[‘o’-‘a’] -= result[1]; letterCount[’n’-‘a’] -= result[1]; letterCount[’e’-‘a’] -= result[1]; } //eight if((result[8] = letterCount[‘g’-‘a’]) != 0) { letterCount[’e’-‘a’] -= result[8]; letterCount[‘i’-‘a’] -= result[8]; letterCount[‘g’-‘a’] -= result[8]; letterCount[‘h’-‘a’] -= result[8]; letterCount[’t’-‘a’] -= result[8]; } //nine if((result[9] = letterCount[‘i’-‘a’]) != 0) { letterCount[’n’-‘a’] -= result[9] * 2; letterCount[‘i’-‘a’] -= result[9]; letterCount[’e’-‘a’] -= result[9]; } result[3] = letterCount[’t’-‘a’]; StringBuilder sb = new StringBuilder(); for(int i = 0 ; i<result.length ; i++) { for(int j = 0 ; j<result[i] ; j++) { sb.append(i); } } return sb.toString(); }上面的代码未免写的太繁琐了，对其进一步优化可以得到如下代码： public String originalDigits2(String s) { int[] alphabets = new int[26]; for (char ch : s.toCharArray()) { alphabets[ch - ‘a’] += 1; } int[] digits = new int[10]; digits[0] = alphabets[‘z’ - ‘a’]; digits[2] = alphabets[‘w’ - ‘a’]; digits[6] = alphabets[‘x’ - ‘a’]; digits[8] = alphabets[‘g’ - ‘a’]; digits[7] = alphabets[’s’ - ‘a’] - digits[6]; digits[5] = alphabets[‘v’ - ‘a’] - digits[7]; digits[3] = alphabets[‘h’ - ‘a’] - digits[8]; digits[4] = alphabets[‘f’ - ‘a’] - digits[5]; digits[9] = alphabets[‘i’ - ‘a’] - digits[6] - digits[8] - digits[5]; digits[1] = alphabets[‘o’ - ‘a’] - digits[0] - digits[2] - digits[4]; StringBuilder sb = new StringBuilder(); for (int d = 0; d < 10; d++) { for (int count = 0; count < digits[d]; count++) sb.append(d); } return sb.toString(); } ...

摘要： 面试刷题指南。原文：如何在 VS Code 中调试 LeetCode 代码作者：neo-csFundebug经授权转载，版权归原作者所有。近期收到不少小伙伴的求助，希望知道如何在 VS Code 中调试 LeetCode 代码。通常来说，为了调试本地代码，我们需要安装相关的语言支持插件。本文中，我们就以调试 LeetCode Java 代码为例，给大家介绍本地调试 LeetCode 代码的常用套路。想要了解如何在 VS Code 中刷题的小伙伴，可以移步：LeetCode for VS Code: 春招 Offer 收割利器。准备工作首先确保系统内安装了JDK，相关教程有很多，此处就不赘述了。之后我们需要确保在 VS Code 中安装了下列插件：1. LeetCode用来生成题目，提交答案。2. Language Support for Java(TM) by Red Hat提供智能提示等语言相关的功能。3. Debugger for Java，Java 调试器。安装完成之后，VS Code 的插件管理栏中，就可以看到这三个插件了：如果在打开 Java 文件后，VS Code 提示找不到 JDK，请检查一下相关配置是否正确。编写调试代码：我们就拿第 20 题：有效的括号作为例子。在作答过程中，可能会看到编辑器里出现一些红线。不要担心，这表明 Language Support for Java 插件正在起作用。通常这意味着你的代码存在语法错误，下面的例子展示的错误原因是用到了依赖包但没有 import 到当前文件当中。我们可以利用 Quick Fix 功能进行修复：将依赖包导入时为了确保文件能够被正确编译。LeetCode 在检查答案的时候，并不会要求文件中存在相应的 import 语句，因此存不存在 import 语句不会影响最后的检查结果。写完答案之后，我们还需要在同一个文件中，增加一个 Main 函数作为调试程序的执行入口，整个文件的代码结构如下：class Main { public static void main(String[] args) { // Create a new Solution instance Solution solution = new Solution(); // Create a test case String testCase = “()[]{}”; // Get the answer boolean answer = solution.isValid(testCase); // Print the answer System.out.println(answer); }}class Solution { … public boolean isValid(String s) { … return answer; }}此时我们会看到在 Main 函数的上方出现了两个 CodeLens 按钮：点击 Run 按钮会运行 Main 函数，我们可以在下方弹出的 Debug Console 中看到程序的输出结果（因为我们在最后一行代码用了 println 输出答案）。如果想要调试的话，可以在相应的行号位置设置好断点，点击 Debug 按钮，就可以进入调试模式查看代码运行情况了。这里有一点需要注意的是，由于 LeetCode 生成的答题模板的类名均为 Solution，因此会造成同一个目录下存在多个同名类的情况出现，可能导致代码无法正确执行，因此如果希望调试 LeetCode Java 代码，但当前目录又存在有多个 LeetCode Java 文件时，需要保证类名的唯一性，我们可以把被调试的 Solution 类改一个名字（但要记住提交时把名字改回来），或者干脆拷贝到另一个干净的目录下调试即可。以上就是如何在 VS Code 中调试 LeetCode Java 代码的步骤，对于其他语言来说，基本也是大同小异的步骤，如果你有更好的建议或者有自己喜欢的调试技巧，欢迎在评论区留言！ ...

Baseball Game题目链接682. Baseball Game题目分析给定一个字符串数组，每一个字符串有以下形式：数字。直接计算得分。+。代表本轮分数为上一轮和上上一轮分数之和。D。代表本轮分数为上一轮分数的两倍。C。代表上一轮分数无效。返回最终得分。思路这题没什么好说的了。用switch…case区分各种情况，进行相应处理即可。最终代码<?phpclass Solution { function calPoints($ops) { $points = []; foreach($ops as $op){ $max = count($points); switch($op){ case ‘+’: $p = 0; if(isset($points[$max-1])){ $p += $points[$max-1]; } if(isset($points[$max-2])){ $p += $points[$max-2]; } $points[] = $p; break; case ‘D’: $points[] = isset($points[$max-1])?$points[$max-1]*2:0; break; case ‘C’: array_pop($points); break; default: $points[] = (int)$op; break; } } return array_sum($points); }}若觉得本文章对你有用，欢迎用爱发电资助。

Given a 32-bit signed integer, reverse digits of an integer.Example 1:Input: 123 Output: 321 Example 2:Input: -123 Output: -321 Example 3:Input: 120 Output: 21 Note: Assume we are dealing with an environmentwhich could only store integers within the 32-bit signed integerrange: [−231, 231 − 1]. For the purpose of this problem, assume thatyour function returns 0 when the reversed integer overflows.注意越界问题public int reverse(int x) { long t=x; if(t<0) t=-t; long nt=Long.parseLong(new StringBuilder(t+"").reverse().toString()); if(x<0) nt=-nt; if(nt>Integer.MAX_VALUE || nt<Integer.MIN_VALUE) return 0; return (int)nt;} ...

Subdomain Visit Count题目链接811. Subdomain Visit Count题目分析题目给定一个字符串数组，每个字符串分两部分，以空格分割。 第一部分为访问次数，第二部分为域名。 要求按同样的格式，分别返回顶级域名、二级域名、三级域名…的访问次数。例如，字符串"9001 discuss.leetcode.com"。discuss.leetcode.com算一个域名；leetcode.com算另一个；com也是一个。因此要返回[“9001 discuss.leetcode.com”, “9001 leetcode.com”, “9001 com”]思路先把域名用explode函数拆分，再按层级把访问次数加到每个层级去。最终代码<?phpclass Solution { function subdomainVisits($cpdomains) { $visits = []; foreach($cpdomains as $cpdomain){ $item = explode(’ ‘,$cpdomain); $domain = explode(’.’,$item[1]); $max = count($domain); for($i=$max-1; $i>=0;$i–){ $d = implode(’.’, array_slice($domain, $i)); if(!isset($visits[$d])){ $visits[$d] = 0; } $visits[$d] += $item[0]; } } $v = []; foreach($visits as $domain => $visit){ $v[] = $visit.’ ‘.$domain; } return $v; }}若觉得本文章对你有用，欢迎用爱发电资助。

The string “PAYPALISHIRING” is written in a zigzag pattern on a givennumber of rows like this: (you may want to display this pattern in afixed font for better legibility)P A H N A P L S I I G Y I R And then read line by line:“PAHNAPLSIIGYIR"Write the code that will take a string and make this conversion givena number of rows:string convert(string s, int numRows); Example 1:Input: s = “PAYPALISHIRING”, numRows = 3 Output: “PAHNAPLSIIGYIR"Example 2:Input: s = “PAYPALISHIRING”, numRows = 4 Output: “PINALSIGYAHRPI"Explanation:P I N A L S I G Y A H R P I一般的问题属于给结果，需要找到那种状态，这种表述不太准确且模糊。而这类问题属于给出给出所有条件，让你输出结果，难点在于找到规律，经验是一般刨除编程大脑告诉你怎么弄就怎么弄。这道题如果是现实中的话就是把数字按规律写出来。问题就可以转化为把字符放到合适的排里。public String convert(String s, int numRows) { if(numRows<=1) return s; ArrayList<Character>[] rows=new ArrayList[numRows]; for(int i=0;i<numRows;i++) rows[i]=new ArrayList(); int index=0; char[] array=s.toCharArray(); for(char c:array){ rows[Math.abs(index)].add(c); index++; if(index==numRows) index=-index+2; } StringBuilder builder=new StringBuilder(); for(int i=0;i<numRows;i++) for(char c:rows[i]) builder.append(c); return builder.toString();} ...

Middle of the Linked List题目链接876. Middle of the Linked List题目分析返回一个链表中最中间的元素。思路先全部塞入数组，再根据长度/2得到中间元素的下标，再返回。最终代码<?php/** * Definition for a singly-linked list. * class ListNode { * public $val = 0; * public $next = null; * function __construct($val) { $this->val = $val; } * } */class Solution { function middleNode($head) { $items = [$head]; while($head){ $items[] = $head; $head = $head->next; }; return $items[ceil(count($items)/2)]; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目要求Given an integer array nums, return the number of range sums that lie in [lower, upper] inclusive.Range sum S(i, j) is defined as the sum of the elements in nums between indices i and j (i ≤ j), inclusive.Note:A naive algorithm of O(n2) is trivial. You MUST do better than that.Example:Input: nums = [-2,5,-1], lower = -2, upper = 2,Output: 3 Explanation: The three ranges are : [0,0], [2,2], [0,2] and their respective sums are: -2, -1, 2.这道题目是指，现有一个整数数组，并输入上界值upper和下界值lower，问数组中一共有多少组连续的子数组，其子数组中数字的和在上界和下界之内。思路一：暴力循环我们可以首先遍历一遍数组，计算子数组下标[0,i）的所有元素的和。根据该结果可以计算自数组[i,j)中所有元素的和。接着计算所有子数组中元素的和，并判断是否位于数值区间内。代码如下： public int countRangeSum(int[] nums, int lower, int upper) { long[] sums = new long[nums.length+1]; for(int i = 0 ; i<nums.length ; i++) { sums[i+1] = sums[i] + nums[i]; } int count = 0; for(int i = 0 ; i<nums.length ; i++) { for(int j = i+1 ; j<=nums.length ; j++) { if(sums[j] - sums[i] >= lower && sums[j] - sums[i] <= upper) { count++; } } } return count; }思路二：分治法分治法的核心思路在于，将计算整个数组的符合条件的子数组的问题切分为子问题，将数组一分为二，并分别计算左子数组的符合条件的子数组个数，右子数组中符合条件的子数组个数和横穿左右数组的符合条件的子数组个数。计算横穿左右的子数组个数的方法很有趣，这采用了归并排序的思想，即无论左子数组中的元素或是右子数组中的元素如何变动，横穿左右的子数组个数都不会受影响。因此，在对左右子数组进行排序后，以左子数组中的每一位作为开头，在右子数组中找到满足upper和lower区间的第一个值，和超过upper区间的第一个值。则二者的差即为横穿左右的满足条件的子数组个数。 public int countRangeSum3(int[] nums, int lower, int upper) { long[] sums = new long[nums.length + 1]; for(int i = 0 ; i<nums.length ; i++) { sums[i+1] = sums[i] + nums[i]; } long[] sortedSums = new long[nums.length + 1]; return mergeCountRangeSum3(sums, sortedSums, 0, nums.length+1, lower, upper); } public int mergeCountRangeSum3(long[] sums,long[] sortedSums, int start, int end, int lower, int upper) { if(end - start <= 1) return 0; int mid = (start + end) / 2; int count = mergeCountRangeSum3(sums, sortedSums, start, mid, lower, upper) + mergeCountRangeSum3(sums, sortedSums, mid, end, lower, upper); int firstLargerThanUpper = mid, firstLargerThanLower = mid, indexOfRightHalf = mid; for(int i = start, sortedSumsIndex = start; i < mid ; i++, sortedSumsIndex++) { while(firstLargerThanUpper < end && sums[firstLargerThanUpper] - sums[i] <= upper) firstLargerThanUpper++; while(firstLargerThanLower < end && sums[firstLargerThanLower] - sums[i] <lower) firstLargerThanLower++; while(indexOfRightHalf < end && sums[indexOfRightHalf] < sums[i]) sortedSums[sortedSumsIndex++] = sums[indexOfRightHalf++]; sortedSums[sortedSumsIndex] = sums[i]; count += firstLargerThanUpper - firstLargerThanLower; } System.arraycopy(sortedSums, start, sums, start, indexOfRightHalf - start); return count; } ...

Given a string s, find the longest palindromic substring in s. You mayassume that the maximum length of s is 1000.Example 1:Input: “babad” Output: “bab” Note: “aba” is also a valid answer.Example 2:Input: “cbbd” Output: “bb"1.第一思路是dp问题，不过对于一阶dp找不到对应关系，可以通过二阶dp解决i<=j的情况下dpi是不是回文数有几种情况i==j ||s[i]==s[j] && (dpi+1 || i==j+1)public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=1; int right=1; int[][] dp=new int[l+1][l+1]; for(int i=l;i>=1;i–){ for(int j=i;j<=l;j++){ if(i==j || (s.charAt(i-1)==s.charAt(j-1) && (dp[i+1][j-1]==1 || j==i+1))){ dp[i][j]=1; if(right-left<j-i){ left=i; right=j; } } } } return s.substring(left-1,right);}2.第二组思路可以对每个字符做匹配public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=0; int right=0; char[] array=s.toCharArray(); for(int i=0;i<array.length;i++){ int j=0; do{ j++; }while(i-j>=0 && i+j<l && array[i-j]==array[i+j]); j–; if(2j+1>=right-left+1){ left=i-j; right=i+j; } } for(int i=0;i<array.length-1;i++){ if(array[i]!=array[i+1]) continue; int j=0; do{ j++; }while(i-j>=0 && i+j+1<l && array[i-j]==array[i+j+1]); j–; if(2j+2>right-left+1){ left=i-j; right=i+j+1; } } return s.substring(left,right+1);}3.然后是一个正常人想不到的思路，就是马拉车算法，他其实和2算法很相似，他解决了两个问题，一个是将两种回文情况通过改变初始数据变为一种，而是在求某个字符的情况下拿到之前已知的结果。public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=0; int right=0; StringBuilder builder=new StringBuilder(”#"); char[] array=s.toCharArray(); for(char c:array){ builder.append(c); builder.append(’#’); } for(int i=0;i<array.length;i++){ int j=0; do{ j++; }while(i-j>=0 && i+j<l && array[i-j]==array[i+j]); j–; if(2j+1>=right-left+1){ left=i-j; right=i+j; } } left=(left+1)/2; right=(right-1)/2; return s.substring(left,right+1);}-mx 123 -i 321 id 123 i 321 mxid代表能到达最右侧回文串的中心点mx代表半径在-mx到mx内，串一定是对称的所以i点最小的半径为Math.min(mx-i,r[-i])public String longestPalindrome(String s) { int l=s.length(); if(l<=0) return s; int left=0; int right=0; StringBuilder builder=new StringBuilder("#"); char[] array=s.toCharArray(); for(char c:array){ builder.append(c); builder.append(’#’); } array=builder.toString().toCharArray(); int[] r=new int[array.length]; int mx=0; int id=0; for(int i=0;i<array.length;i++){ int j=0; if(mx>i){ j=Math.min(mx-i,r[2id-i]); } do{ j++; }while(i-j>=0 && i+j<array.length && array[i-j]==array[i+j]); j–; r[i]=j; if(i+j>mx) { mx=i+j; id=i; } if(2*j+1>=right-left+1){ left=i-j; right=i+j; } } left=(left+1)/2; right=(right-1)/2; return s.substring(left,right+1); } ...

There are two sorted arrays nums1 and nums2 of size m and nrespectively.Find the median of the two sorted arrays. The overall run timecomplexity 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.0 Example 2:nums1 = [1, 2] nums2 = [3, 4]The median is (2 + 3)/2 = 2.5难点主要在于复杂度的要求，logn的复杂度我们就会想到二分查找，二分查找本质上就是对一个有序值的寻找过程，会比遍历的寻找合适值寻找复杂度更低，两个数组都做二分查找的值并没什么意义，我们需要想到一个隐藏条件oooxxxooooxxxx寻找中位数其实就是剔除比较小的数，而这些小的数都在整个数组的左边，且个数是固定的。public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1=nums1.length; int l2=nums2.length; if(l1>l2) return findMedianSortedArrays(nums2,nums1); int left=0; int right=l1; int need=(l1+l2-1)/2; while(left<=right){ int count1=(left+right)/2; int count2=need-count1; if(count1<l1 && count2>=1 && nums1[count1]<nums2[count2-1]) left=count1+1; else if(count1>=1 && nums2[count2]<nums1[count1-1]) right=count1-1; else{ if((l1+l2)%2==1){ int[] array=new int[]{count1>=l1?Integer.MAX_VALUE:nums1[count1],count2>=l2?Integer.MAX_VALUE:nums2[count2]}; Arrays.sort(array); return (double) (array[0]); }else{ int[] array=new int[]{count1>=l1?Integer.MAX_VALUE:nums1[count1],count2>=l2?Integer.MAX_VALUE:nums2[count2],count1+1>=l1?Integer.MAX_VALUE:nums1[count1+1],count2+1>=l2?Integer.MAX_VALUE:nums2[count2+1]}; Arrays.sort(array); return (double) (array[0]+array[1])/2.0; } } } return 0.0;} ...

题目要求A frog is crossing a river. The river is divided into x units and at each unit there may or may not exist a stone. The frog can jump on a stone, but it must not jump into the water.Given a list of stones’ positions (in units) in sorted ascending order, determine if the frog is able to cross the river by landing on the last stone. Initially, the frog is on the first stone and assume the first jump must be 1 unit.If the frog’s last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. Note that the frog can only jump in the forward direction.Note:The number of stones is ≥ 2 and is < 1,100.Each stone’s position will be a non-negative integer < 231.The first stone’s position is always 0.Example 1:[0,1,3,5,6,8,12,17]There are a total of 8 stones.The first stone at the 0th unit, second stone at the 1st unit,third stone at the 3rd unit, and so on…The last stone at the 17th unit.Return true. The frog can jump to the last stone by jumping 1 unit to the 2nd stone, then 2 units to the 3rd stone, then 2 units to the 4th stone, then 3 units to the 6th stone, 4 units to the 7th stone, and 5 units to the 8th stone.Example 2:[0,1,2,3,4,8,9,11]Return false. There is no way to jump to the last stone as the gap between the 5th and 6th stone is too large.假设有一只青蛙需要过河，河中会有一些石子，青蛙必须踩在石头上才算成功。石头的位置用整数数组来表示。青蛙的行走规则为：假设上一次青蛙跳了k格，则当前青蛙只能跳k-1或k或k+1格，且青蛙只能向前跳，不能向后跳。广度优先遍历可以从起点开始，对从该点出发的所有可能步数进行遍历，并更新从该点可达的点的所有的可行步数。利用Map<Integer, Set<Integer>>数据结构来记录该结果，其中map的key为stone的unit数，它的value对应的是从该key出发的所有的上一步的步长。该遍历思路类似于广度优先遍历，即将该点出发遍历所有的可达点。代码如下： public boolean canCross(int[] stones) { if(stones.length < 2) return true; if(stones.length == 2 && stones[1] == 1) return true; if(stones.length >= 2 && stones[1] != 1) return false; Map<Integer, Set<Integer>> stoneJump = new HashMap<>(); for(int i = 1 ; i<stones.length ; i++) { stoneJump.put(stones[i], new HashSet<>()); } stoneJump.get(1).add(1); int finalStone = stones[stones.length-1]; boolean hasNext = false; for(int i = 1 ; i<stones.length; i++) { for(int step : stoneJump.get(stones[i])) { int next = stones[i] + step - 1; for(int addOn = -1 ; addOn <= 1 ; addOn++) { if(step + addOn != 0) { if(next == finalStone) { return true; } if(stoneJump.containsKey(next)) { stoneJump.get(next).add(step + addOn); hasNext = true; } } next++; } } if(!hasNext) break; hasNext = false; } return false; }深度优先遍历和上一种思路的区别在于，这种方法会尽可能往远处遍历。即只要该点可以到达下一点，则会立刻尝试从一点到达终点。代码如下： public boolean canCross(int[] stones) { for(int i = 1 ; i<stones.length ; i++) { if(stones[i] - stones[i-1] > i) return false; } return canCross2(stones, 1, 1); } public boolean canCross2(int[] stones, int idx, int lastStep) { if(idx == stones.length-1) return true; if(idx < 0 || lastStep <= 0) return false; for(int jump = lastStep + 1 ; jump >= lastStep -1 ; jump–) { if(canCross2(stones, Arrays.binarySearch(stones, stones[idx] + jump), jump)){ return true; } } return false; } ...

写在前面最近忙着调教新装备，没有及时的写题解，但是没有在偷懒没刷题喔来认真整理下最近做的题目之前考虑按tag来刷题，后来收到了推荐的leetcode题解，就根据上面的说明陆续刷题啦tag主要做了：数组、双指针找时间要开始部署gitbook了，然后将题解部署到电子书上认真做题的分割线第一题387. 字符串中的第一个唯一字符难度：简单给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回-1。案例:s = “leetcode"返回 0.s = “loveleetcode”,返回 2.我的题解：class Solution(object): def firstUniqChar(self, s): "”" :type s: str :rtype: int """ mapa = dict() for i in s: if i not in mapa: mapa[i] = 1 else: mapa[i] += 1 for j in range(len(s)): a = s[j] if a in mapa and mapa[a] == 1: return j return -1我的思路：第二题283. 移动零难度：简单给定一个数组 nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。案例:输入: [0,1,0,3,12]输出: [1,3,12,0,0]返回 2.我的题解：class Solution(object): def moveZeroes(self, nums): """ :type nums: List[int] :rtype: None Do not return anything, modify nums in-place instead. """ l = len(nums) j = 0 for i in range(l): if nums[i] !=0: nums[j] = nums[i] j +=1 nums[j:l] = [0 for i in range(l-j)]我的思路：第三题268. 缺失数字难度：简单给定一个包含0, 1, 2, …, n中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。案例:输入: [3,0,1]输出: 2输入: [9,6,4,2,3,5,7,0,1]输出: 8我的题解：class Solution(object): def missingNumber(self, nums): """ :type nums: List[int] :rtype: int """ sum = 0 l =len(nums) sum_a = (1+l)*l/2 for i in nums: sum += i return sum_a - sum```第四题229. 求众数 II难度：简单给定一个大小为 n 的数组，找出其中所有出现超过⌊ n/3 ⌋次的元素。说明: 要求算法的时间复杂度为O(n)，空间复杂度为O(1)。案例:输入: [3,2,3]输出: [3]输入: [1,1,1,3,3,2,2,2]输出: [1,2]我的题解：class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: List[int] """ a = dict() b = list() n = len(nums) / 3 for i in nums: if i not in a: a[i] = 1 else: a[i] += 1 for j in a: if a[j] > n: b.append(j) return b我的思路：第五题101. 对称二叉树难度：简单给定一个二叉树，检查它是否是镜像对称的。例如，二叉树[1,2,2,3,4,4,3]是对称的。但是下面这个[1,2,2,null,3,null,3]则不是镜像对称的:我的题解：# Definition for a binary tree node.# class TreeNode(object):# def init(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def isSymmetric(self, root): """ :type root: TreeNode :rtype: bool """ if not root: return True return self.isSame(root.left,root.right) def isSame(self,leftNode,rightNode): if leftNode == None: return rightNode == None if rightNode == None: return leftNode == None if rightNode.val == leftNode.val: return self.isSame(leftNode.left,rightNode.right) and self.isSame(leftNode.right,rightNode.left) return False我的思路：第六题905. 按奇偶排序数组难度：简单给定一个非负整数数组A，返回一个由A的所有偶数元素组成的数组，后面跟A的所有奇数元素。你可以返回满足此条件的任何数组作为答案。示例：输入：[3,1,2,4]输出：[2,4,3,1]输出 [4,2,3,1]，[2,4,1,3] 和 [4,2,1,3] 也会被接受。我的题解：class Solution(object): def sortArrayByParity(self, A): """ :type A: List[int] :rtype: List[int] """ n = [0]len(A) k = 0 j = len(A) - 1 for i in range(len(A)): if A[i] % 2 ==1: #奇数 n[j] = A[i] j -= 1 else: n[k] = A[i] k += 1 return n我的思路：第七题832. 翻转图像难度：简单给定一个二进制矩阵A，我们想先水平翻转图像，然后反转图像并返回结果。水平翻转图片就是将图片的每一行都进行翻转，即逆序。例如，水平翻转[1, 1, 0]的结果是[0, 1, 1]。反转图片的意思是图片中的0全部被1替换，1全部被0替换。例如，反转[0, 1, 1]的结果是[1, 0, 0]。我的题解：class Solution(object): def flipAndInvertImage(self, A): """ :type A: List[List[int]] :rtype: List[List[int]] """ #逆序 return [[j ^ 1 for j in i[::-1]] for i in A]我的思路：第八题922. 按奇偶排序数组 II难度：简单给定一个非负整数数组A，A中一半整数是奇数，一半整数是偶数。对数组进行排序，以便当A[i]为奇数时，i也是奇数；当A[i]为偶数时，i也是偶数。你可以返回任何满足上述条件的数组作为答案。我的题解：class Solution(object): def sortArrayByParityII(self, A): """ :type A: List[int] :rtype: List[int] """ count0 = 0 count1 = 1 re = [] for i in A: if i%2 == 0: re.insert(count0, i) count0 += 2 else: re.insert(count1, i) count1 += 2 return re我的思路：第九题509. 斐波那契数难度：简单斐波那契数，通常用F(n)表示，形成的序列称为斐波那契数列。该数列由0和1开始，后面的每一项数字都是前面两项数字的和。也就是：F(0) = 0, F(1) = 1F(N) = F(N - 1) + F(N - 2), 其中 N > 1.给定N，计算F(N)。我的题解：class Solution(object): def fib(self, N): """ :type N: int :rtype: int """ if N == 0:return 0 if N==1 or N == 2:return 1 return (self.fib(N-1)+self.fib(N-2))我的思路：第十题561. 数组拆分 I难度：简单给定长度为2n的数组, 你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从1 到 n 的 min(ai, bi) 总和最大。输入: [1,4,3,2]输出: 4解释: n 等于 2, 最大总和为 4 = min(1, 2) + min(3, 4).提示:n 是正整数,范围在 [1, 10000].数组中的元素范围在 [-10000, 10000].我的题解：class Solution(object): def arrayPairSum(self, nums): """ :type nums: List[int] :rtype: int """ nums.sort() return sum(nums[::2])我的思路：第十一题867. 转置矩阵难度：简单给定一个矩阵A， 返回A的转置矩阵。矩阵的转置是指将矩阵的主对角线翻转，交换矩阵的行索引与列索引。我的题解：class Solution(object): def transpose(self, A): """ :type A: List[List[int]] :rtype: List[List[int]] """ return zip(A)我的思路：第十二题1002. 查找常用字符难度：简单给定仅有小写字母组成的字符串数组 A，返回列表中的每个字符串中都显示的全部字符（包括重复字符）组成的列表。例如，如果一个字符在每个字符串中出现3次，但不是4次，则需要在最终答案中包含该字符3次。你可以按任意顺序返回答案。示例 1：输入：[“bella”,“label”,“roller”]输出：[“e”,“l”,“l”]我的题解：class Solution(object): def commonChars(self, A): """ :type A: List[str] :rtype: List[str] """ tmp = list(A[0]) for i in range(1,len(A)): tmp_list =list() for j in A[i]: if j in tmp: index = tmp.index(j) del tmp[index] tmp_list.append(j) tmp = tmp_list return tmp我的思路：第十三题350. 两个数组的交集 II难度：简单给定两个数组，编写一个函数来计算它们的交集。示例 1:输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2,2]输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [4,9]说明：输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。我们可以不考虑输出结果的顺序。我的题解：class Solution(object): def intersect(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ l = list() for i in nums2: if i in nums1: index = nums1.index(i) del nums1[index] l.append(i) return l我的思路：第十四题1002. 查找常用字符难度：简单给定两个数组，编写一个函数来计算它们的交集。示例:输入: nums1 = [1,2,2,1], nums2 = [2,2]输出: [2]输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]输出: [9,4]说明:输出结果中的每个元素一定是唯一的。我们可以不考虑输出结果的顺序。我的题解：class Solution(object): def intersection(self, nums1, nums2): """ :type nums1: List[int] :type nums2: List[int] :rtype: List[int] """ l = dict() a = list() for i in nums2: if i in nums1: if i not in l: l[i] = 1 for key in l: a.append(key) return a我的思路：第十五题566. 重塑矩阵难度：简单在MATLAB中，有一个非常有用的函数reshape，它可以将一个矩阵重塑为另一个大小不同的新矩阵，但保留其原始数据。给出一个由二维数组表示的矩阵，以及两个正整数r和c，分别表示想要的重构的矩阵的行数和列数。重构后的矩阵需要将原始矩阵的所有元素以相同的行遍历顺序填充。如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。示例：输入: nums = [[1,2], [3,4]]r = 1, c = 4输出: [[1,2,3,4]]解释:行遍历nums的结果是 [1,2,3,4]。新的矩阵是 1 * 4 矩阵, 用之前的元素值一行一行填充新矩阵。我的题解：class Solution(object): def matrixReshape(self, nums, r, c): """ :type nums: List[List[int]] :type r: int :type c: int :rtype: List[List[int]] """ l_a = len(nums) l_b = len(nums[0]) if l_al_b != rc: return nums if l_a == r: return nums list_a = list() list_b = list() count = 0 for i in range(l_a): for j in range(l_b): list_b.append(nums[i][j]) count += 1 if count == c: list_a.append(list_b) list_b = list() count = 0 return list_a我的思路：第十六题485. 最大连续1的个数难度：简单给定一个二进制数组， 计算其中最大连续1的个数。示例 1:输入: [1,1,0,1,1,1]输出: 3解释: 开头的两位和最后的三位都是连续1，所以最大连续1的个数是3注意：输入的数组只包含0和1。输入数组的长度是正整数，且不超过10,000。我的题解：class Solution(object): def findMaxConsecutiveOnes(self, nums): """ :type nums: List[int] :rtype: int """ max_l = 0 count = 0 for i in nums: if i == 1 : count +=1 else: ###遇到0 if count > max_l: max_l = count count = 0 if count > max_l: max_l = count return max_l我的思路：第十七题167. 两数之和 II - 输入有序数组难度：简单给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值index1 和index2，其中index1必须小于index2。说明:返回的下标值（index1 和 index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。我的题解：class Solution(object): def twoSum(self, numbers, target): """ :type numbers: List[int] :type target: int :rtype: List[int] """ l = len(numbers) i = 0 j = l - 1 l_a = list() while i < j: if numbers[i]+numbers[j] == target: l_a.append(i+1) l_a.append(j+1) return l_a elif numbers[i]+numbers[j] > target: j -= 1 else: i +=1 return null我的思路：第十八题633. 平方数之和难度：简单给定一个非负整数 c ，你要判断是否存在两个整数a和b，使得a²+b²= c。示例:输入: 5输出: True解释: 1 1 + 2 2 = 5我的题解：import mathclass Solution(object): def judgeSquareSum(self, c): """ :type c: int :rtype: bool """ a = int(math.sqrt(c)) b = 0 while a > b: if a2 + b2 == c: return True elif a2 + b2 > c: a -= 1 else: b += 1 if a2 + b2 == c: return True else: return False 我的思路：第十九题345. 反转字符串中的元音字母难度：简单编写一个函数，以字符串作为输入，反转该字符串中的元音字母。示例:输入: “hello"输出: “holle"我的题解：class Solution(object): def reverseVowels(self, s): "”” :type s: str :rtype: str """ y = [‘a’,’e’,‘i’,‘o’,‘u’,‘A’,‘E’,‘I’,‘O’,‘U’] p = 0 q = len(s) - 1 s = list(s) while p<=q: if s[q] not in y and s[p] not in y: p += 1 q -= 1 elif s[p] in y and s[q] not in y: q -= 1 elif s[q] in y and s[p] not in y: p += 1 else: flag = s[q] s[q] = s[p] s[p] = flag p += 1 q -= 1 return ‘’.join(s)我的思路：第二十题141. 环形链表难度：简单给定一个链表，判断链表中是否有环。为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果pos是-1，则在该链表中没有环。我的题解：# Definition for singly-linked list.# class ListNode(object):# def init(self, x):# self.val = x# self.next = Noneclass Solution(object): def hasCycle(self, head): """ :type head: ListNode :rtype: bool """ if not head: return False l1 = head l2 = head.next while l1 and l2 and l2.next: if l1 == l2: return True l1 = l1.next l2 = l2.next.next return False我的思路：第二十一题985. 查询后的偶数和难度：简单给出一个整数数组A和一个查询数组queries。对于第i次查询，有val=queriesi, index = queriesi，我们会把val加到A[index]上。然后，第i次查询的答案是A中偶数值的和。（此处给定的 index = queriesi 是从 0 开始的索引，每次查询都会永久修改数组 A。）返回所有查询的答案。你的答案应当以数组 answer 给出，answer[i] 为第 i 次查询的答案。我的题解：class Solution(object): def sumEvenAfterQueries(self, A, queries): """ :type A: List[int] :type queries: List[List[int]] :rtype: List[int] """ l =list() sum = 0 sum_a = 0 for j in A: if j%2 ==0: sum_a += j for i in range(len(queries)): A[queries[i][1]] += queries[i][0]#增加数值 if A[queries[i][1]] % 2 ==0:#是偶数 if queries[i][0]%2 ==0:#是偶数 sum = sum_a + queries[i][0] else:#是奇数 sum = sum_a + A[queries[i][1]] else:#是奇数 if queries[i][0]%2 ==0:#是偶数 sum = sum_a else: sum = sum_a - A[queries[i][1]] + queries[i][0] l.append(sum) sum_a =sum return l我的思路小小总结 ...

Given a string, find the length of the longest substring withoutrepeating characters.Example 1:Input: “abcabcbb” Output: 3 Explanation: The answer is “abc”, withthe length of 3. Example 2:Input: “bbbbb” Output: 1 Explanation: The answer is “b”, with thelength of 1. Example 3:Input: “pwwkew” Output: 3 Explanation: The answer is “wke”, with thelength of 3. Note that the answer must be a substring, “pwke” is a subsequence and not a substring.对xxx串，它的最长不重复子串情况可以完全由xx可以决定，确认是dp问题确定状态转移方程，定义dp[i]为与当前串构成不重复串的indexdp[i]=Math.max(dp[i-1],count[s.charAt(i-1)]+1);public int lengthOfLongestSubstring(String s) { int ret=0; int l=s.length(); int[] dp=new int[l+1]; int[] count=new int[128]; for(int i=1;i<=l;i++){ dp[i]=Math.max(dp[i-1],count[s.charAt(i-1)]+1); ret=Math.max(ret,i+1-dp[i]); count[s.charAt(i-1)]=i; } return ret; } ...

题目要求Given an array of characters, compress it in-place.The length after compression must always be smaller than or equal to the original array.Every element of the array should be a character (not int) of length 1.After you are done modifying the input array in-place, return the new length of the array. Follow up:Could you solve it using only O(1) extra space? Example 1:Input:[“a”,“a”,“b”,“b”,“c”,“c”,“c”]Output:Return 6, and the first 6 characters of the input array should be: [“a”,“2”,“b”,“2”,“c”,“3”]Explanation:“aa” is replaced by “a2”. “bb” is replaced by “b2”. “ccc” is replaced by “c3”. Example 2:Input:[“a”]Output:Return 1, and the first 1 characters of the input array should be: [“a”]Explanation:Nothing is replaced. Example 3:Input:[“a”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”,“b”]Output:Return 4, and the first 4 characters of the input array should be: [“a”,“b”,“1”,“2”].Explanation:Since the character “a” does not repeat, it is not compressed. “bbbbbbbbbbbb” is replaced by “b12”.Notice each digit has it’s own entry in the array. Note:All characters have an ASCII value in [35, 126].1 <= len(chars) <= 1000.对字符串进行简单的压缩操作，压缩的规则是，如果出现多个重复的字母，则用字母加上字母出现的字数进行表示。如果字母只出现一次，则不记录次数。思路和代码核心思路是用三个指针分别记录三个下标：p1: 记录压缩后的内容的插入下标p2: 记录当前相同字符串的起始位置p3: 记录当前和起始位置比较的字符串的位置一旦出现p3的值不等于p2或是p3的值大于字符数组的长度，则将压缩结果从p1开始填写，实现O(1)的空间复杂度。 public int compress(char[] chars) { int p1 = 0; int p2 = 0; int p3 = 1; while(p2 < chars.length) { if(p3 >= chars.length || chars[p3] != chars[p2]) { int length = p3 - p2; chars[p1++] = chars[p2]; if(length != 1) { int count = 0; while(length != 0) { int num = length % 10; for(int i = p1+count ; i>p1 ; i–) { chars[i] = chars[i-1]; } chars[p1] = (char)(‘0’ + num); length /= 10; count++; } p1 += count; } p2 = p3; } p3++; } return p1; } ...

最近准备系统的学习数据结构与算法，学习的时候想配合着leetcode刷题，这样会加深印象。在学习栈的时候，老师举了计算器实现的例子，我搜了一下leetcode刚好有这样的题，就想着自己实现一下吧。leetcode题目：leetcode224leetcode227实现一个基本计算器肯定是要有四则运算和括号运算的，实现一个这样的计算器自然就把这两题做出来了。思路这里参考了浙大mooc数据结构课程的栈的部分，首先是将常用的中缀表达式转换为后缀表达式，再将后缀表达式进行求值运算。中缀表达式转为后缀表达式用栈来存运算符，按顺序读取中缀表达式的每个对象，对每个对象按不同情况处理：运算数：直接输出左括号：压入栈右括号：弹出并输出栈顶元素，直至遇到左括号停止，将左括号出栈丢弃运算符：若优先级大于栈顶元素，则把它压栈；若优先级小于等于栈顶元素，则弹出并输出栈顶元素，再比较新的栈顶元素，直至优先级大于栈顶元素或者栈为空，再将该元素压入栈处理完中序表达式后，将栈中还存留的运算符全部输出例：2*(9+1) -> 2 9 1 + 2+9/3-5 -> 2 9 3 / + 5 -后缀表达式求值用栈来存取运算数，按顺序读取后缀表达式各项，对运算符和运算数做不同处理：运算数：入栈运算符：从栈中弹出两个运算数，根据运算符做运算求出结果后，将结果压栈最后栈顶的元素就是表达式的值，此时栈中只有一个元素代码：转换表达式// 将中缀转为后缀表达式，以空格分割运算数和运算符private static String parseRPN(String s) { // 用于返回的字符串 StringBuilder returnSb = new StringBuilder(); // 创建操作符栈 Stack<Character> stack = new Stack<Character>(); // 将字符串转换为字符数组，这样遍历字符串会快一些，使用String.charAt()会每次从头遍历 char[] cs = s.toCharArray(); //开始从头处理中缀表达式的每个对象 int i = 0; while (i < cs.length) { // 匹配空格，将其舍弃 if (cs[i] == ’ ‘) { i++; continue; } // 匹配数字，若匹配成功则将数字添加至numberSb StringBuilder numberSb = new StringBuilder(); while(i < cs.length&&cs[i]>=‘0’&&cs[i]<=‘9’){ numberSb.append(cs[i]); i++; } if (numberSb.length()!=0) {//若前面匹配到了数字，则numberSb长度必不为0 returnSb.append(numberSb.append(’ ‘));//将numberSb添加空格后追加到returnSb continue; } // 匹配运算符 char symbol = cs[i]; // 遇到左括号直接压栈 if (symbol == ‘(’) { stack.push(symbol); } else // 遇到右括号，输出栈顶元素至左括号结束 if (symbol == ‘)’) { while (stack.peek() != ‘(’) { returnSb.append(stack.pop() + " “); } stack.pop();// 将左括号移出栈 } else // 处理其他符号 // 优先级大于栈顶元素时，直接压栈 if (stack.isEmpty() || (symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’)) { stack.push(symbol); } else {// 否则就输出栈顶元素至优先级大于栈顶元素或者遇到左括号或者栈为空，然后压栈 while (!stack.isEmpty()) { if (stack.peek() == ‘(’) break; if (!((symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’))) { returnSb.append(stack.pop() + " “); } else break; } stack.push(symbol); } i++; } //输出运算符栈的元素 while (!stack.isEmpty()) { returnSb.append(stack.pop() + " “); } return returnSb.toString();}后缀表达式求值定义的几个long型变量是为了观察运行时间public int calculate(String s) { long time1 = System.currentTimeMillis(); // 操作数栈 Stack<Integer> stack = new Stack<Integer>(); // 将s转为后缀表达式，并转为字符数组 char[] cs = parseRPN2(s).toCharArray(); long time2 = System.currentTimeMillis(); int i = 0; //tmpSb用来临时存放数字，主要是考虑到数字不止一位 StringBuilder tmpSb = new StringBuilder(); while (i < cs.length) { if (cs[i] == ’ ‘) {//遇到空格就把tmpSb转为数字并压入栈 if (tmpSb.length() != 0) { stack.push(Integer.parseInt(tmpSb + “”)); tmpSb = new StringBuilder(); } i++; continue; } //遇到数字就加在tmpSb后 if (cs[i] >= ‘0’ && cs[i] <= ‘9’) { tmpSb.append(cs[i]); i++; continue; } //不是空格也不是数字就是运算符，弹出两个数进行运算，注意这里弹出的第一个数为b，第二个数才是a，这里我一开始写错了 int b = stack.pop(); int a = stack.pop(); switch (cs[i]) { case ‘+’: stack.push(a + b); break; case ‘-’: stack.push(a - b); break; case ‘’: stack.push(a * b); break; case ‘/’: stack.push(a / b); break; } i++; } long time3 = System.currentTimeMillis(); System.out.println(“总耗时：” + (time3 - time1)); System.out.println(“转换后缀耗时：” + (time2 - time1)); System.out.println(“求值耗时：” + (time3 - time2)); //最后在栈里的唯一一个元素就是要求的值 return stack.pop();}测试public static void main(String[] args) { Scanner in = new Scanner(System.in); String s = in.next(); System.out.println(new Solution().calculate(s));}输入:19 * (2+8)输出:总耗时：44转换后缀耗时：26求值耗时：18结果为：190还有一个输入为leetcode测试用例，s非常长，我写的这个方法也能在半秒之内得出结果，速度还是很快的。我之前写的一个转换后缀的方法由于大量的新建StringBuilder，就导致了这个测试用例因为超时而未通过，大概是7秒左右，在这里我也贴一下代码，这里不提倡使用。超时代码private static String parseRPN2(String s) { StringBuilder returnSb = new StringBuilder(); Stack<Character> stack = new Stack<Character>(); Pattern space = Pattern.compile(”\s+”); Pattern number = Pattern.compile(”\d+"); StringBuilder sb = new StringBuilder(s); while (sb.length() != 0) { Matcher spaceMatcher = space.matcher(sb); if (spaceMatcher.lookingAt()) { sb = new StringBuilder(sb.subSequence(spaceMatcher.end(), sb.length())); continue; } Matcher numberMatcher = number.matcher(sb); if (numberMatcher.lookingAt()) { returnSb.append(numberMatcher.group() + " “); sb = new StringBuilder(sb.subSequence(numberMatcher.end(), sb.length())); continue; } char symbol = sb.charAt(0); if (symbol == ‘(’) { stack.push(symbol); } else if (symbol == ‘)’) { while (stack.peek() != ‘(’) { returnSb.append(stack.pop() + " “); } stack.pop(); } else if (stack.isEmpty() || (symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’)) { stack.push(symbol); } else { while (!stack.isEmpty()) { if (stack.peek() == ‘(’) break; if (!((symbol == ‘’ || symbol == ‘/’) && (stack.peek() == ‘+’ || stack.peek() == ‘-’))) { returnSb.append(stack.pop() + " “); } else break; } stack.push(symbol); } sb = new StringBuilder(sb.subSequence(1, sb.length())); } while (!stack.isEmpty()) { returnSb.append(stack.pop() + " “); } return returnSb.toString();}结语计算器的基本实现就是基于这样的方法，后面我在学习其他数据结构和算法时会继续分享， ...

You are given two non-empty linked lists representing two non-negativeintegers. The digits are stored in reverse order and each of theirnodes contain a single digit. Add the two numbers and return it as alinked list.You may assume the two numbers do not contain any leading zero, exceptthe number 0 itself.Example:Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation:342 + 465 = 807.考察大数相加，注意进位，加法是否完成取决于进位，两个链表任意不为空，循环中这几个条件都不满足才退出这种或的循环一定要注意循环体内有些条件已经不满足public ListNode addTwoNumbers(ListNode l1, ListNode l2) { int carry=0; ListNode head=new ListNode(0); ListNode cur=head; while(l1!=null || l2!=null || carry>0){ int sum=carry; if(l1!=null){ sum+=l1.val; l1=l1.next; } if(l2!=null){ sum+=l2.val; l2=l2.next; } if(sum>=10){ sum-=10; carry=1; }else carry=0; cur.next=new ListNode(sum); cur=cur.next; } return head.next; } ...

Given an array of integers, return indices of the two numbers suchthat they add up to a specific target.You may assume that each input would have exactly one solution, andyou 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].1.暴力 O(n^2)2.排序后双指针 O(nlogn)3.hash o(n) public int[] twoSum(int[] nums, int target) { Map<Integer,Integer> map=new HashMap(); for(int i=0;i<nums.length;++i){ int need=target-nums[i]; if(map.containsKey(need)) return new int[]{i,map.get(i)}; map.put(nums[i],i); } throw null; } ...

题目给定一个二叉树，原地将它展开为链表。例如，给定二叉树 1 / \ 2 5 / \ \3 4 6将其展开为：1 \ 2 \ 3 \ 4 \ 5 \ 6题解这算是比较经典的一道题目了, 博主面试快手的时候原题。最开始一想，觉得递归的求解不就好了，但是递归的时候发现需要注意一个地方就是：需要先递归右子树，然后记录下右子树展开完成之后的链表头。然后再递归的求解左子树，把左子树的最后一个链到右子树的链表头。基于这个，我们用一个pre指针来记录右子树的头结点。class Solution { private TreeNode prev = null; public void flatten(TreeNode root) { if (root == null) return; flatten(root.right); flatten(root.left); root.right = prev; root.left = null; prev = root; }}递归的方式转换为迭代的方式用stack就好了，反而比较好理解。class Solution { public void flatten(TreeNode root) { if (root == null) return; Stack<TreeNode> stack = new Stack<TreeNode>(); stack.push(root); while (!stack.isEmpty()) { TreeNode current = stack.pop(); if (current.right != null) stack.push(current.right); if (current.left != null) stack.push(current.left); if (!stack.isEmpty()) current.right = stack.peek(); current.left = null; } }}有问题加手撕代码QQ群讨论：805423079 ...

Search in a Binary Search Tree题目链接700. Search in a Binary Search Tree题目分析从给定的二叉树中，查找指定值及其子节点。思路这个好像不用多说什么了吧…按先序遍历搜索，找到则返回。没有则返回NULL。最终代码<?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 searchBST($root, $val) { if($root->val == $val){ return $root; } $a = NULL; $b = NULL; if($root->left){ $a = $this->searchBST($root->left, $val); if($a){ return $a; } } if($root->right){ $b = $this->searchBST($root->right, $val); if($b){ return $b; } } return NULL; }}若觉得本文章对你有用，欢迎用爱发电资助。

前言Weekly Contest 132的 除数博弈：爱丽丝和鲍勃一起玩游戏，他们轮流行动。爱丽丝先手开局。最初，黑板上有一个数字 N 。在每个玩家的回合，玩家需要执行以下操作：选出任一 x，满足 0 < x < N 且 N % x == 0 。用 N - x 替换黑板上的数字 N 。如果玩家无法执行这些操作，就会输掉游戏。只有在爱丽丝在游戏中取得胜利时才返回 true，否则返回 false。假设两个玩家都以最佳状态参与游戏。示例1：输入：2输出：true解释：爱丽丝选择 1，鲍勃无法进行操作。示例2：输入：3输出：false解释：爱丽丝选择 1，鲍勃也选择 1，然后爱丽丝无法进行操作。提示：1 <= N <= 1000解题思路本题难度为简单，可是题目的描述会感觉解题十分困难，实际上本题只需要找出爱丽丝和鲍勃胜负的周期即可，同类型的题目有292. Nim游戏。下面先列出前5次的胜负情况：N为1时，由于爱丽丝先手，无法进行操作，鲍勃胜利，为falseN为2时，爱丽丝胜利，为trueN为3时，鲍勃胜利，为falseN为4时，取数情况为1,1,1，爱丽丝胜利，为trueN为5时，取数情况为1,1,1,1，鲍勃胜利，为false从上面列出的胜负情况可以看出，当N为奇数时，鲍勃胜利，当N为偶数时，爱丽丝胜利。实现代码 /** * 5024. 除数博弈 * 1 false * 2 1 true * 3 1 false * 4 1,1,1 true * 5 1,1,1,1 false * @param N * @return */ public boolean divisorGame(int N) { return N%2==0; } ...

前言Weekly Contest 132的 节点与其祖先之间的最大差值：给定二叉树的根节点 root，找出存在于不同节点 A 和 B 之间的最大值 V，其中 V = |A.val - B.val|，且 A 是 B 的祖先。（如果 A 的任何子节点之一为 B，或者 A 的任何子节点是 B 的祖先，那么我们认为 A 是 B 的祖先）示例：输入：[8,3,10,1,6,null,14,null,null,4,7,13]输出：7解释： 我们有大量的节点与其祖先的差值，其中一些如下：|8 - 3| = 5|3 - 7| = 4|8 - 1| = 7|10 - 13| = 3在所有可能的差值中，最大值 7 由 |8 - 1| = 7 得出。提示：树中的节点数在 2 到 5000 之间。每个节点的值介于 0 到 100000 之间。解题思路本题需要将问题分解一下，首先先实现根节点与每个节点的差值的最大值的算法，然后只需要遍历每个子树即可。实现代码 /** * 5030. 节点与其祖先之间的最大差值 * @param root * @return / public int maxAncestorDiff(TreeNode root) { Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); int max=0; while(!queue.isEmpty()){//层序遍历 TreeNode node=queue.poll(); max=Math.max(max,getMaxDiffByRoot(node)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; } /* * 获取某个根节点下所有节点与根节点的差值的最大值 * 这里选择使用层序遍历 * @param root * @return */ private int getMaxDiffByRoot(TreeNode root){ Queue<TreeNode> queue = new LinkedList<>(); queue.add(root); //根节点的值，用于比较 int rootValue=root.val; //最大差值 int max=0; while(!queue.isEmpty()){//层序遍历每个节点 TreeNode node=queue.poll(); // 获取最大值 max=Math.max(max,Math.abs(node.val-rootValue)); if(node.left!=null){ queue.add(node.left); } if(node.right!=null){ queue.add(node.right); } } return max; } ...

Merge Two Binary Trees题目链接617. Merge Two Binary Trees题目分析给定两个二叉树，返回一个 将对应位置值相加后的二叉树。例如，树A的顶点值为1，树B的顶点值为2，那么返回的二叉树的顶点值需要是3。思路顶点自然不用多说，直接相加就可以了。按照习惯，先遍历左节点。如果树A和树B都有左节点，那么直接相加，再递归当前函数去判断左节点的左节点。若树A和树B任意一棵树没有左节点时，直接把有左节点迁移过来即可。 因为，如果没有左节点，不可能会有左节点的左节点，或左节点的右节点。 因此，直接照搬过来就可以了。若两颗树都没有左节点时，忽略，直接去算右节点，并遵从以上规则即可。最终代码<?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 mergeTrees($t1, $t2) { if(is_null($t1->val)&&is_null($t2->val)){ return; } $t1->val += $t2->val; if($t1->left&&$t2->left){ $this->mergeTrees($t1->left, $t2->left); } if(!$t1->left&$t2->left){ $t1->left = $t2->left; } if($t1->right && $t2->right){ $this->mergeTrees($t1->right, $t2->right); } if(!$t1->right&&$t2->right){ $t1->right = $t2->right; } return $t1; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。说明: 叶子节点是指没有子节点的节点。示例:给定如下二叉树，以及目标和 sum = 22， 5 / \ 4 8 / / \ 11 13 4 / \ / \ 7 2 5 1返回:[ [5,4,11,2], [5,8,4,5]]题解这道题目是上一道的延伸，但是需要记录下路径，返回回去。这就是一个典型的backtrack的题目了。我们用迭代的方式需要记录中间的路径状态，稍显复杂，所以我们想用递归的方式来解，先探索左子树，然后探索右子树。如果都探索完之后，右满足的就加入到最终结果中。public class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> res = new LinkedList<>(); helper(root, sum, res, new LinkedList<>()); return res; } public void helper(TreeNode root, int sum, List<List<Integer>> res, List<Integer> current) { if (root == null) { return; } current.add(root.val); if (root.left == null && root.right == null && sum == root.val) { // leaf node. res.add(new LinkedList<>(current)); // back track. current.remove(current.size() - 1); return; } helper(root.left, sum - root.val, res, current); helper(root.right, sum - root.val, res, current); // back track. current.remove(current.size() - 1); }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树手撕代码QQ群：805423079， 群密码：1024 ...

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。push(x) – 将元素 x 推入栈中。pop() – 删除栈顶的元素。top() – 获取栈顶元素。getMin() – 检索栈中的最小元素。示例:MinStack minStack = new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); –> 返回 -3.minStack.pop();minStack.top(); –> 返回 0.minStack.getMin(); –> 返回 -2.解法：大概思路是使用维护两个栈，一个保存数据，一个保存最小值的索引。type MinStack struct { data []interface{} minIndex []int}/** initialize your data structure here. */func Constructor() MinStack { var instance MinStack return instance}func (this *MinStack) Push(x int) { this.data = append(this.data, x) if len(this.minIndex) == 0 { this.minIndex = append(this.minIndex, 0) } else { //当前最小值比新值大 if this.data[this.minIndex[len(this.minIndex) - 1]].(int) > x { //当前最小值索引压入minIndex this.minIndex = append(this.minIndex, len(this.data) - 1) } }}func (this *MinStack) Pop() { length := len(this.data) currentMinIndex := length - 1 if currentMinIndex == this.minIndex[len(this.minIndex) - 1] { this.minIndex = this.minIndex[:len(this.minIndex) - 1] } this.data = this.data[:len(this.data) - 1]}func (this MinStack) Top() int { return this.data[len(this.data) - 1].(int)}func (this MinStack) GetMin() int { return this.data[this.minIndex[len(this.minIndex) - 1]].(int)}/ * Your MinStack object will be instantiated and called as such: * obj := Constructor(); * obj.Push(x); * obj.Pop(); * param_3 := obj.Top(); * param_4 := obj.GetMin(); */参考最小栈的实现Golang基础篇之数据结构-栈 ...

Univalued Binary Tree题目链接965. Univalued Binary Tree题目分析如果二叉树中所有节点的值都相同，那么该二叉树被称为单值二叉树。当给定的二叉树是单值二叉树时返回true，否则返回false。思路思路比较简单，把值存入全局变量数组中，再对数组的值去重。判断该数组长度是否为1即可。最终代码<?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 { private $vals = []; function isUnivalTree($root) { $this->getVal($root); return count(array_count_values(array_filter($this->val,function($v){ return !is_null($v); })))==1; } function getVal($root){ $this->val[] = $root->val; if($root->left){ $this->getVal($root->left); } if($root->right){ $this->getVal($root->right); } }}优化方案把值作为数组的键则可以省去去重步骤。在存入之前就可以判断值是否与前面的值相同。若不同则直接退出即可。若觉得本文章对你有用，欢迎用爱发电资助。

K Closest Points to Origin题目链接973. K Closest Points to Origin题目分析给一个坐标数组points，从中返回K个离0,0最近的坐标。其中，用欧几里得距离计算。思路把距离作为数组的键，把对应坐标作为数组的值。用ksort函数排序，再用array_slice函数获取前K个即可。最终代码<?phpclass Solution { function kClosest($points, $K) { $dists = []; foreach($points as $point){ $dists[(string)sqrt(pow($point[0],2)+pow($point[1],2))] = $point; } ksort($dists); return array_slice($dists,0,$K); }}若觉得本文章对你有用，欢迎用爱发电资助。

Uncommon Words from Two Sentences题目链接884. Uncommon Words from Two Sentences题目分析返回给定的两个句子中唯一不同的单词。思路先把两个句子分别按空格分割成数组，再计算两个数组的差集，即可得知两个句子的差异。测试后发现没通过apple apple和banana这个测试组合。系统提示应当返回banana。那么我们计算一下这个差集中单词出现的次数，只返回出现次数为1的。因为用了array count values函数，因此键为单词，值为出现次数。我们需要用array_keys返回键部分即可。最终代码<?phpclass Solution { function uncommonFromSentences($A, $B) { $d = array_merge(array_diff(explode(’ ‘, $A), explode(’ ‘, $B)),array_diff(explode(’ ‘, $B), explode(’ ‘, $A))); return array_keys(array_filter(array_count_values($d),function($val){ return $val==1; })); }}若觉得本文章对你有用，欢迎用爱发电资助。

一、题目最长回文子串：给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。示例 1：输入: “babad"输出: “bab"注意: “aba” 也是一个有效答案。示例 2：输入: “cbbd"输出: “bb"二、我的答案思路1.排除法，最优解法肯定不是暴力遍历 2.紧接着想到第三题中使用的两个指针同步遍历一个字符串的方法，尝试了一下，发现跟暴力遍历没有区别 3.再看几遍题，要找的是回文字符串，回文字符串的特点在于两边字符都相同，也就是说需要找的是两边字符都相同中间点(注意是中间点而不是中间字符，因为题干中例1的中间点是a，但是例2的中间点是bb)代码v1.0(过于丑陋，可跳过直接看说明和v2.0) /** * @param {string} s * @return {string} / var longestPalindrome = function(s) { function expendString(index1, index2) { if(index1 > 0 && index2 + 1 < s.length &&s[index1 -1] === s[index2 + 1]){ return expendString(index1 -1, index2 + 1) } else { return [index1, index2, index2 - index1] } } let longestArr = [0, 0, 0] let tempArr for(let i = 1; i< s.length; i++) { if(i + 1 < s.length&&s[i-1] === s[i+1]) { tempArr = expendString(i-1, i+1) tempArr[2] > longestArr[2] ? longestArr = tempArr : null } if(s[i -1] === s[i]) { tempArr = expendString(i - 1, i) tempArr[2] > longestArr[2] ? longestArr = tempArr : null } } return s.slice(longestArr[0], longestArr[1] + 1) };讲解1. 函数expendString作用为以两个传参拓展字符串，判断是否依然是回文字符串2. 数组longestArr作用为防止当前最长字串的两个下标和长度(我也不知道当时自己为什么还要费劲写个数组)3. for循环中判断回文串的中点是一个(‘aba’)还是两个(‘abba’),然后分别调用上文定义的expendString函数进行拓展 通过，下一步要做的就是优化成能看懂的版本 v2.0/* * @param {string} s * @return {string} */var longestPalindrome = function(s){ function expendString(index1, index2) { if (index1 >= 0 && index2 < s.length && s[index1] === s[index2]) { expendString(index1 - 1, index2 + 1) } else { index2 - index1 > longestString.length ? longestString = s.slice(index1 + 1, index2) : null } } let longestString = s[0] || ’’ for (let i = 1; i < s.length; i++) { if (i + 1 < s.length) { expendString(i - 1, i + 1) } if (s[i - 1] === s[i]) { expendString(i - 1, i) } } return longestString};三、优秀答案to be continued四、路漫漫其修远兮 ...

Toeplitz Matrix题目链接766. Toeplitz Matrix题目分析拓普利兹矩阵，应该不用多说了。要求自己的右下和左上元素值相等。思路拿当前行的前0n-1位，与下一行的1n位对比即可。把二维数组降维为一维，再取当前行的头n位和下一行的头n位（去掉第一个元素，因为在下一行会比较它）比较即可。用这个方法会重复较多值，有优化空间。最终代码<?phpclass Solution { function isToeplitzMatrix($matrix) { $indicies = array_reduce(array_reverse($matrix), ‘array_merge’, []); $cols = count($matrix[0]); $rows = count($matrix); if($rows == 1 ){ return true; } foreach(range(0,$rows-2) as $val){ $left = array_slice($indicies, $val*$cols+1, $cols-1); $right = array_slice($indicies,($val+1)*$cols,$cols-1); if(implode($left)!=implode($right)){ return false; } } return true; }}若觉得本文章对你有用，欢迎用爱发电资助。

Keyboard Row题目链接500. Keyboard Row题目分析给定一个字符串数组，返回那些所出现的字母在QWERTY键盘中同一行的字符串。例如，单词hello中，字母h和l在键盘的第二行（或者中间那一行），剩余字母e和o在第一行。故排除之。 再如，Dalas中，所有字母都在中间那一行，则返回它。思路我的思路是，把键盘中每一行出现的字母存进3个数组中（因为有3行），将每个字符串分割成数组，判断该数组与每一行字母数组是否有差集。如果分散在不同行，则必定会在与某一行有差。用array_filter函数过滤这些有差的字符串即可。最终代码<?phpclass Solution { function findWords($words) { return array_filter($words, function($val){ $val = array_unique(str_split(strtolower($val))); $q = [‘q’,‘w’,’e’,‘r’,’t’,‘y’,‘u’,‘i’,‘o’,‘p’]; $a = [‘a’,’s’,’d’,‘f’,‘g’,‘h’,‘j’,‘k’,’l’]; $z = [‘z’,‘x’,‘c’,‘v’,‘b’,’n’,’m’]; return !(array_diff($val,$q) && array_diff($val,$a)&& array_diff($val,$z)); }); } } 若觉得本文章对你有用，欢迎用爱发电资助。

leetcode里和graph相关的题目根据解题思路可以分成以下几个大类：Depth First Search 典型题型：求具体路径Breadth First Search 典型题型：求最短距离Topological Sort 典型题型：node之间有先后顺序，需要判断图中是否存在有向环Union Find 典型题型：节点之间相互连接，求group的个数等等有些题目的关键是如何建图。

Number of Lines To Write String题目链接806. Number of Lines To Write String题目分析每行只能容纳100个字符，给定每个字符所占宽度；计算给定的字符串需要占多少行，最后一行占多少个字符。思路首先第一行，直接添加即可。 当到达100时，当前单词要写到下一行。那么行数增加，当且单词长度直接作为下一行的末尾坐标。返回行数和最后一行的末尾坐标即可。最终代码<?phpclass Solution { function numberOfLines($widths, $S) { $S = str_split($S); $rows = 1; $cols = 0; foreach($S as $s){ $width = $widths[ord($s)-ord(‘a’)]; $cols += $width; if($cols>100){ $rows++; $cols = $width; } } return [$rows,$cols]; } } 若觉得本文章对你有用，欢迎用爱发电资助。

Reverse String题目链接344. Reverse String题目分析题目要求以O(1)时间复杂度把字符串倒转过来。思路题目提示说用原地算法……Emmm…我并不会，只能用strrev函数先应付了。最终代码<?phpclass Solution { function reverseString($s) { return strrev($s); }}若觉得本文章对你有用，欢迎用爱发电资助。

Transpose Matrix题目链接867. Transpose Matrix题目分析这个题目比较简单，就是矩阵转置。就是把第0行变成第0列，第1行变成第1列。思路用array_column方法获取每一列，塞入数组末尾作为一行即可。最终代码<?phpclass Solution { function transpose($A) { $t = []; foreach($A[0] as $key => $val){ $t[] = array_column($A,$key); } return $t; }}若觉得本文章对你有用，欢迎用爱发电资助。

AlgorithmLeetCode 145. Binary Tree Postorder Traversal后序遍历二叉树Given a binary tree, return the postorder traversal of its nodes’ values.Example:Input: [1,null,2,3] 1 \ 2 / 3Output: [3,2,1]Follow up: Recursive solution is trivial, could you do it iteratively?迭代版本class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> result = new ArrayList<>(); Stack<TreeNode> s = new Stack<>(); TreeNode p = root; // 记录上一次被访问的节点 TreeNode q = null; do{ //先找到最左下角的节点，记录沿途的位置 while(p!=null){ s.push(p); p = p.left; } q = null; while(!s.isEmpty()){ p = s.pop(); //BCA的访问次序，如果上一次访问了C，那么A就是该访问的节点 if(p.right == q){ result.add(p.val); q = p; }else{ //二次进栈 s.push(p); p = p.right; break; } } }while(!s.isEmpty()); return result; }}ReviewThe Key To Accelerating Your Coding Skills主题为提升编码技能的关键，首先提出获得解决问题的能力比开发一些应用更加重要。指导阶段，3-8周，入门阶段啥都不懂起步阶段的学生，最重要的是关注细节 根据错误信息调试很重要，随着经验增长，可以学会解读错误信息，抽取相关问题细节，从错误问题中学习经验，不要只是修复完就算了。刚开始可能需要问别人，后面可以google或者追踪代码。编程是终身学习的过程，有经验的工程师会为了解决未解决的问题而不断去学习，只等待是无用的。大师失败的次数比菜鸟尝试的次数还要多得多！进入下个阶段前，你有如下的特征：你见过了足够多的错误了，并且它们不再困扰着你你已经熟悉用google搜寻答案了你可以将你的代码遵循一定规则应用到其他的地方了拐点阶段，2-4周，正确的思维方式最令人困扰的阶段，根据指导，没有现成的方法解决你的问题困扰的原因是：编码速度比上个阶段慢了10-20倍剩余的日子，每天都要突破你的限制，不要待在舒适区关于web开发，有两个转折点会一同到来不要做个CRUD BOY，试试整合第三方的库学好数据结构和算法它们是编程王国的钥匙招聘主管喜欢扎实基础的算法和开发工程师不要追寻热点技术，基础扎实学起来都快变得依赖自己，不要等着别人来帮助写代码时候，想想之前是否写过类似的，可否借鉴视频吞掉了细节，查看API文档更加快速尽可能有效的度过拐点阶段指导阶段，做一些没有指导的任务尽可能少的使用指导文档假设你已经是度过拐点的开发者，适量阅读遵循github文档对你更有帮助重点关注重要且频繁使用的事情要明白这是困难的阶段，放轻松你自己如果你缺乏自信，找那些度过拐点的人聊聊，坚持学习，但不要太大负担，一天不要超过6小时，否则会加长这个阶段的时间。最好获取自信的方法是解决困惑你的问题，如果你挣扎了15个小时，那么之后就会平静下来如果5分钟或者5小时没思路，你会有困扰，但是你成功的次数多了，你的自信心会迅速增长如何知道自己度过了拐点阶段拐点度过之后是接受以下的事实：软件开发是持续的学习（还得学……）如果你觉得自己对所有都掌握了，那么应该解决更复杂的问题了Tip使用VSCode来开发JavaShare雾计算和边缘计算对物联网的意义何在？雾计算其响应更快，过滤信息，取决于网关灵活性，解决带宽瓶颈和延迟问题雾计算将一些处理和资源置于云的边缘，它不是为云存储和计算建立渠道，而是减少信息的发送降低对带宽的需求，再在某些接入点进行聚合。通过使用这种分布式策略，可以降低成本并提高效率。 ...

要点这一题的要点有三个：接收长度不同的数字并翻转判断结果是否溢出解决方法翻转：为了能够接收不同长度的数字进行反转操作,我们使用循环结构进行操作。（注：这里创建的sum变量一定要用long类型而不能用int，原因是采用int的话，即使结果溢出，该溢出的结果仍然在int的取值范围内，不利于判断溢出。所以采用占位64bit的long类型更佳。）long sum = 0;while(x != 0){ sum = sum * 10 + x % 10; x /= 10;}判断溢出：这里使用了Java中的Integer类（整数类，缩写就是Int）的静态变量MAX_VALUE和MIN_VALUE，就能直接得到整型变量可表示数值的上下限。当结果不在此范围内时，则溢出，并返回0.否则返回正常结果。（注：因为题目给定的函数返回类型为int，所以在最后返回结果时务必先将long型转换为int型再返回。）if(sum < Integer.MIN_VALUE || sum > Integer.MAX_VALUE) return 0;return new Long(sum).intValue();最终程序class Solution { public int reverse(int x) { long sum = 0; while(x != 0){ sum = sum * 10 + x % 10; x /= 10; } if(sum < Integer.MIN_VALUE || sum > Integer.MAX_VALUE) return 0; return new Long(sum).intValue(); }}

Sort Array By Parity II题目链接922. Sort Array By Parity II题目分析给定一个整数数组A，使数组中偶数位的值为偶数，奇数位的值为奇数。例如，A[0]，0是偶数，所以A[0]要为偶数。A[1]，1是奇数，所以A[1]要为奇数。思路用array_filter 拆分数组中的偶数和奇数，再轮流塞进新数组中。最终代码<?phpclass Solution { function sortArrayByParityII($A) { $odd = array_filter($A, function($val){ return ($val&1); }); $odd = array_values($odd); $even = array_filter($A, function($val){ return (!($val&1)); }); $even = array_values($even); $a = []; foreach($odd as $key => $o){ $a[] = $even[$key]; $a[] = $o; } return $a; }}若觉得本文章对你有用，欢迎用爱发电资助。

上周日就想写vue.nextTick的源码分析，可是总是不知道从哪儿下手，今天有时间，先把leetcode第二题补了，感觉这道题还挺简单的一、题目两数之和：给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。示例：示例给定 nums = [2, 7, 11, 15], target = 9因为 nums[0] + nums[1] = 2 + 7 = 9所以返回 [0, 1]二、我的答案/** *. Definition for singly-linked list. *. function ListNode(val) { *. this.val = val; *. this.next = null; . } // *. @param {ListNode} l1 . @param {ListNode} l2 . @return {ListNode} /var addTwoNumbers = function(l1, l2) { function ListToArray(list) { if(list.next) { return [list.val, …ListToArray(list.next)] } else { return [list.val] } } function sumArray(arr1, arr2) { if(arr1.length < arr2.length) { let arr = [] arr = arr1 arr1 = arr2 arr2 = arr } let littleLen = arr2.length let i =0 for(; i < littleLen; i++) { arr1[i] += arr2[i] if(arr1[i] >= 10) { arr1[i] -= 10 arr1[i + 1] ? arr1[i + 1]++ : arr1[i+1] =1 } } for(; i < arr1.length; i++ ) { if(arr1[i] >= 10) { arr1[i] -= 10 arr1[i + 1] ? arr1[i + 1]++ : arr1[i+1] =1 } } return arr1.reverse() } function ArrayToList(arr) { if(arr.length > 0) { let node = new ListNode(arr.pop()) node.next = ArrayToList(arr) return node } else { return null } } return ArrayToList(sumArray(ListToArray(l1),ListToArray(l2))) };计算两个链表表示的数的和，统共分三步：把冰箱门打开 链表转数组；两个数组相加得到和数组；和数组转链表我的写法答案简单易懂，就不做解释，这里说一下写的时候碰到一个坑关于第二步两个数组相加，一开始的思路并不是这样的，而是转成String再转Number相加再转回来，那么这个思路折哪儿了呢，有一个测试用例是[1,0,0,0,0,0,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]和[5,6,4]，转成Number相加得1e+30，没错，万恶的弱类型，查询能不能不转换，未果，就只能遍历各数位相加了这题一开始没懂啥意思，懂了之后思路还挺清晰的，击败33.45%，嘛，喜闻乐见，看看大手子们是咋写的吧三、优秀答案/ * Definition for singly-linked list. * function ListNode(val) { * this.val = val; * this.next = null; * } // * @param {ListNode} l1 * @param {ListNode} l2 * @return {ListNode} */var addTwoNumbers = function(l1, l2, curr = 0) { if(l1 === null && l2 === null) { if(curr) return new ListNode(curr) else return null; } else { if(l1 == null) l1 = new ListNode(0) if(l2 == null) l2 = new ListNode(0) let nextVal = (l2.val || 0) + (l1.val || 0) + curr curr = 0 if(nextVal > 9) { curr = 1 nextVal -= 10 } l1.val = nextVal l1.next = addTwoNumbers(l1.next, l2.next, curr) return l1 }}; 这个是我看到的最优秀的答案，本地跑击败91%，甩我不知道几条街，看各种优秀答案总是能刷新认知，来看他的思路首先他把函数改了，函数的本意是相加两个链表，他改成了相加两个节点，参数中curr的意思是上一组节点相加是否进位这什么命名再来看函数内，if部分的代码意为处理最后的边界情况，例[1],[9,9,9,9],即遍历完两个链表之后，如果上一次遍历有进位，则new一个节点else内则是主要的节点相加部分，其中 if(l1 == null) l1 = new ListNode(0) if(l2 == null) l2 = new ListNode(0) let nextVal = (l2.val || 0) + (l1.val || 0) + curr(l2.val || 0)明显是多余的，我猜他本来写的是let nextVal = (l2.val || 0) + (l1.val || 0) + curr但是执行发现null点不出val，就加了上面的判断不过下面的没删，不精简代码差评。剩下的逻辑就显而易见了，进位什么的，不过这种同步遍历真的很巧妙，我怎么就是学不会/捂脸四、路漫漫其修远兮看优秀答案的最后三行，怎么总感觉好像可以用尾调用优化一下，有空看一下，今天这篇博客到此为止，下面该做的第四题难度为hard，害怕之余突然有点期待看到各种神仙解法/捂脸。谢谢阅读(^_^)THE END ...

写在前面这几天断断续续做了题目，也在慢慢体会一些数据思维。终于不用边做视频边写题目啦开心把这几天的题解发一下认真做题的分割线第一题977. 有序数组的平方难度：简单给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。我的题解：class Solution(object): def sortedSquares(self, A): """ :type A: List[int] :rtype: List[int] """ result = [0]*len(A) m = 0 n = k = len(A)-1 while m <= n: if A[m]**2 < A[n]**2: result[k] = A[n]**2 n = n -1 else: result[k] = A[m]**2 m = m + 1 k = k - 1 return result我的思路：这题参考了思路，有点类似之前做过的一题，因为可能存在负数，而且为了减小循环长度，分别从两头来进行计算判断，并判断最大值，从数组的末尾开始计入。第二题461. 汉明距离难度：简单两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。给出两个整数x和y，计算它们之间的汉明距离。我的题解：class Solution(object): def hammingDistance(self, x, y): """ :type x: int :type y: int :rtype: int """ return (bin(x^y)).count(‘1’)我的思路：这题用异或，判断二进制下剩余的1即可。第三题121. 买卖股票的最佳时机难度：简单给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。我的题解：class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ min_p, max_p = 999999, 0 for i in range(len(prices)): min_p = min(min_p, prices[i]) max_p = max(max_p, prices[i] - min_p) return max_p我的思路：为了获取最大的利润，我们必须找到最低的价格，并用当前日期的价格减去最低价格，获得利润。这题也是动态规划思路，最关键要找到最低价格是我们必须判断的点，接着判断最大的利润值，不断进行比对。第四题122. 买卖股票的最佳时机 II难度：简单给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。我的题解：class Solution(object): def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ profit = 0 for i in range(len(prices)-1): if prices[i+1] - prices[i] > 0: profit += prices[i+1] - prices[i] return profit我的思路：这题需要考虑到，1.当天卖出后可以当天继续买入；2.为了买卖尽可能多次，当后来日期的金额>买入日期的时候，即做卖出动作，获取收益。第五题557. 反转字符串中的单词 III难度：简单给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。我的题解：class Solution(object): def reverseWords(self, s): """ :type s: str :rtype: str """ l = s.split(" “) return " “.join(map(lambda x:x[::-1],l))我的思路：这题参考了评论里的方案，python似乎在字符串的处理上有先天的优势。顺便复习了下知识点：join 用于连接字符串 “-".join([a,b]）map map(函数，需要处理的对象）lambda表达式 匿名函数，一目了然的输入和输出[:]数组默认参数为0和len-1，等于复制一份数组，即a[:]=a[::-1] 当步长小于0的时候，默认缺省值为-1和len-1,即a[::-1] = a[len(a)-1👎-1]，即逆序遍历第六题231. 2的幂难度：简单给定一个整数，编写一个函数来判断它是否是 2 的幂次方我的题解：class Solution(object): def isPowerOfTwo(self, n): "”” :type n: int :rtype: bool "”" if n == 0: return False if n == 1: return True if n % 2 == 1: return False elif n == 2: return True else: return self.isPowerOfTwo(n/2)我的思路：这题用了非常暴力的方法，但是还是提交错了两次，少判断了为0和1的情况。因为自己写的递归，就非常的开心…emmm递归栈有趣但是效率不太高总结一下 ...

Fibonacci Number题目链接509. Fibonacci Number题目分析斐波那契数列应该不用我多说了吧？ 是个经典的递归问题。递归有两个条件。 一个是终止条件。要不然会无限递归下去。 另一个是自己调自己。这才叫递归。思路因为该数列中，当前数字为前两项之和，所以要计算前一项的“前两项之和”和前前一项的“前两项之和”。但，当当前为第1项或第2项时，没有前一项或前前一项。此时第1项返回0，第2项返回1即可。最终代码<?phpclass Solution { function fib($N) { if($N == 0){ return 0; } if($N == 1){ return 1; } return $this->fib($N-1) + $this->fib($N-2); }}若觉得本文章对你有用，欢迎用爱发电资助。

写在前面的话感觉做题越多遇到的写法越多，有种跃跃欲试的感觉~认真做题第一题70. 爬楼梯难度：简单假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？注意：给定n是一个正整数。我的题解：class Solution(object): def climbStairs(self, n): """ :type n: int :rtype: int """ old = 1 new = 1 for i in range(2,n+1): old,new = new,new+old return newv我的思路：这题是一个标准的动态规划的题目，第二步所需要的步数其实是基于第一步，第三步则基于第二步。用笔计算就可以看出，有一定的规律，新的一步的最优解等于前面一步的最优解+之前所有步数的最优解。不过可能还没有抓到动态规划的真谛，总觉得哪里需要再校正下思路。第二题771. 宝石与石头难度：简单给定字符串J代表石头中宝石的类型，和字符串S代表你拥有的石头。S中每个字符代表了一种你拥有的石头的类型，你想知道你拥有的石头中有多少是宝石。J中的字母不重复，J和S中的所有字符都是字母。字母区分大小写，因此"a"和"A"是不同类型的石头。我的题解：class Solution(object): def numJewelsInStones(self, J, S): """ :type J: str :type S: str :rtype: int """ num = 0 if not J or not S: return 0 map = {} for i in J: map[i] = 1 for j in S: if j in map: num += map[j] return num我的思路：这题用了hash表的思路，将J里的每个字母单独存成哈希表的一个键，且对应的值为1。这样当S进行搜索的时候，对应将值相加即可得到结果。第三题709. 转换成小写字母难度：简单实现函数 ToLowerCase()，该函数接收一个字符串参数 str，并将该字符串中的大写字母转换成小写字母，之后返回新的字符串。我的题解：class Solution(object): def toLowerCase(self, str): """ :type str: str :rtype: str """ s = list(str) map = {‘A’:‘a’,‘B’:‘b’,‘C’:‘c’,‘D’:’d’,‘E’:’e’,‘F’:‘f’,‘G’:‘g’,‘H’:‘h’,‘I’:‘i’,‘J’:‘j’,‘K’:‘k’,‘L’:’l’,‘M’:’m’,‘N’:’n’,‘O’:‘o’,‘P’:‘p’,‘Q’:‘q’,‘R’:‘r’,‘S’:’s’,‘T’:’t’,‘U’:‘u’,‘V’:‘v’,‘W’:‘w’,‘X’:‘x’,‘Y’:‘y’,‘Z’:‘z’} for i in range(len(s)): if s[i] in map: s[i] = map[s[i]] s1=’’.join(s) return s1 我的思路：这题….大概写法非常土了….emmm认真的写了个字典，然后对应的写一下，效率也还可以，但是只能用于数量少的情况下，还可以看下有没有其他的写法。第四题62. 不同路径难度：中等我的题解：class Solution(object): def uniquePaths(self, m, n): """ :type m: int :type n: int :rtype: int """ dp = [[0 for _ in range(m)] for _ in range(n)] #建立二维数组 for i in range(n): for j in range(m): if i ==0 or j ==0: dp[i][j] = 1 else: dp[i][j] = dp[i-1][j] + dp[i][j-1] return dp[n-1][m-1]我的思路：非常粗暴的画了网格图，然后发现了规律，dp[i][j] = dp[i-1][j] + dp[i][j-1],和少棉在讨论的时候，非常真挚的为了为什么他知道需要是左边的值加上上方的值，给的说法是最优解的目标就是从左上角到该位置的最优解，局部最优再到全局最优。这题也是动态规划的题目，目标总是要分解为子问题。总结看《算法图解》的时候，涉及动态规划的小结中有这样的每种动态规划解决方案都涉及网格。单元格中的值通常就是你要优化的值每个单元格都是一个子问题，因为你需要考虑如何将问题分解为子问题。 ...

Robot Return to Origin题目链接657. Robot Return to Origin题目分析输入一串指令操作机器人，判断执行完指令后，能否回到原点。思路判断向上移动的次数是否等于向下移动的次数，且向左次数是否等于向右次数。先用array_count_values计算元素个数。 再直接U个数和D个数是否相等，L个数和R个数是否相等即可。但是，如果在指令中没有出现所有4种方向的话，在判断时会获取不到数值。 因此还要和给定默认的UDLR出现次数。用array_merge即可。最终代码<?phpclass Solution { function judgeCircle($moves) { $moves = array_count_values(str_split($moves)); $moves = array_merge([‘U’=>0,‘L’=>0,‘R’=>0,‘D’=>0],$moves); return ($moves[‘U’]==$moves[‘D’])&&($moves[‘L’]==$moves[‘R’]); }}若觉得本文章对你有用，欢迎用爱发电资助。

【LeetCode篇】 First Missing PositiveIDE: C++ (C)author : MinRamcreate : 03/19/2019update: 03/19/2019题目First Missing Positive - LeetCodeGiven an unsorted integer array, find the smallest missing positive integer.Your algorithm should run in O(n) time and uses constant extra space.思路大体思路，简易桶。 直接以值为Key，发散到数组中，通过Swap实现。伪代码判断Current是否满足一下情况，若满足则2，反之3正数小于答案的最大值 $（所求的正数 \leq 数组长度）$将Current 与Num[Current - 1] 交换。下一位，重复1，直到数组遍历结束。图片流代码实现// 优化io流static const auto __ = { ios::sync_with_stdio(false); cin.tie(nullptr); return nullptr;}();class Solution {public: int firstMissingPositive(vector<int>& nums) { int numsLen = nums.size(); // 简易桶 for (int i = 0 ; i < numsLen; ){ if (nums[i] != (i + 1) && nums[i] >= 1 && nums[i] <= numsLen && nums[nums[i] - 1] != nums[i]) swap(nums[i], nums[nums[i] - 1]); else ++i; } // 遍历查值 for (int i = 0; i < numsLen; ++i) if (nums[i] != (i + 1)) return i + 1; // 最大值 return numsLen + 1; }};参考[1] Longest palindromic substring - LeetCode反馈与建议E-mail: minfysui@gmail.comQ Q: MinRam ...

写在前面的话慢慢转变思路，不再死磕不会做的题，思路可以先借鉴，但是一定要吃透透。上周末看完看完了《算法图解》，感觉对一些题目的思路有比较大的帮助，但是还是要在实践中理解。认真做题的分割线第一题152. 乘积最大子序列难度：中等给定一个整数数组nums，找出一个序列中乘积最大的连续子序列（该序列至少包含一个数）。我的题解：class Solution(object): def maxProduct(self, nums): """ :type nums: List[int] :rtype: int """ length = len(nums) maxsum = [0 for _ in range(length)] minsum = [0 for _ in range(length)] maxsum[0] = minsum[0] = nums[0] # 限定最大最小值 dp = nums[0] #当前状态 for i in range(1,len(nums)): maxsum[i] = max(maxsum[i-1]nums[i],minsum[i-1]nums[i],nums[i]) minsum[i] = min(maxsum[i-1]nums[i],minsum[i-1]nums[i],nums[i]) dp = max(dp,maxsum[i]) return dp我的思路：这题做了两次，主体思路为：每次都找到乘积中的最大正值和最小负值，因为绝对值最大的两个数在下一次计算中才有可能成为最大值。（毕竟题目没有限制非负数）第一次的时候报错的原因是，我记录了每次的maxsum和minsum，没有记录上一次循环留下的值。然鹅，上一次的状态会影响到下一次的状态，所以必须记住上一步的最优解。可以判断是个NP问题，但是动态规划还得多多练习第二题202. 快乐数难度：简单编写一个算法来判断一个数是不是“快乐数”。一个“快乐数”定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。我的题解：class Solution(object): def isHappy(self, n): """ :type n: int :rtype: bool """ l = [] while 1: l.append(n) n = sum([int(i)2 for i in str(n)]) if n == 1: return True elif n in l: return False我的思路：条件一：要判断每次的值是否各位平方总和为1，得出是快乐数的结论；条件二：为了得出非快乐数的结论，这个数可能会陷入循环，那么就要记录下每轮的值，并进行比对。其他：在评论中发现了一个很有趣的算法，就是用dict记录下肯定会循环的数字的词典，当遇到相关数字的时候就可以跳出了。一般为{4,16,37,58,89,145,42,20}第三题204. 计数质数难度：简单统计所有小于非负整数 n 的质数的数量。我的题解：class Solution(object): def countPrimes(self, n): """ :type n: int :rtype: int """ if n < 3: return 0 else: output = [1]*n output[0],output[1] = 0,0 for i in range(2,int(n0.5+1)): if output[i] == 1: m = i**2 while m < n: output[m] = 0 m += i return sum(output)我的思路：这个算法借鉴了评论里的一个炒鸡有趣的算法，默认查询是否质数的时候，我们习惯用循环判断，这样肯定会超时。而这个算法呢，叫做厄拉多塞筛法，他给了如下解释：比如说求20以内质数的个数,首先0,1不是质数.2是第一个质数,然后把20以内所有2的倍数划去.2后面紧跟的数即为下一个质数3,然后把3所有的倍数划去.3后面紧跟的数即为下一个质数5,再把5所有的倍数划去.以此类推包括他的题解的写法也很有趣，但是我还没弄明白output[ii:n:i] = [0] * len(output[ii:n:i])这一句的意思，还要琢磨下，所以用的是循环的写法。def countPrimes(self, n: int) -> int: if n < 3: return 0 else: # 首先生成了一个全部为1的列表 output = [1] * n # 因为0和1不是质数,所以列表的前两个位置赋值为0 output[0],output[1] = 0,0 # 此时从index = 2开始遍历,output[2]==1,即表明第一个质数为2,然后将2的倍数对应的索引 # 全部赋值为0. 此时output[3] == 1,即表明下一个质数为3,同样划去3的倍数.以此类推. for i in range(2,int(n**0.5)+1): if output[i] == 1: output[ii:n:i] = [0] * len(output[ii:n:i]) # 最后output中的数字1表明该位置上的索引数为质数,然后求和即可. return sum(output)总结小李今天的做题，是痛并快乐着的！ ...

题目：Given a 2D board and a list of words from the dictionary, find allwords in the board.Each word must be constructed from letters of sequentially adjacentcell, where “adjacent” cells are those horizontally or verticallyneighboring. The same letter cell may not be used more than once in aword.Example:Input: words = [“oath”,“pea”,“eat”,“rain”] and board = [ [‘o’,‘a’,‘a’,’n’], [’e’,’t’,‘a’,’e’], [‘i’,‘h’,‘k’,‘r’], [‘i’,‘f’,’l’,‘v’] ]Output: [“eat”,“oath”] Note: You may assume that all inputs areconsist of lowercase letters a-z.这道题是79题word search的follow up，如果按照那道题的做法我们在二维数组中寻找每一个单词那么一定会超时，因为每个单词都要搜索一次会产生很多重复搜索，所以我们想到的是从头到尾遍历二维数组，在遍历过程中dfs，那么在这个过程中一定把所有可能组成的单词都遍历了一遍，所以我们想到可以用一个hashset来存储需要搜索的单词，然后在dfs过程中把每个产生的单词在hashset中寻找。代码如下：class Solution { List<String> res = new ArrayList<>(); HashSet<String> set = new HashSet<>(); boolean[][] visited; public List<String> findWords(char[][] board, String[] words) { visited = new boolean[board.length][board[0].length]; for (String word : words) set.add(word); for (int i = 0; i < board.length; i ++) { for (int j = 0; j < board[0].length; j ++) { dfs(board, “”, i, j); } } return res; } public void dfs(char[][] board, String cur, int x, int y) { if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y]) return; char c = board[x][y]; if (set.contains(cur+c)) { res.add(cur+c); set.remove(cur+c); } visited[x][y] = true; dfs(board, cur+c, x+1, y); dfs(board, cur+c, x-1, y); dfs(board, cur+c, x, y+1); dfs(board, cur+c, x, y-1); visited[x][y] = false; }}但不幸的是这种方法还是会超时，所以我们想能否有种方法能让我们提前结束backtrack呢，如果在所有单词中都没有这个前缀我们就可以提前结束backtarcking。因此想到可以用Trie来实现，代码如下：class Solution { class TrieNode { TrieNode[] next = new TrieNode[26]; String word; public TrieNode() {} } TrieNode buildTrie(String[] words) { TrieNode root = new TrieNode(); for (String word : words) { TrieNode p = root; for (char c : word.toCharArray()) { if (p.next[c-‘a’] == null) p.next[c-‘a’] = new TrieNode(); p = p.next[c-‘a’]; } p.word = word; } return root; } List<String> res = new ArrayList<>(); boolean[][] visited; public List<String> findWords(char[][] board, String[] words) { visited = new boolean[board.length][board[0].length]; TrieNode root = buildTrie(words); for (int i = 0; i < board.length; i ++) { for (int j = 0; j < board[0].length; j ++) { if (root.next[board[i][j]-‘a’] == null) continue; dfs(board, root, i, j); } } return res; } public void dfs(char[][] board, TrieNode node, int x, int y) { if (x == board.length || x < 0 || y == board[0].length || y < 0 || visited[x][y]) return; char c = board[x][y]; if (node.next[c-‘a’] == null) return; if (node.next[c-‘a’].word != null) { res.add(node.next[c-‘a’].word); //如果找到了这个单词就把它设成null，避免重复的结果 node.next[c-‘a’].word = null; } visited[x][y] = true; dfs(board, node.next[c-‘a’], x+1, y); dfs(board, node.next[c-‘a’], x-1, y); dfs(board, node.next[c-‘a’], x, y+1); dfs(board, node.next[c-‘a’], x, y-1); visited[x][y] = false; }} ...

Flipping an Image题目链接832. Flipping an Image题目分析题目要求把一个只有0和1的二维数组中的0和1取反变为1和0。即1变0，0变1。且需要把每行数据倒序过来。思路今天我尝试换一种方法描述思路。输入是一个二维数组，那么我们需要先降为一维。这个可以用foreach完成。接下来需要完成替换。我本来想用取反操作符完成的，但是如果开头为1的话，需要补0。我懒得补0，所以我用implode先转换成字符串了。str_replace([‘0’,‘1’,‘2’],[‘2’,‘0’,‘1’],implode(’’,$row));这里我先把0换成2，1换成0，再把2换成1的。如果直接把0替换成1，1替换成0的话，最后会全0。因为他是先完成第一个替换对，再重新遍历字符串替换第二个替换对的。再用str_split把字符串变会数组。最后，用array_reverse把数组顺序倒转过来即可。当然，也可以先用strrev先反转字符串，再str_split。这样就完成了每一行的处理。最终代码<?phpclass Solution { function flipAndInvertImage($A) { $flipped = []; foreach($A as $row){ $flipped[] = array_reverse(str_split(str_replace([‘0’,‘1’,‘2’],[‘2’,‘0’,‘1’],implode(’’,$row)))); } return $flipped; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目：Given a 2D board and a word, find if the word exists in the grid.The word can be constructed from letters of sequentially adjacentcell, where “adjacent” cells are those horizontally or verticallyneighboring. The same letter cell may not be used more than once.Example:board = [ [‘A’,‘B’,‘C’,‘E’], [‘S’,‘F’,‘C’,‘S’], [‘A’,‘D’,‘E’,‘E’] ]Given word = “ABCCED”, return true. Given word = “SEE”, return true.Given word = “ABCB”, return false.这是一道搜索题，用backtracking做，问题就是怎样设计这个回溯过程。我们需要的就是在这个二维数组里面一个个寻找每个字符，所以dfs的终止条件是当我们把每个字符全部搜索了，也就是index==word.length。因为每个字符只能使用一次所以我们还需要一个visited数组来记录当前元素是否被访问过，如果我们找到了和当前搜索的字符相匹配的元素，我们就要上下左右搜索四个方向。这么看来思路还是很清晰的，但是我在做这一题时被几点困扰：1.我们需要遍历二维数组，但同时我们又需要移动移动被搜索字符串的index，一开始我是把遍历二维数组和移动字符串的index写在了同一个dfs的recursion里面然后接下去我就没办法写了，看了discuss之后才知道应该把遍历二维数组写在主函数里面，让它来调用dfs。2.选择下一个可以走的adjacent，我一开始还在想需不需要用一个list来存储每一步可以走的adjacent，这样的话就太麻烦了，还需要分情况讨论，但其实是没有必要的。我们把这些判断都加在recursion的终止条件里面就好了。代码如下：class Solution { public boolean exist(char[][] board, String word) { int m = board.length, n = board[0].length; boolean[][] visited = new boolean[m][n]; for (int i = 0; i < board.length; i ++) { for (int j = 0; j < board[0].length; j ++) { if (word.charAt(0) == board[i][j] && dfs(board, word, visited, 0, i, j)) return true; } } return false; } public boolean dfs(char[][] board, String word, boolean[][] visited, int index, int row, int col) { if (index == word.length()) return true; if (row == board.length || row < 0 || col == board[0].length || col < 0 || visited[row][col] || word.charAt(index) != board[row][col]) return false; visited[row][col] = true; if (dfs(board, word, visited, index+1, row+1, col) || dfs(board, word, visited, index+1, row, col+1) || dfs(board, word, visited, index+1, row-1, col) || dfs(board, word, visited, index+1, row, col-1)) return true; visited[row][col] = false; return false; }} ...

题目给定一个单链表，其中的元素按升序排序，将其转换为高度平衡的二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。示例:给定的有序链表： [-10, -3, 0, 5, 9],一个可能的答案是：[0, -3, 9, -10, null, 5], 它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5题解这道题和上一道类似,改动是把数组改成了链表。链表求中间节点的经典方法是快慢指针,慢指针每次走一步,快指针每次都走两步，这样快指针走到链表结尾的时候，慢指针就指向中间节点。这样就可以把问题转化为递归的子问题进行求解。class Solution { public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } return helper(head, null); } public TreeNode helper(ListNode head, ListNode tail) { if (head == null || head == tail) { return null; } ListNode slow = head; ListNode fast = head; while (fast.next != tail && fast.next.next != tail) { fast = fast.next.next; slow = slow.next; } TreeNode current = new TreeNode(slow.val); current.left = helper(head, slow); current.right = helper(slow.next, tail); return current; } }这道题目还有一个比较巧妙的办法是利用BST中序遍历是升序的性质，去求解，具体看代码注释。class Solution { private ListNode node; public TreeNode sortedListToBST(ListNode head) { if (head == null) { return null; } int size = 0; ListNode runner = head; node = head; while (runner != null) { runner = runner.next; size++; } // 先计算有几个节点 return inorderHelper(0, size - 1); } public TreeNode inorderHelper(int start, int end) { if (start > end) { return null; } // 划分左右子树 int mid = start + (end - start) / 2; TreeNode left = inorderHelper(start, mid - 1); // 中序遍历 TreeNode treenode = new TreeNode(node.val); treenode.left = left; node = node.next; TreeNode right = inorderHelper(mid + 1, end); treenode.right = right; return treenode; }}最关键的一个步骤是node = node.next 这步的意思是基于：在BST中任意子树，它的中序遍历的结果如果存在一个链表中，一定是一个升序的，可以一一对应上，所以中序遍历完（这里是构建完）一个节点链表+1。热门阅读【Leetcode】108. 将有序数组转换为二叉搜索树【Leetcode】107. 二叉树的层次遍历 II【Leetcode】105. 从前序与中序遍历序列构造二叉树【Leetcode】106. 从中序与后序遍历序列构造二叉树手撕代码QQ群：805423079， 群密码：1024 ...

DescriptionOne way to serialize a binary tree is to use pre-order traversal. When we encounter a non-null node, we record the node’s value. If it is a null node, we record using a sentinel value such as #. 9 / \ 3 2 / \ / \ 4 1 # 6/ \ / \ / # # # # # #For example, the above binary tree can be serialized to the string “9,3,4,#,#,1,#,#,2,#,6,#,#”, where # represents a null node.Given a string of comma separated values, verify whether it is a correct preorder traversal serialization of a binary tree. Find an algorithm without reconstructing the tree.Each comma separated value in the string must be either an integer or a character ‘#’ representing null pointer.You may assume that the input format is always valid, for example it could never contain two consecutive commas such as “1,,3”.Example 1:Input: “9,3,4,#,#,1,#,#,2,#,6,#,#“Output: trueExample 2:Input: “1,#“Output: falseExample 3:Input: “9,#,#,1"Output: false描述序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。 9 / \ 3 2 / \ / \ 4 1 # 6/ \ / \ / # # # # # #例如，上面的二叉树可以被序列化为字符串 “9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 ‘#’ 。你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 “1,,3” 。示例 1:输入: “9,3,4,#,#,1,#,#,2,#,6,#,#“输出: true示例 2:输入: “1,#“输出: false示例 3:输入: “9,#,#,1"输出: false思路使用栈，如果两个 # 连续出现，根据前序遍历的定义，前面一个一定是叶子节点，我们将这两个 # 弹出，然后将叶子节点重置为 None (即#)，如此循环下去。如果满足前序遍历，那么最后栈中有且仅有一个元素，且是 # 。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-03-17 09:44:27# @Last Modified by: 何睿# @Last Modified time: 2019-03-17 10:03:55class Solution: def isValidSerialization(self, preorder: str) -> bool: # stack：用于记录遍历到的节点值 # count：stack 中剩余的节点个数 stack, count = [], 0 for item in preorder.split(”,”): stack.append(item) count += 1 # 如果 stack 中末位两个元素是 #，说明这两个节点前面是一个叶子节点 # 将两个 # 弹出 ，将叶子节点置为 None，即 # # 如果是前序遍历，那么 stack 最后一定会剩下一个 # while count > 1 and stack[-1] == “#” and stack[-2] == “#”: stack.pop() stack.pop() if not stack: return False stack[-1] = “#” count -= 2 # 当且仅当 stack 中只剩下一个元素且为 # 时返回 True. return True if len(stack) == 1 and stack[0] == “#” else False源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明. ...

Sort Array By Parity题目链接905. Sort Array By Parity题目分析这个题目非常简单。要求把数组重新排序成偶数在前，奇数在后。思路把数组拆分成奇偶两组，再拼接即可。最终代码<?phpclass Solution { function sortArrayByParity($A) { $odd = array_filter($A,function($var){return ($var & 1);}); $even = array_filter($A,function($var){return (!($var & 1));}); return $even + $odd; }}若觉得本文章对你有用，欢迎用爱发电资助。

题目给定一个二叉树，返回其节点值自底向上的层次遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）例如：给定二叉树 [3,9,20,null,null,15,7], 3 / \ 9 20 / \ 15 7返回其自底向上的层次遍历为：[ [15,7], [9,20], [3]]题解利用层次遍历,层次遍历的时候进入下一层的时候记录一下当前队列中有几个元素。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); List<Integer> levelVal = new LinkedList<>(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } levelVal.add(current.val); size–; } res.add(0, levelVal); } return res; }}用递归去做。用递归去做的关键在于需要把层数也带上。class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); if (root == null) { return res; } helper(root, res, 0); return res; } public void helper(TreeNode root, List<List<Integer>> res, int depth) { if (root == null) { return; } if (depth == res.size()) { res.add(0, new LinkedList<>()); } List<Integer> current = res.get(res.size() - depth - 1); helper(root.left, res, depth + 1); helper(root.right, res, depth + 1); current.add(root.val); }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树手撕代码QQ群：805423079， 群密码：1024 ...

Big Countries题目链接595. Big Countries题目分析这道题是个SQL题。要求返回国土面积大于300万平方公里或者人口多于2500万人的国家的名称、人口、面积。思路国土面积大于300万平方公里：area>3000000人口多于2500万人：population>25000000返回名称、人口、面积：select name, population, area最终代码# Write your MySQL query statement belowselect name, population,area from worldwhere area>3000000 or population>25000000;若觉得本文章对你有用，欢迎用爱发电资助。

DescriptionGiven a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n] inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.Example 1:Input: nums = [1,3], n = 6Output: 1 Explanation:Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.Now if we add/patch 2 to nums, the combinations are: [1], [2], [3], [1,3], [2,3], [1,2,3].Possible sums are 1, 2, 3, 4, 5, 6, which now covers the range [1, 6].So we only need 1 patch.Example 2:Input: nums = [1,5,10], n = 20Output: 2Explanation: The two patches can be [2, 4].Example 3:Input: nums = [1,2,2], n = 5Output: 0描述给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。示例 1:输入: nums = [1,3], n = 6输出: 1 解释:根据 nums 里现有的组合 [1], [3], [1,3]，可以得出 1, 3, 4。现在如果我们将 2 添加到 nums 中， 组合变为: [1], [2], [3], [1,3], [2,3], [1,2,3]。其和可以表示数字 1, 2, 3, 4, 5, 6，能够覆盖 [1, 6] 区间里所有的数。所以我们最少需要添加一个数字。示例 2:输入: nums = [1,5,10], n = 20输出: 2解释: 我们需要添加 [2, 4]。示例 3:输入: nums = [1,2,2], n = 5输出: 0思路贪心算法，每次都取最小的值把范围扩大更大。对于给定的一个数组，假设前 k 个数字的和为 tmp （前 k 个数为 num[0] ~ num[k-1]），也就是说从 0 到 tmp 的所有的数我们都可以取到。我们要扩大这个范围，如果 num[k] 比 tmp + 1大，如果这个时候直接把 num[k] 添加到数组中，那么 [tmp+1,num[k])之间的和是无法构造得到的。于是我们将此时的边界 tmp + 1 作为需要的新的数添加到数组中；如果num[k] 小于等于 tmp + 1，我们直接把 num[k] 添加的数组中扩边界。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-03-14 20:40:22# @Last Modified by: 何睿# @Last Modified time: 2019-03-14 21:57:33class Solution: def minPatches(self, nums: [int], n: int) -> int: # tmp 表示所有数字的和，count表示需要添加数字，i 为索引 # 定义[0,8) 8 为和的边界 tmp, count, i = 0, 0, 0 # 循环条件 while tmp < n: # 如果 num[i] 在当前和的范围之内，那么把 num[i] 添加到 # 当前的和范围内是最经济的做法 if i < len(nums) and nums[i] <= tmp + 1: tmp += nums[i] i += 1 # 否则，我们需要把当前和的边界的数字作为一个新的数字添加到和中 else: tmp += tmp + 1 count += 1 return count源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明. ...

Unique Morse Code Words题目链接804. Unique Morse Code Words题目分析这个题目要求算出把给定数组中的字符串转换成摩尔斯码后，有多少个不同的摩尔斯码。思路第一步需要把字符串转换成摩尔斯码。$morse = [ “.-”,"-…","-.-.","-..",".","..-.","–.","….","..",".—","-.-",".-..","–", “-.”,"—",".–.","–.-",".-.","…","-","..-","…-",".–","-..-","-.–","–.."];$replaced = [];foreach($words as $word){ $chars = str_split($word); $string = ‘’; foreach($chars as $char){ $string .= $morse[ord($char)-ord(‘a’)]; }}转换完成后存进数组内，再用array_unique函数排除。再count排除结果即可。最终代码<?phpclass Solution { function uniqueMorseRepresentations($words) { $morse = [".-","-…","-.-.","-..",".","..-.","–.","….","..",".—","-.-",".-..","–","-.","—",".–.","–.-",".-.","…","-","..-","…-",".–","-..-","-.–","–.."]; $replaced = []; foreach($words as $word){ $chars = str_split($word); $string = ‘’; foreach($chars as $char){ $string .= $morse[ord($char)-ord(‘a’)]; } $replaced[] = $string; } return count(array_unique($replaced)); }}若觉得本文章对你有用，欢迎用爱发电资助。优化方案直接存为数组的键则可以省去用array_unique去重的步骤。

写在前面的话做做做题，慢慢上手了就觉得刷题速度变快了，果然还是有点笨希望最后一窍快点通吧开始做题第一题169. 求众数难度：简单给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于⌊ n/2 ⌋的元素。你可以假设数组是非空的，并且给定的数组总是存在众数。我的题解：class Solution(object): def majorityElement(self, nums): """ :type nums: List[int] :rtype: int """ value = nums[0] count = 0 for i in nums: if value == i: count = count + 1 else: if count == 0: value = i count = 1 continue count =count - 1 return value 我的思路：这题参考了评论的题解，做了两次，明白了来龙去脉。中心思想就是：按顺序遍历数字，存在不同的数字就抵消相应的count，存在相同数字则增加，最后总能获取到唯一一个不会被抵消全部的数字，就是众数了。第二题136. 只出现一次的数字难度：简单给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？我的题解：class Solution(object): def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ a = 0 for num in nums: a = a ^ num return a我的思路：异或，两个相同的数字的计算结果为0，最后剩余的则为唯一值第三题83. 删除排序链表中的重复元素难度：简单给定一个排序链表，删除所有重复的元素，使得每个元素只出现一次。我的题解：# Definition for singly-linked list.# class ListNode(object):# def init(self, x):# self.val = x# self.next = Noneclass Solution(object): def deleteDuplicates(self, head): """ :type head: ListNode :rtype: ListNode """ a = head if not a: return a while head.next: if head.next.val == head.val and head.next.next == None: head.next = None elif head.next.val == head.val and head.next.next: head.next = head.next.next else: head = head.next return a我的思路：当存在前后节点一致的时候，则前一个节点的next指向后一个节点的next，跳过即可。其他：因为链表的结构指向的是内存，遍历完之后指向最后的节点，所以需要一个a指向头结点。第四题100. 相同的树难度：简单给定两个二叉树，编写一个函数来检验它们是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。我的题解：# Definition for a binary tree node.# class TreeNode(object):# def init(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def isSameTree(self, p, q): """ :type p: TreeNode :type q: TreeNode :rtype: bool """ if not p and not q: return True if p and q: if p.val == q.val: return self.isSameTree(p.left,q.left) and self.isSameTree(p.right,q.right) else: return False else: return False我的思路：递归，主要是判断两个节点的值是否一致，一致的前提下，判断向下的左右节点及更向下是否一致。第五题88. 合并两个有序数组难度：简单给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。说明:初始化 nums1 和 nums2 的元素数量分别为 m 和 n。你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。我的题解：class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ while m>0 and n>0: if nums1[m-1] >=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m -= 1 else: nums1[m+n-1] = nums2[n-1] n -= 1 if n >0 : nums1[:n] = nums2[:n]class Solution(object): def merge(self, nums1, m, nums2, n): """ :type nums1: List[int] :type m: int :type nums2: List[int] :type n: int :rtype: None Do not return anything, modify nums1 in-place instead. """ while m>0 and n>0: if nums1[m-1] >=nums2[n-1]: nums1[m+n-1] = nums1[m-1] m -= 1 else: nums1[m+n-1] = nums2[n-1] n -= 1 if n >0 : nums1[:n] = nums2[:n]我的思路：因为nums1[m+n]为空的部分，所以我们可以从后向前写，判断两个数组的值，更大的数字不断向后挪，挪到一定程度的时候，剩余部分则为更长的数组的剩余未判断部分。第六题104. 二叉树的最大深度难度：简单给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。我的题解：# Definition for a binary tree node.# class TreeNode(object):# def init(self, x):# self.val = x# self.left = None# self.right = Noneclass Solution(object): def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 if root.right is None and root.left is None: return 1 return max(self.maxDepth(root.right),self.maxDepth(root.left))+1 我的思路：递归图上为调用栈的情况，不断向下寻找更远的根节点。基线判断为：节点是否为空递归判断为：节点不为空且左节点或右节点还有值总结最近在看《算法图解》，感觉对递归理解更深一点，但学习之后重要的是实践，还是要多做题。 ...

题目要求Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.Note:The number of people is less than 1,100.ExampleInput:[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]Output:[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]假设有一组人站成一堆，每个人都记录下了自己的高度，以及在自己前面有多少个不比自己矮的人。现在请按照这个信息将这组人放在队列中正确的位置上并返回。思路和代码刚开始我试图用分治法来解决，因为每一个小队列中，高度最矮且站在自己前面的高个最少的人一定位于k位置上。但是这样解决其实复杂化了问题。可以从另一个角度来想，首先我们知道，同等高度的人，其相对位置一定是根据k的值从小到大排列的。即k越大，则该同等高度的人一定在另一个同等高度的人后面。如果我们从高到低将人们插入队列中，可以知道，k的值就该人在当前队列中的下标，如：[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]首先将其按照h和k排序，得出结果：[[7,0],[7,1],[6,1],[5,1],[5,0],[5,2],[4,4]]当前结果队列为[]将[7,0]插入下标为0的位置上 结果队列[[7,0]]将[7,1]插入下标为1的位置上 结果队列[[7,0],[7,1]]将[6,1]插入下标为1的位置上 结果队列[[7,0],[6,1],[7,1]]按照这种规则，依次按照顺序和k的值将数据插入结果队列中代码如下： public int[][] reconstructQueue(int[][] people) { int[][] result = new int[people.length][2]; Arrays.sort(people, new Comparator<int[]>() { @Override public int compare(int[] o1, int[] o2) { return o1[0] == o2[0] ? o1[1] - o2[1] : o2[0] - o1[0]; } }); for(int i = 0 ; i<people.length ; i++) { int pos = people[i][1]; for (int j = i; j > pos; j–) { result[j] = result[j - 1]; } result[pos] = people[i]; } return result; } ...

题目要求Given an 2D board, count how many battleships are in it. The battleships are represented with ‘X’s, empty slots are represented with ‘.’s. You may assume the following rules:You receive a valid board, made of only battleships or empty slots.Battleships can only be placed horizontally or vertically. In other words, they can only be made of the shape 1xN (1 row, N columns) or Nx1 (N rows, 1 column), where N can be of any size.At least one horizontal or vertical cell separates between two battleships - there are no adjacent battleships.Example:X..X…X…XIn the above board there are 2 battleships.Invalid Example:…XXXXX…XThis is an invalid board that you will not receive - as battleships will always have a cell separating between them.Follow up:Could you do it in one-pass, using only O(1) extra memory and without modifying the value of the board?假设有一个2D板，在板上用X表示战舰，已知板上任意两个战舰体之间一定会用.隔开，因此不会出现两个X相邻的情况。现在要求用O(N)的时间复杂度和O(1)的空间复杂度来完成。思路和代码这题的思路非常清晰，我们只需要判断哪个X是战舰头即可，当我们遇到战舰头时，就将总战舰数加一，其余时候都继续遍历。战舰头即战舰的左侧和上侧没有其它的X。 public int countBattleships(char[][] board) { int count = 0; if(board == null || board.length == 0 || board[0].length == 0) return count; for(int i = 0 ; i<board.length ; i++) { for(int j = 0 ; j<board[i].length ; j++) { if(board[i][j] == ‘X’) { if((i > 0 && board[i-1][j] == ‘X’) || (j > 0 && board[i][j-1] == ‘X’)) { continue; } count++; } } } return count; } ...

【Leetcode】146.LRU缓存机制【Leetcode】108.将有序数组转换为二叉搜索树【Leetcode】107.二叉树的层次遍历【Leetcode】106. 从中序与后序遍历序列构造二叉树【Leetcode】105. 从前序与中序遍历序列构造二叉树【Leetcode】101.镜像二叉树【Leetcode】100.相同的树

题目要求Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).Example 1:rectangles = [ [1,1,3,3], [3,1,4,2], [3,2,4,4], [1,3,2,4], [2,3,3,4]]Return true. All 5 rectangles together form an exact cover of a rectangular region.Example 2:rectangles = [ [1,1,2,3], [1,3,2,4], [3,1,4,2], [3,2,4,4]]Return false. Because there is a gap between the two rectangular regions.Example 3:rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [3,2,4,4]]Return false. Because there is a gap in the top center.Example 4:rectangles = [ [1,1,3,3], [3,1,4,2], [1,3,2,4], [2,2,4,4]]Return false. Because two of the rectangles overlap with each other.用一个二维数组来表示一堆矩形，二维数组中的每一行分别记录矩形左下角和右上角的坐标。试判断这些矩形拼接成的新的图形是否还是一个矩形。如果矩形存在重合，则不构成矩形，见图例4.思路和代码这是一道纯粹的考验思维的一道题目。首先我们知道，这些矩形如果能够拼接成一个大的矩形，那么大的矩形的左下角坐标一定是所有矩形中最小的x1和y1值构成的，同理，右上角坐标一定是由最大的x2和y2的值构成的。该理想情况下矩形的面积应当等于所有矩形的面积之和。一旦不相等，则一定无法构成大的矩形。其次，光判断面积并不足够，可以这样三个矩形构成的图形[1,1,2,2],[2,2,3,3],[2,1,3,3]。可以看到该图形的理想矩形就是一个2*2的正方形，它的面积与所有的小矩形的和相等，但是这些小矩形并没有构成该理想的矩形。那么我们能用什么方式来过滤掉这种矩形呢。只能从矩形的顶点入手了。我们知道，任何一个能够构成理想矩形的小矩形，一定会有顶点的重合，直到只剩下四个重合度为1的点，即大矩形的四个顶点。其它的所有顶点都应当有另一个矩形与其重合。因此我们只需要留下所有度为1的顶点，判断其是否都是大矩形的四个顶点即可。代码如下：public boolean isRectangleCover(int[][] rectangles) { if(rectangles==null || rectangles.length == 0 || rectangles[0].length == 0) return false; int areaSum = 0; int x1 = Integer.MAX_VALUE; int x2 = Integer.MIN_VALUE; int y1 = Integer.MAX_VALUE; int y2 = Integer.MIN_VALUE; Set<String> points = new HashSet<>(rectangles.length * 4); for(int[] rectangle : rectangles) { x1 = Math.min(rectangle[0], x1); x2 = Math.max(rectangle[2], x2); y1 = Math.min(rectangle[1], y1); y2 = Math.max(rectangle[3], y2); areaSum += (rectangle[0] - rectangle[2]) * (rectangle[1] - rectangle[3]); String s1 = rectangle[0] + " " + rectangle[1]; String s2 = rectangle[0] + " " + rectangle[3]; String s3 = rectangle[2] + " " + rectangle[1]; String s4 = rectangle[2] + " " + rectangle[3]; if (!points.add(s1)) { points.remove(s1); } if (!points.add(s2)) { points.remove(s2); } if (!points.add(s3)) { points.remove(s3); } if (!points.add(s4)) { points.remove(s4); } } if(!points.contains(x1 + " " + y1) || !points.contains(x1 + " " + y2) || !points.contains(x2 + " " + y1) || !points.contains(x2 + " " + y2) || points.size() != 4) return false; return areaSum == (x2 - x1) * (y2 - y1); } ...

题目要求Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.Note:The length of num is less than 10002 and will be ≥ k.The given num does not contain any leading zero.Example 1:Input: num = “1432219”, k = 3Output: “1219"Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.Example 2:Input: num = “10200”, k = 1Output: “200"Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.Example 3:Input: num = “10”, k = 2Output: “0"Explanation: Remove all the digits from the number and it is left with nothing which is 0.假设现在有一个用字符串表示的非负的整数，问从中删除掉k个数字后能够得到的最小结果是多少？思路和代码直观的来说，删除数字得到最小的数字意味着我们应当尽可能的将越小的数字保留在高位，因此当我们从左往右遍历时，一旦遇到比前一个数字更小的数字，就应当删除前一个数字而保留这个数字。当我们用尽了所有删除时，就保留后面所有的数字，不再进行任何比较。因为我们已经尽可能获得了最小的最高位，因此无论后面的数字如何取值，其最高位上的数字一定是可以获得的最小的这个数字。举个例子：10200 k=1第一步： 0和1比较，此时0比1小，且还有一次可用的删除，因此删除1，保留0第二步：因为无可用的删除次数，因此剩下的值全部保留123450123 k=5第一步：2>1 保留第二步：3>2 保留第三步: 4>3 保留第四步: 5>4 保留第五步：0<5 删除5 保留0 k=4第六步: 0<4 删除4 保留0 k=3第七步：0<3 删除3 保留0 k=2第八步：0<2 删除2 保留0 k=1第九步：0<1 删除1 保留0 k=0第十步: 此时所有的删除次数用完，因此剩余的值全部保留可以看到，当我们遇到较小值时，我们会尽可能的将其往左边移动，因为只要它比左边的值小且剩余删除次数，则删除左边的值一定会得到一个更小的值。代码如下： public String removeKdigits(String num, int k) { if(num == null || num.length() == 0 || k==num.length()) return “0”; Stack<Character> stack = new Stack<>(); for(int i = 0 ; i < num.length() ; i++) { char c = num.charAt(i); while(k> 0 && !stack.isEmpty() && stack.peek() > c) { stack.pop(); k–; } stack.push(c); } while(k > 0) { stack.pop(); k–; } StringBuilder result = new StringBuilder(); while(!stack.isEmpty()) { result.append(stack.pop()); } while(result.length() > 1 && result.charAt(result.length()-1) == ‘0’) { result.deleteCharAt(result.length()-1); } return result.reverse().toString(); } ...

题目要求Design a simplified version of Twitter where users can post tweets, follow/unfollow another user and is able to see the 10 most recent tweets in the user’s news feed. Your design should support the following methods:postTweet(userId, tweetId): Compose a new tweet.getNewsFeed(userId): Retrieve the 10 most recent tweet ids in the user’s news feed. Each item in the news feed must be posted by users who the user followed or by the user herself. Tweets must be ordered from most recent to least recent.follow(followerId, followeeId): Follower follows a followee.unfollow(followerId, followeeId): Follower unfollows a followee.Example:Twitter twitter = new Twitter();// User 1 posts a new tweet (id = 5).twitter.postTweet(1, 5);// User 1’s news feed should return a list with 1 tweet id -> [5].twitter.getNewsFeed(1);// User 1 follows user 2.twitter.follow(1, 2);// User 2 posts a new tweet (id = 6).twitter.postTweet(2, 6);// User 1’s news feed should return a list with 2 tweet ids -> [6, 5].// Tweet id 6 should precede tweet id 5 because it is posted after tweet id 5.twitter.getNewsFeed(1);// User 1 unfollows user 2.twitter.unfollow(1, 2);// User 1’s news feed should return a list with 1 tweet id -> [5],// since user 1 is no longer following user 2.twitter.getNewsFeed(1);设计一个迷你推特，要求能够支持以下几个方法：发布推特，关注用户，取关用户，查看最近的十条关注用户发送的推特。思路和代码这道题目本质上是考察是否能将数据结构的知识灵活的运用于现实生活中。从最直观的想法来看，我们会有一个用户实体，每个用户会记录自己关注的用户的id，以及记录自己发表的所有tweet。这里唯一的难点在于我们如何按照时间顺序获取tweet流。这么一想，这题其实就转换为如何将N个有序排列的数组汇合成一个有序的数组。这题等价于我们每次都会比较当前所有被关注者发布的最新未读tweet，选出结果后将其插入结果集。这里我们可以利用等价队列帮助我们更快的完成选择的过程。public class Twitter { public Twitter() { users = new HashMap<>(); } public static int timestamp = 0; private Map<Integer, User> users; /** Compose a new tweet. / public void postTweet(int userId, int tweetId) { if(!users.containsKey(userId)) { User user = new User(userId); users.put(userId, user); } User user = users.get(userId); user.tweet(tweetId); } /* Retrieve the 10 most recent tweet ids in the user’s news feed. * Each item in the news feed must be posted by users who the user followed or by the user herself. * Tweets must be ordered from most recent to least recent. * / public List<Integer> getNewsFeed(int userId) { List<Integer> result = new ArrayList<Integer>(); if(!users.containsKey(userId)) { return result; } User user = users.get(userId); PriorityQueue<Tweet> queue = new PriorityQueue<>(user.followed.size()); for(int followee : user.followed) { User tmp = users.get(followee); if(tmp != null && tmp.headTweet != null) { queue.offer(tmp.headTweet); } } while(!queue.isEmpty() && result.size() < 10) { Tweet t = queue.poll(); result.add(t.tweetId); if(t.next != null) { queue.offer(t.next); } } return result; } /* Follower follows a followee. If the operation is invalid, it should be a no-op. / public void follow(int followerId, int followeeId) { if(!users.containsKey(followerId)) { User user = new User(followerId); users.put(followerId, user); } if(!users.containsKey(followeeId)) { User user = new User(followeeId); users.put(followeeId, user); } User user = users.get(followerId); user.follow(followeeId); } /* Follower unfollows a followee. If the operation is invalid, it should be a no-op. */ public void unfollow(int followerId, int followeeId) { if(!users.containsKey(followerId) || followerId == followeeId) { return; } User user = users.get(followerId); user.unfollow(followeeId); } public static class User{ int userId; Set<Integer> followed; Tweet headTweet; public User(int userId) { this.userId = userId; this.followed = new HashSet<>(); follow(userId); } public void follow(int userId) { followed.add(userId); } public void unfollow(int userId) { followed.remove(userId); } public void tweet(int tweetId) { Tweet tweet = new Tweet(tweetId); tweet.next = headTweet; headTweet = tweet; } } public static class Tweet implements Comparable<Tweet>{ int tweetId; Tweet next; int time; public Tweet(int tweetId) { this.tweetId = tweetId; this.time = timestamp++; } @Override public int compareTo(Tweet o) { return o.time - this.time; } }} ...

写在前面的话今天持续做题ing，python有意思今天的题有点虐心…兴许是我太笨了…会努力学习的！动态规划我来啦开始做题第一题459. 重复的子字符串难度：简单给定一个非空的字符串，判断它是否可以由它的一个子串重复多次构成。给定的字符串只含有小写英文字母，并且长度不超过10000。我的题解：class Solution(object): def repeatedSubstringPattern(self, s): """ :type s: str :rtype: bool """ if len(s) <= 1 : return False res = [] n = 0 length = len(s) for i in range(1,length): if s[i] == s[0]: res.append(i) for i in range(1,length): a = s[:i] length_a = len(a) n = length/length_a if a * n == s: return True return False我的思路：参考了小佳扬的思路后，重新写了一遍。主要是因为如果存在重复的话，第一个字母开始就会形成重复最小字符串的长度可以被字符串长度给整除那么就记录下第一个字母每次出现的地方，检查每次字符出现的前一段字符串是否可以形成重复。其他：写的时候遇到一个坑，一直遇到报错integer division or modulo by zero检查了一圈发现，是在第二个循环的时候，i从0开始作为除数，所以产生了报错。第二题5. 最长回文子串 —-超时需要再解答难度：中等给定一个字符串s，找到s中最长的回文子串。你可以假设s的最大长度为 1000。我的题解：class Solution(object): def longestPalindrome(self, s): """ :type s: str :rtype: str """ l = len(s) if len(s) <= 1: return s length = 0 for i in range(0,l): for j in range(i+1,l+1): res = s[i:j] if res == res[::-1]: #逆向相等 if (len(res) > length): mark = res #存储数据 length = len(res) return mark 我的思路：用的是最暴力的解法，双重循环，逐个字段进行比较，复杂度应该是O(N²)（这个复杂度超时很必然啊，被pia飞….其他：这题超时了，要重做!!!!可以执行通过较短的字符串，但是超过一定长度之后就会超时。建议使用动态规划，好好学习!!!重新做一次。第三题69. x 的平方根 —-超出内存需要再解答难度：简单实现int sqrt(int x)函数。计算并返回x的平方根，其中x是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。我的题解：class Solution(object): def mySqrt(self, x): """ :type x: int :rtype: int """ for i in range(x): if i**2 <= x and (i+1)**2 >x: return i我的思路：因为只取整数部分，所以值会介于i的平方及i+1的平方之间。其他：这题Memory Error了，要重做!!!!看了其他的人的题解，使用的是无限逼近中位值的办法，理论基础应该是泰勒公式。（万万没想到居然用到了泰勒公式….手工执行了下算法，反而理解的更快，但是泰勒公式还得再复习下。总结今天的做题就到这里啦，还有很多要学习的地方~数据结构与算法要加油呀！ ...

DescriptionGiven an integer matrix, find the length of the longest increasing path.From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).Example 1:Input: nums = [ [9,9,4], [6,6,8], [2,1,1]] Output: 4 Explanation: The longest increasing path is [1, 2, 6, 9].Example 2:Input: nums = [ [3,4,5], [3,2,6], [2,2,1]] Output: 4 Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.描述给定一个整数矩阵，找出最长递增路径的长度。对于每个单元格，你可以往上，下，左，右四个方向移动。 你不能在对角线方向上移动或移动到边界外（即不允许环绕）。示例 1:输入: nums = [ [9,9,4], [6,6,8], [2,1,1]] 输出: 4 解释: 最长递增路径为 [1, 2, 6, 9]。示例 2:输入: nums = [ [3,4,5], [3,2,6], [2,2,1]] 输出: 4 解释: 最长递增路径是 [3, 4, 5, 6]。注意不允许在对角线方向上移动。思路这道题主要使用记忆化递归和深度优先遍历。我们以给定的矩阵的每一个位置为起点，进行深度优先遍历。我们存储每个位置深度优先遍历的结果，当下一次走到这个位置的时候，我们直接返回当前位置记录的值，这样可以减少遍历的次数，加快执行速度。二维矩阵 dp 初始化每个位置都为 0 ，当遍历到某个位置不为 0 的时候，说明该位置已经遍历过了，我们直接返回其值。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-03-07 21:19:51# @Last Modified by: 何睿# @Last Modified time: 2019-03-07 22:23:10from itertools import productclass Solution: def longestIncreasingPath(self, matrix: [[int]]) -> int: # 如果矩阵为空，返回 0 if not matrix or not matrix[0]: return 0 # 获取矩阵的行数和列数 row, col = len(matrix), len(matrix[0]) # 记忆化递归，记录每个位置的最大值 dp = [[0] * col for _ in range(row)] # 遍历每一个位置，以每一个位置为起点进行深度优先遍历 # 返回最大值 return max( self._dfs(i, j, row, col, matrix, dp) for i, j in product(range(row), range(col))) def _dfs(self, i, j, row, col, matrix, dp): # 如果当前位置不为零，说明当前位置的最大值已经被找到 # 采用记忆化递归，直接返回最大值 if dp[i][j]: return dp[i][j] # 遍历四个方向 for x, y in [(0, -1), (-1, 0), (0, 1), (1, 0)]: m, n = x + i, y + j # 如果下一个位置没有越界并且下一个位置的只严格大于位置i，j if 0 <= m < row and 0 <= n < col and matrix[i][j] < matrix[m][n]: # 记录最大值 dp[i][j] = max(dp[i][j], self._dfs(m, n, row, col, matrix, dp)) # 把当前位置本身加上 dp[i][j] += 1 # 返回以当前位置为起点，所有路径中的最大值 return dp[i][j]源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明.微信公众号：techruicore ...

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。示例:输入: [0,1,0,2,1,0,1,3,2,1,2,1]输出: 6答案参考：/** * @param {number[]} height * @return {number} */var trap = function (height) { let left = 0, right = height.length - 1 let count = 0 let leftMax = 0, rightMax = 0 while (left <= right) { leftMax = Math.max(leftMax, height[left]) rightMax = Math.max(rightMax, height[right]) if (leftMax < rightMax) { count += leftMax - height[left] left++ } else { count += rightMax - height[right] right– } } return count}; ...

写在前面的话好几天木有刷题啦，今天猛刷了一把，要梳理一个顺序好好的学习啦~一定要好好执行每天做题的计划！最近真的好忙碌啊，还要做视频。不过呢，看了高效学习的书，感觉其实不能说太分散的学习，应该考虑多方面的联系，形成整体性的学习，还得琢磨琢磨…小李加油呀！认真做题第一题58. 最后一个单词的长度难度：简单给定一个仅包含大小写字母和空格 ’ ’ 的字符串，返回其最后一个单词的长度。如果不存在最后一个单词，请返回0。说明：一个单词是指由字母组成，但不包含任何空格的字符串。我的题解：class Solution(object): def lengthOfLastWord(self, s): """ :type s: str :rtype: int """ lastindex = 0 res = 0 for i in s: if i == ’ ‘: lastindex = 0 else: lastindex = lastindex + 1 if lastindex > 0: res = lastindex return res方法的效率不是太高。解题思路：每次遇到空格的时候，单词的长度就置空，不是的话就加1，然后用res记录上一次的lastindex长度。其他这题也要再多刷一次。第二题53. 最大子序和难度：简单给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。我的题解：class Solution(object): def maxSubArray(self, nums): """ :type nums: List[int] :rtype: int """ maxSum = nums[0] sum = 0 for i in nums: sum = sum + i if sum > maxSum: maxSum = sum if sum < 0: sum = 0 return maxSum 解题思路：这题是参考了小佳扬的思路。重点考虑什么时候会有最大的值。maxSum其实相当于一个记住上次最大值的点，sum则是移动的点。当遇到会导致总和小于0的值，那一定是要排除的，因为肯定会拉低总和大小。其他：这次还要多考虑情况，然后再刷一次。第三题35. 搜索插入位置难度：简单给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素。我的题解：class Solution(object): def searchInsert(self, nums, target): """ :type nums: List[int] :type target: int :rtype: int """ length = len(nums) for i in range(length): if nums[i] == target: return i if nums[i] > target: nums.insert(i,target) return i nums.append(target) return length解题思路：用了insert的办法，找到对应的Index之后插入即可。第四题28. 实现strStr()难度：简单实现 strStr() 函数。给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。我的题解：class Solution(object): def strStr(self, haystack, needle): """ :type haystack: str :type needle: str :rtype: int """ if needle == ‘’: return 0 length_a = len(needle) length_b = len(haystack) if length_b < length_a: return -1 for i in range(length_b): if haystack[i] == needle[0]: for j in range(length_a): if i+j == length_b: return -1 if haystack[i+j] != needle[j]: i = -1 if j == length_a-1 and i !=-1: return i i = -1 return i 解题思路：这串代码其实写的有点土，还得优化下，用的就是反复循环check，暴力破解。 ...

再来看比较复杂的几道题未完待续

题目根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。例如，给出中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树： 3 / \ 9 20 / \ 15 7题解根据前序和中序可以构造一颗二叉树，根据中序和后续也可以构建一颗二叉树。反正必须要有中序才能构建，因为没有中序，你没办法确定树的形状。比如先序和后序是不能构建唯一的一颗二叉树的。例如：先序为：[1, 2]后序为：[2, 1]可以构建如下 1 / 2 1 \ 2 这个面试官也会问的。回到这个题目。那回到这个题目, 其实思路比较好想到，就是如何划分子问题，然后递归的构建左子树和右子树。inorder = [9,3,15,20,7]postorder = [9,15,7,20,3]因为后序后遍历根节点，后续最后一个节点为整棵树的根节点，可以确定根节点为3;再根据中序得到:leftInOrder = [9]RightInOrder = [15, 20 ,7]又由于中序和先序的数组大小应该相同的,所以,LeftPostOrder = [9]RightPostOrder = [15, 7, 20]至此,划分为子问题:leftInOrder = [9]LeftPostOrder = [9]构建左子树。RightPreOrder = [20, 15, 7]RightPostOrder = [15, 7, 20]构建右子树。class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1); } public TreeNode helper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) { if (inStart > inEnd) { return null; } int currentVal = postorder[postEnd]; TreeNode current = new TreeNode(currentVal); int inIndex = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == currentVal) { inIndex = i; } } TreeNode left = helper(inorder, postorder, postEnd - (inEnd- inIndex) - 1, inStart, inIndex - 1); TreeNode right = helper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd); current.left = left; current.right = right; return current; }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树手撕代码QQ群：805423079， 群密码：1024 ...

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1,2,3,1].Given the array-form A of a non-negative integer X, return the array-form of the integer X+K.Example 1:Input: A = [1,2,0,0], K = 34Output: [1,2,3,4]Explanation: 1200 + 34 = 1234Example 2:Input: A = [2,7,4], K = 181Output: [4,5,5]Explanation: 274 + 181 = 455Example 3:Input: A = [2,1,5], K = 806Output: [1,0,2,1]Explanation: 215 + 806 = 1021Example 4:Input: A = [9,9,9,9,9,9,9,9,9,9], K = 1Output: [1,0,0,0,0,0,0,0,0,0,0]Explanation: 9999999999 + 1 = 10000000000Note：1 <= A.length <= 100000 <= A[i] <= 90 <= K <= 10000If A.length > 1, then A[0] != 0难度：easy题目：非负整数Ｘ的数组表示形式为一个单数字数组且顺序由左到右。例如，Ｘ＝1231,数组表示为［1,2,3,1]。给定数字Ｘ的数组表示形式Ａ，返回Ｘ＋Ｋ的数组表示形式。思路：从右向左加法运算Runtime: 11 ms, faster than 91.55% of Java online submissions for Add to Array-Form of Integer.Memory Usage: 41.8 MB, less than 75.63% of Java online submissions for Add to Array-Form of Integer.class Solution { public List<Integer> addToArrayForm(int[] A, int K) { List<Integer> result = new ArrayList<>(); int carry = 0, t = 0, n = A.length; while (–n >= 0 || K > 0) { t = n >= 0 ? A[n] + K % 10 + carry: K % 10 + carry; carry = t / 10; result.add(t % 10); K /= 10; } if (carry > 0) { result.add(carry); } Collections.reverse(result); return result; }} ...

Given a column title as appear in an Excel sheet, return its corresponding column number.For example:A -> 1B -> 2C -> 3…Z -> 26AA -> 27AB -> 28 …Example 1:Input: “A"Output: 1Example 2:Input: “AB"Output: 28Example 3:Input: “ZY"Output: 701难度：easy题目：给定Excel 表单里的一列名，返回其整数表示。思路：26进制Runtime: 1 ms, faster than 100.00% of Java online submissions for Excel Sheet Column Number.Memory Usage: 34.5 MB, less than 86.88% of Java online submissions for Excel Sheet Column Number.class Solution { public int titleToNumber(String s) { int result = 0, scale = 1; for (int i = s.length() - 1; i >= 0; i–) { result += (s.charAt(i) - ‘A’ + 1) * scale; scale *= 26; } return result; }} ...

Given an array A of strings made only from lowercase letters, return a list of all characters that show up in all strings within the list (including duplicates). For example, if a character occurs 3 times in all strings but not 4 times, you need to include that character three times in the final answer.You may return the answer in any order.Example 1:Input: [“bella”,“label”,“roller”]Output: [“e”,“l”,“l”]Example 2:Input: [“cool”,“lock”,“cook”]Output: [“c”,“o”]Note:1 <= A.length <= 1001 <= A[i].length <= 100Ai is a lowercase letter难度: easy题目：给定字符串数组Ａ仅由小字符组成，返回所有在所有字符串中都出现过的字符，包括重复。例如，如果一个字符在所有字符串出现了3次而非4次，则返回结果中要包含3次。返回顺序不限。思路：每个字符串一个统计表。Runtime: 7 ms, faster than 100.00% of Java online submissions for Find Common Characters.Memory Usage: 38.1 MB, less than 100.00% of Java online submissions for Find Common Characters.class Solution { public List<String> commonChars(String[] A) { int n = A.length; int[][] cc = new int[n][26]; for (int i = 0; i < n; i++) { for (char c : A[i].toCharArray()) { cc[i][c - ‘a’]++; } } List<String> result = new ArrayList<>(); for (int i = 0; i < 26; i++) { int minCount = 100; for (int j = 0; j < n; j++) { minCount = Math.min(minCount, cc[j][i]); } for (int j = 0; j < minCount; j++) { result.add(String.valueOf((char) (i + ‘a’))); } } return result; }} ...

Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.Example 1:Input: A = “ab”, B = “ba"Output: trueExample 2:Input: A = “ab”, B = “ab"Output: falseExample 3:Input: A = “aa”, B = “aa"Output: trueExample 4:Input: A = “aaaaaaabc”, B = “aaaaaaacb"Output: trueExample 5:Input: A = “”, B = “aa"Output: falseNote:0 <= A.length <= 200000 <= B.length <= 20000A and B consist only of lowercase letters.难度: Medium题目：给定两字符串Ａ和Ｂ且由小写字线组成，返回ＡＢ是否由仅交换两个字符可以相互生成。思路：判断长度，记录不同位置的个数，记录是否有相同的字符。Runtime: 3 ms, faster than 81.94% of Java online submissions for Buddy Strings.Memory Usage: 38.6 MB, less than 50.00% of Java online submissions for Buddy Strings.class Solution { public boolean buddyStrings(String A, String B) { if (A.length() != B.length()) { return false; } int[] tableA = new int[26]; int[] tableB = new int[26]; int diffPosition = 0; for (int i = 0; i < A.length(); i++) { char a = A.charAt(i); char b = B.charAt(i); if (a != b) { diffPosition++; } if (diffPosition > 2) { return false; } tableA[a - ‘a’]++; tableB[b - ‘a’]++; } boolean duplicated = false; for (int i = 0; !duplicated && i < 26; i++) { if (tableA[i] != tableB[i]) { return false; } duplicated = tableA[i] > 1 ? !duplicated : duplicated; } return 2 == diffPosition || duplicated; }} ...

题目根据一棵树的中序遍历与后序遍历构造二叉树。注意:你可以假设树中没有重复的元素。例如，给出中序遍历 inorder = [9,3,15,20,7]后序遍历 postorder = [9,15,7,20,3]返回如下的二叉树： 3 / \ 9 20 / \ 15 7题解根据前序和中序可以构造一颗二叉树，根据中序和后续也可以构建一颗二叉树。反正必须要有中序才能构建，因为没有中序，你没办法确定树的形状。比如先序和后序是不能构建唯一的一颗二叉树的。例如：先序为：[1, 2]后序为：[2, 1]可以构建如下 1 / 2 1 \ 2 这个面试官也会问的。回到这个题目。那回到这个题目, 其实思路比较好想到，就是如何划分子问题，然后递归的构建左子树和右子树。inorder = [9,3,15,20,7]postorder = [9,15,7,20,3]因为后序后遍历根节点，后续最后一个节点为整棵树的根节点，可以确定根节点为3;再根据中序得到:leftInOrder = [9]RightInOrder = [15, 20 ,7]又由于中序和先序的数组大小应该相同的,所以,LeftPostOrder = [9]RightPostOrder = [15, 7, 20]至此,划分为子问题:leftInOrder = [9]LeftPostOrder = [9]构建左子树。RightPreOrder = [20, 15, 7]RightPostOrder = [15, 7, 20]构建右子树。class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1); } public TreeNode helper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) { if (inStart > inEnd) { return null; } int currentVal = postorder[postEnd]; TreeNode current = new TreeNode(currentVal); int inIndex = 0; for (int i = inStart; i <= inEnd; i++) { if (inorder[i] == currentVal) { inIndex = i; } } TreeNode left = helper(inorder, postorder, postEnd - (inEnd- inIndex) - 1, inStart, inIndex - 1); TreeNode right = helper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd); current.left = left; current.right = right; return current; }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树 ...

Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order.Example 1:Input: “Let’s take LeetCode contest"Output: “s’teL ekat edoCteeL tsetnoc"Note: In the string, each word is separated by single space and there will not be any extra space in the string.难度: easy题目：给定字符串，返转字符串中的单词，保留空格和单词顺序。思路：遍历，返转Runtime: 11 ms, faster than 50.54% of Java online submissions for Reverse Words in a String III.Memory Usage: 38.7 MB, less than 96.70% of Java online submissions for Reverse Words in a String III.class Solution { public String reverseWords(String s) { s = " " + s + " “; StringBuilder result = new StringBuilder(); int begin = 0, end = 0; for (int i = 1; i < s.length() - 1; i++) { char c = s.charAt(i); if (c != ’ ’ && s.charAt(i - 1) == ’ ‘) { begin = i; result.append(s.substring(end + 1, begin)); } if (c != ’ ’ && s.charAt(i + 1) == ’ ‘) { end = i; for (int j = end; j >= begin; j–) { result.append(s.charAt(j)); } } } return result.toString(); }} ...

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, …) which sum to n.Example 1:Input: n = 12Output: 3 Explanation: 12 = 4 + 4 + 4.Example 2:Input: n = 13Output: 2Explanation: 13 = 4 + 9.难度: medium题目：给定一正整数n，找出其最少个平方数之和为n。思路：参考 (322. Coin Change)Runtime: 22 ms, faster than 91.72% of Java online submissions for Perfect Squares.Memory Usage: 36.6 MB, less than 47.46% of Java online submissions for Perfect Squares.class Solution { public int numSquares(int n) { int s = (int) Math.floor(Math.sqrt(n)); if (s * s == n) { return 1; } int[] squares = new int[s]; int[] nums = new int[n + 1]; for (int i = 1; i <= s; i++) { squares[i - 1] = i * i; if (squares[i - 1] < nums.length) { nums[squares[i - 1]] = 1; } } for (int i = squares[0]; i <= n; i++) { if (nums[i] > 0) { continue; } nums[i] = n + 1; for (int j = 0; j < squares.length && i - squares[j] >= 0; j++) { if (nums[i - squares[j]] > 0) { nums[i] = Math.min(nums[i - squares[j]] + 1, nums[i]); } } } return nums[n]; }} ...

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.Examples:s = “leetcode"return 0.s = “loveleetcode”,return 2.难度: easy题目：给定字符串，找出第一个不重复的字符，并返回其下标。如果不存在则返回－1.思路：数组分别记录下标与出现次数。Runtime: 10 ms, faster than 93.94% of Java online submissions for First Unique Character in a String.Memory Usage: 40 MB, less than 14.74% of Java online submissions for First Unique Character in a String.class Solution { public int firstUniqChar(String s) { int[] count = new int[26]; int[] index = new int[26]; int result = s.length(); for (int i = 0; i < result; i++) { char c = s.charAt(i); count[c - ‘a’]++; index[c - ‘a’] = i + 1; } for (int i = 0; i < 26; i++) { if (1 == count[i]) { result = Math.min(result, index[i] - 1); } } return result >= s.length() ? -1 : result; }} ...

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.Example 1:Input: coins = [1, 2, 5], amount = 11Output: 3 Explanation: 11 = 5 + 5 + 1Example 2:Input: coins = [2], amount = 3Output: -1Note:You may assume that you have an infinite number of each kind of coin.难度：medium题目：给定不同面值的硬币和一总金额。写一个函数来计算你需要的最少的硬币数量来构成这个总金额。如果这笔钱不能用硬币的任何组合来构成，则返回-1。思路：DPtotal[i]表示这个金额最少需要多少硬币组成。total[amount] = Math.min(total[amount - coins[i]] + 1) (total[amount - coins[i]] > 0) (total[amount - coins[i]] = 0) 意味着不可达。Runtime: 13 ms, faster than 97.29% of Java online submissions for Coin Change.Memory Usage: 38 MB, less than 42.39% of Java online submissions for Coin Change.class Solution { public int coinChange(int[] coins, int amount) { if (null == coins || coins.length < 1 || amount <= 0) { return 0; } int[] total = new int[amount + 1]; Arrays.sort(coins); for (int i = 0; i < coins.length && coins[i] < total.length; i++) { total[coins[i]] = 1; } for (int i = coins[0]; i <= amount; i++) { if (total[i] > 0) { continue; } total[i] = amount + 1; for (int j = 0; j < coins.length && i - coins[j] >= 0; j++) { if (total[i - coins[j]] > 0) { total[i] = Math.min(total[i - coins[j]] + 1, total[i]); } } } return total[amount] > amount || total[amount] <= 0 ? -1 : total[amount]; }} ...

Given a string array words, find the maximum value of length(word[i]) * length(word[j]) where the two words do not share common letters. You may assume that each word will contain only lower case letters. If no such two words exist, return 0.Example 1:Input: [“abcw”,“baz”,“foo”,“bar”,“xtfn”,“abcdef”]Output: 16 Explanation: The two words can be “abcw”, “xtfn”.Example 2:Input: [“a”,“ab”,“abc”,“d”,“cd”,“bcd”,“abcd”]Output: 4 Explanation: The two words can be “ab”, “cd”.Example 3:Input: [“a”,“aa”,“aaa”,“aaaa”]Output: 0 Explanation: No such pair of words.难度：medium题目：给定一字符串数组，找出其最大length(word[i]) * length(word[j]),两个字符串不含有相同的字符。假定每个字符串只含有小写字母。如果没有这样的两个字符串返回0.思路：ＢＦ (待更优方法）Runtime: 443 ms, faster than 11.27% of Java online submissions for Maximum Product of Word Lengths.Memory Usage: 40.4 MB, less than 30.44% of Java online submissions for Maximum Product of Word Lengths.class Solution { public int maxProduct(String[] words) { int n = words.length, maxProductLength = 0; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { if (!isWordsOverlap(words[i], words[j])) { maxProductLength = Math.max(maxProductLength, words[i].length() * words[j].length()); } } } return maxProductLength; } private boolean isWordsOverlap(String word1, String word2) { int[] digit1 = new int[26]; int[] digit2 = new int[26]; for (int i = 0; i < word1.length(); i++) { digit1[word1.charAt(i) - ‘a’]++; } for (int i = 0; i < word2.length(); i++) { digit2[word2.charAt(i) - ‘a’]++; } for (int i = 0; i < 26; i++) { if (digit1[i] > 0 && digit2[i] > 0) { return true; } } return false; }} ...

写在前面咱不是计算机专业的，却一直对计算机算法感兴趣，也一直致力于减小自己程序的复杂度[捂脸]，昨日吃饭时，某老铁考我一道算法题，思索良久，辗转反侧，夜不能寐，遂厚着脸皮去问答案，然则令吾汗颜，果真是一波骚操作……看题！给定一个非空整数数组, 除了某个元素只出现一次以外, 其余每个元素均出现两次, 找出那个只出现了一次的元素。说明：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？示例 1:输入: [2,2,1] 输出: 1示例 2:输入: [4,1,2,1,2] 输出: 4看答案之前，不妨独立思考一下，看看能不能想出解决方案!推荐先想一会儿！如果实在想不出来, 可以看一下提示 继续想 ！！提示看一下标题！！！题目解析根据题目描述，由于加上了时间复杂度必须是O(n)，并且空间复杂度为O(1)的条件，因此不能用排序方法，也不能使用map数据结构。咱想了一晚上，结果, 答案是使用 位操作Bit Operation 来解此题。将所有元素做异或运算，即 a[1] ⊕ a[2] ⊕ a[3] ⊕…⊕ a[n]，而结果就是那个只出现一次的数字，时间复杂度为O(n)。什么？？你忘记了异或？？？异或运算 A ⊕ B 的真值表如下:ABA ⊕ BFalseFalseFalseTrueTrueTrueTrueFalseTrueFalseTrueTrue即:不相等即为True题目进阶有一个 n 个元素的数组，除了两个数只出现一次外，其余元素都出现两次，让你找出这两个只出现一次的数分别是几，要求时间复杂度为 O(n) 且再开辟的内存空间固定(与 n 无关)。示例 :输入: [1,2,2,1,3,4] 输出: [3,4]题目再解析根据前面找 一个 不同数的思路算法，在这里把所有元素都异或，那么得到的结果就是那两个只出现一次的元素异或的结果, 为了叙述方便, 我们这里把这个结果简单记为字母 K 。因为这两个只出现一次的元素一定是不相同的，所以 K 一定不为零, 将K从左往右数的第一个为1的位记录下来。再然后，以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分。将这一位为 0 的所有元素做异或，得出的数就是只出现一次的数中的一个将这一位为 1 的所有元素做异或，得出的数就是只出现一次的数中的另一个。这样就解出题目, 忽略寻找不同位的过程，总共遍历数组两次，时间复杂度为O(n)。举个例子吧假如:输入是: [1,2,2,1,3,4,7,7] 进行异或操作:>>> 1^2^2^1^3^4 # python的异或操作符7异或完毕为7即0000 0111数字7从左往右数的第一个为1的位为0000 0111 ^也就是第六位以这一位是 1 还是 0 为标准，将数组的 n 个元素分成两部分(也就是数组大于等于4的分一组, 小于4的分一组)即[4, 7, 7] 和 [1,2,2,1,3]>>> # 数组[4,7,7]所有元素做异或操作>>> 4^7^74>>> 数组[1,2,2,1,3]所有元素做异或操作>>> 1^2^2^1^33大功告成！！据说此题来源于 LeetCode 第 136 号问题：https://leetcode-cn.com/probl… ...

Write a program to find the nth super ugly number. Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. Example: Input: n = 12, primes = [2,7,13,19]Output: 32 Explanation: [1,2,4,7,8,13,14,16,19,26,28,32] is the sequence of the first 12 super ugly numbers given primes = [2,7,13,19] of size 4. Note: ...

上篇文章写了以我自己的思路来解决这个问题，但是运行时间过长，看了leetcode 上的高效写法是使用位运算的解法，当初我自己写这个问题是也想到了可以用位运算快一点，但是因为基础差，对位运算的掌握不牢靠，还是选择使用了减法的思路，在此将leetcode上高效解法做一个思路分析，加深下自己对位运算的理解LeetCode上高效解法代码class Solution { public static int divide(int dividend, int divisor) { //首先处理Integer的最小值溢出问题（和我思路一样） if (dividend == Integer.MIN_VALUE && divisor == -1) { return Integer.MAX_VALUE; } //判断结果符号（这个写法比我的号，但是结果的时候用到了乘法，难道符合题意？？费解????） int sign = (dividend < 0) ^ (divisor < 0) ? -1 : 1; //取被除数最大值 long dvd = Math.abs((long) dividend); //取除数最大值 long dvs = Math.abs((long) divisor); //定义结果 int res = 0; //循环条件：当被除数大于等于除数时候 while (dvd >= dvs) { //为防止溢出,这里使用long类型 long temp = dvs; long mult = 1; //<< 移位操作,向左移动1位 //当dvd大于dvs*2的mult次方的时候,即计算dvd中最多有2的几次方个dvs while (dvd >= (temp << 1)) { temp <<= 1; mult <<= 1; } System.out.printf("%d里面有,2的%d次方个%d\r\n", dvd, mult, dvs); //计算新的dvd,和累加mult dvd -= temp; res += mult; } return res * sign; } }用例[100,3]输出结果100里面有,2的32次方个34里面有,2的1次方个3总结上面的算法将以前的减操作优化称为位移操作，一次可以累加2的n次方个，减少了循环次数，所以比Part 1 中算法要快 ...

Given an Iterator class interface with methods: next() and hasNext(), design and implement a PeekingIterator that support the peek() operation – it essentially peek() at the element that will be returned by the next call to next().Example:Assume that the iterator is initialized to the beginning of the list: [1,2,3].Call next() gets you 1, the first element in the list.Now you call peek() and it returns 2, the next element. Calling next() after that still return 2. You call next() the final time and it returns 3, the last element. Calling hasNext() after that should return false.Follow up: How would you extend your design to be generic and work with all types, not just integer?难度: medium题目：给定一迭代器包含方法next()和hasNext(),设计PeekIterator,支持peek()操作其返回值为下一次调用next时的值。思路：预先设置一变量存储peek值。Runtime: 48 ms, faster than 100.00% of Java online submissions for Peeking Iterator.Memory Usage: 36.8 MB, less than 74.37% of Java online submissions for Peeking Iterator.// Java Iterator interface reference:// https://docs.oracle.com/javase/8/docs/api/java/util/Iterator.htmlclass PeekingIterator implements Iterator<Integer> { private Integer peek; private Iterator<Integer> iterator; public PeekingIterator(Iterator<Integer> iterator) { // initialize any member here. this.iterator = iterator; if (this.iterator.hasNext()) { this.peek = iterator.next(); } } // Returns the next element in the iteration without advancing the iterator. public Integer peek() { return this.peek; } // hasNext() and next() should behave the same as in the Iterator interface. // Override them if needed. @Override public Integer next() { Integer nextElem = peek; peek = iterator.hasNext() ? iterator.next() : null; return nextElem; } @Override public boolean hasNext() { return peek != null; }} ...

DescriptionYou are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.Example 1:Input: coins = [1, 2, 5], amount = 11Output: 3 Explanation: 11 = 5 + 5 + 1Example 2:Input: coins = [2], amount = 3Output: -1Note:You may assume that you have an infinite number of each kind of coin.描述给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。示例 1:输入: coins = [1, 2, 5], amount = 11输出: 3 解释: 11 = 5 + 5 + 1示例 2:输入: coins = [2], amount = 3输出: -1说明:你可以认为每种硬币的数量是无限的。思路这道题目使用动态规划。对于要兑换面值为 a 的硬币，我们从面值为 0 的硬币开始找，一路规划到 a。状态：matrix[i][j],表示使用 coins 的前 i 个硬币，兑换面值为 j 的硬币所需要的硬币的个数。状态转移：对于面值的 k 的硬币，假设此时我们已经使用了 coins 的前 i 个银币，则1.我们可以把 k 拆分成 k - coins[i] + coins[i]，即需要面值为 k - coins[i] 的硬币需要兑换的硬币个数 + 1；2.我们也可以不使用当前的硬币，那么兑换面值为 k 的硬币就需要使用前 i-1 个硬币兑换面值为 k 的硬币的个数；我们取出上面两种情况的最小值。结果：矩阵的最后一个值。# -- coding: utf-8 --# @Author: 何睿# @Create Date: 2019-03-01 10:21:19# @Last Modified by: 何睿# @Last Modified time: 2019-03-01 14:33:42class Solution: def coinChange(self, coins: [int], amount: int) -> int: # 声明一个二维矩阵 matrix = [[i for i in range(amount + 1)] for _ in range(2)] # 初始化第一行 for i in range(amount + 1): # 如果当前位置表示的需要兑换的钱数可以被整除，将当前位置置为需要钱的个数 if i % coins[0] == 0: matrix[0][i] = i // coins[0] # 否则将当前的钱数目置为 amount+1 else: matrix[0][i] = amount + 1 for i in range(1, len(coins)): for j in range(amount + 1): row = i % 2 # 不使用第 i 个硬币，仅使用 i 前面的所有硬币 # 则一共需要当前行上一行对应位置的硬币 top = matrix[(i - 1) % 2][j] # 使用当前的硬币，如果当前需要兑换的硬币面值大于当前硬币的面值 if j >= coins[i]: # 动态规划：兑换面值为 a 的硬币，在已经使用了coins[0:col-1]这些硬币的情况下 # 可以由 a - coins[col] 需要的硬币加上硬币 coins[col]， # 所以需要的硬币个数为 matrix[row][a - coins[col]]+1； # 也可以不使用当前的硬币，仅仅使用前 i 个硬币 # 那么需要的硬币个数为 matrix[row-1][col] # 取出最下值 matrix[row][j] = min(top, matrix[row][j - coins[i]] + 1) else: matrix[i % 2][j] = top res = 0 # 为了节省空间，我们的矩阵仅仅使用了两行， # 如果 coins 的个数为奇数个，那么最终结果在第一行 if len(coins) % 2: res = -1 if matrix[0][-1] == amount + 1 else matrix[0][-1] # 如果 coins 的个位数为偶数个，那么最终结果为第二行 else: res = -1 if matrix[1][-1] == amount + 1 else matrix[1][-1] return res def coinChange2(self, coins: [int], amount: int) -> int: # 思路同方法一完全一样，仅仅是换了一种写的方式 # python 对于列表解析式的执行效率更快 count = amount + 1 line = [i for i in range(count)] for i in range(1, count): line[i] = min(line[i - c] if i >= c else count for c in coins) if line[i] != count: line[i] += 1 return line[-1] if line[-1] != count else -1源代码文件在 这里 。©本文首发于 何睿的博客 ，欢迎转载，转载需保留 文章来源 ，作者信息和本声明.微信公众号：techruicore ...

题目给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明: 叶子节点是指没有子节点的节点。示例：给定二叉树 [3,9,20,null,null,15,7]， 3 / \ 9 20 / \ 15 7返回它的最大深度 3 。题解求最大深度,和深度相关,我们很容易想到用层序遍历。每遍历一层,就深度加1, 怎么记录是第几层我们之前的文章中讲过了。/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } int depth = 0; LinkedList<TreeNode> queue = new LinkedList<>(); queue.add(root); while (!queue.isEmpty()) { int size = queue.size(); while (size > 0) { TreeNode current = queue.poll(); if (current.left != null) { queue.add(current.left); } if (current.right != null) { queue.add(current.right); } size–; } depth++; } return depth; }}这道题用递归解代码比较简单.递归的结束条件: 当节点为叶子节点的时候.递归的子问题: 当前最大深度 = 左右子树最大深度的较大者 + 1代码实现就很简单了。class Solution { public int maxDepth(TreeNode root) { if (root == null) { return 0; } return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; }}热门阅读技术文章汇总【Leetcode】103. 二叉树的锯齿形层次遍历【Leetcode】102. 二叉树的层次遍历【Leetcode】101. 对称二叉树【Leetcode】100. 相同的树【Leetcode】98. 验证二叉搜索树 ...

Count the number of prime numbers less than a non-negative number, n.Example:Input: 10Output: 4Explanation: There are 4 prime numbers less than 10, they are 2, 3, 5, 7.难度：easy题目：统计小于非负整数n的所有素数。思路：参考素数筛选法。Runtime: 11 ms, faster than 94.69% of Java online submissions for Count Primes.Memory Usage: 35.9 MB, less than 21.43% of Java online submissions for Count Primes.class Solution { public int countPrimes(int n) { boolean[] notPrimes = new boolean[n]; int count = 0; for (int i = 2; i < n; i++) { if (!notPrimes[i]) { count++; for (int j = 2 * i; j < n; j += i) { notPrimes[j] = true; } } } return count; }} ...