xmuwww
探索云世界
xmuwww
暂无个人介绍
我的博客即将入驻“云栖社区”，诚邀技术同仁一同入驻。
本文首发于我的个人博客：尾尾部落 来源：http://www.runoob.com/java/java-collections.html 来源：https://www.cnblogs.com/jing99/p/7057245.html 1. Iterator接口 Iterator接口，这是一个用于遍历集合中元素的接口，主要包含hashNext(),next(),remove()三种方法。它的一个子接口LinkedIterator在它的基础上又添加了三种方法，分别是add(),previous(),hasPrevious()。也就是说如果是先Iterator接口，那么在遍历集合中元素的时候，只能往后遍历，被遍历后的元素不会在遍历到，通常无序集合实现的都是这个接口，比如HashSet，HashMap；而那些元素有序的集合，实现的一般都是LinkedIterator接口，实现这个接口的集合可以双向遍历，既可以通过next()访问下一个元素，又可以通过previous()访问前一个元素，比如ArrayList。 2. List List是元素有序并且可以重复的集合。 List的主要实现：ArrayList, LinkedList, Vector。 image 2. ArrayList、LinkedList、Vector 的区别 ArrayList LinkedList Vector 底层实现 数组 双向循环链表 数组 同步性及效率 不同步，非线程安全，效率高 不同步，非线程安全，效率高 同步，线程安全，效率低 特点 查询快,增删慢 查询慢,增删快 查询快,增删慢 默认容量 10 / 10 扩容机制 int newCapacity = oldCapacity + (oldCapacity >> 1); //1.5 倍 / 2 倍 总结： ArrayList 和 Vector 基于数组实现，对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。 LinkedList 不会出现扩容的问题，所以比较适合随机位置增、删。但是其基于链表实现，所以在定位时需要线性扫描，效率比较低。 当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能； 当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。 3. Set Set集合中的对象不按特定的方式排序(存入和取出的顺序不一定一致)，并且没有重复对象。 Set的主要实现类：HashSet, TreeSet。 image HashSet TreeSet LinkedHashSet 底层实现 HashMap 红黑树 LinkedHashMap 重复性 不允许重复 不允许重复 不允许重复 有/无序 无序 有序，支持两种排序方式，自然排序和定制排序，其中自然排序为默认的排序方式。 有序，以元素插入的顺序来维护集合的链接表 时间复杂度 add()，remove()，contains()方法的时间复杂度是O(1) add()，remove()，contains()方法的时间复杂度是O(logn) LinkedHashSet在迭代访问Set中的全部元素时，性能比HashSet好，但是插入时性能稍微逊色于HashSet，时间复杂度是 O(1)。 同步性 不同步，线程不安全 不同步，线程不安全 不同步，线程不安全 null值 允许null值 不支持null值，会抛出 java.lang.NullPointerException 异常。因为TreeSet应用 compareTo() 方法于各个元素来比较他们，当比较null值时会抛出 NullPointerException异常。 允许null值 比较 equals() compareTo() equals() HashSet如何检查重复 当你把对象加入HashSet时，HashSet会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的hashcode值作比较，如果没有相符的hashcode，HashSet会假设对象没有重复出现。但是如果发现有相同hashcode值的对象，这时会调用equals（）方法来检查hashcode相等的对象是否真的相同。如果两者相同，HashSet就不会让加入操作成功。 hashCode（）与equals（）的相关规定： 如果两个对象相等，则hashcode一定也是相同的 两个对象相等,对两个equals方法返回true 两个对象有相同的hashcode值，它们也不一定是相等的 综上，equals方法被覆盖过，则hashCode方法也必须被覆盖 hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode()，则该class的两个对象无论如何都不会相等（即使这两个对象指向相同的数据）。 总结： HashSet是一个通用功能的Set，而LinkedHashSet 提供元素插入顺序保证，TreeSet是一个SortedSet实现，由Comparator 或者 Comparable指定的元素顺序存储元素。 4. Map Map 是一种把键对象和值对象映射的集合，它的每一个元素都包含一对键对象和值对象。 Map没有继承于Collection接口从Map集合中检索元素时，只要给出键对象，就会返回对应的值对象。 Map 的常用实现类：HashMap、TreeMap、HashTable、LinkedHashMap、ConcurrentHashMap image HashMap HashTable 底层实现 数组+链表 数组+链表 同步性 线程不同步 同步 null值 允许 key 和 Vale 是 null，但是只允许一个 key 为 null,且这个元素存放在哈希表 0 角标位置 不允许key、value 是 null hash 使用hash(Object key)扰动函数对 key 的 hashCode 进行扰动后作为 hash 值 直接使用 key 的 hashCode() 返回值作为 hash 值 容量 容量为 2^4 且容量一定是 2^n 默认容量是11,不一定是 2^n 扩容 两倍，且哈希桶的下标使用 &运算代替了取模 2倍+1，取哈希桶下标是直接用模运算 几个问题： 1. HashMap 的工作原理？ 通过hash的方法，通过put和get存储和获取对象。存储对象时，我们将K/V传给put方法时，它调用hashCode计算hash从而得到bucket位置，进一步存储，HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)。获取对象时，我们将K传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。如果发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高效率。2.get和put的原理吗？equals()和hashCode()的都有什么作用？ 通过对key的hashCode()进行hashing，并计算下标( n-1 & hash)，从而获得buckets的位置。如果产生碰撞，则利用key.equals()方法去链表或树中去查找对应的节点3. HashMap 的长度为什么是2的幂次方？ 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀，每个链表/红黑树长度大致相同。这个实现就是把数据存到哪个链表/红黑树中的算法。 HashMap 和 LinkedHashMap 的区别 LinkedHashMap 拥有与 HashMap 相同的底层哈希表结构，即数组 + 单链表 + 红黑树，也拥有相同的扩容机制。 LinkedHashMap 相比 HashMap 的拉链式存储结构，内部额外通过 Entry 维护了一个双向链表。 HashMap 元素的遍历顺序不一定与元素的插入顺序相同，而 LinkedHashMap 则通过遍历双向链表来获取元素，所以遍历顺序在一定条件下等于插入顺序。 LinkedHashMap 可以通过构造参数 accessOrder 来指定双向链表是否在元素被访问后改变其在双向链表中的位置。 HashMap & TreeMap 的区别 HashMap实现了Map接口，不保障元素顺序。 TreeMap实现了SortedMap接口，是一个有序的Map。内部采用红黑树实现，红黑树是一种维护有序数据的高效数据结构 ConcurrentHashMap 和 Hashtable 的区别 ConcurrentHashMap 和 Hashtable 的区别主要体现在实现线程安全的方式上不同。 底层数据结构： JDK1.7的 ConcurrentHashMap 底层采用 分段的数组+链表 实现，JDK1.8 采用的数据结构跟HashMap1.8的结构一样，数组+链表/红黑二叉树。Hashtable 和 JDK1.8 之前的 HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的； 实现线程安全的方式（重要）： ① 在JDK1.7的时候，ConcurrentHashMap（分段锁） 对整个桶数组进行了分割分段(Segment)，每一把锁只锁容器其中一部分数据，多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。（默认分配16个Segment，比Hashtable效率提高16倍。） 到了 JDK1.8 的时候已经摒弃了Segment的概念，而是直接用 Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。（JDK1.6以后 对 synchronized锁做了很多优化） 整个看起来就像是优化过且线程安全的 HashMap，虽然在JDK1.8中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；② Hashtable(同一把锁) :使用 synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。 image JDK1.7的ConcurrentHashMap： image JDK1.8的ConcurrentHashMap（TreeBin: 红黑二叉树节点 Node: 链表节点）： image 参考 这几道Java集合框架面试题在面试中几乎必问 搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目 获取最新资讯，请关注微信公众号：南强说晚安 image
本文首发于我的个人博客：尾尾部落 1. KMP 算法 谈到字符串问题，不得不提的就是 KMP 算法，它是用来解决字符串查找的问题，可以在一个字符串（S）中查找一个子串（W）出现的位置。KMP 算法把字符匹配的时间复杂度缩小到 O(m+n) ,而空间复杂度也只有O(m)。因为“暴力搜索”的方法会反复回溯主串，导致效率低下，而KMP算法可以利用已经部分匹配这个有效信息，保持主串上的指针不回溯，通过修改子串的指针，让模式串尽量地移动到有效的位置。 具体算法细节请参考： 字符串匹配的KMP算法 从头到尾彻底理解KMP 如何更好的理解和掌握 KMP 算法? KMP 算法详细解析 图解 KMP 算法 汪都能听懂的KMP字符串匹配算法【双语字幕】 KMP字符串匹配算法1 1.1 BM 算法 BM算法也是一种精确字符串匹配算法，它采用从右向左比较的方法，同时应用到了两种启发式规则，即坏字符规则 和好后缀规则 ，来决定向右跳跃的距离。基本思路就是从右往左进行字符匹配，遇到不匹配的字符后从坏字符表和好后缀表找一个最大的右移值，将模式串右移继续匹配。字符串匹配的KMP算法 2. 替换空格 剑指offer：替换空格 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 public class Solution { public String replaceSpace(StringBuffer str) { StringBuffer res = new StringBuffer(); int len = str.length() - 1; for(int i = len; i >= 0; i--){ if(str.charAt(i) == ' ') res.append("02%"); else res.append(str.charAt(i)); } return res.reverse().toString(); } } 3. 最长公共前缀 Leetcode: 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。如果不存在公共前缀，返回空字符串 ""。 image 首先对字符串数组进行排序，然后拿数组中的第一个和最后一个字符串进行比较，从第 0 位开始，如果相同，把它加入 res 中，不同则退出。最后返回 res class Solution { public String longestCommonPrefix(String[] strs) { if(strs == null || strs.length == 0) return ""; Arrays.sort(strs); char [] first = strs[0].toCharArray(); char [] last = strs[strs.length - 1].toCharArray(); StringBuffer res = new StringBuffer(); int len = first.length < last.length ? first.length : last.length; int i = 0; while(i < len){ if(first[i] == last[i]){ res.append(first[i]); i++; } else break; } return res.toString(); } } 4. 最长回文串 LeetCode: 最长回文串 给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。在构造过程中，请注意区分大小写。比如 "Aa" 不能当做一个回文字符串。 image 统计字母出现的次数即可，双数才能构成回文。因为允许中间一个数单独出现，比如“abcba”，所以如果最后有字母落单，总长度可以加 1。 class Solution { public int longestPalindrome(String s) { HashSet<Character> hs = new HashSet<>(); int len = s.length(); int count = 0; if(len == 0) return 0; for(int i = 0; i<len; i++){ if(hs.contains(s.charAt(i))){ hs.remove(s.charAt(i)); count++; }else{ hs.add(s.charAt(i)); } } return hs.isEmpty() ? count * 2 : count * 2 + 1; } } 4.1 验证回文串 Leetcode: 验证回文串 给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。 说明：本题中，我们将空字符串定义为有效的回文串。 两个指针比较头尾。要注意只考虑字母和数字字符，可以忽略字母的大小写。 image class Solution { public boolean isPalindrome(String s) { if(s.length() == 0) return true; int l = 0, r = s.length() - 1; while(l < r){ if(!Character.isLetterOrDigit(s.charAt(l))){ l++; }else if(!Character.isLetterOrDigit(s.charAt(r))){ r--; }else{ if(Character.toLowerCase(s.charAt(l)) != Character.toLowerCase(s.charAt(r))) return false; l++; r--; } } return true; } } 4.2 最长回文子串 LeetCode: 最长回文子串 给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为1000。 image 以某个元素为中心，分别计算偶数长度的回文最大长度和奇数长度的回文最大长度。 class Solution { private int index, len; public String longestPalindrome(String s) { if(s.length() < 2) return s; for(int i = 0; i < s.length()-1; i++){ PalindromeHelper(s, i, i); PalindromeHelper(s, i, i+1); } return s.substring(index, index+len); } public void PalindromeHelper(String s, int l, int r){ while(l >= 0 && r < s.length() && s.charAt(l) == s.charAt(r)){ l--; r++; } if(len < r - l - 1){ index = l + 1; len = r - l - 1; } } } 4.3 最长回文子序列 LeetCode: 最长回文子序列 给定一个字符串s，找到其中最长的回文子序列。可以假设s的最大长度为1000。最长回文子序列和上一题最长回文子串的区别是，子串是字符串中连续的一个序列，而子序列是字符串中保持相对位置的字符序列，例如，"bbbb"可以使字符串"bbbab"的子序列但不是子串。 image 动态规划： dp[i][j] = dp[i+1][j-1] + 2 if s.charAt(i) == s.charAt(j) otherwise, dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]) class Solution { public int longestPalindromeSubseq(String s) { int len = s.length(); int [][] dp = new int[len][len]; for(int i = len - 1; i>=0; i--){ dp[i][i] = 1; for(int j = i+1; j < len; j++){ if(s.charAt(i) == s.charAt(j)) dp[i][j] = dp[i+1][j-1] + 2; else dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]); } } return dp[0][len-1]; } } 5. 字符串的排列 Leetcode: 字符串的排列 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。 换句话说，第一个字符串的排列之一是第二个字符串的子串。 image 我们不用真的去算出s1的全排列，只要统计字符出现的次数即可。可以使用一个哈希表配上双指针来做。 class Solution { public boolean checkInclusion(String s1, String s2) { int l1 = s1.length(); int l2 = s2.length(); int [] count = new int [128]; if(l1 > l2) return false; for(int i = 0; i<l1; i++){ count[s1.charAt(i) - 'a']++; count[s2.charAt(i) - 'a']--; } if(allZero(count)) return true; for(int i = l1; i<l2; i++){ count[s2.charAt(i) - 'a']--; count[s2.charAt(i-l1) - 'a']++; if(allZero(count)) return true; } return false; } public boolean allZero(int [] count){ int l = count.length; for(int i = 0; i < l; i++){ if(count[i] != 0) return false; } return true; } } 6. 打印字符串的全排列 剑指offer：字符串的排列 输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 把问题拆解成简单的步骤： 第一步求所有可能出现在第一个位置的字符（即把第一个字符和后面的所有字符交换[相同字符不交换]）； 第二步固定第一个字符，求后面所有字符的排列。这时候又可以把后面的所有字符拆成两部分（第一个字符以及剩下的所有字符），依此类推。这样，我们就可以用递归的方法来解决。 public class Solution { ArrayList<String> res = new ArrayList<String>(); public ArrayList<String> Permutation(String str) { if(str == null) return res; PermutationHelper(str.toCharArray(), 0); Collections.sort(res); return res; } public void PermutationHelper(char[] str, int i){ if(i == str.length - 1){ res.add(String.valueOf(str)); }else{ for(int j = i; j < str.length; j++){ if(j!=i && str[i] == str[j]) continue; swap(str, i, j); PermutationHelper(str, i+1); swap(str, i, j); } } } public void swap(char[] str, int i, int j) { char temp = str[i]; str[i] = str[j]; str[j] = temp; } } 7. 第一个只出现一次的字符 剑指offer: 第一个只出现一次的字符 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1. 先在hash表中统计各字母出现次数，第二次扫描直接访问hash表获得次数。也可以用数组代替hash表。 import java.util.HashMap; public class Solution { public int FirstNotRepeatingChar(String str) { int len = str.length(); if(len == 0) return -1; HashMap<Character, Integer> map = new HashMap<>(); for(int i = 0; i < len; i++){ if(map.containsKey(str.charAt(i))){ int value = map.get(str.charAt(i)); map.put(str.charAt(i), value+1); }else{ map.put(str.charAt(i), 1); } } for(int i = 0; i < len; i++){ if(map.get(str.charAt(i)) == 1) return i; } return -1; } } 8. 翻转单词顺序列 剑指offer: 翻转单词顺序列 LeetCode: 翻转字符串里的单词 借助trim()和 split()就很容易搞定 public class Solution { public String reverseWords(String s) { if(s.trim().length() == 0) return s.trim(); String [] temp = s.trim().split(" +"); String res = ""; for(int i = temp.length - 1; i > 0; i--){ res += temp[i] + " "; } return res + temp[0]; } } 9. 旋转字符串 Leetcode: 旋转字符串 给定两个字符串, A 和 B。 A 的旋转操作就是将 A 最左边的字符移动到最右边。 例如, 若 A = 'abcde'，在移动一次之后结果就是'bcdea' 。如果在若干次旋转操作之后，A 能变成B，那么返回True。 image 一行代码搞定 class Solution { public boolean rotateString(String A, String B) { return A.length() == B.length() && (A+A).contains(B); } } 9.1 左旋转字符串 剑指offer: 左旋转字符串 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！ 在第 n 个字符后面将切一刀，将字符串分为两部分，再重新并接起来即可。注意字符串长度为 0 的情况。 public class Solution { public String LeftRotateString(String str,int n) { int len = str.length(); if(len == 0) return ""; n = n % len; String s1 = str.substring(n, len); String s2 = str.substring(0, n); return s1+s2; } } 9.2 反转字符串 LeetCode: 反转字符串 编写一个函数，其作用是将输入的字符串反转过来。 image class Solution { public String reverseString(String s) { if(s.length() < 2) return s; int l = 0, r = s.length() - 1; char [] strs = s.toCharArray(); while(l < r){ char temp = strs[l]; strs[l] = strs[r]; strs[r] = temp; l++; r--; } return new String(strs); } } 10. 把字符串转换成整数 剑指offer: 把字符串转换成整数 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。 public class Solution { public int StrToInt(String str) { if(str.length() == 0) return 0; int flag = 0; if(str.charAt(0) == '+') flag = 1; else if(str.charAt(0) == '-') flag = 2; int start = flag > 0 ? 1 : 0; long res = 0; while(start < str.length()){ if(str.charAt(start) > '9' || str.charAt(start) < '0') return 0; res = res * 10 + (str.charAt(start) - '0'); start ++; } return flag == 2 ? -(int)res : (int)res; } } 11. 正则表达式匹配 剑指offer：正则表达式匹配 请实现一个函数用来匹配包括’.’和’*’的正则表达式。模式中的字符’.’表示任意一个字符，而’*’表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串”aaa”与模式”a.a”和”ab*ac*a”匹配，但是与”aa.a”和”ab*a”均不匹配 image 动态规划： 这里我们采用dp[i+1][j+1]代表s[0..i]匹配p[0..j]的结果，结果自然是采用布尔值True/False来表示。 首先，对边界进行赋值，显然dp[0][0] = true，两个空字符串的匹配结果自然为True; 接着，我们对dp[0][j+1]进行赋值，因为 i=0 是空串，如果一个空串和一个匹配串想要匹配成功，那么只有可能是p.charAt(j) == '*' && dp[0][j-1] 之后，就可以愉快地使用动态规划递推方程了。 public boolean isMatch(String s, String p) { if (s == null || p == null) { return false; } boolean[][] dp = new boolean[s.length()+1][p.length()+1]; dp[0][0] = true; for (int j = 0; i < p.length(); j++) { if (p.charAt(j) == '*' && dp[0][j-1]) { dp[0][j+1] = true; } } for (int i = 0 ; i < s.length(); i++) { for (int j = 0; j < p.length(); j++) { if (p.charAt(j) == '.') { dp[i+1][j+1] = dp[i][j]; } if (p.charAt(j) == s.charAt(i)) { dp[i+1][j+1] = dp[i][j]; } if (p.charAt(j) == '*') { if (p.charAt(j-1) != s.charAt(i) && p.charAt(j-1) != '.') { dp[i+1][j+1] = dp[i+1][j-1]; } else { dp[i+1][j+1] = (dp[i+1][j] || dp[i][j+1] || dp[i+1][j-1]); } } } } return dp[s.length()][p.length()]; } 12. 表示数值的字符串 剑指offer: 表示数值的字符串 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100″,”5e2″,”-123″,”3.1416″和”-1E-16″都表示数值。 但是”12e”,”1a3.14″,”1.2.3″,”+-5″和”12e+4.3″都不是。 设置三个标志符分别记录“+/-”、“e/E”和“.”是否出现过。 public class Solution { public boolean isNumeric(char[] str) { int len = str.length; boolean sign = false, decimal = false, hasE = false; for(int i = 0; i < len; i++){ if(str[i] == '+' || str[i] == '-'){ if(!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false; if(sign && str[i-1] != 'e' && str[i-1] != 'E') return false; sign = true; }else if(str[i] == 'e' || str[i] == 'E'){ if(i == len - 1) return false; if(hasE) return false; hasE = true; }else if(str[i] == '.'){ if(hasE || decimal) return false; decimal = true; }else if(str[i] < '0' || str[i] > '9') return false; } return true; } } 13. 字符流中第一个不重复的字符 剑指offer: 字符流中第一个不重复的字符 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。 用一个哈希表来存储每个字符及其出现的次数，另外用一个字符串 s 来保存字符流中字符的顺序。 import java.util.HashMap; public class Solution { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); StringBuffer s = new StringBuffer(); //Insert one char from stringstream public void Insert(char ch) { s.append(ch); if(map.containsKey(ch)){ map.put(ch, map.get(ch)+1); }else{ map.put(ch, 1); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { for(int i = 0; i < s.length(); i++){ if(map.get(s.charAt(i)) == 1) return s.charAt(i); } return '#'; } }
本文首发于我的个人博客：尾尾部落 0. 基础概念 栈：后进先出（LIFO） image 队列：先进先出（FIFO） image 1. 栈的 java 实现 import java.util.Arrays; public class Stack { private int size = 0; //栈顶位置 private int[] array; public Stack(){ this(10); } public Stack(int init) { if(init <= 0){ init = 10; } array = new int[init]; } /** * 入栈操作 * @param item 入栈的元素 */ public void push(int item){ if(size == array.length){ array = Arrays.copyOf(array, size*2); //扩容操作 } array[size++] = item; } /** * 获取栈顶元素，但栈顶元素不出栈 * @return 栈顶元素 */ public int peek(){ if(size == 0){ //空栈 throw new IndexOutOfBoundsException("栈是空的"); } return array[size-1]; } /** * 出栈，同时获取栈顶元素 * @return */ public int pop(){ int item = peek(); //获取栈顶元素 size--; //直接使元素个数减1，不用清除元素，下次入栈会覆盖旧元素的值 return item; } /** * 判断栈是否已满 * @return */ public boolean isFull(){ return size == array.length; } /** * 判断栈是否为空 * @return */ public boolean isEmpty(){ return size == 0; } public int getSize(){ return size; } } 2. 队列的 java 实现 public class ArrayQueue { private final Object[] queue; //声明一个数组 private int head; private int tail; /** * 初始化队列 * @param capacity 队列长度 */ public ArrayQueue(int capacity){ this.queue = new Object[capacity]; } /** * 入队 * @param o 入队元素 * @return 入队成功与否 */ public boolean put(Object o){ if(head == (tail+1)%queue.length){ //说明队满 return false; } queue[tail] = o; tail = (tail+1)%queue.length; //tail标记后移一位 return true; } /** * 返回队首元素，但不出队 * @return */ public Object peak() { if(head==tail){ //队空 return null; } return queue[head]; } /** * 出队 * @return 出队元素 */ public Object pull(){ if(head==tail){ return null; } Object item = queue[head]; queue[head] = null; return item; } /** * 判断是否为空 * @return */ public boolean isEmpty(){ return head == tail; } /** * 判断是否为满 * @return */ public boolean isFull(){ return head == (tail+1)%queue.length; } /** * 获取队列中的元素个数 * @return */ public int getsize(){ if(tail>=head){ return tail-head; }else{ return (tail+queue.length)-head; } } } 3. 用两个栈实现队列 剑指offer：用两个栈实现队列 LeetCode：Implement Queue using Stacks class MyQueue { Stack<Integer> input = new Stack<Integer>(); Stack<Integer> output = new Stack<Integer>(); /** Push element x to the back of queue. */ public void push(int x) { input.push(x); } /** Removes the element from in front of queue and returns that element. */ public int pop() { peek(); return output.pop(); } /** Get the front element. */ public int peek() { if(output.isEmpty()){ while(!input.isEmpty()) output.push(input.pop()); } return output.peek(); } /** Returns whether the queue is empty. */ public boolean empty() { return input.isEmpty() && output.isEmpty(); } } 4. 用队列实现栈 LeetCode：Implement Stack using Queues class MyStack { Queue<Integer> q1 = new LinkedList<Integer>(); Queue<Integer> q2 = new LinkedList<Integer>(); /** Push element x onto stack. */ public void push(int x) { if(q1.isEmpty()){ q1.add(x); for(int i = 0; i < q2.size(); i++){ q1.add(q2.poll()); } }else{ q2.add(x); for(int i = 0; i < q1.size(); i++){ q2.add(q1.poll()); } } } /** Removes the element on top of the stack and returns that element. */ public int pop() { return q1.isEmpty() ? q2.poll() : q1.poll(); } /** Get the top element. */ public int top() { return q1.isEmpty() ? q2.peek() : q1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return q1.isEmpty() && q2.isEmpty(); } } 5. 包含min函数的栈 剑指offer：包含min函数的栈 定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。 class MinStack { Stack<Integer> stack = new Stack<Integer>(); Stack<Integer> temp = new Stack<Integer>(); public void push(int x) { stack.push(x); if(temp.isEmpty() || temp.peek() >= x) temp.push(x); } public void pop() { int x = stack.pop(); int min = temp.peek(); if(x == min) temp.pop(); } public int top() { return stack.peek(); } public int getMin() { return temp.peek(); } } 6. 栈的压入、弹出序列 剑指offer：栈的压入、弹出序列 输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的） import java.util.ArrayList; import java.util.Stack; public class Solution { public boolean IsPopOrder(int [] pushA, int [] popA) { if(pushA.length != popA.length || pushA.length == 0 || popA.length == 0) return false; Stack<Integer> stack = new Stack<>(); int index = 0; for(int i = 0; i < pushA.length; i++){ stack.push(pushA[i]); while(!stack.empty() && stack.peek() == popA[index]){ stack.pop(); index++; } } return stack.empty(); } }
本文首发于我的个人博客：尾尾部落 0. 几个概念 完全二叉树：若二叉树的高度是h，除第h层之外，其他（1h-1）层的节点数都达到了最大个数，并且第h层的节点都连续的集中在最左边。想到点什么没？实际上，完全二叉树和堆联系比较紧密哈~~ 满二叉树：除最后一层外，每一层上的所有节点都有两个子节点，最后一层都是叶子节点。 哈夫曼树：给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。 二叉排序树：又称二叉查找树（Binary Search Tree），亦称二叉搜索树。二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若右子树不空，则右子树上所有结点的值均大于或等于它的根结点的值； 左、右子树也分别为二叉排序树； 没有键值相等的节点 二分查找的时间复杂度是O(log(n))，最坏情况下的时间复杂度是O(n)（相当于顺序查找） 平衡二叉树：又称 AVL 树。平衡二叉树是二叉搜索树的进化版，所谓平衡二叉树指的是，左右两个子树的高度差的绝对值不超过 1。 红黑树：红黑树是每个节点都带颜色的树，节点颜色或是红色或是黑色，红黑树是一种查找树。红黑树有一个重要的性质，从根节点到叶子节点的最长的路径不多于最短的路径的长度的两倍。对于红黑树，插入，删除，查找的复杂度都是O（log N）。 1. 求二叉树中的节点个数 递归解法： （1）如果二叉树为空，节点个数为0 （2）如果不为空，二叉树节点个数 = 左子树节点个数 + 右子树节点个数 + 1 参考代码如下： public static int getNodeNumRec(TreeNode root) { if (root == null) { return 0; } return getNodeNumRec(root.left) + getNodeNumRec(root.right) + 1; } 2. 求二叉树的最大层数(最大深度) 剑指offer：二叉树的深度 递归解法： （1）如果二叉树为空，二叉树的深度为0 （2）如果二叉树不为空，二叉树的深度 = max(左子树深度， 右子树深度) + 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; return Math.max(maxDepth(root.left), maxDepth(root.right))+1; } } 2.1 二叉树的最小深度 LeetCode：Minimum Depth of Binary Tree 给定一个二叉树，找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 image class Solution { public int minDepth(TreeNode root) { if(root == null) return 0; int left = minDepth(root.left); int right = minDepth(root.right); return (left == 0 || right == 0) ? left + right + 1 : Math.min(left, right) + 1; } } 3. 先序遍历/前序遍历 LeetCode：Binary Tree Preorder Traversal 给定二叉树，返回其节点值的前序遍历。 image 根 - 左 - 右 递归 ArrayList<Integer> preOrderReverse(TreeNode root){ ArrayList<Integer> result = new ArrayList<Integer>(); preOrder(root, result); return result; } void preOrder(TreeNode root,ArrayList<Integer> result){ if(root == null){ return; } result.add(root.val); preOrder(root.left, result); preOrder(root.right, result); } 非递归 法一： import java.util.Stack; class Solution { public List<Integer> preorderTraversal(TreeNode root) { LinkedList<Integer> res = new LinkedList<>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<>(); stack.push(root); while(!stack.isEmpty()){ TreeNode node = stack.pop(); res.add(node.val); if(node.right != null){ stack.push(node.right); } if(node.left != null){ stack.push(node.left); } } return res; } } 法二： class Solution { public List<Integer> preorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; while(cur != null || !stack.isEmpty()){ if(cur!=null){ res.add(cur.val); stack.push(cur); cur = cur.left; }else{ cur = stack.pop(); cur = cur.right; } } return res; } } 4. 中序遍历 LeetCode：Binary Tree Inorder Traversal 给定二叉树，返回其节点值的中序遍历。 image 左 - 根 - 右 递归 void inOrder(TreeNode root,ArrayList<Integer> result){ if(root == null){ return; } preOrder(root.left, result); result.add(root.val); preOrder(root.right, result); } 非递归 /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> inorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; while(!stack.isEmpty() || cur != null){ if(cur != null){ stack.push(cur); cur = cur.left; }else{ cur = stack.pop(); res.add(cur.val); cur = cur.right; } } return res; } } 5. 后序遍历 Leetcode：Binary Tree Postorder Traversal 给定二叉树，返回其节点值的后序遍历。 image 左 - 右 - 根 递归 void inOrder(TreeNode root,ArrayList<Integer> result){ if(root == null){ return; } preOrder(root.left, result); preOrder(root.right, result); result.add(root.val); } 非递归 方法一： /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> ans = new LinkedList<>(); Stack<TreeNode> stack = new Stack<>(); if (root == null) return ans; stack.push(root); while (!stack.isEmpty()) { TreeNode cur = stack.pop(); //采用逆序插入的方式 ans.addFirst(cur.val); if (cur.left != null) { stack.push(cur.left); } if (cur.right != null) { stack.push(cur.right); } } return ans; } } 方法二： /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<Integer> postorderTraversal(TreeNode root) { List<Integer> res = new ArrayList<Integer>(); if(root == null) return res; Stack<TreeNode> stack = new Stack<TreeNode>(); TreeNode cur = root; TreeNode visited = null; while(!stack.isEmpty() || cur != null){ if(cur != null){ stack.push(cur); cur = cur.left; }else{ cur = stack.peek(); if(cur.right != null && cur.right != visited){ cur = cur.right; }else{ res.add(cur.val); visited = cur; stack.pop(); cur = null; } } } return res; } } 方法三(推荐)： class Solution { public List<Integer> postorderTraversal(TreeNode root) { LinkedList<Integer> result = new LinkedList<>(); Deque<TreeNode> stack = new ArrayDeque<>(); TreeNode p = root; while(!stack.isEmpty() || p != null) { if(p != null) { stack.push(p); result.addFirst(p.val); // Reverse the process of preorder p = p.right; // Reverse the process of preorder } else { TreeNode node = stack.pop(); p = node.left; // Reverse the process of preorder } } return result; } } 6. 分层遍历 LeetCode：Binary Tree Level Order Traversal 剑指offer：从上往下打印二叉树 剑指offer：把二叉树打印成多行 给定二叉树，返回其节点值的级别顺序遍历。 image /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(root == null) return res; Queue<TreeNode> queue = new LinkedList<TreeNode>(); TreeNode cur = null; queue.add(root); while(!queue.isEmpty()){ ArrayList<Integer> level = new ArrayList<Integer>(); int l = queue.size(); for(int i=0; i<l;i++){ cur = queue.poll(); level.add(cur.val); if(cur.left != null) queue.add(cur.left); if(cur.right != null) queue.add(cur.right); } res.add(level); } return res; } } 6.1 自下而上分层遍历 LeetCode：Binary Tree Level Order Traversal II 给定二叉树，返回其节点值的自下而上级别顺序遍历。 class Solution { public List<List<Integer>> levelOrderBottom(TreeNode root) { List<List<Integer>> res = new LinkedList<>(); Queue<TreeNode> queue = new LinkedList<>(); if(root == null) return res; queue.add(root); while(!queue.isEmpty()){ int count = queue.size(); List<Integer> temp = new LinkedList<>(); for(int i=0; i<count; i++){ TreeNode node = queue.poll(); temp.add(node.val); if(node.left != null) queue.add(node.left); if(node.right != null) queue.add(node.right); } // 每次都添加到第一个位置 res.add(0, temp); } return res; } } 6.2 按之字形顺序打印二叉树 剑指offer：按之字形顺序打印二叉树 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 设两个栈，s2存放奇数层，s1存放偶数层 遍历s2节点的同时按照左子树、右子树的顺序加入s1， 遍历s1节点的同时按照右子树、左子树的顺序加入s2 import java.util.ArrayList; import java.util.Stack; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); int flag = 1; if(pRoot == null) return res; s2.push(pRoot); ArrayList<Integer> temp = new ArrayList<Integer>(); while(!s1.isEmpty() || !s2.isEmpty()){ if(flag % 2 != 0){ while(!s2.isEmpty()){ TreeNode node = s2.pop(); temp.add(node.val); if(node.left != null){ s1.push(node.left); } if(node.right != null){ s1.push(node.right); } } } if(flag % 2 == 0){ while(!s1.isEmpty()){ TreeNode node = s1.pop(); temp.add(node.val); if(node.right != null){ s2.push(node.right); } if(node.left != null){ s2.push(node.left); } } } res.add(new ArrayList<Integer>(temp)); temp.clear(); flag ++; } return res; } } 7. 求二叉树第K层的节点个数 void get_k_level_number(TreeNode root, int k){ if(root == null || k <=0){ return 0; } if(root != null && k == 1){ return 1; } return get_k_level_number(root.left, k-1) + get_k_level_number(root.right, k-1); } 8. 求二叉树第K层的叶子节点个数 void get_k_level_leaf_number(TreeNode root, int k){ if(root == null || k <=0){ return 0; } if(root != null && k == 1){ if(root.left == null && root.right == null) return 1; else return 0; } return get_k_level_number(root.left, k-1) + get_k_level_number(root.right, k-1); } 9. 判断两棵二叉树是否结构相同 LeetCode：Same Tree 给定两个二叉树，编写一个函数来检查它们是否相同。 递归解法： （1）如果两棵二叉树都为空，返回真 （2）如果两棵二叉树一棵为空，另一棵不为空，返回假 （3）如果两棵二叉树都不为空，如果对应的左子树和右子树都同构返回真，其他返回假 class Solution { public boolean isSameTree(TreeNode p, TreeNode q) { if(p == null && q == null) return true; if(p == null || q == null) return false; if(p.val == q.val) return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); return false; } } 10. 判断二叉树是不是平衡二叉树 LeetCode：Balanced Binary Tree 给定二叉树，确定它是否是高度平衡的。 对于此问题，高度平衡二叉树定义为： 一个二叉树，其中每个节点的两个子树的深度差不相差超过1。 递归解法： （1）如果二叉树为空，返回真 （2）如果二叉树不为空，如果左子树和右子树高度相差不大于1且左子树和右子树都是AVL树，返回真，其他返回假 class Solution { public boolean isBalanced(TreeNode root) { if(root == null) return true; return Math.abs(maxHigh(root.left) - maxHigh(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } public int maxHigh(TreeNode root){ if(root == null) return 0; return Math.max(maxHigh(root.left), maxHigh(root.right))+1; } } 11. 求二叉树的镜像 剑指offer：二叉树的镜像 LeetCode：Invert Binary Tree 反转二叉树 image class Solution { public TreeNode invertTree(TreeNode root) { if(root == null) return root; TreeNode node = root.left; root.left = invertTree(root.right); root.right = invertTree(node); return root; } } 11.1 对称二叉树 剑指offer：对称的二叉树 LeetCode：Symmetric Tree 给定一个二叉树，检查它是否是镜像对称的。 image class Solution { public boolean isSymmetric(TreeNode root) { return root == null || isSymmetricHelper(root.left, root.right); } public boolean isSymmetricHelper(TreeNode left, TreeNode right){ if(left == null && right == null) return true; if(left == null || right == null) return false; if(left.val != right.val) return false; return isSymmetricHelper(left.left, right.right) && isSymmetricHelper(left.right, right.left); } } 12. 求二叉树中两个节点的最低公共祖先节点 LeetCode：Lowest Common Ancestor of a Binary Tree 给定二叉树，找到树中两个给定节点的最低共同祖先（LCA）。 image 递归解法： （1）如果两个节点分别在根节点的左子树和右子树，则返回根节点 （2）如果两个节点都在左子树，则递归处理左子树；如果两个节点都在右子树，则递归处理右子树 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); if(left != null && right != null) return root; return left == null ? right : left; } } 12.1 求二叉搜索树的最近公共祖先 LeetCode：Lowest Common Ancestor of a Binary Search Tree 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” image 注意二叉搜索树的特性：左子树 < 根节点 < 右子树 class Solution { public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { if(root.val > p.val && root.val > q.val){ return lowestCommonAncestor(root.left, p, q); } else if(root.val < p.val && root.val < q.val){ return lowestCommonAncestor(root.right, p, q); } else{ return root; } } } 13. 求二叉树的直径 LeetCode：Diameter of Binary Tree 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过根结点。 image 递归解法：对于每个节点，它的最长路径等于左子树的最长路径+右子树的最长路径 class Solution { private int path = 0; public int diameterOfBinaryTree(TreeNode root) { diamHelper(root); return path; } private int diamHelper(TreeNode root){ if(root == null) return 0; int left = diamHelper(root.left); int right = diamHelper(root.right); path = Math.max(path, left + right); return Math.max(left, right) + 1; } } 14. 由前序遍历序列和中序遍历序列重建二叉树 剑指offer：重建二叉树 LeetCode：Construct Binary Tree from Preorder and Inorder Traversal 根据一棵树的前序遍历与中序遍历构造二叉树。 image class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length == 0 || inorder.length == 0) return null; return buildTreeHelper(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1); } public TreeNode buildTreeHelper(int[] preorder, int pre_start, int pre_end, int[] inorder, int in_start, int in_end){ if(pre_start > pre_end || in_start > in_end) return null; TreeNode root = new TreeNode(preorder[pre_start]); for(int i = in_start; i <= in_end; i++){ if(inorder[i] == preorder[pre_start]){ // 左子树的长度：i-is root.left = buildTreeHelper(preorder, pre_start + 1, pre_start + i - in_start, inorder, in_start, i - 1); root.right = buildTreeHelper(preorder, pre_start + i - in_start + 1, pre_end, inorder, i + 1, in_end); } } return root; } } 14.1 从中序与后序遍历序列构造二叉树 LeetCode：Construct Binary Tree from Inorder and Postorder Traversal 根据一棵树的中序遍历与后序遍历构造二叉树。 image 本题与“从前序与中序遍历序列构造二叉树”是一个套路。唯一的区别是，后序序列的最后一个节点是根节点，因此我们要从后序序列的最后一个节点入手，再去中序序列中找到这个节点。在这个节点左侧的属于根节点的左子树部分，右侧的属于根节点右子树部分。然后根据左右子树节点的数量，在后序序列中找到他们各自的后序序列。比左子树节点个数为5，那么在后序序列中前五个节点就是左子树节点，之后的节点除了最后一个节点都是右子树节点。 class Solution { public TreeNode buildTree(int[] inorder, int[] postorder) { if(inorder.length == 0 || postorder.length == 0) return null; return buildTreeHelper(inorder, 0, inorder.length - 1, postorder, 0, postorder.length - 1); } public TreeNode buildTreeHelper(int[] inorder, int in_start, int in_end, int[] postorder, int post_start, int post_end){ if(in_start > in_end || post_start > post_end) return null; TreeNode root = new TreeNode(postorder[post_end]); for(int i = in_start; i <= in_end; i++){ if(inorder[i] == postorder[post_end]){ root.left = buildTreeHelper(inorder, in_start, i - 1, postorder, post_start, post_start + i - in_start - 1); root.right = buildTreeHelper(inorder, i + 1, in_end, postorder, post_start + i - in_start, post_end - 1); } } return root; } } 提示：根据前序和后序遍历无法构造出唯一的二叉树 15. 判断二叉树是不是完全二叉树 完全二叉树是指最后一层左边是满的，右边可能慢也不能不满，然后其余层都是满的，根据这个特性，利用层遍历。如果我们当前遍历到了NULL结点，如果后续还有非NULL结点，说明是非完全二叉树。 class Solution { public boolean _CheckCompleteTree(TreeNode root) { Queue<TreeNode> queue = LinkedList<>(); if(root == null) return true; queue.add(root); while(!queue.isEmpty()){ TreeNode node = queue.pop(); if(node != null){ if(flag == true) return false; queue.add(node.left); queue.add(node.right); }else{ flag = true; } } return true; } } 16. 树的子结构 剑指offer：树的子结构 输入两棵二叉树A，B，判断B是不是A的子结构。 public class Solution { public boolean HasSubtree(TreeNode root1,TreeNode root2) { if(root1 == null || root2 == null){ return false; } return IsSubtree(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2); } public boolean IsSubtree(TreeNode root1, TreeNode root2){ //要先判断roo2, 不然{8,8,7,9,2,#,#,#,#,4,7},{8,9,2}这个测试用例通不过。 if(root2 == null) return true; if(root1 == null) return false; if(root1.val == root2.val){ return IsSubtree(root1.left, root2.left) && IsSubtree(root1.right, root2.right); }else return false; } } 17. 二叉树中和为某一值的路径 剑指offer：二叉树中和为某一值的路径 输入一颗二叉树和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。 public class Solution { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); ArrayList<Integer> temp = new ArrayList<Integer>(); public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) { if(root == null) return res; target -= root.val; temp.add(root.val); if(target == 0 && root.left == null && root.right == null) res.add(new ArrayList<Integer>(temp)); else{ FindPath(root.left, target); FindPath(root.right, target); } temp.remove(temp.size()-1); return res; } } 18. 二叉树的下一个结点 剑指offer：二叉树的下一个结点 给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。 public class Solution { public TreeLinkNode GetNext(TreeLinkNode pNode) { if(pNode == null){ return null; } if(pNode.right != null){ TreeLinkNode node = pNode.right; while(node.left != null){ node = node.left; } return node; } while(pNode.next != null){ TreeLinkNode root = pNode.next; if(pNode == root.left) return root; pNode = root; } return null; } } 19. 序列化二叉树 剑指offer：序列化二叉树 LeetCode：Serialize and Deserialize Binary Tree 请实现两个函数，分别用来序列化和反序列化二叉树 image public class Codec { // Encodes a tree to a single string. public String serialize(TreeNode root) { if(root == null) return "#,"; StringBuffer res = new StringBuffer(root.val + ","); res.append(serialize(root.left)); res.append(serialize(root.right)); return res.toString(); } // Decodes your encoded data to tree. public TreeNode deserialize(String data) { String [] d = data.split(","); Queue<String> queue = new LinkedList<>(); for(int i = 0; i < d.length; i++){ queue.offer(d[i]); } return pre(queue); } public TreeNode pre(Queue<String> queue){ String val = queue.poll(); if(val.equals("#")) return null; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = pre(queue); node.right = pre(queue); return node; } } 20. 二叉搜索树的第k个结点 剑指offer：二叉搜索树的第k个结点 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。 image 因为二叉搜索树按照中序遍历的顺序打印出来就是排好序的，所以，我们按照中序遍历找到第k个结点就是题目所求的结点。 class Solution { public int kthSmallest(TreeNode root, int k) { if(root == null) return Integer.MIN_VALUE; Stack<TreeNode> stack = new Stack<>(); int count = 0; TreeNode p = root; while(p != null || !stack.isEmpty()){ if(p != null){ stack.push(p); p = p.left; }else{ TreeNode node = stack.pop(); count ++; if(count == k) return node.val; p = node.right; } } return Integer.MIN_VALUE; } }
本文首发于我的个人博客：尾尾部落 链表是面试过程中经常被问到的，这里把剑指offer 和 LeetCode 中的相关题目做一个汇总，方便复习。 1. 在 O(1) 时间删除链表节点 题目描述：给定单向链表的头指针和一个节点指针，定义一个函数在O(1)时间删除该节点。解题思路：常规的做法是从链表的头结点开始遍历，找到需要删除的节点的前驱节点，把它的 next 指向要删除节点的下一个节点，平均时间复杂度为O(n)，不满足题目要求。 那是不是一定要得到被删除的节点的前一个节点呢？其实不用的。我们可以很方面地得到要删除节点的下一个节点，如果我们把下一个节点的内容复制到要删除的节点上覆盖原有的内容，再把下一个节点删除，那就相当于把当前要删除的节点删除了。举个栗子，我们要删除的节点i，先把i的下一个节点j的内容复制到i，然后把i的指针指向节点j的下一个节点。此时再删除节点j，其效果刚好是把节点i给删除了。 要注意两种情况： 如果链表中只有一个节点，即头节点等于要删除的节点，此时我们在删除节点之后，还需要把链表的头节点设置为NULL。 如果要删除的节点位于链表的尾部，那么它就没有下一个节点，这时我们就要从链表的头节点开始，顺序遍历得到该节点的前序节点，并完成删除操作。 参考代码 public static ListNode deleteNode(ListNode head, ListNode toBeDeleted) { // 如果输入参数有空值就返回表头结点 if (head == null || toBeDeleted == null) { return head; } // 如果删除的是头结点，直接返回头结点的下一个结点 if (head == toBeDeleted) { return head.next; } // 下面的情况链表至少有两个结点 // 在多个节点的情况下，如果删除的是最后一个元素 if (toBeDeleted.next == null) { // 找待删除元素的前驱 ListNode tmp = head; while (tmp.next != toBeDeleted) { tmp = tmp.next; } // 删除待结点 tmp.next = null; } // 在多个节点的情况下，如果删除的是某个中间结点 else { // 将下一个结点的值输入当前待删除的结点 toBeDeleted.value = toBeDeleted.next.value; // 待删除的结点的下一个指向原先待删除引号的下下个结点，即将待删除的下一个结点删除 toBeDeleted.next = toBeDeleted.next.next; } // 返回删除节点后的链表头结点 return head; } 2. 翻转单链表 题目描述：输出一个单链表的逆序反转后的链表。解题思路：用三个临时指针 prev、cur、next 在链表上循环一遍即可。 [剑指offer] 从尾到头打印链表[剑指offer] 反转链表 3. 翻转部分单链表： 题目描述：给定一个单向链表的头结点head,以及两个整数from和to,在单链表上把第from个节点和第to个节点这一部分进行反转 举例：1->2->3->4->5->null, from = 2, to = 4 结果：1->4->3->2->5->null public ListNode reverseBetween(ListNode head, int m, int n) { if (head == null) return null; if (head.next == null) return head; int i = 1; ListNode reversedNewHead = null;// 反转部分链表反转后的头结点 ListNode reversedTail = null;// 反转部分链表反转后的尾结点 ListNode oldHead = head;// 原链表的头结点 ListNode reversePreNode = null;// 反转部分链表反转前其头结点的前一个结点 ListNode reverseNextNode = null; while (head != null) { if (i > n) { break; } if (i == m - 1) { reversePreNode = head; } if (i >= m && i <= n) { if (i == m) { reversedTail = head; } reverseNextNode = head.next; head.next = reversedNewHead; reversedNewHead = head; head = reverseNextNode; } else { head = head.next; } i++; } reversedTail.next = reverseNextNode; if (reversePreNode != null) { reversePreNode.next = reversedNewHead; return oldHead; } else { return reversedNewHead; } } 4. 旋转单链表 题目描述：给定一个单链表，设计一个算法实现链表向右旋转 K 个位置。 举例： 给定 1->2->3->4->5->6->NULL, K=3 则4->5->6->1->2->3->NULL解题思路： 方法一 双指针，快指针先走k步，然后两个指针一起走，当快指针走到末尾时，慢指针的下一个位置是新的顺序的头结点，这样就可以旋转链表了。 方法二 先遍历整个链表获得链表长度n，然后此时把链表头和尾链接起来，在往后走n - k % n个节点就到达新链表的头结点前一个点，这时断开链表即可。 方法二代码： public class Solution { { public ListNode rotateRight(ListNode head, int k) { if (!head) return null; int n = 1; ListNode cur = head; while (cur.next) { ++n; cur = cur.next; } cur.next = head; int m = n - k % n; for (int i = 0; i < m; ++i) { cur = cur.next; } ListNode newhead = cur.next; cur.next = NULL; return newhead; } }; 5. 删除单链表倒数第 n 个节点 题目描述：删除单链表倒数第 n 个节点，1 <= n <= length，尽量在一次遍历中完成。解题思路：双指针法，找到倒数第 n+1 个节点，将它的 next 指向倒数第 n-1个节点。 [剑指offer] 链表中倒数第k个结点 6. 求单链表的中间节点 题目描述：求单链表的中间节点，如果链表的长度为偶数，返回中间两个节点的任意一个，若为奇数，则返回中间节点。解题思路：快慢指针，慢的走一步，快的走两步，当快指针到达尾节点时，慢指针移动到中间节点。 // 遍历一次，找出单链表的中间节点 public ListNode findMiddleNode(ListNode head) { if (null == head) { return; } ListNode slow = head; ListNode fast = head; while (null != fast && null != fast.next) { fast = fast.next.next; slow = slow.next; } return slow; } 7. 链表划分 题目描述： 给定一个单链表和数值x，划分链表使得所有小于x的节点排在大于等于x的节点之前。 public class Solution { /** * @param head: The first node of linked list. * @param x: an integer * @return: a ListNode */ public ListNode partition(ListNode head, int x) { // write your code here if(head == null) return null; ListNode leftDummy = new ListNode(0); ListNode rightDummy = new ListNode(0); ListNode left = leftDummy, right = rightDummy; while (head != null) { if (head.val < x) { left.next = head; left = head; } else { right.next = head; right = head; } head = head.next; } right.next = null; left.next = rightDummy.next; return leftDummy.next; } } 8. 链表求和 题目描述：你有两个用链表代表的整数，其中每个节点包含一个数字。数字存储按照在原来整数中相反的顺序，使得第一个数字位于链表的开头。写出一个函数将两个整数相加，用链表形式返回和。解题思路：做个大循环，对每一位进行操作： 当前位：(A[i]+B[i])%10 进位：（A[i]+B[i]）/10 public class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode c1 = l1; ListNode c2 = l2; ListNode sentinel = new ListNode(0); ListNode d = sentinel; int sum = 0; while (c1 != null || c2 != null) { sum /= 10; if (c1 != null) { sum += c1.val; c1 = c1.next; } if (c2 != null) { sum += c2.val; c2 = c2.next; } d.next = new ListNode(sum % 10); d = d.next; } if (sum / 10 == 1) d.next = new ListNode(1); return sentinel.next; } } 9. 单链表排序 题目描述：在O(nlogn)时间内对链表进行排序。快速排序： public ListNode sortList(ListNode head) { //采用快速排序 quickSort(head, null); return head; } public static void quickSort(ListNode head, ListNode end) { if (head != end) { ListNode node = partion(head, end); quickSort(head, node); quickSort(node.next, end); } } public static ListNode partion(ListNode head, ListNode end) { ListNode p1 = head, p2 = head.next; //走到末尾才停 while (p2 != end) { //大于key值时，p1向前走一步，交换p1与p2的值 if (p2.val < head.val) { p1 = p1.next; int temp = p1.val; p1.val = p2.val; p2.val = temp; } p2 = p2.next; } //当有序时，不交换p1和key值 if (p1 != head) { int temp = p1.val; p1.val = head.val; head.val = temp; } return p1; } 归并排序： public ListNode sortList(ListNode head) { //采用归并排序 if (head == null || head.next == null) { return head; } //获取中间结点 ListNode mid = getMid(head); ListNode right = mid.next; mid.next = null; //合并 return mergeSort(sortList(head), sortList(right)); } /** * 获取链表的中间结点,偶数时取中间第一个 * * @param head * @return */ private ListNode getMid(ListNode head) { if (head == null || head.next == null) { return head; } //快慢指针 ListNode slow = head, quick = head; //快2步，慢一步 while (quick.next != null && quick.next.next != null) { slow = slow.next; quick = quick.next.next; } return slow; } /** * * 归并两个有序的链表 * * @param head1 * @param head2 * @return */ private ListNode mergeSort(ListNode head1, ListNode head2) { ListNode p1 = head1, p2 = head2, head; //得到头节点的指向 if (head1.val < head2.val) { head = head1; p1 = p1.next; } else { head = head2; p2 = p2.next; } ListNode p = head; //比较链表中的值 while (p1 != null && p2 != null) { if (p1.val <= p2.val) { p.next = p1; p1 = p1.next; p = p.next; } else { p.next = p2; p2 = p2.next; p = p.next; } } //第二条链表空了 if (p1 != null) { p.next = p1; } //第一条链表空了 if (p2 != null) { p.next = p2; } return head; } 10. 合并两个排序的链表 题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。 [剑指offer] 合并两个排序的链表 11. 复杂链表的复制 题目描述：输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空） [剑指offer] 复杂链表的复制 12. 删除链表中重复的结点 题目描述：在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 [剑指offer] 删除链表中重复的结点 13. 判断单链表是否存在环 题目描述：判断一个单链表是否有环 分析：快慢指针，慢指针每次移动一步，快指针每次移动两步，如果存在环，那么两个指针一定会在环内相遇。 14. 单链表是否有环扩展：找到环的入口点 题目描述：判断单链表是否有环，如果有，找到环的入口点解题思路：在第 5 题两个指针相遇后，让其中一个指针回到链表的头部，另一个指针在原地，同时往前每次走一步，当它们再次相遇时，就是在环路的入口点。 [剑指offer] 链表中环的入口结点 15. 判断两个无环单链表是否相交 题目描述：给出两个无环单链表解题思路： 方法一 最直接的方法是判断 A 链表的每个节点是否在 B 链表中，但是这种方法的时间复杂度为 O(Length(A) * Length(B))。 方法二 转化为环的问题。把 B 链表接在 A 链表后面，如果得到的链表有环，则说明两个链表相交。可以之前讨论过的快慢指针来判断是否有环，但是这里还有更简单的方法。如果 B 链表和 A 链表相交，把 B 链表接在 A 链表后面时，B 链表的所有节点都在环内，所以此时只需要遍历 B 链表，看是否会回到起点就可以判断是否相交。这个方法需要先遍历一次 A 链表，找到尾节点，然后还要遍历一次 B 链表，判断是否形成环，时间复杂度为 O(Length(A) + Length(B))。 方法三 除了转化为环的问题，还可以利用“如果两个链表相交于某一节点，那么之后的节点都是共有的”这个特点，如果两个链表相交，那么最后一个节点一定是共有的。所以可以得出另外一种解法，先遍历 A 链表，记住尾节点，然后遍历 B 链表，比较两个链表的尾节点，如果相同则相交，不同则不相交。时间复杂度为 O(Length(A) + Length(B))，空间复杂度为 O(1)，思路比解法 2 更简单。 方法三的代码： public boolean isIntersect(ListNode headA, ListNode headB) { if (null == headA || null == headB) { return false; } if (headA == headB) { return true; } while (null != headA.next) { headA = headA.next; } while (null != headB.next) { headB = headB.next; } return headA == headB; } 16. 两个链表相交扩展：求两个无环单链表的第一个相交点 题目描述：找到两个无环单链表第一个相交点，如果不相交返回空，要求在线性时间复杂度和常量空间复杂度内完成。解题思路： 方法一 如果两个链表存在公共结点，那么它们从公共结点开始一直到链表的结尾都是一样的，因此我们只需要从链表的结尾开始，往前搜索，找到最后一个相同的结点即可。但是题目给出的单向链表，我们只能从前向后搜索，这时，我们就可以借助栈来完成。先把两个链表依次装到两个栈中，然后比较两个栈的栈顶结点是否相同，如果相同则出栈，如果不同，那最后相同的结点就是我们要的返回值。 方法二 先找出2个链表的长度，然后让长的先走两个链表的长度差，然后再一起走，直到找到第一个公共结点。 方法三 由于2个链表都没有环，我们可以把第二个链表接在第一个链表后面，这样就把问题转化为求环的入口节点问题。 方法四 两个指针p1和p2分别指向链表A和链表B，它们同时向前走，当走到尾节点时，转向另一个链表，比如p1走到链表 A 的尾节点时，下一步就走到链表B，p2走到链表 B 的尾节点时，下一步就走到链表 A，当p1==p2 时，就是链表的相交点 方法四的代码： public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (null == headA || null == headB) { return null; } if (headA == headB) { return headA; } ListNode p1 = headA; ListNode p2 = headB; while (p1 != p2) { // 遍历完所在链表后从另外一个链表再开始 // 当 p1 和 p2 都换到另一个链表时，它们对齐了： // （1）如果链表相交，p1 == p2 时为第一个相交点 // （2）如果链表不相交，p1 和 p2 同时移动到末尾，p1 = p2 = null，然后退出循环 p1 = (null == p1) ? headB : p1.next; p2 = (null == p2) ? headA : p2.next; } return p1; } [剑指offer] 两个链表的第一个公共结点 17. 两个链表相交扩展：判断两个有环单链表是否相交 题目描述：上面的问题是针对无环链表的，如果是链表有环呢？解题思路：如果两个有环单链表相交，那么它们一定共有一个环，即环上的任意一个节点都存在于两个链表上。因此可以先用之前快慢指针的方式找到两个链表中位于环内的两个节点，如果相交的话，两个节点在一个环内，那么移动其中一个节点，在一次循环内肯定可以与另外一个节点相遇。
本文首发于我的个人博客：尾尾部落 排序算法是最经典的算法知识。因为其实现代码短，应该广，在面试中经常会问到排序算法及其相关的问题。一般在面试中最常考的是快速排序和归并排序等基本的排序算法，并且经常要求现场手写基本的排序算法。如果这些问题回答不好，估计面试就凉凉了。所以熟练掌握排序算法思想及其特点并能够熟练地手写代码至关重要。 下面介绍几种常见的排序算法：冒泡排序、选择排序、插入排序、归并排序、快速排序、希尔排序、堆排序、计数排序、桶排序、基数排序的思想，其代码均采用Java实现。 1. 冒泡排序 冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。 算法描述 比较相邻的元素。如果第一个比第二个大，就交换它们两个； 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数； 针对所有的元素重复以上的步骤，除了最后一个； 重复步骤1~3，直到排序完成。 动图演示 冒泡排序 算法实现 public static void bubbleSort(int[] arr) { int temp = 0; for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度 for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; } }//loop j }//loop i }// method bubbleSort 稳定性 在相邻元素相等时，它们并不会交换位置，所以，冒泡排序是稳定排序。 适用场景 冒泡排序思路简单，代码也简单，特别适合小数据的排序。但是，由于算法复杂度较高，在数据量大的时候不适合使用。 代码优化 在数据完全有序的时候展现出最优时间复杂度，为O(n)。其他情况下，几乎总是O( n^2 )。因此，算法在数据基本有序的情况下，性能最好。 要使算法在最佳情况下有O(n)复杂度，需要做一些改进，增加一个swap的标志，当前一轮没有进行交换时，说明数组已经有序，没有必要再进行下一轮的循环了，直接退出。 public static void bubbleSort(int[] arr) { int temp = 0; boolean swap; for (int i = arr.length - 1; i > 0; i--) { // 每次需要排序的长度 swap=false; for (int j = 0; j < i; j++) { // 从第一个元素到第i个元素 if (arr[j] > arr[j + 1]) { temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; swap=true; } }//loop j if (swap==false){ break; } }//loop i }// method bubbleSort 2. 选择排序 选择排序是一种简单直观的排序算法，它也是一种交换排序算法，和冒泡排序有一定的相似度，可以认为选择排序是冒泡排序的一种改进。 算法描述 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。 重复第二步，直到所有元素均排序完毕。 动图演示 选择排序 算法实现 public static void selectionSort(int[] arr) { int temp, min = 0; for (int i = 0; i < arr.length - 1; i++) { min = i; // 循环查找最小值 for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { min = j; } } if (min != i) { temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; } } } 稳定性 用数组实现的选择排序是不稳定的，用链表实现的选择排序是稳定的。 不过，一般提到排序算法时，大家往往会默认是数组实现，所以选择排序是不稳定的。 适用场景 选择排序实现也比较简单，并且由于在各种情况下复杂度波动小，因此一般是优于冒泡排序的。在所有的完全交换排序中，选择排序也是比较不错的一种算法。但是，由于固有的O(n^2)复杂度，选择排序在海量数据面前显得力不从心。因此，它适用于简单数据排序。 3. 插入排序 插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。 算法描述 把待排序的数组分成已排序和未排序两部分，初始的时候把第一个元素认为是已排好序的。 从第二个元素开始，在已排好序的子数组中寻找到该元素合适的位置并插入该位置。 重复上述过程直到最后一个元素被插入有序子数组中。 动图演示 插入排序 算法实现 public static void insertionSort(int[] arr){ for (int i=1; i<arr.length; ++i){ int value = arr[i]; int position=i; while (position>0 && arr[position-1]>value){ arr[position] = arr[position-1]; position--; } arr[position] = value; }//loop i } 稳定性 由于只需要找到不大于当前数的位置而并不需要交换，因此，直接插入排序是稳定的排序方法。 适用场景 插入排序由于O( n^2 )的复杂度，在数组较大的时候不适用。但是，在数据比较少的时候，是一个不错的选择，一般做为快速排序的扩充。例如，在STL的sort算法和stdlib的qsort算法中，都将插入排序作为快速排序的补充，用于少量元素的排序。又如，在JDK 7 java.util.Arrays所用的sort方法的实现中，当待排数组长度小于47时，会使用插入排序。 4. 归并排序 归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。 算法描述 两种方法 递归法（Top-down） 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列 设定两个指针，最初位置分别为两个已经排序序列的起始位置 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置 重复步骤3直到某一指针到达序列尾 将另一序列剩下的所有元素直接复制到合并序列尾 迭代法（Bottom-up） 原理如下（假设序列共有n个元素）： 将序列每相邻两个数字进行归并操作，形成ceil(n/2)个序列，排序后每个序列包含两/一个元素 若此时序列数不是1个则将上述序列再次归并，形成ceil(n/4)个序列，每个序列包含四/三个元素 重复步骤2，直到所有元素排序完毕，即序列数为1 动图演示 归并排序 算法实现 public static void mergeSort(int[] arr){ int[] temp =new int[arr.length]; internalMergeSort(arr, temp, 0, arr.length-1); } private static void internalMergeSort(int[] arr, int[] temp, int left, int right){ //当left==right的时，已经不需要再划分了 if (left<right){ int middle = (left+right)/2; internalMergeSort(arr, temp, left, middle); //左子数组 internalMergeSort(arr, temp, middle+1, right); //右子数组 mergeSortedArray(arr, temp, left, middle, right); //合并两个子数组 } } // 合并两个有序子序列 private static void mergeSortedArray(int arr[], int temp[], int left, int middle, int right){ int i=left; int j=middle+1; int k=0; while (i<=middle && j<=right){ temp[k++] = arr[i] <= arr[j] ? arr[i++] : arr[j++]; } while (i <=middle){ temp[k++] = arr[i++]; } while ( j<=right){ temp[k++] = arr[j++]; } //把数据复制回原数组 for (i=0; i<k; ++i){ arr[left+i] = temp[i]; } } 稳定性 因为我们在遇到相等的数据的时候必然是按顺序“抄写”到辅助数组上的，所以，归并排序同样是稳定算法。 适用场景 归并排序在数据量比较大的时候也有较为出色的表现（效率上），但是，其空间复杂度O(n)使得在数据量特别大的时候（例如，1千万数据）几乎不可接受。而且，考虑到有的机器内存本身就比较小，因此，采用归并排序一定要注意。 5. 快速排序 快速排序是一个知名度极高的排序算法，其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现使它注定得到比其他算法更多的宠爱。 算法描述 从数列中挑出一个元素，称为"基准"（pivot）， 重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。 递归地（recursively）把小于基准值元素的子数列和大于基准值元素的子数列排序。 动图演示 快速排序 算法实现 public static void quickSort(int[] arr){ qsort(arr, 0, arr.length-1); } private static void qsort(int[] arr, int low, int high){ if (low >= high) return; int pivot = partition(arr, low, high); //将数组分为两部分 qsort(arr, low, pivot-1); //递归排序左子数组 qsort(arr, pivot+1, high); //递归排序右子数组 } private static int partition(int[] arr, int low, int high){ int pivot = arr[low]; //基准 while (low < high){ while (low < high && arr[high] >= pivot) --high; arr[low]=arr[high]; //交换比基准大的记录到左端 while (low < high && arr[low] <= pivot) ++low; arr[high] = arr[low]; //交换比基准小的记录到右端 } //扫描完成，基准到位 arr[low] = pivot; //返回的是基准的位置 return low; } 稳定性 快速排序并不是稳定的。这是因为我们无法保证相等的数据按顺序被扫描到和按顺序存放。 适用场景 快速排序在大多数情况下都是适用的，尤其在数据量大的时候性能优越性更加明显。但是在必要的时候，需要考虑下优化以提高其在最坏情况下的性能。 6. 堆排序 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。 树的概念 关于树的概念请参考：[算法总结] 二叉树 堆的概念 堆是一种特殊的完全二叉树（complete binary tree）。完全二叉树的一个“优秀”的性质是，除了最底层之外，每一层都是满的，这使得堆可以利用数组来表示（普通的一般的二叉树通常用链表作为基本容器表示），每一个结点对应数组中的一个元素。 如下图，是一个堆和数组的相互关系： image 对于给定的某个结点的下标 i，可以很容易的计算出这个结点的父结点、孩子结点的下标： Parent(i) = floor(i/2)，i 的父节点下标 Left(i) = 2i，i 的左子节点下标 Right(i) = 2i + 1，i 的右子节点下标 二叉堆一般分为两种：最大堆和最小堆。最大堆： 最大堆中的最大元素值出现在根结点（堆顶） 堆中每个父节点的元素值都大于等于其孩子结点（如果存在） image 最小堆： 最小堆中的最小元素值出现在根结点（堆顶） 堆中每个父节点的元素值都小于等于其孩子结点（如果存在） image 堆排序原理 堆排序就是把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。在堆中定义以下几种操作： 最大堆调整（Max-Heapify）：将堆的末端子节点作调整，使得子节点永远小于父节点 创建最大堆（Build-Max-Heap）：将堆所有数据重新排序，使其成为最大堆 堆排序（Heap-Sort）：移除位在第一个数据的根节点，并做最大堆调整的递归运算 继续进行下面的讨论前，需要注意的一个问题是：数组都是 Zero-Based，这就意味着我们的堆数据结构模型要发生改变 image 相应的，几个计算公式也要作出相应调整： Parent(i) = floor((i-1)/2)，i 的父节点下标 Left(i) = 2i + 1，i 的左子节点下标 Right(i) = 2(i + 1)，i 的右子节点下标 堆的建立和维护 堆可以支持多种操作，但现在我们关心的只有两个问题： 给定一个无序数组，如何建立为堆？ 删除堆顶元素后，如何调整数组成为新堆？ 先看第二个问题。假定我们已经有一个现成的大根堆。现在我们删除了根元素，但并没有移动别的元素。想想发生了什么：根元素空了，但其它元素还保持着堆的性质。我们可以把最后一个元素（代号A）移动到根元素的位置。如果不是特殊情况，则堆的性质被破坏。但这仅仅是由于A小于其某个子元素。于是，我们可以把A和这个子元素调换位置。如果A大于其所有子元素，则堆调整好了；否则，重复上述过程，A元素在树形结构中不断“下沉”，直到合适的位置，数组重新恢复堆的性质。上述过程一般称为“筛选”，方向显然是自上而下。 删除后的调整，是把最后一个元素放到堆顶，自上而下比较 删除一个元素是如此，插入一个新元素也是如此。不同的是，我们把新元素放在末尾，然后和其父节点做比较，即自下而上筛选。 插入是把新元素放在末尾，自下而上比较 那么，第一个问题怎么解决呢？ 常规方法是从第一个非叶子结点向下筛选，直到根元素筛选完毕。这个方法叫“筛选法”，需要循环筛选n/2个元素。 但我们还可以借鉴“插入排序”的思路。我们可以视第一个元素为一个堆，然后不断向其中添加新元素。这个方法叫做“插入法”，需要循环插入(n-1)个元素。 由于筛选法和插入法的方式不同，所以，相同的数据，它们建立的堆一般不同。大致了解堆之后，堆排序就是水到渠成的事情了。 动图演示 image 算法描述 我们需要一个升序的序列，怎么办呢？我们可以建立一个最小堆，然后每次输出根元素。但是，这个方法需要额外的空间（否则将造成大量的元素移动，其复杂度会飙升到O(n^2) ）。如果我们需要就地排序（即不允许有O(n)空间复杂度），怎么办？ 有办法。我们可以建立最大堆，然后我们倒着输出，在最后一个位置输出最大值，次末位置输出次大值……由于每次输出的最大元素会腾出第一个空间，因此，我们恰好可以放置这样的元素而不需要额外空间。很漂亮的想法，是不是？ 算法实现 public class ArrayHeap { private int[] arr; public ArrayHeap(int[] arr) { this.arr = arr; } private int getParentIndex(int child) { return (child - 1) / 2; } private int getLeftChildIndex(int parent) { return 2 * parent + 1; } private void swap(int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /** * 调整堆。 */ private void adjustHeap(int i, int len) { int left, right, j; left = getLeftChildIndex(i); while (left <= len) { right = left + 1; j = left; if (j < len && arr[left] < arr[right]) { j++; } if (arr[i] < arr[j]) { swap(array, i, j); i = j; left = getLeftChildIndex(i); } else { break; // 停止筛选 } } } /** * 堆排序。 * */ public void sort() { int last = arr.length - 1; // 初始化最大堆 for (int i = getParentIndex(last); i >= 0; --i) { adjustHeap(i, last); } // 堆调整 while (last >= 0) { swap(0, last--); adjustHeap(0, last); } } } 稳定性 堆排序存在大量的筛选和移动过程，属于不稳定的排序算法。 适用场景 堆排序在建立堆和调整堆的过程中会产生比较大的开销，在元素少的时候并不适用。但是，在元素比较多的情况下，还是不错的一个选择。尤其是在解决诸如“前n大的数”一类问题时，几乎是首选算法。 7. 希尔排序（插入排序的改良版） 在希尔排序出现之前，计算机界普遍存在“排序算法不可能突破O(n2)”的观点。希尔排序是第一个突破O(n2)的排序算法，它是简单插入排序的改进版。希尔排序的提出，主要基于以下两点： 插入排序算法在数组基本有序的情况下，可以近似达到O(n)复杂度，效率极高。 但插入排序每次只能将数据移动一位，在数组较大且基本无序的情况下性能会迅速恶化。 算法描述 先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1； 按增量序列个数k，对序列进行 k 趟排序； 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 动图演示 image 算法实现 Donald Shell增量 public static void shellSort(int[] arr){ int temp; for (int delta = arr.length/2; delta>=1; delta/=2){ //对每个增量进行一次排序 for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ //注意每个地方增量和差值都是delta temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta } O(n^(3/2)) by Knuth public static void shellSort2(int[] arr){ int delta = 1; while (delta < arr.length/3){//generate delta delta=delta*3+1; // <O(n^(3/2)) by Knuth,1973>: 1, 4, 13, 40, 121, ... } int temp; for (; delta>=1; delta/=3){ for (int i=delta; i<arr.length; i++){ for (int j=i; j>=delta && arr[j]<arr[j-delta]; j-=delta){ temp = arr[j-delta]; arr[j-delta] = arr[j]; arr[j] = temp; } }//loop i }//loop delta } 希尔排序的增量 希尔排序的增量数列可以任取，需要的唯一条件是最后一个一定为1（因为要保证按1有序）。但是，不同的数列选取会对算法的性能造成极大的影响。上面的代码演示了两种增量。 切记：增量序列中每两个元素最好不要出现1以外的公因子！（很显然，按4有序的数列再去按2排序意义并不大）。 下面是一些常见的增量序列。 第一种增量是最初Donald Shell提出的增量，即折半降低直到1。据研究，使用希尔增量，其时间复杂度还是O(n2)。 第二种增量Hibbard：{1, 3, ..., 2k-1}。该增量序列的时间复杂度大约是O(n1.5)。 第三种增量Sedgewick增量：(1, 5, 19, 41, 109,...)，其生成序列或者是94^i - 92^i + 1或者是4^i - 3*2^i + 1。 稳定性 我们都知道插入排序是稳定算法。但是，Shell排序是一个多次插入的过程。在一次插入中我们能确保不移动相同元素的顺序，但在多次的插入中，相同元素完全有可能在不同的插入轮次被移动，最后稳定性被破坏，因此，Shell排序不是一个稳定的算法。 适用场景 Shell排序虽然快，但是毕竟是插入排序，其数量级并没有后起之秀--快速排序O(n㏒n)快。在大量数据面前，Shell排序不是一个好的算法。但是，中小型规模的数据完全可以使用它。 计数排序 计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。 算法描述 找出待排序的数组中最大和最小的元素； 统计数组中每个值为i的元素出现的次数，存入数组C的第i项； 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）； 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。 动图演示 image 算法实现 public static void countSort(int[] a, int max, int min) { int[] b = new int[a.length];//存储数组 int[] count = new int[max - min + 1];//计数数组 for (int num = min; num <= max; num++) { //初始化各元素值为0，数组下标从0开始因此减min count[num - min] = 0; } for (int i = 0; i < a.length; i++) { int num = a[i]; count[num - min]++;//每出现一个值，计数数组对应元素的值+1 } for (int num = min + 1; num <= max; num++) { //加总数组元素的值为计数数组对应元素及左边所有元素的值的总和 count[num - min] += sum[num - min - 1] } for (int i = 0; i < a.length; i++) { int num = a[i];//源数组第i位的值 int index = count[num - min] - 1;//加总数组中对应元素的下标 b[index] = num;//将该值存入存储数组对应下标中 count[num - min]--;//加总数组中，该值的总和减少1。 } //将存储数组的值一一替换给源数组 for(int i=0;i<a.length;i++){ a[i] = b[i]; } } 稳定性 最后给 b 数组赋值是倒着遍历的，而且放进去一个就将C数组对应的值（表示前面有多少元素小于或等于A[i]）减去一。如果有相同的数x1,x2，那么相对位置后面那个元素x2放在（比如下标为4的位置），相对位置前面那个元素x1下次进循环就会被放在x2前面的位置3。从而保证了稳定性。 适用场景 排序目标要能够映射到整数域，其最大值最小值应当容易辨别。例如高中生考试的总分数，显然用0-750就OK啦；又比如一群人的年龄，用个0-150应该就可以了，再不济就用0-200喽。另外，计数排序需要占用大量空间，它比较适用于数据比较集中的情况。 桶排序 桶排序又叫箱排序，是计数排序的升级版，它的工作原理是将数组分到有限数量的桶子里，然后对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），最后将各个桶中的数据有序的合并起来。 计数排序是桶排序的一种特殊情况，可以把计数排序当成每个桶里只有一个元素的情况。网络中很多博文写的桶排序实际上都是计数排序，并非标准的桶排序，要注意辨别。 算法描述 找出待排序数组中的最大值max、最小值min 我们使用 动态数组ArrayList 作为桶，桶里放的元素也用 ArrayList 存储。桶的数量为(max-min)/arr.length+1 遍历数组 arr，计算每个元素 arr[i] 放的桶 每个桶各自排序 遍历桶数组，把排序好的元素放进输出数组 图片演示 image 算法实现 public static void bucketSort(int[] arr){ int max = Integer.MIN_VALUE; int min = Integer.MAX_VALUE; for(int i = 0; i < arr.length; i++){ max = Math.max(max, arr[i]); min = Math.min(min, arr[i]); } //桶数 int bucketNum = (max - min) / arr.length + 1; ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum); for(int i = 0; i < bucketNum; i++){ bucketArr.add(new ArrayList<Integer>()); } //将每个元素放入桶 for(int i = 0; i < arr.length; i++){ int num = (arr[i] - min) / (arr.length); bucketArr.get(num).add(arr[i]); } //对每个桶进行排序 for(int i = 0; i < bucketArr.size(); i++){ Collections.sort(bucketArr.get(i)); } System.out.println(bucketArr.toString()); } 稳定性 可以看出，在分桶和从桶依次输出的过程是稳定的。但是，由于我们在对每个桶进行排序时使用了其他算法，所以，桶排序的稳定性依赖于这一步。如果我们使用了快排，显然，算法是不稳定的。 适用场景 桶排序可用于最大最小值相差较大的数据情况，但桶排序要求数据的分布必须均匀，否则可能导致数据都集中到一个桶中。比如[104,150,123,132,20000], 这种数据会导致前4个数都集中到同一个桶中。导致桶排序失效。 基数排序 基数排序(Radix Sort)是桶排序的扩展，它的基本思想是：将整数按位数切割成不同的数字，然后按每个位数分别比较。 排序过程：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。 算法描述 取得数组中的最大数，并取得位数； arr为原始数组，从最低位开始取每个位组成radix数组； 对radix进行计数排序（利用计数排序适用于小范围数的特点）； 动图 image 算法实现 public abstract class Sorter { public abstract void sort(int[] array); } public class RadixSorter extends Sorter { private int radix; public RadixSorter() { radix = 10; } @Override public void sort(int[] array) { // 数组的第一维表示可能的余数0-radix，第二维表示array中的等于该余数的元素 // 如：十进制123的个位为3，则bucket[3][] = {123} int[][] bucket = new int[radix][array.length]; int distance = getDistance(array); // 表示最大的数有多少位 int temp = 1; int round = 1; // 控制键值排序依据在哪一位 while (round <= distance) { // 用来计数：数组counter[i]用来表示该位是i的数的个数 int[] counter = new int[radix]; // 将array中元素分布填充到bucket中，并进行计数 for (int i = 0; i < array.length; i++) { int which = (array[i] / temp) % radix; bucket[which][counter[which]] = array[i]; counter[which]++; } int index = 0; // 根据bucket中收集到的array中的元素，根据统计计数，在array中重新排列 for (int i = 0; i < radix; i++) { if (counter[i] != 0) for (int j = 0; j < counter[i]; j++) { array[index] = bucket[i][j]; index++; } counter[i] = 0; } temp *= radix; round++; } } private int getDistance(int[] array) { int max = computeMax(array); int digits = 0; int temp = max / radix; while(temp != 0) { digits++; temp = temp / radix; } return digits + 1; } private int computeMax(int[] array) { int max = array[0]; for(int i=1; i<array.length; i++) { if(array[i]>max) { max = array[i]; } } return max; } } 稳定性 通过上面的排序过程，我们可以看到，每一轮映射和收集操作，都保持从左到右的顺序进行，如果出现相同的元素，则保持他们在原始数组中的顺序。可见，基数排序是一种稳定的排序。 适用场景 基数排序要求较高，元素必须是整数，整数时长度10W以上，最大值100W以下效率较好，但是基数排序比其他排序好在可以适用字符串，或者其他需要根据多个条件进行排序的场景，例如日期，先排序日，再排序月，最后排序年 ，其它排序算法可是做不了的。 总结 image 参考 LeetCode领扣:面试 | 常用的排序算法总结 飞翔的猫咪: 用Java写算法 bubkoo: 常见排序算法
序号 题解 牛客 OJ 数据结构类型 03 [剑指offer] 二维数组中的查找 二维数组中的查找 数组 04 [剑指offer] 替换空格 替换空格 字符串 05 [剑指offer] 从尾到头打印链表 从尾到头打印链表 链表 06 [剑指offer] 重建二叉树 重建二叉树 树 07 [剑指offer] 用两个栈实现队列 用两个栈实现队列 栈、队列 08 [剑指offer] 旋转数组的最小数字 旋转数组的最小数字 数组 09 [剑指offer] 斐波那契数列 斐波那契数列 数组 10 [剑指offer] 二进制中1的个数 二进制中1的个数 数组 11 [剑指offer] 数值的整数次方 数值的整数次方 数值 14 [剑指offer] 调整数组顺序使奇数位于偶数前面 调整数组顺序使奇数位于偶数前面 数组 15 [剑指offer] 链表中倒数第k个结点 链表中倒数第k个结点 链表 16 [剑指offer] 反转链表 反转链表 链表 17 [剑指offer] 合并两个排序的链表 合并两个排序的链表 链表 18 [剑指offer] 树的子结构 树的子结构 树 19 [剑指offer] 二叉树的镜像 二叉树的镜像 树 20 [剑指offer] 顺时针打印矩阵 顺时针打印矩阵 数组 21 [剑指offer] 包含min函数的栈 包含min函数的栈 栈 22 [剑指offer] 栈的压入、弹出序列 栈的压入、弹出序列 栈 23 [剑指offer] 从上往下打印二叉树 从上往下打印二叉树 树 24 [剑指offer] 二叉搜索树的后序遍历序列 二叉搜索树的后序遍历序列 树 25 [剑指offer] 二叉树中和为某一值的路径 二叉树中和为某一值的路径 树 26 [剑指offer] 复杂链表的复制 复杂链表的复制 链表 27 [剑指offer] 二叉搜索树与双向链表 二叉搜索树与双向链表 树、链表 28 [剑指offer] 字符串的排列 字符串的排列 字符串 29 [剑指offer] 数组中出现次数超过一半的数字 数组中出现次数超过一半的数字 数组 30 [剑指offer] 最小的K个数 最小的k个数 数组 31 [剑指offer] 连续子数组的最大和 连续子数组的最大和 数组 32 [剑指offer] 整数中1出现的次数（从1到n整数中1出现的次数） 从1到n整数中1出现的次数 数组 33 [剑指offer] 把数组排成最小的数 把数组排成最小的数 数组 34 [剑指offer] 丑数 丑数 数值 35 [剑指offer] 第一个只出现一次的字符 第一个只出现一次的字符 字符串 36 [剑指offer] 数组中的逆序对 数组中的逆序对 数组 37 [剑指offer] 两个链表的第一个公共结点 两个链表的第一个公共结点 链表 38 [剑指offer] 数字在排序数组中出现的次数 数字在排序数组中出现的次数 数组 39 [剑指offer] 二叉树的深度 二叉树的深度 树 40 [剑指offer] 数组中只出现一次的数字 数组中只出现一次的数字 数组 41 [剑指offer] 和为S的两个数字 VS [剑指offer] 和为S的连续正数序列 和为s的两个数字 VS 和为S的连续正数序列 数值 42 [剑指offer] 翻转单词顺序列 VS [剑指offer] 左旋转字符串 翻转单词顺序 VS 左旋转字符串 字符串 44 [剑指offer] 扑克牌顺子 扑克牌的顺子 数组 45 [剑指offer] 孩子们的游戏(圆圈中最后剩下的数) 圆圈中最后剩下的数字 数组 46 [剑指offer] 求1+2+3+…+n 求1+2+…+n 233 数值 47 [剑指offer] 不用加减乘除做加法 不用加减乘除做加法 数值 49 [剑指offer] 把字符串转换成整数 把字符串转换成整数 字符串 51 [剑指offer] 数组中重复的数字 数组中重复的数字 数组 52 [剑指offer] 构建乘积数组 构建乘积数组 数组 53 [剑指offer] 正则表达式匹配 正则表达式匹配 字符串 54 [剑指offer] 表示数值的字符串 表示数值的字符串 字符串 55 [剑指offer] 字符流中第一个不重复的字符 字符流中第一个不重复的字符 字符串 56 [剑指offer] 链表中环的入口结点 链表中环的入口结点 链表 57 [剑指offer] 删除链表中重复的结点 删除链表中重复的结点 链表 58 [剑指offer] 二叉树的下一个结点 二叉树的下一个结点 树 59 [剑指offer] 对称的二叉树 对称的二叉树 树 60 [剑指offer] 按之字形顺序打印二叉树 按之字形顺序打印二叉树 树 61 [剑指offer] 把二叉树打印成多行 把二叉树打印成多行 树 62 [剑指offer] 序列化二叉树 序列化二叉树 树 63 [剑指offer] 二叉搜索树的第k个结点 二叉搜索树的第k个结点 树 64 [剑指offer] 数据流中的中位数 数据流中的中位数 数值 65 [剑指offer] 滑动窗口的最大值 滑动窗口的最大值 数组 66 [剑指offer] 矩阵中的路径 矩阵中的路径 数组 67 [剑指offer] 机器人的运动范围 机器人的运动范围 数组 Array 数组题目汇总[18题] [剑指offer] 二维数组中的查找 [剑指offer] 旋转数组的最小数字 [剑指offer] 调整数组顺序使奇数位于偶数前面 [剑指offer] 顺时针打印矩阵 [剑指offer] 数组中出现次数超过一半的数字 [剑指offer] 最小的K个数 [剑指offer] 连续子数组的最大和 [剑指offer] 把数组排成最小的数 [剑指offer] 数组中的逆序对 [剑指offer] 数字在排序数组中出现的次数 [剑指offer] 数组中只出现一次的数字 [剑指offer] 扑克牌顺子 [剑指offer] 孩子们的游戏(圆圈中最后剩下的数) [剑指offer] 数组中重复的数字 [剑指offer] 构建乘积数组 [剑指offer] 滑动窗口的最大值 [剑指offer] 矩阵中的路径 [剑指offer] 机器人的运动范围 链表题目汇总[8题] [剑指offer] 从尾到头打印链表 [剑指offer] 反转链表 [剑指offer] 链表中倒数第k个结点 [剑指offer] 合并两个排序的链表 [剑指offer] 复杂链表的复制 [剑指offer] 删除链表中重复的结点 [剑指offer] 链表中环的入口结点 [剑指offer] 两个链表的第一个公共结点 更多关于链表面试题的总结，请移步[算法总结] 一文搞懂面试链表题 二叉树题目汇总[13题] [剑指offer] 重建二叉树 [剑指offer] 树的子结构 [剑指offer] 二叉树的镜像 [剑指offer] 从上往下打印二叉树 [剑指offer] 二叉搜索树的后序遍历序列 [剑指offer] 二叉树中和为某一值的路径 [剑指offer] 二叉树的深度 [剑指offer] 二叉树的下一个结点 [剑指offer] 对称的二叉树 [剑指offer] 按之字形顺序打印二叉树 [剑指offer] 把二叉树打印成多行 [剑指offer] 序列化二叉树 [剑指offer] 二叉搜索树的第k个结点 更多关于二叉树面试题的总结，请移步 [算法总结] 20 道题搞定 BAT 面试——二叉树 堆栈和队列题目汇总[3题] [剑指offer] 用两个栈实现队列 [剑指offer] 包含min函数的栈 [剑指offer] 栈的压入、弹出序列 更多关于堆栈和队列面试题的总结，请移步 [算法总结] 6 道题搞定 BAT 面试——堆栈和队列
本文首发于我的个人博客：尾尾部落 题目描述 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。 解题思路 如果一个整数不为0，那么这个整数至少有一位是1。如果我们把这个整数减1，那么原来处在整数最右边的1就会变为0，原来在1后面的所有的0都会变成1(如果最右边的1后面还有0的话)。其余所有位将不会受到影响。 举个例子：一个二进制数1100，从右边数起第三位是处于最右边的一个1。减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.我们发现减1的结果是把最右边的一个1开始的所有位都取反了。这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。 来源于牛客网@菩提旭光 参考代码 public class Solution { public int NumberOf1(int n) { int count = 0; while(n!=0){ count += 1; n &= (n-1); } return count; } }
本文首发于我的个人博客：尾尾部落 题目描述 我们可以用2 * 1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2 * 1的小矩形无重叠地覆盖一个2 * n的大矩形，总共有多少种方法？ 解题思路 依旧是斐波那契数列 f(1) = 1 f(2) = 2 当n=3时，它可以由n=2的情况再覆盖一块得到，也可以由 n=1的情况再覆盖 2 块得到，所以 f(3) = f(1) + f(2)，依次往下推，可以得到 f(n) = 1, (n=1) f(n) = 2, (n=2) f(n) = f(n-1) + f(n-2), (n>2) 用递归的方法即可实现 参考代码 public class Solution { public int RectCover(int target) { if(target<=0){ return 0; } else if(target == 1|| target ==2){ return target; } else{ return RectCover(target-1) + RectCover(target-2); } } }
本文首发于我的个人博客：尾尾部落 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。 解题思路 f(1) = 1 f(2) = f(2-1) + f(2-2) f(3) = f(3-1) + f(3-2) + f(3-3) ... f(n) = f(n-1) + f(n-2) + f(n-3) + ... + f(n-(n-1)) + f(n-n) 因为青蛙可以跳上任意级的台阶，所以以青蛙跳上一个 4 级的台阶为例进行分析，它可以在开始直接跳 4 级到 4 级台阶，也可以从 1 级台阶上往上跳 3 个台阶到 4 级，也可以从 2 级台阶往上跳 2 个台阶到 4 级，还可以从 3 级台阶上跳 3 级到 4 级。所以f(4) = f(4-1) + f(4-2) + f(4-3) + f(4-4) 可以得出以下的公式： f(n) = f(n-1)+f(n-2)+...+f(n-(n-1)) + f(n-n) => f(0) + f(1) + f(2) + f(3) + ... + f(n-1) 又因为： f(n-1) = f(0) + f(1)+f(2)+f(3) + ... + f((n-1)-1) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) f(n) = f(0) + f(1) + f(2) + f(3) + ... + f(n-2) + f(n-1) = f(n-1) + f(n-1) = 2 * f(n-1) 最后可以得到 f(n) = 1, (n=0) f(n) = 1, (n=1) f(n) = 2*f(n-1),(n>=2) 参考代码 public class Solution { public int JumpFloorII(int target) { if(target<=0) return 0; if(target == 1||target ==2) return target; else return 2*JumpFloorII(target-1); } }
本文首发于我的个人博客：尾尾部落 题目描述 一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。 解题思路 按照题意， 1 级 ---- 1 种 2 级 ---- 2 种 3 级 ---- 3 种 4 级 ---- 5 种 5 级 ---- 8 种 我们可以得到一种规律，如果要跳 6 级，可以从 5 级跳一步到 6 级，5 级的方案中有多少种就有多少种跳法跳到 6 级；还可以从 4 级跳两步到 6 级，同理，4 级的方案有多少种就有多少种方法从 4 级跳到 6 级，所以可以得到公式f(n) = f(n-1) + f(n-2)，再结合 1 级和 2 级的情况，可以得以如下的规律： f(n) = 1, (n=1) f(n) = 2, (n=2) f(n) = f(n-1)+f(n-2) ,(n>2,n为整数) 这就是斐波那契数列的变形，因此可以用递归来实现。 参考代码 public class Solution { public int JumpFloor(int target) { if(target<=0) return 0; else if(target == 1|| target == 2) return target; else return JumpFloor(target-1)+JumpFloor(target-2); } }
本文首发于我的个人博客：尾尾部落 题目描述 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。 n<=39 解题思路 公式: f(n) = n, n <= 1 f(n) = f(n-1) + f(n-2), n > 1 可以直接使用递归的方法： if(n<=1) return n; else return Fibonacci(n-1)+Fibonacci(n-2); 递归的方法可能会遇到Stack Overflow， 所以我们可以考虑用动态规划的方法来实现。 采用自底向上方法来保存了先前计算的值，为后面的调用服务。 参考代码 public class Solution { public int Fibonacci(int n) { if(n == 0 || n == 1) return n; int fn1 = 0; int fn2 = 1; for(int i=2; i<=n; i++){ fn2 += fn1; fn1 = fn2 - fn1; } return fn2; } }
本文首发于我的个人博客：尾尾部落 题目描述 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。 解题思路 采用二分查找法。 需要考虑三种情况： array[mid] > array[high]: 出现这种情况的array类似[3,4,5,6,0,1,2]，此时最小数字一定在mid的右边。low = mid + 1 array[mid] == array[high]: 出现这种情况的array类似 [1,0,1,1,1] 或者[1,1,1,0,1]，此时最小数字不好判断在mid左边 还是右边,这时只好一个一个试high = high - 1 array[mid] < array[high]: 出现这种情况的array类似[2,2,3,4,5,6,6],此时最小数字一定就是array[mid]或者在mid的左 边。因为右边必然都是递增的。high = mid 注意这里有个坑：如果待查询的范围最后只剩两个数，那么mid 一定会指向下标靠前的数字。比如 array = [4,6]， array[low] = 4 array[mid] = 4 array[high] = 6 如果high = mid - 1，就会产生错误， 因此high = mid 参考代码 import java.util.ArrayList; public class Solution { public int minNumberInRotateArray(int [] array) { int len = array.length; if(len == 0) return 0; int low = 0, high = len - 1; while(low < high){ int mid = low + (high - low) / 2; if(array[mid] > array[high]){ low = mid + 1; }else if(array[mid] == array[high]){ high = high - 1; }else{ high = mid; } } return array[low]; } }
本文首发于我的个人博客：尾尾部落 题目描述 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。 解题思路 两个栈 stack1 和 stack2: push 动作都在 stack1 中进行， pop 动作在 stack2 中进行。当 stack2 不为空时，直接 pop，当 stack2 为空时，先把 stack1 中的元素 pop 出来，push 到 stack2 中，再从 stack2 中 pop 元素。 参考代码 import java.util.Stack; public class Solution { Stack<Integer> stack1 = new Stack<Integer>(); Stack<Integer> stack2 = new Stack<Integer>(); public void push(int node) { stack1.push(node); } public int pop() { if(stack1.isEmpty() && stack2.isEmpty()) throw new RuntimeException("Queue is empty!"); int node; if(stack2.isEmpty()){ while(!stack1.isEmpty()){ node = stack1.pop(); stack2.push(node); } } return stack2.pop(); } }
本文首发于我的个人博客：尾尾部落 题目描述 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。 解题思路 我们知道，前序遍历的第一个节点就是树的根节点，所以我们先根据前序遍历序列的第一个数字创建根结点，接下来在中序遍历序列中找到根结点的位置，根节点的左边就是左子树，右边就是右子树，这样就能确定左、右子树结点的数量。在前序遍历和中序遍历的序列中划分了左、右子树结点的值之后，就可以递归地去分别构建它的左右子树。 image 参考代码 /** * Definition for binary tree * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] in) { if(pre.length ==0 || in.length == 0) return null; return ConstructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length - 1); } public TreeNode ConstructBinaryTree(int [] pre, int ps, int pe, int [] in, int is, int ie){ if(ps > pe || is > ie){ return null; } TreeNode root = new TreeNode(pre[ps]); for(int i = is; i<=ie; i++){ if(in[i] == pre[ps]){ root.left = ConstructBinaryTree(pre, ps+1, ps+i-is, in, is, i-1); root.right = ConstructBinaryTree(pre, ps+i-is+1, pe, in, i+1, ie); break; } } return root; } }
本文首发于我的个人博客：尾尾部落 题目描述 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。 解题思路 一种方法是利用栈来实现； 另外一种方法是利用三个指针把链表反转，关键是 r 指针保存断开的节点。 image 参考代码 /** * public class ListNode { * int val; * ListNode next = null; * * ListNode(int val) { * this.val = val; * } * } * */ import java.util.ArrayList; public class Solution { public ArrayList<Integer> printListFromTailToHead(ListNode listNode) { if(listNode == null) return new ArrayList<Integer>(); ListNode head = listNode; ListNode cur = listNode.next; while( cur!= null){ ListNode temp = cur.next; cur.next = head; head = cur; cur = temp; } //此时listNode的next还指向第二个node，所以要让listNode.next=null,防止循环 listNode.next = null; ArrayList<Integer> res = new ArrayList<Integer>(); while(head !=null){ res.add(head.val); head = head.next; } return res; } }
本文首发于我的个人博客：尾尾部落 题目描述 请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。 解题思路 很简单，从后往前遍历就对了。 参考代码 public class Solution { public String replaceSpace(StringBuffer str) { StringBuffer res = new StringBuffer(); int len = str.length() - 1; for(int i = len; i >= 0; i--){ if(str.charAt(i) == ' ') res.append("02%"); else res.append(str.charAt(i)); } return res.reverse().toString(); } }
本文首发于我的个人博客：尾尾部落 题目描述 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数 解题思路 image 二维数组是有序的，从右上角来看，向左数字递减，向下数字递增。 因此从右上角开始查找， 当要查找数字比右上角数字大时，下移； 当要查找数字比右上角数字小时，左移； 如果出了边界，则说明二维数组中不存在该整数。 参考代码 public class Solution { public boolean Find(int target, int [][] array) { if(array.length==0 || array[0].length==0) return false; int m = array[0].length-1; int n = 0; int temp = array[n][m]; while(target != temp){ if(m>0 && n<array.length-1){ if(target>temp){ n = n + 1; }else if(target<temp){ m = m - 1; } temp = array[n][m]; }else{ return false; } } return true; } }
本文首发于我的个人博客：尾尾部落 题目描述 输入一棵二叉树，判断该二叉树是否是平衡二叉树。 解题思路 定义：平衡二叉查找树，简称平衡二叉树。 可以是空树。 假如不是空树，任何一个结点的左子树与右子树都是平衡二叉树，并且高度之差的绝对值不超过1。 遍历每个结点，借助一个获取树深度的递归函数，根据该结点的左右子树高度差判断是否平衡，然后递归地对左右子树进行判断。 参考代码 public class Solution { public boolean IsBalanced_Solution(TreeNode root) { if(root == null) return true; return Math.abs(maxDept(root.left) - maxDept(root.right)) <=1 && IsBalanced_Solution(root.left) && IsBalanced_Solution(root.right); } public int maxDept(TreeNode root){ if(root == null) return 0; return 1 + Math.max(maxDept(root.left), maxDept(root.right)); } }
本文首发于我的个人博客：尾尾部落 题目描述 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。 解题思路 设两个栈，s2存放奇数层，s1存放偶数层 遍历s2节点的同时按照左子树、右子树的顺序加入s1， 遍历s1节点的同时按照右子树、左子树的顺序加入s2 参考代码 import java.util.ArrayList; import java.util.Stack; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); Stack<TreeNode> s1 = new Stack<TreeNode>(); Stack<TreeNode> s2 = new Stack<TreeNode>(); int flag = 1; if(pRoot == null) return res; s2.push(pRoot); ArrayList<Integer> temp = new ArrayList<Integer>(); while(!s1.isEmpty() || !s2.isEmpty()){ if(flag % 2 != 0){ while(!s2.isEmpty()){ TreeNode node = s2.pop(); temp.add(node.val); if(node.left != null){ s1.push(node.left); } if(node.right != null){ s1.push(node.right); } } } if(flag % 2 == 0){ while(!s1.isEmpty()){ TreeNode node = s1.pop(); temp.add(node.val); if(node.right != null){ s2.push(node.right); } if(node.left != null){ s2.push(node.left); } } } res.add(new ArrayList<Integer>(temp)); temp.clear(); flag ++; } return res; } }
本文首发于我的个人博客：尾尾部落 题目描述 求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。 解题思路 累加不能用循环的话，那就试试递归吧。 判断递归的终止条件不能用 if 和 switch，那就用短路与代替。(n > 0) && (sum += Sum_Solution(n-1))>0 只有满足n > 0的条件，&&后面的表达式才会执行。 参考代码 public class Solution { public int Sum_Solution(int n) { int sum = n; boolean t = (n > 0) && (sum += Sum_Solution(n-1))>0; return sum; } }
本文首发于我的个人博客：尾尾部落 题目描述 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。 解题思路 先统计王(0)的数量，再把牌排序，如果后面一个数比前面一个数大于1以上，那么中间的差值就必须用王来补了。看王的数量够不够，如果够就返回true，否则返回false。 参考代码 import java.util.Arrays; public class Solution { public boolean isContinuous(int [] numbers) { int zero = 0, dis = 0; if(numbers.length != 5) return false; Arrays.sort(numbers); for(int i = 0; i < 4; i++){ if(numbers[i] == 0){ zero ++; continue; } if(numbers[i] == numbers[i+1]) return false; if(numbers[i+1] - numbers[i] > 1){ dis += numbers[i+1] - numbers[i] - 1; } } if(zero >= dis) return true; else return false; } }
本文首发于我的个人博客：尾尾部落 题目描述 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 解题思路 滑动窗口的方法：用两个数字 start 和 end 分别表示序列的最小值和最大值，首先将 start 初始化为1，end 初始化为2。如果从start到end的和大于sum，我们就从序列中去掉较小的值(即增大start), 相反，只需要增大end。 终止条件为：一直增加begin到(1+sum)/2并且end小于sum为止 参考代码 import java.util.ArrayList; public class Solution { public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); if(sum < 3) return res; int start = 1, end = 2, mid = (1+sum)/2; while(start < mid){ int s = totalSum(start, end); if(s == sum){ res.add(getSequence(start, end)); end ++; }else if(s < sum){ end ++; }else if(s > sum){ start ++; } } return res; } public int totalSum(int start, int end){ int sum = 0; for(int i = start; i <= end; i++){ sum += i; } return sum; } public ArrayList<Integer> getSequence(int start, int end){ ArrayList<Integer> temp = new ArrayList<>(); for(int i = start; i <= end; i++){ temp.add(i); } return temp; } }
本文首发于我的个人博客：尾尾部落 题目描述 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！ 解题思路 很简单的题，在第 n 个字符后面将切一刀，将字符串分为两部分，再重新并接起来即可。注意字符串长度为 0 的情况。 参考代码 public class Solution { public String LeftRotateString(String str,int n) { int len = str.length(); if(len == 0) return ""; n = n % len; String s1 = str.substring(n, len); String s2 = str.substring(0, n); return s1+s2; } }
本文首发于我的个人博客：尾尾部落 HTTPS（全称：Hyper Text Transfer Protocol over Secure Socket Layer），是以安全为目标的HTTP通道，简单讲是HTTP的安全版。即HTTP下加入SSL层，HTTPS的安全基础是SSL，因此加密的详细内容就需要SSL。 它是一个URI scheme（抽象标识符体系），句法类同http:体系。用于安全的HTTP数据传输。https:URL表明它使用了HTTP，但HTTPS存在不同于HTTP的默认端口及一个加密/身份验证层（在HTTP与TCP之间）。这个系统的最初研发由网景公司(Netscape)进行，并内置于其浏览器Netscape Navigator中，提供了身份验证与加密通讯方法。现在它被广泛用于万维网上安全敏感的通讯，例如交易支付方面。 简而言之，就是让你的网站有下图这个小绿标： image 之前用过阿里云的 SSL 免费证书，但是期限只有一年，昨天过期了，看了其他收费的 SSL 证书，还是很贵的，在读小硕实在买不起，只能找找免费的 SSL 证书了。 我们可以从 Let’s Encrypt 获得网站域名的免费的证书。 Certbot是Let’s Encrypt推出的获取证书的客户端，可以让我们免费快速地获取Let’s Encrypt证书。 下面，一步一步教你申请部署ssl证书，并自动续期。 进入Certbot官网，并选择你的系统和软件。我这边是 Nginx和Ubuntu 16.04 (xenial)。 image 选择好之后，就会出现具体的部署教程，如下图 image 安装 先安装python-certbot-nginx $ sudo apt-get update $ sudo apt-get install software-properties-common $ sudo add-apt-repository ppa:certbot/certbot $ sudo apt-get update $ sudo apt-get install python-certbot-nginx 开始 certbot有一个Nginx插件，运行它，按照提示一步一步操作就会自动帮你把证书部署好。 运行如下命令 $ sudo certbot --nginx 选择你要激活 HTTPS 的域名，输入序号即可 image 选择直接通过 HTTPS 访问并删除 HTTP 的方式，或者保留 HTTP，如何你确定你网站中所有的链接都是按照HTTPS来配置的，那么你可以像我这样选择 2。 image 之后，看到Congratulations!就表示部署成功了。 image 自动续期 由于Let的加密证书的有效期是90天，90 天之后证书就会过期，如果要续期就要重复一次上面的步骤，这太麻烦了，Certbot提供了一个自动续期的功能，只需运行如下命令即可： $ sudo certbot renew --dry-run 至此，SSL证书的部署和自动续期的配置就完成，你的网站就不再是无证驾驶了。
本文首发于我的个人博客：尾尾部落 题目描述 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。 解题思路 设置三个标志符分别记录“+/-”、“e/E”和“.”是否出现过。 对于“+/-”： 正常来看它们第一次出现的话应该出现在字符串的第一个位置，如果它第一次出现在不是字符串首位，而且它的前面也不是“e/E”，那就不符合规则；如果是第二次出现，那么它就应该出现在“e/E”的后面，如果“+/-”的前面不是“e/E”，那也不符合规则。 对于“e/E”： 如果它的后面不接任何数字，就不符合规则；如果出现多个“e/E”也不符合规则。 对于“.”： 出现多个“.”是不符合规则的。还有“e/E”的字符串出现“.”也是不符合规则的。 同时，要保证其他字符均为 0-9 之间的数字。 参考代码 public class Solution { public boolean isNumeric(char[] str) { int len = str.length; boolean sign = false, decimal = false, hasE = false; for(int i = 0; i < len; i++){ if(str[i] == '+' || str[i] == '-'){ if(!sign && i > 0 && str[i-1] != 'e' && str[i-1] != 'E') return false; if(sign && str[i-1] != 'e' && str[i-1] != 'E') return false; sign = true; }else if(str[i] == 'e' || str[i] == 'E'){ if(i == len - 1) return false; if(hasE) return false; hasE = true; }else if(str[i] == '.'){ if(hasE || decimal) return false; decimal = true; }else if(str[i] < '0' || str[i] > '9') return false; } return true; } }
本文首发于我的个人博客：尾尾部落 题目描述 给定一个数组A[0,1,...,n-1],请构建一个数组B[0,1,...,n-1],其中B中的元素B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1]。不能使用除法。 解题思路 image B[i]的值可以看作图中矩阵第 i 行所有元素的乘积。我们可以先算下三角中的连乘，即我们先算出B[i]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。 参考代码 public class Solution { public int[] multiply(int[] A) { if(A.length <= 1) return A; int [] B = new int[A.length]; B[0] = 1; for(int i = 1; i < A.length; i++){ B[i] = B[i-1] * A[i-1]; } int temp = 1; for(int j = A.length - 2; j>=0; j--){ temp *= A[j+1]; B[j] *= temp; } return B; } }
本文首发于我的个人博客：尾尾部落 题目描述 请实现两个函数，分别用来序列化和反序列化二叉树 解题思路 对于序列化：使用前序遍历，递归的将二叉树的值转化为字符，并且在每次二叉树的结点不为空时，在转化val所得的字符之后添加一个','作为分割; 对于空节点则以 '#,' 代替。 对于反序列化：将字符串按照“，”进行分割，插入到队列中，然后依次从队列中取出字符建立节点，递归创建一个二叉树。 参考代码 /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ import java.util.Queue; import java.util.LinkedList; public class Solution { String Serialize(TreeNode root) { if(root == null){ return "#,"; } StringBuffer res = new StringBuffer(root.val + ","); res.append(Serialize(root.left)); res.append(Serialize(root.right)); return res.toString(); } TreeNode Deserialize(String str) { String [] res = str.split(","); Queue<String> queue = new LinkedList<String>(); for(int i = 0; i < res.length; i++){ queue.offer(res[i]); } return pre(queue); } TreeNode pre(Queue<String> queue){ String val = queue.poll(); if(val.equals("#")) return null; TreeNode node = new TreeNode(Integer.parseInt(val)); node.left = pre(queue); node.right = pre(queue); return node; } }
本文首发于我的个人博客：尾尾部落 题目描述 将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。 解题思路 常规思路，先判断第一位是不是符号位，如果有符号，有flag 做标记。 遍历字符串中的每个字符，如果存在非数字的字符，直接返回 0，否则，用当前字符减去'0'得到当前的数字，再进行运算。 参考代码 public class Solution { public int StrToInt(String str) { if(str.length() == 0) return 0; int flag = 0; if(str.charAt(0) == '+') flag = 1; else if(str.charAt(0) == '-') flag = 2; int start = flag > 0 ? 1 : 0; long res = 0; while(start < str.length()){ if(str.charAt(start) > '9' || str.charAt(start) < '0') return 0; res = res * 10 + (str.charAt(start) - '0'); start ++; } return flag == 2 ? -(int)res : (int)res; } }
本文首发于我的个人博客：尾尾部落 题目描述 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。 解题思路 法一：递归法。求二叉树的深度，就是求左子树、右子树的中深度最大的加上一个根节点，依此递归即可。 法二：层次遍历。每遍历一层，deep 加 1，直接到最后一层，输出 deep。 参考代码 法一：递归法 /** public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { public int TreeDepth(TreeNode root) { if(root == null) return 0; int left = TreeDepth(root.left) + 1; int right = TreeDepth(root.right) + 1; return left > right ? left : right; } } 法二：层次遍历 import java.util.Queue; import java.util.LinkedList; public class Solution { public int TreeDepth(TreeNode root) { if(root == null) return 0; int deep = 0; Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); int start = 0, end = 1; while(!queue.isEmpty()){ TreeNode node = queue.poll(); start ++; if(node.left != null){ queue.offer(node.left); } if(node.right != null){ queue.offer(node.right); } if(start == end){ end = queue.size(); start = 0; deep ++; } } return deep; } }
本文首发于我的个人博客：尾尾部落 题目描述 请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。 解题思路 用一个哈希表来存储每个字符及其出现的次数，另外用一个字符串 s 来保存字符流中字符的顺序。 每次插入的时候，在字符串 s 中插入该字符，然后在哈希表中查看是否存在该字符，如果存在则它的 value 加1，如果不存在，它在哈希表中插入该字符，它的 value 为 1。 查找第一个只出现一次的字符时，按照 s 的顺序，依次查找 map 中字符出现的次数，当 value 为 1 时，该字符就是第一个只出现一次的字符。 参考代码 import java.util.HashMap; public class Solution { HashMap<Character, Integer> map = new HashMap<Character, Integer>(); StringBuffer s = new StringBuffer(); //Insert one char from stringstream public void Insert(char ch) { s.append(ch); if(map.containsKey(ch)){ map.put(ch, map.get(ch)+1); }else{ map.put(ch, 1); } } //return the first appearence once char in current stringstream public char FirstAppearingOnce() { for(int i = 0; i < s.length(); i++){ if(map.get(s.charAt(i)) == 1) return s.charAt(i); } return '#'; } }
本文首发于我的个人博客：尾尾部落 题目描述 在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5 解题思路 首先添加一个头节点，以方便碰到第一个，第二个节点就相同的情况 设置 first ，second 指针， first 指针指向当前确定不重复的那个节点，而second指针相当于工作指针，一直往后面搜索。 image 参考代码 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode deleteDuplication(ListNode pHead) { if(pHead == null || pHead.next == null) return pHead; ListNode head = new ListNode(-1); head.next = pHead; ListNode first = head; ListNode second = first.next; while(second != null){ if(second.next != null && second.val == second.next.val){ while(second.next != null && second.val == second.next.val){ second = second.next; } first.next = second.next; }else{ first = first.next; } second = second.next; } return head.next; } }
本文首发于我的个人博客：尾尾部落 题目描述 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。 解题思路 法一：哈希法。用一个HashMap，它的 key 存储数S与数组中每个数的差，value 存储当前的数字，比较S=15, 当前的数为 4，则往 hashmap 中插入(key=11, value=4)。我们遍历数组，判断hashmap 中的 key 是否存在当前的数字，如果存在，说明存在着另一个数与当前的数相加和为 S，我们就可以判断它们的乘积是否小于之前的乘积，如果小的话就替换之前的找到的数字，如果大就放弃当前找到的。如果hashmap 中的 key 不存在当前的数字，说明还没有找到相加和为 S 的两个数，那就把S与当前数字的差作为 key，当前数字作为 value 插入到 hashmap 中，继续遍历。 法二：左右夹逼的方法。a+b=sum，a和b越远乘积越小，因为数组是递增排序，所以一头一尾两个指针往内靠近的方法找到的就是乘积最小的情况。 若ai + aj == sum，就是答案（相差越远乘积越小） 若ai + aj > sum，说明 aj 太大了，j -- 若ai + aj < sum，说明 ai 太小了，i ++ 参考代码 import java.util.ArrayList; import java.util.HashMap; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res = new ArrayList<Integer>(); if(array.length < 2) return res; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); int less = Integer.MAX_VALUE; for(int i = 0; i < array.length; i++){ if(map.containsKey(array[i])){ if(array[i] * map.get(array[i]) < less){ less = array[i] * map.get(array[i]); res.clear(); res.add(map.get(array[i])); res.add(array[i]); } }else{ int key = sum - array[i]; map.put(key, array[i]); } } return res; } } 法二：左右夹逼 import java.util.ArrayList; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { ArrayList<Integer> res = new ArrayList<Integer>(); if(array.length < 2) return res; int i = 0, j = array.length - 1; while(i != j){ if(array[i] + array[j] == sum){ res.add(array[i]); res.add(array[j]); break; }else if(array[i] + array[j] < sum){ i++; }else{ j--; } } return res; } }
本文首发于我的个人博客：尾尾部落 题目描述 每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1) 解题思路 用环形链表模拟圆圈。创建一个总共有 n 个结点的环形链表，然后每次在这个链表中删除第 m 个结点。注意，起步是-1 不是 0。 参考代码 import java.util.LinkedList; public class Solution { public int LastRemaining_Solution(int n, int m) { if(n < 1 || m < 1) return -1; LinkedList<Integer> link = new LinkedList<Integer>(); for(int i = 0; i < n; i++) link.add(i); int index = -1; //起步是 -1 不是 0 while(link.size() > 1){ index = (index + m) % link.size(); //对 link的长度求余不是对 n link.remove(index); index --; } return link.get(0); } }
本文首发于我的个人博客：尾尾部落 题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。 解题思路 最简单的就是用一个数组或者哈希表来存储已经遍历过的数字，但是这样需要开辟额外的空间。 如果题目要求不能开辟额外的空间，那我们可以用如下的方法： 因为数组中的数字都在0~n-1的范围内，所以，如果数组中没有重复的数，那当数组排序后，数字i将出现在下标为i的位置。现在我们重排这个数组，从头到尾扫描每个数字，当扫描到下标为i的数字时，首先比较这个数字(记为m)是不是等于i。如果是，则接着扫描下一个数字；如果不是，则再拿它和m 位置上的数字进行比较，如果它们相等，就找到了一个重复的数字（该数字在下标为i和m的位置都出现了），返回true；如果它和m位置上的数字不相等，就把第i个数字和第m个数字交换，把m放到属于它的位置。接下来再继续循环，直到最后还没找到认为没找到重复元素，返回false。 参考代码 public class Solution { // Parameters: // numbers: an array of integers // length: the length of array numbers // duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation; // Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++ // 这里要特别注意~返回任意重复的一个，赋值duplication[0] // Return value: true if the input is valid, and there are some duplications in the array number // otherwise false public boolean duplicate(int numbers[],int length,int [] duplication) { if(length == 0) return false; for(int i = 0; i < length; i++){ while(i != numbers[i]){ if(numbers[i] == numbers[numbers[i]]){ duplication[0] = numbers[i]; return true; }else{ int temp = numbers[numbers[i]]; numbers[numbers[i]] = numbers[i]; numbers[i] = temp; } } } return false; } }
本文首发于我的个人博客：尾尾部落 题目描述 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。 解题思路 就是二叉树的层序遍历，用队列来实现。我们需要两个变量，一个start记录当前层已经打印的节点个数，一个end记录前当层所有的节点个数，当 start == end 时，表时当前层遍历完了，就可以开始下一层遍历。 参考代码 import java.util.ArrayList; import java.util.Queue; import java.util.LinkedList; /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) { ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >(); if(pRoot == null) return res; ArrayList<Integer> temp = new ArrayList<Integer>(); Queue<TreeNode> layer = new LinkedList<TreeNode>(); layer.offer(pRoot); int start = 0, end = 1; while(!layer.isEmpty()){ TreeNode node = layer.poll(); temp.add(node.val); start ++; if(node.left != null) layer.add(node.left); if(node.right != null) layer.add(node.right); if(start == end){ start = 0; res.add(temp); temp = new ArrayList<Integer>(); end = layer.size(); } } return res; } }
本文首发于我的个人博客：尾尾部落 题目描述 请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。 解题思路 法一：递归。根节点的左右子树相同，左子树的左子树和右子树的右子树相同，左子树的右子树和右子树的左子树相同即可。 法二：非递归。非递归也是一样，采用栈或队列存取各级子树根节点。 参考代码 法一：递归。 /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null) return true; return isSymmetrical(pRoot.left, pRoot.right); } boolean isSymmetrical(TreeNode left, TreeNode right){ if(left == null && right == null) return true; if(left == null || right == null) return false; if(left.val == right.val){ return isSymmetrical(left.left, right.right) && isSymmetrical(left.right, right.left); } return false; } } 法二：非递归。 import java.util.Stack; public class Solution { boolean isSymmetrical(TreeNode pRoot) { if(pRoot == null) return true; Stack<TreeNode> s = new Stack<TreeNode>(); s.push(pRoot.left); s.push(pRoot.right); while(!s.isEmpty()){ TreeNode right = s.pop(); TreeNode left = s.pop(); if(right == null && left == null) continue; if(right == null || left == null) return false; if(right.val != left.val) return false; s.push(left.left); s.push(right.right); s.push(left.right); s.push(right.left); } return true; } }
本文首发于我的个人博客：尾尾部落 题目描述 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。 解题思路 用位运算来实现。 step1: 进行异或运算，计算两个数各个位置上的相加，不考虑进位； step2: 进行位与运算，然后左移一位，计算进位值； step3: 把异或运算的结果赋给 num1，把进位值赋给 num2，依此循环，进位值为空的时候结束循环，num1就是两数之和。 参考代码 public class Solution { public int Add(int num1, int num2) { if(num2 == 0) return num1; int sum = 0, carry = 0; while(num2 != 0){ sum = num1 ^ num2; carry = (num1 & num2) << 1; num1 = sum; num2 = carry; } return num1; } }
本文首发于我的个人博客：尾尾部落 题目描述 一个整型数组里除了两个数字之外，其他的数字都出现了偶数次。请写程序找出这两个只出现一次的数字。 解题思路 法一：大家都能想到的HashMap法 法二：异或法 任何一个数字异或它自己都等于0。 如果数组中只一个数字是只出现一次的，其他数字都是成双成对出现的，那么我们从头到尾依次异或数组中的每个数字，最终的结果刚好就是那个只出现一次的数字，因为那些成对出现两次的数字全部在异或中抵消了。 那么回到我们的题目，因为有两个只出现一次的数字，所以我们可以试着把原数组分成两个子数组，使得每个数组包含一个只出现一次的数字，而其他数字都成对出现两次。如果这样拆分成两个数组，那么我们就可以按照之前的办法分别对两个数组进行异或运算找出两个只出现一次的数字。 问题来了，如何进行分组呢？ 我们还是从头到尾依次异或数组中的每个数字，那么最终得到的结果就是两个只出现一次的数字异或的结果。由于这两个数字不一样，所以异或的结果至少有一位为1，我们在结果数字中找到第一个为1的位置，记为index位，现在我们以第index位是不是1为标准把原数组拆分成两个子数组，第一个子数组中的数组第index位都为1，第二个子数组中的数组第index位都为0，那么只出现一次的数字将被分配到两个子数组中去，于是每个子数组中只包含一个出现一次的数字，而其他数字都出现两次。这样我们就可以用之前的方法找到数组中只出现一次的数字了。 参考代码 法一：HashMap import java.util.HashMap; public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { HashMap<Integer, Integer> temp = new HashMap<Integer, Integer>(); for(int i = 0; i < array.length; i++){ if(temp.containsKey(array[i])) temp.remove(array[i]); else temp.put(array[i], 1); } int [] a = new int [array.length]; int i = 0; for(Integer k: temp.keySet()){ a[i] = k; i++; } num1[0] = a[0]; num2[0] = a[1]; } } 法二：异或法 public class Solution { public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) { num1[0] = 0; num2[0] = 0; if(array.length == 0) return; int num = 0; for(int i = 0; i < array.length; i++){ num ^= array[i]; } int index = 0; while((num & 1) == 0 && index < 8){ num = num >> 1; index ++; } for(int i = 0; i < array.length; i++){ if(isa1(array[i], index)) num1[0] ^= array[i]; else num2[0] ^= array[i]; } } public boolean isa1(int i, int index){ i = i >> index; return (i & 1) == 1; } }
本文首发于我的个人博客：尾尾部落 题目描述 牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一翻转这些单词顺序可不在行，你能帮助他么？ 解题思路 很简单的题，也没啥好说的，注意一下测试用例为全是空格的情况：" " trim() : 去除字符串首尾空格 split() : 对字符串按照所传参数进行分割 参考代码 public class Solution { public String ReverseSentence(String str) { if(str.trim().length() == 0) return str; String [] temp = str.split(" "); String res = ""; for(int i = temp.length - 1; i >= 0; i--){ res += temp[i]; if(i != 0) res += " "; } return res; } }
本文首发于我的个人博客：尾尾部落 题目描述 给定一棵二叉搜索树，请找出其中的第k小的结点。例如， （5，3，7，2，4，6，8）中，按结点数值大小顺序第三小结点的值为4。 解题思路 因为二叉搜索树按照中序遍历的顺序打印出来就是排好序的，所以，我们按照中序遍历找到第k个结点就是题目所求的结点。 参考代码 /* public class TreeNode { int val = 0; TreeNode left = null; TreeNode right = null; public TreeNode(int val) { this.val = val; } } */ public class Solution { int index = 0; TreeNode KthNode(TreeNode pRoot, int k) { if(pRoot != null){ TreeNode node = KthNode(pRoot.left, k); if(node != null) return node; index ++; if(index == k) return pRoot; node = KthNode(pRoot.right, k); if(node != null) return node; } return null; } }
本文首发于我的个人博客：尾尾部落 题目描述 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。 解题思路 我们可以将数据排序后分为两部分，左边部分的数据总是比右边的数据小。那么，我们就可以用最大堆和最小堆来装载这些数据： 最大堆装左边的数据，取出堆顶（最大的数）的时间复杂度是O(1) 最小堆装右边的数据，同样，取出堆顶（最小的数）的时间复杂度是O(1) 从数据流中拿到一个数后，先按顺序插入堆中：如果左边的最大堆是否为空或者该数小于等于最大堆顶的数，则把它插入最大堆，否则插入最小堆。然后，我们要保证左边的最大堆的size等于右边的最小堆的size或者最大堆的size比最小堆的size大1。 要获取中位数的话，直接判断最大堆和最小堆的size，如果相等，则分别取出两个堆的堆顶除以2得到中位数，不然，就是最大堆的size要比最小堆的size大，这时直接取出最大堆的堆顶就是我们要的中位数。 参考代码 import java.util.PriorityQueue; import java.util.Comparator; public class Solution { // 最小堆（右） private PriorityQueue<Integer> rHeap = new PriorityQueue<>(); // 最大堆（左） private PriorityQueue<Integer> lHeap = new PriorityQueue<Integer>(15, new Comparator<Integer>() { public int compare(Integer o1, Integer o2) { return o2 - o1; } }); // 保证lHeap.size()>=rHeap.size() public void Insert(Integer num) { // 先按大小插入，再调整 if(lHeap.isEmpty() || num <= lHeap.peek()) lHeap.offer(num); else rHeap.offer(num); if(lHeap.size() < rHeap.size()){ lHeap.offer(rHeap.peek()); rHeap.poll(); }else if(lHeap.size() - rHeap.size() == 2){ rHeap.offer(lHeap.peek()); lHeap.poll(); } } public Double GetMedian() { if(lHeap.size() > rHeap.size()) return new Double(lHeap.peek()); else return new Double(lHeap.peek() + rHeap.peek())/2; } }
本文首发于我的个人博客：[尾尾部落](https://weiweiblog.cn/maxinwindows/） 题目描述 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。 解题思路 法一：简单的暴力法 法二：双向队列 用一个双向队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次，判断当前最大值是否过期（当前最大值的位置是不是在窗口之外），新增加的值从队尾开始比较，把所有比他小的值丢掉。这样时间复杂度为O(n)。 参考代码 法一：简单的暴力法 import java.util.ArrayList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { ArrayList<Integer> res = new ArrayList<Integer>(); if(num.length < size || size == 0) return res; for(int i = 0; i < num.length - size + 1; i++){ res.add(max(num, i, size)); } return res; } public int max(int [] num, int index, int size){ int res = num[index]; for(int i = index + 1; i < index + size; i++){ if(num[i] > res) res = num[i]; } return res; } } 法二：双向队列 import java.util.ArrayList; import java.util.LinkedList; public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size){ ArrayList<Integer> res = new ArrayList<Integer>(); LinkedList<Integer> deque = new LinkedList<Integer>(); if(num.length == 0 || size == 0) return res; for(int i = 0; i < num.length; i++){ if(!deque.isEmpty() && deque.peekFirst() <= i - size) deque.poll(); while(!deque.isEmpty() && num[deque.peekLast()] < num[i]) deque.removeLast(); deque.offerLast(i); if(i + 1 >= size) res.add(num[deque.peekFirst()]); } return res; } }
本文首发于我的个人博客：尾尾部落 题目描述 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。 例如 a b c e s f c s a d e e 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。 解题思路 回溯法： 将matrix字符串映射为一个字符矩阵（index = i * cols + j） 遍历matrix的每个坐标，与str的首个字符对比，如果相同，用flag做标记，matrix的坐标分别上、下、左、右、移动（判断是否出界或者之前已经走过[flag的坐标为1]），再和str的下一个坐标相比，直到str全部对比完，即找到路径，否则找不到。 参考代码 public class Solution { public boolean hasPath(char[] matrix, int rows, int cols, char[] str) { if(matrix.length == 0 || str.length == 0) return false; int [][] flag = new int[rows][cols]; for(int i = 0; i < rows; i++){ for(int j = 0; j < cols; j++){ if(search(matrix, rows, cols, i, j, str, 0, flag)) return true; } } return false; } public boolean search(char[] matrix, int rows, int cols, int i, int j, char[] str, int index, int[][] flag){ int m_i = i * cols + j; if(i<0 || j<0 || i >= rows || j>=cols || flag[i][j] == 1 || matrix[m_i] != str[index]) return false; if(index >= str.length - 1) return true; flag[i][j] = 1; if(search(matrix, rows, cols, i+1, j, str, index+1, flag) || search(matrix, rows, cols, i-1, j, str, index+1, flag) || search(matrix, rows, cols, i, j+1, str, index+1, flag) || search(matrix, rows, cols, i, j-1, str, index+1, flag)) return true; flag[i][j] = 0; return false; } }
本文首发于我的个人博客：尾尾部落 题目描述 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ 解题思路 回溯法：从(0,0)开始走，每成功走一步用一个flag数组标记当前位置为1，然后从当前位置往四个方向探索， 返回1 + 4 个方向的探索值之和。 参考代码 public class Solution { public int movingCount(int threshold, int rows, int cols) { if(threshold == 0) return 0; int flag[][] = new int[rows][cols]; return count(threshold, rows, cols, 0, 0, flag); } public int count(int threshold, int rows, int cols, int i, int j, int[][] flag){ if(i<0 || j<0 || i>=rows || j>=cols || sum(i)+sum(j) > threshold || flag[i][j] == 1){ return 0; } flag[i][j] = 1; return 1 + count(threshold, rows, cols, i - 1, j, flag) + count(threshold, rows, cols, i + 1, j, flag) + count(threshold, rows, cols, i, j - 1, flag) + count(threshold, rows, cols, i, j + 1, flag); } public int sum(int i){ int s = 0; while(i>0){ s += i%10; i /= 10; } return s; } }
本文首发于我的个人博客：尾尾部落 题目描述 给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。 解题思路 第一步，用两个快慢指针找环中相汇点。分别用slow, fast指向链表头部，slow每次走一步，fast每次走二步，直到fast == slow找到在环中的相汇点。 第二步，找环的入口。当fast == slow时，假设slow走过x个节点，则fast走过2x个节点。设环中有n个节点，因为fast比slow多走一圈（n个节点），所以有等式2x = n + x，可以推出n = x，即slow实际上走了一个环的步数。这时，我们让fast重新指向链表头部pHead，slow的位置不变，然后slow和fast一起向前每次走一步，直到fast == slow，此时两个指针相遇的节点就是环的入口。 参考代码 /* public class ListNode { int val; ListNode next = null; ListNode(int val) { this.val = val; } } */ public class Solution { public ListNode EntryNodeOfLoop(ListNode pHead) { if(pHead.next == null || pHead.next.next == null) return null; ListNode slow = pHead.next; ListNode fast = pHead.next.next; while(fast != null){ if(fast == slow){ fast = pHead; while(fast != slow){ fast = fast.next; slow = slow.next; } return fast; } slow = slow.next; fast = fast.next.next; } return null; } }
本文首发于我的个人博客：尾尾部落 题目描述 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"和"ab*a"均不匹配 解题思路 当模式中的第二个字符不是“*”时： 1、如果字符串第一个字符和模式中的第一个字符相匹配，那么字符串和模式都后移一个字符，然后匹配剩余的。 2、如果 字符串第一个字符和模式中的第一个字符相不匹配，直接返回false。 而当模式中的第二个字符是“*”时： 如果字符串第一个字符跟模式第一个字符不匹配，则模式后移2个字符，继续匹配。如果字符串第一个字符跟模式第一个字符匹配，可以有3种匹配方式： 1、模式后移2字符，相当于x*被忽略； 2、字符串后移1字符，模式后移2字符； 3、字符串后移1字符，模式不变，即继续匹配字符下一位，因为*可以匹配多位。 参考代码 public class Solution { public boolean match(char[] str, char[] pattern) { int sindex = 0, pindex = 0; return matchCore(str, sindex, pindex, pattern); } public boolean matchCore(char[] str, int sindex, int pindex, char[] pattern){ if(sindex >= str.length && pindex == pattern.length) return true; if(pindex >= pattern.length && sindex < str.length) return false; if(pindex+1 < pattern.length && pattern[pindex+1] == '*'){ if(sindex < str.length && (str[sindex] == pattern[pindex] || pattern[pindex] == '.') ){ return matchCore(str, sindex, pindex+2, pattern) || matchCore(str, sindex+1, pindex+2, pattern ) || matchCore(str, sindex+1, pindex, pattern); }else{ return matchCore(str, sindex, pindex+2, pattern); } } if(sindex < str.length && (str[sindex] == pattern[pindex] || pattern[pindex] == '.')) return matchCore(str, sindex+1, pindex+1, pattern); return false; } } 参考牛客网@披萨大叔
本文首发于我的个人博客：尾尾部落 今天在用uwsgi+nginx在部署flask应用时，遇到502的错误，vim /var/log/nginx/error.log查看nginx的错误日志，提示如下错误信息： 2018/07/22 00:46:36 [crit] 15890#15890: *74 connect() to unix:/root/jianshuvue/jianshu.sock failed (13: Permission denied) while connecting to upstream, client: 120.42.13.98, server: jianshu.weiweiblog.cn, request: "GET /favicon.ico HTTP/1.1", upstream: "uwsgi://unix:/root/jianshuvue/jianshu.sock:", host: "jianshu.weiweiblog.cn", referrer: "http://jianshu.weiweiblog.cn/jianshu/67eb7ed414d3" Permission denied，一看就知道是权限出了问题，通过ps -ef | grep nginx,查看nginx的进程信息： root 15889 1 0 00:01 ? 00:00:00 nginx: master process /usr/sbin/nginx -g daemon on; master_process on; www-data 15890 15889 0 00:01 ? 00:00:00 nginx: worker process root 16795 15654 0 00:48 pts/3 00:00:00 grep --color=auto nginx 发现nginx进程的用户是nginx，而我们创建/root/jianshuvue/jianshu.sock文件的用户是root，因此，只要把nginx的进程user改为root即可，vim /etc/nginx/nginx.conf: 1 # user www-data; 2 user root; 3 worker_processes auto; 4 pid /run/nginx.pid; 之后，/etc/init.d/nginx restart重启nginx，就可以正常访问网站了。
本文首发于我的个人博客：尾尾部落 在阿里云服务器上，用virtualenv创建虚拟环境时，报了个错误 root@iZwz982qla1uxm1s5dnyo7Z:/usr/lib/python3/dist-packages/virtualenv-15.0.1.egg-info# virtualenv -p python3 venv Running virtualenv with interpreter /usr/bin/python2 New python executable in /usr/lib/python3/dist-packages/virtualenv-15.0.1.egg-info/venv/bin/python2 Not overwriting existing python script /usr/lib/python3/dist-packages/virtualenv-15.0.1.egg-info/venv/bin/python (you must use /usr/lib/python3/dist-packages/virtualenv-15.0.1.egg-info/venv/bin/python2) Please make sure you remove any previous custom paths from your /root/.pydistutils.cfg file. 1 [global] Installing setuptools, pkg_resources, pip, wheel... Complete output from command /usr/lib/python3/dis...nfo/venv/bin/python2 - setuptools pkg_resources pip wheel: Collecting setuptools Downloading http://mirrors.aliyun.com/pypi/packages/ff/f4/385715ccc461885f3cedf57a41ae3c12b5fec3f35cce4c8706b1a112a133/setuptools-40.0.0-py2.py3-none-any.whl (567kB) Collecting pkg_resources Exception: Traceback (most recent call last): File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/basecommand.py", line 209, in main status = self.run(options, args) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/commands/install.py", line 328, in run wb.build(autobuilding=True) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/wheel.py", line 748, in build self.requirement_set.prepare_files(self.finder) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/req/req_set.py", line 360, in prepare_files ignore_dependencies=self.ignore_dependencies)) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/req/req_set.py", line 512, in _prepare_file finder, self.upgrade, require_hashes) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/req/req_install.py", line 273, in populate_link self.link = finder.find_requirement(self, upgrade) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/index.py", line 442, in find_requirement all_candidates = self.find_all_candidates(req.name) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/index.py", line 400, in find_all_candidates for page in self._get_pages(url_locations, project_name): File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/index.py", line 545, in _get_pages page = self._get_page(location) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/index.py", line 648, in _get_page return HTMLPage.get_page(link, session=self.session) File "/usr/share/python-wheels/pip-8.1.1-py2.py3-none-any.whl/pip/index.py", line 760, in get_page resp.raise_for_status() File "/usr/lib/python3/dist-packages/virtualenv-15.0.1.egg-info/venv/share/python-wheels/requests-2.9.1-py2.py3-none-any.whl/requests/models.py", line 840, in raise_for_status raise HTTPError(http_error_msg, response=self) HTTPError: 404 Client Error: Not Found for url: http://mirrors.aliyun.com/pypi/simple/pkg-resources/ ---------------------------------------- ...Installing setuptools, pkg_resources, pip, wheel...done. Traceback (most recent call last): File "/usr/lib/python3/dist-packages/virtualenv.py", line 2363, in <module> main() File "/usr/lib/python3/dist-packages/virtualenv.py", line 719, in main symlink=options.symlink) File "/usr/lib/python3/dist-packages/virtualenv.py", line 988, in create_environment download=download, File "/usr/lib/python3/dist-packages/virtualenv.py", line 918, in install_wheel call_subprocess(cmd, show_stdout=False, extra_env=env, stdin=SCRIPT) File "/usr/lib/python3/dist-packages/virtualenv.py", line 812, in call_subprocess % (cmd_desc, proc.returncode)) OSError: Command /usr/lib/python3/dis...nfo/venv/bin/python2 - setuptools pkg_resources pip wheel failed with error code 2 看到HTTPError: 404 Client Error: Not Found for url: http://mirrors.aliyun.com/pypi/simple/pkg-resources/以为是阿里云的安全组配置没配好，折腾了半天，原来是访问PyPI镜像源出了问题，将pip的默认的源地址改为国内源即可。具体操作如下： vim ~/.pip/pip.conf打开pip配置文件: 写入 [global] index-url = http://e.pypi.python.org/simple 以下这几个国内源都可以 e.pypi.python.org pypi.douban.com pypi.hustunique.com
发表了文章
2016-03-20
发表了文章
2016-06-20
发表了文章
2016-06-20
发表了文章
2016-06-21
发表了文章
2016-06-23
发表了文章
2016-06-23
发表了文章
2016-06-23
发表了文章
2016-06-24
发表了文章
2016-06-24
发表了文章
2016-06-24
发表了文章
2016-06-28
发表了文章
2016-06-28
发表了文章
2016-06-30
发表了文章
2016-07-01
发表了文章
2016-07-05
发表了文章
2016-11-28
发表了文章
2017-01-15
发表了文章
2017-01-17
发表了文章
2017-03-21
发表了文章
2017-03-24
