【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 153.寻找旋转排序数组中的最小值 二分查找的变种，想这些二分查找变种相关的题目我掌握的实际并不好，需多次练习理解 public int findMin(int[] nums) { int l = 0; int h = nums.length - 1; while (l < h) { int mid = (l + h)/2; if (nums[mid] < nums[h]) { h = mid; }else { l = mid + 1; } } return nums[l]; } 排序 （纯排序题目，这里就不放代码了，之前有） 128. 最长连续序列 题目要求O(n)的时间复杂度，这里先使用Set把元素放入并去重，开始遍历，遍历数为x 如果存在x-1，跳过此次（因为要避免重复计算，要每次从连续数列的第一个开始计算） 存在x+1，继续查找更大的 更新结果 public int longestConsecutive(int[] nums) { if (nums.length == 0) { return 0; } Set<Integer> set = new HashSet<>(); for (int i = 0; i < nums.length; i++) { set.add(nums[i]); } int res = 0; for (int i = 0; i < nums.length; i++) { int x = nums[i]; if (!set.contains(x-1)) { int cur = 0; while (set.contains(x)) { cur++; x++; } res = Math.max(res, cur); } } return res; } 62.不同路径 经典动规，不多说了 public int uniquePaths(int m, int n) { int[][] dp = new int[m][n]; for (int i = 0; i < m; i++) { dp[i][0] = 1; } for (int i = 0; i < n; i++) { dp[0][i] = 1; } for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } 136.只出现一次的数字 要求时间O(n)，空间O(1)，则使用异或！ 因为0^a=a，a^a=0，所以一个数字连续两次和0异或之后为0 又因为异或操作满足分配律，所以一个数组里的数字连续异或之后，剩余的结果即为只出现一次的数字！ public int singleNumber(int[] nums) { int res = 0; for (int num : nums) { res ^= num; } return res; } 240.搜索二维矩阵 II 从右上角开始，向左下开始寻找 public boolean searchMatrix(int[][] matrix, int target) { int row = 0; int col = matrix[0].length - 1; while (col >= 0 && row < matrix.length) { if (matrix[row][col] == target) { return true; } if (target < matrix[row][col]) { col--; }else { row++; } } return false; } 221.最大正方形 动规，状态转移方程为dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1，同时更新最优解 public int maximalSquare(char[][] matrix) { int[][] dp = new int[matrix.length][matrix[0].length]; int res = 0; for (int i = 0; i < matrix.length; i++) { dp[i][0] = matrix[i][0] - '0'; res = Math.max(res, dp[i][0]); } for (int i = 0; i < matrix[0].length; i++) { dp[0][i] = matrix[0][i] - '0'; res = Math.max(res, dp[0][i]); } for (int i = 1; i < dp.length; i++) { for (int j = 1; j < dp[0].length; j++) { if (matrix[i][j] == '0') { continue; } dp[i][j] = Math.min(dp[i-1][j-1], Math.min(dp[i-1][j],dp[i][j-1])) + 1; res = Math.max(res, dp[i][j]); } } return res*res; } 162.寻找峰值 二分变体 public int findPeakElement(int[] nums) { int l = 0, r = nums.length - 1; while (l < r) { int mid = (l + r) / 2; if (nums[mid] < nums[mid + 1]) { l = mid + 1; } else { r = mid; } } return l; }
本文将记录力扣SQL下的题目： 除了较多的连接题目以外，有很多的排序题目，需要用到窗口函数 175.组合两个表 很基本的两表关联 SELECT p.FirstName AS firstName, p.LastName as lastName, a.City AS city, a.State AS state FROM Person p LEFT JOIN Address a ON p.PersonId = a.PersonId 176.第二高的薪水 考查LIMIT的使用，同时考虑记录只有一条的情况 SELECT (SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1,1) AS SecondHighestSalary 177.第N高的薪水 这道题给了一个mysql的脚本 CREATE FUNCTION getNthHighestSalary(N INT) RETURNS INT BEGIN SET N:=N-1; RETURN ( # Write your MySQL query statement below. SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT N,1 ); END 178. 分数排名 这道题使用窗口函数会很方便 row_number() 在排名是序号连续、不重复，即使遇到表中的两个一样的数值亦是如此 rank() 函数会把要求排序的值相同的归为一组且每组序号一样（序号可能会间断） dense_rank() 排序是连续的，也会把相同的值分为一组且每组排序号一样 ntile(group_num) 将所有记录分成group_num个组，每组序号一样 select Score, dense_rank() over(order by Score desc) 'Rank' from Scores 179.连续出现的数字 数字连续出现三次以上，将同一张表自关联三次 SELECT DISTINCT l1.Num AS ConsecutiveNums FROM Logs l1,Logs l2,Logs l3 WHERE l1.Id = l2.Id - 1 AND l2.Id = l3.Id - 1 AND l1.Num = l2.Num AND l2.Num = l3.Num 181.超过经理收入的员工 自关联作比较 SELECT a.NAME AS Employee FROM Employee AS a JOIN Employee AS b ON a.ManagerId = b.Id AND a.Salary > b.Salary 182.查找重复的电子邮箱 分组之后根据count判断 SELECT Email FROM Person GROUP BY Email HAVING count(Email) > 1 183.从不订购的客户 使用NOT IN SELECT Name Customers FROM Customers WHERE Id NOT IN (SELECT CustomerId FROM Orders) 184.部门工资最高的员工 关键在于WHERE之后的限定，使用两个字段IN一个子查询（ID和最大薪资） SELECT Department.name AS 'Department', Employee.name AS 'Employee', Salary FROM Employee JOIN Department ON Employee.DepartmentId = Department.Id WHERE (Employee.DepartmentId, Employee.Salary) IN (SELECT DepartmentId, MAX(Salary) FROM Employee GROUP BY DepartmentId)
本文将记录力扣shell下的题目： shell脚本需要熟悉常见的awk、grep等命令 词频统计 写一个 bash 脚本以统计一个文本文件 words.txt 中每个单词出现的频率： # 输入 the day is sunny the the the sunny is is # 输出 the 4 is 3 sunny 2 day 1 首先cat命令查看words.txt tr -s ' ' '\n'将空格都替换为换行 实现分词 sort排序将分好的词按照顺序排序 uniq -c 统计重复次数（此步骤与上一步息息相关，-c原理是字符串相同则加一，如果不进行先排序的话将无法统计数目） sort -r 将数目倒序排列 awk '{print $2,$1}' 将词频和词语调换位置打印出来 cat words.txt | tr -s ' ' '\n' | sort | uniq -c | sort -r | awk '{print $2,$1}' 有效电话号码 给定一个包含电话号码列表（一行一个电话号码）的文本文件 file.txt，写一个单行 bash 脚本输出所有有效的电话号码。 你可以假设一个有效的电话号码必须满足以下两种格式： (xxx) xxx-xxxx 或 xxx-xxx-xxxx。（x 表示一个数字） 你也可以假设每行前后没有多余的空格字符。 解法就是正则匹配 grep -P '^xxxxxxxxx$' file.txt。其中 ^ 是正则的开始，$是正则的结束 (a|b)代表a或者b都可以 对于特殊字符前面要加上\ [0-9]{3}代表数字0-9需要连续出现3次 grep -P '^([0-9]{3}-|\([0-9]{3}\) )[0-9]{3}-[0-9]{4}$' file.txt 转置文件 给定一个文件 file.txt，转置它的内容。 你可以假设每行列数相同，并且每个字段由 ' ' 分隔。 法1： # 获取第一行，然后用wc来获取列数 COLS=`head -1 file.txt | wc -w` # 使用awk依次去输出文件的每一列的参数，然后用xargs做转置 for (( i = 1; i <= $COLS; i++ )) do # 这里col就是在代码里要替换的参数，而它等于$i awk -v col=$i '{print $col}' file.txt | xargs done 法2： awk '{ for (i=1;i<=NF;i++){ if (NR==1){ res[i]=$i } else{ res[i]=res[i]" "$i } } }END{ for(j=1;j<=NF;j++){ print res[j] } }' file.txt awk是一行一行地处理文本文件，运行流程是： 先运行BEGIN后的{Action}，相当于表头 再运行{Action}中的文件处理主体命令 最后运行END后的{Action}中的命令 有几个经常用到的awk常量：NF是当前行的field字段数；NR是正在处理的当前行数。 注意到是转置，假如原始文本有m行n列（字段），那么转置后的文本应该有n行m列，即原始文本的每个字段都对应新文本的一行。我们可以用数组res来储存新文本，将新文本的每一行存为数组res的一个元素。 在END之前我们遍历file.txt的每一行，并做一个判断：在第一行时，每碰到一个字段就将其按顺序放在res数组中；从第二行开始起，每碰到一个字段就将其追加到对应元素的末尾（中间添加一个空格）。 文本处理完了，最后需要输出。在END后遍历数组，输出每一行。注意printf不会自动换行，而print会自动换行。 第十行 打印第十行 ：sed -n '10p' file.txt 打印一到十行 ：sed -n '1,10p' file.txt 查找指定字符 ：grep -n 'KeyWord' file.txt
本文将记录力扣多线程下的题目： 每道题基本都有很多种解法，基本都可以使用变量、Semaphore、CountDownLatch等手段来控制。 1114.按序打印 1.变量控制 class Foo { private volatile int flag = 1; public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printSecond.run() outputs "first". Do not change or remove this line. printFirst.run(); flag = 2; } public void second(Runnable printSecond) throws InterruptedException { while (flag != 2); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); flag = 3; } public void third(Runnable printThird) throws InterruptedException { while (flag != 3); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } 2.Semaphore class Foo { public Semaphore seam_first_two = new Semaphore(0); public Semaphore seam_two_second = new Semaphore(0); public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printSecond.run() outputs "first". Do not change or remove this line. printFirst.run(); seam_first_two.release(); } public void second(Runnable printSecond) throws InterruptedException { seam_first_two.acquire(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); seam_two_second.release(); } public void third(Runnable printThird) throws InterruptedException { seam_two_second.acquire(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } 3.CountDownLatch class Foo { private CountDownLatch second = new CountDownLatch(1); private CountDownLatch third = new CountDownLatch(1); public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printSecond.run() outputs "first". Do not change or remove this line. printFirst.run(); second.countDown(); } public void second(Runnable printSecond) throws InterruptedException { second.await(); // printSecond.run() outputs "second". Do not change or remove this line. printSecond.run(); third.countDown(); } public void third(Runnable printThird) throws InterruptedException { third.await(); // printThird.run() outputs "third". Do not change or remove this line. printThird.run(); } } 4.AtomicInteger class Foo { private AtomicInteger firstJobDone = new AtomicInteger(0); private AtomicInteger secondJobDone = new AtomicInteger(0); public Foo() {} public void first(Runnable printFirst) throws InterruptedException { // printFirst.run() outputs "first". printFirst.run(); // mark the first job as done, by increasing its count. firstJobDone.incrementAndGet(); } public void second(Runnable printSecond) throws InterruptedException { while (firstJobDone.get() != 1) { // waiting for the first job to be done. } // printSecond.run() outputs "second". printSecond.run(); // mark the second as done, by increasing its count. secondJobDone.incrementAndGet(); } public void third(Runnable printThird) throws InterruptedException { while (secondJobDone.get() != 1) { // waiting for the second job to be done. } // printThird.run() outputs "third". printThird.run(); } } 1115.交替打印FooBar 1.Semaphore class FooBar { private int n; public Semaphore semaphoreFoo = new Semaphore(1); public Semaphore semaphoreBar = new Semaphore(0); public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { semaphoreBar.acquire(); // printFoo.run() outputs "foo". Do not change or remove this line. printFoo.run(); semaphoreBar.release(); } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { semaphoreBar.acquire(); // printBar.run() outputs "bar". Do not change or remove this line. printBar.run(); semaphoreFoo.release(); } } } 2.CyclicBarrier class FooBar { private int n; private CyclicBarrier cb = new CyclicBarrier(2); private volatile boolean fooExec = true; public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { while (!fooExec) { //false的时候，bar线程在执行，foo线程在这此处空转 } printFoo.run();//打印foo fooExec = false;//设置变量 try { cb.await();//线程foo到达同步点 } catch (BrokenBarrierException e) { e.printStackTrace(); } } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { try { cb.await(); } catch (BrokenBarrierException e) { e.printStackTrace(); } printBar.run(); fooExec = true; } } } 3.Thread.yield() class FooBar { private int n; private volatile boolean fooExec = true; public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n;) { if (fooExec) { printFoo.run(); fooExec = false; i++; } else { Thread.yield(); } } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n;) { if (!fooExec) { printBar.run(); fooExec = true; i++; } else { Thread.yield(); } } } } 4.BlockingQueue class FooBar { private int n; private BlockingQueue<Integer> fooQueue = new LinkedBlockingQueue<Integer>() {{ add(0); }}; private BlockingQueue<Integer> barQueue = new LinkedBlockingQueue<>(); public FooBar(int n) { this.n = n; } public void foo(Runnable printFoo) throws InterruptedException { for (int i = 0; i < n; i++) { fooQueue.take(); printFoo.run(); barQueue.add(0); } } public void bar(Runnable printBar) throws InterruptedException { for (int i = 0; i < n; i++) { barQueue.take(); printBar.run(); fooQueue.add(0); } } } 1116.打印零与奇偶数 1.Semaphore class ZeroEvenOdd { private int n; private Semaphore zeroSema = new Semaphore(1); private Semaphore oddSema = new Semaphore(0); private Semaphore evenSema = new Semaphore(0); public ZeroEvenOdd(int n) { this.n = n; } // printNumber.accept(x) outputs "x", where x is an integer. public void zero(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { zeroSema.acquire(); printNumber.accept(0); if (i % 2 == 1) { oddSema.release(); } else { evenSema.release(); } } } public void even(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { if (i % 2 == 0) { evenSema.acquire(); printNumber.accept(i); zeroSema.release(); } } } public void odd(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { if (i % 2 == 1) { oddSema.acquire(); printNumber.accept(i); zeroSema.release(); } } } } 2.CountDownLatch class ZeroEvenOdd { private int n; private CountDownLatch zeroLatch = new CountDownLatch(0); private CountDownLatch evenLatch = new CountDownLatch(1);//偶数 private CountDownLatch oddLatch = new CountDownLatch(1);//奇数 public ZeroEvenOdd(int n) { this.n = n; } public void zero(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { zeroLatch.await(); printNumber.accept(0); zeroLatch = new CountDownLatch(1); if (i % 2 == 1) { oddLatch.countDown(); } else { evenLatch.countDown(); } } } public void even(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { if (i % 2 == 0) { evenLatch.await(); printNumber.accept(i); evenLatch = new CountDownLatch(1); zeroLatch.countDown(); } } } public void odd(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { if (i % 2 == 1) { oddLatch.await(); printNumber.accept(i); oddLatch = new CountDownLatch(1); zeroLatch.countDown(); } } } } 3.AtomicInteger+Thread.yield() class ZeroEvenOdd { private int n; private AtomicInteger ai = new AtomicInteger(0); public ZeroEvenOdd(int n) { this.n = n; } public void zero(IntConsumer printNumber) throws InterruptedException { for (int i = 0; i < n; i++) { while (ai.get() != 0 && ai.get() != 2) { Thread.yield(); } printNumber.accept(0); ai.incrementAndGet(); } } public void even(IntConsumer printNumber) throws InterruptedException { for (int i = 2; i <= n; i += 2) { while (ai.get() != 3) { Thread.yield(); } printNumber.accept(i); ai.set(0); } } public void odd(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i += 2) { while (ai.get() != 1) { Thread.yield(); } printNumber.accept(i); ai.set(2); } } } 4.变量+Thread.yield() class ZeroEvenOdd { private int n; private volatile int state; public ZeroEvenOdd(int n) { this.n = n; } public void zero(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i++) { while (state != 0) { Thread.yield(); } printNumber.accept(0); if (i % 2 == 1) { state = 1; } else { state = 2; } } } public void even(IntConsumer printNumber) throws InterruptedException { for (int i = 2; i <= n; i += 2) { while (state != 2) { Thread.yield(); } printNumber.accept(i); state = 0; } } public void odd(IntConsumer printNumber) throws InterruptedException { for (int i = 1; i <= n; i += 2) { while (state != 1) { Thread.yield(); } printNumber.accept(i); state = 0; } } } 5.ReentrantLock+Condition class ZeroEvenOdd { private int n; private volatile int start = 1; private volatile int state; private Lock lock = new ReentrantLock(); private Condition zero = lock.newCondition(); private Condition even = lock.newCondition(); private Condition odd = lock.newCondition(); public ZeroEvenOdd(int n) { this.n = n; } // printNumber.accept(x) outputs "x", where x is an integer. public void zero(IntConsumer printNumber) throws InterruptedException { lock.lock(); try { while (start <= n) { if (state != 0) { zero.await(); } printNumber.accept(0); if (start % 2 == 0) { state = 2; even.signal(); } else { state = 1; odd.signal(); } zero.await(); } odd.signal(); even.signal(); } finally { lock.unlock(); } } //偶数 public void even(IntConsumer printNumber) throws InterruptedException { lock.lock(); try { while (start <= n) { if (state != 2) { even.await(); } else { printNumber.accept(start++); state = 0; zero.signal(); } } } finally { lock.unlock(); } } //基数 public void odd(IntConsumer printNumber) throws InterruptedException { lock.lock(); try { while (start <= n) { if (state != 1) { odd.await(); } else { printNumber.accept(start++); state = 0; zero.signal(); } } } finally { lock.unlock(); } } }
【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 155.最小栈 使用 辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。 当一个元素要入栈时，我们取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中 class MinStack { ArrayDeque<Integer> stack; ArrayDeque<Integer> minStack; public MinStack() { stack = new ArrayDeque<>(); minStack = new ArrayDeque<>(); minStack.push(Integer.MAX_VALUE); } public void push(int val) { stack.push(val); minStack.push(Math.min(val, minStack.peekFirst())); } public void pop() { stack.pop(); minStack.pop(); } public int top() { return stack.peekFirst(); } public int getMin() { return minStack.peekFirst(); } } 41.缺失的第一个正数 缺失的正数一定在[1, nums.length+1]中，由于题目限制空间复杂度为O(1)，我们需要修改原数组，结合数组下标的特性来替代哈希表。 public int firstMissingPositive(int[] nums) { int l = nums.length; //将所有小于等于0的数置为l+1 for (int i = 0; i < l; i++) { if (nums[i] <= 0) { nums[i] = l+1; } } for (int i = 0; i < l; i++) { int temp = Math.abs(nums[i]); if (temp <= l) { nums[temp-1] = -Math.abs(nums[temp-1]); } } //寻找下标对应的第一个正数，返回该下标 for (int i = 0; i < l; i++) { if (nums[i] > 0) { return i+1; } } return l+1; } 718.最长重复子数组 这里要注意是连续子数组，不同于字符串的子序列，所以状态转移方程中不相等的情况下：dp[i][j] = 0; 动规：时间O(MN)，空间O(MN) 滑动窗口： O((N+M)×min(N,M)) ，空间 O(1) public int findLength(int[] nums1, int[] nums2) { int[][] dp = new int[nums1.length+1][nums2.length+1]; int res = 0; for (int i = 1; i <= nums1.length ; i++) { for (int j = 1; j <= nums2.length; j++) { if (nums1[i-1] == nums2[j-1]) { dp[i][j] = 1 + dp[i-1][j-1]; } else { dp[i][j] = 0; } res = Math.max(res, dp[i][j]); } } return res; } 234.回文链表 时间O(n)，空间O(1)，思路还是比较好想的 快慢指针找中点 翻转一半 再遍历比较 class Solution { public boolean isPalindrome(ListNode head) { if (head.next == null) { return true; } ListNode slow = head, fast = head, slowPre = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slowPre = slow; slow = slow.next; } ListNode l2 = slow.next, l1; if (fast.next != null) { slowPre = slow; } slowPre.next = null; l1 = reverseList(head); while (l1 != null && l2 != null) { if (l1.val != l2.val) { return false; } l1 = l1.next; l2 = l2.next; } return true; } public ListNode reverseList(ListNode head) { ListNode prev = null, next = null; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } } 78.子集 记原序列中元素的总数为 n。原序列中的每个数字 ai 的状态可能有两种，即「在子集中」和「不在子集中」。 我们用 1 表示「在子集中」，0 表示不在子集中，那么每一个子集可以对应一个长度为 n 的 0/1 序列，第 i 位表示 ai是否在子集中。 （这里会用到位运算） public List<List<Integer>> subsets(int[] nums) { List<List<Integer>> res = new ArrayList<>(); List<Integer> t = new ArrayList<>(); int n = nums.length; for (int i = 0; i < (1 << n); i++) { t.clear(); for (int j = 0; j < n; j++) { if ((i & (1 << j)) != 0) { t.add(nums[j]); } } res.add(new ArrayList<>(t)); } return res; } 112.路径总和 递归 class Solution { public boolean hasPathSum(TreeNode root, int sum) { if (root == null) { return false; } if (root.left == null && root.right == null) { return sum == root.val; } return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); } } 98.验证二叉搜索树 两个递归思路： 递归，但要判断节点的上下界 递归，中序遍历需递增 class Solution { Long last = Long.MIN_VALUE; public boolean isValidBST(TreeNode root) { if (root == null) { return true; } if (isValidBST(root.left)) { if (last < root.val) { last = root.val + 0l; return isValidBST(root.right); } } return false; } } 32.最长有效括号 也是一道动态规划，但是动态规划的转移方程比较难想，dp[i]代表以s.charAt(i)结尾时的最长有效括号，由于题目要求为最长且连续，那么： 如果dp[i] == '('，那么在当前位置一定是0 如果dp[i] == ')'，那么需要根据dp[i-1]来找到前一个为被匹配的 '(' 如果存在，则dp[i] = 2 + dp[i-1] + dp[i - dp[i-1] - 2] 这里的dp[i - dp[i-1] - 2]为上一个未被匹配的'('，也就是上一个断连之前的最长连续有效括号值 其中还需要判断数组下标-1的情况 public int longestValidParentheses(String s) { int len = s.length(); if (len <= 1) { return 0; } int res = 0; int[] dp = new int[len]; for (int i = 1; i < len; i++) { if (s.charAt(i) == ')' && i - dp[i-1] > 0 && s.charAt(i - dp[i-1] -1) == '(') { dp[i] += (2 + dp[i-1]); if (i - dp[i-1] > 1) { dp[i] += dp[i - dp[i-1] - 2]; } res = Math.max(res, dp[i]); } } return res; } 101.对称二叉树 两个指针，同步对称移动 class Solution { public boolean isSymmetric(TreeNode root) { return dfs(root, root); } public boolean dfs(TreeNode q, TreeNode p) { if (q == null && p == null) { return true; } if (q == null || p == null) { return false; } return q.val == p.val && dfs(q.left, p.right) && dfs(q.right, p.left); } } 322.零钱兑换 区间dp，dp数组定义不是根据硬币，而是根据金额：dp[i] 代表总金额为 i 时所需的最小硬币个数 状态转移方程也是有些难度的，将数组初始化为无穷大，代表此金额无法使用所给金币凑出，dp[0] = 0 如果当前金额可以被某一种硬币凑出，则：dp[i] = Math.min(dp[i - coin] + 1, dp[i]); public int coinChange(int[] coins, int amount) { if (amount == 0) { return 0; } int[] dp = new int[amount+1]; Arrays.fill(dp, Integer.MAX_VALUE); dp[0] = 0; for (int coin : coins) { for (int i = coin; i <= amount ; i++) { if (dp[i - coin] != Integer.MAX_VALUE) { dp[i] = Math.min(dp[i - coin] + 1, dp[i]); } } } return dp[amount] < Integer.MAX_VALUE ? dp[amount] : -1; } 22.括号生成 题目要求给出所有可能，暴力dfs即可 class Solution { List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { dfs(n, n, ""); return res; } public void dfs(int left, int right, String s) { for (int i = 0; i < 2; i++) { if (left == 0 && right == 0) { res.add(s); break; } if (i == 0 && left > 0) { dfs(left - 1, right, s + "("); }else if (i == 1 && right > left) { dfs(left, right - 1, s + ")"); } } } } 169.多数元素 Boyer-Moore 投票算法，时间O(n)，空间O(1) 算法过程： 我们维护一个候选众数 candidate 和它出现的次数 count。初始时 candidate 可以为任意值，count 为 0； 我们遍历数组 nums 中的所有元素，对于每个元素 x，在判断 x 之前，如果 count 的值为 0，我们先将 x 的值赋予candidate，随后我们判断 x： 如果 x 与 candidate 相等，那么计数器 count 的值增加 1； 如果 x 与 candidate 不等，那么计数器 count 的值减少 1。 在遍历完成后，candidate 即为整个数组的众数。 投票算法证明： 如果候选人不是maj 则 maj,会和其他非候选人一起反对 会反对候选人,所以候选人一定会下台(maj==0时发生换届选举) 如果候选人是maj , 则maj 会支持自己，其他候选人会反对，同样因为maj 票数超过一半，所以maj 一定会成功当选 public int majorityElement(int[] nums) { int cand = 0, count = 0; for (int i = 0; i < nums.length; i++) { if (count == 0) { cand = nums[i]; } count += (cand == nums[i] ? 1 : -1); } return cand; } 48.旋转图像 原地旋转：将矩形分为四块，两个for循环一块的量，但是每次swap四个块的坐标 就是四个对应坐标的转换方程有些难推 public void rotate(int[][] matrix) { int n = matrix.length; for (int i = 0; i < n/2; i++) { for (int j = 0; j < (n+1)/2; j++) { int temp = matrix[i][j]; matrix[i][j] = matrix[n - j - 1][i]; matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1]; matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1]; matrix[j][n - i - 1] = temp; } } } 43.字符串相乘 很恶心的题，费劲又麻烦，没啥特别简洁的套路 public String multiply(String num1, String num2) { if (num1.equals("0") || num2.equals("0")) { return "0"; } int[] res = new int[num1.length() + num2.length()]; for (int i = num1.length() - 1; i >= 0; i--) { int n1 = num1.charAt(i) - '0'; for (int j = num2.length() - 1; j >= 0; j--) { int n2 = num2.charAt(j) - '0'; int sum = (res[i + j + 1] + n1 * n2); res[i + j + 1] = sum % 10; res[i + j] += sum / 10; } } StringBuilder result = new StringBuilder(); for (int i = 0; i < res.length; i++) { if (i == 0 && res[i] == 0) continue; result.append(res[i]); } return result.toString(); } 64.最小路径和 很简单常规的二维dp，转移方程 dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]) public int minPathSum(int[][] grid) { int row = grid.length; int col = grid[0].length; int[][] dp = new int[row][col]; dp[0][0] = grid[0][0]; for (int i = 1; i < row; i++) { dp[i][0] = dp[i-1][0] + grid[i][0]; } for (int i = 1; i < col; i++) { dp[0][i] = dp[0][i-1] + grid[0][i]; } for (int i = 1; i < row; i++) { for (int j = 1; j < col; j++) { dp[i][j] = grid[i][j] + Math.min(dp[i][j-1], dp[i-1][j]); } } return dp[row-1][col-1]; } 226. 翻转二叉树 典型递归 public TreeNode invertTree(TreeNode root) { if (root != null) { invertTree(root.left); invertTree(root.right); TreeNode tree = root.left; root.left = root.right; root.right = tree; } return root; } 165.比较版本号 String.split分割，但是注意特殊字符前加\\ class Solution { public int compareVersion(String version1, String version2) { String[] s1 = version1.split("\\."); String[] s2 = version2.split("\\."); int len1 = s1.length; int len2 = s2.length; for (int i = 0; i < len1 && i < len2; i++) { if (Integer.valueOf(s1[i]) > Integer.valueOf(s2[i])) { return 1; } if (Integer.valueOf(s1[i]) < Integer.valueOf(s2[i])) { return -1; } } if (len1 > len2 && remain(s1, len2) > 0) { return 1; }else if (len1 < len2 && remain(s2, len1) > 0) { return -1; } return 0; } public int remain(String[] arr, int start) { StringBuilder sb = new StringBuilder(""); for (int i = start; i < arr.length; i++) { sb.append(arr[i]); } return Integer.valueOf(sb.toString()); } } 34.在排序数组中查找元素的第一个和最后一个位置 在使用二分查找第一次查找到目标值之后继续二分查找 那么第一次出现的即为一直二分后最左的位置，最后一次出现即为第一次比target大的数的下标-1 class Solution { public int[] searchRange(int[] nums, int target) { int leftIdx = binarySearch(nums, target, true); int rightIdx = binarySearch(nums, target, false) - 1; if (leftIdx <= rightIdx && rightIdx < nums.length && nums[leftIdx] == target && nums[rightIdx] == target) { return new int[]{leftIdx, rightIdx}; } return new int[]{-1, -1}; } public int binarySearch(int[] nums, int target, boolean lower) { int left = 0, right = nums.length - 1, ans = nums.length; while (left <= right) { int mid = (left + right)/2; if (nums[mid] > target || (lower && nums[mid] >= target)) { right = mid -1; ans = mid; } else { left = mid + 1; } } return ans; } } 83.删除排序链表中的重复元素 链表基操 public ListNode deleteDuplicates(ListNode head) { ListNode node = head; while (node != null) { ListNode cur = node.next; while (cur != null && node.val == cur.val) { cur = cur.next; } node.next = cur; node = node.next; } return head; } 39.组合总和 由于题目要求所有情况，暴力dfs + 剪枝 + 回溯 即可 class Solution { List<List<Integer>> res = new ArrayList<>(); int[] arr; public List<List<Integer>> combinationSum(int[] candidates, int target) { arr = candidates; dfs(new ArrayList<>(), target, 0); return res; } public void dfs(List<Integer> list, int val, int index) { if (val < 0) { return; } if (val == 0) { res.add(new ArrayList<>(list)); } for (int i = index; i < arr.length; i++) { list.add(arr[i]); dfs(list, val - arr[i], i); list.remove(list.size() - 1); } } }
【CodeTop x LeetCode】Page 3 ： 41-60面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 8.字符串转换整数 (atoi) 自动机 我的代码就是根据题意一步一步判断的，所以非常臃肿，但是根据官方给的自动机解法暂时还没看懂 public int myAtoi(String s) { int j = 0; for (; j < s.length();) { if (s.charAt(j) == ' ') { j++; }else { break; } } s = s.substring(j); if (s.length() <= 0) { return 0; } boolean isNegative = false; int i = 0, res = 0; if (s.charAt(0) == '-' || s.charAt(0) == '+') { if (s.charAt(0) == '-') { isNegative = true; } i = 1; } for (; i < s.length();) { if (s.charAt(i) == '0') { i++; }else { break; } } StringBuilder sb = new StringBuilder(""); for (; i < s.length(); i++) { if (s.charAt(i) >= '0' && s.charAt(i) <= '9') { sb.append(s.charAt(i)); }else { break; } } String str = sb.toString(); if (str.length() != 0) { if (str.length() > 10) { if (isNegative) { return Integer.MIN_VALUE; } return Integer.MAX_VALUE; }else { long l = Long.valueOf(str); if (l > Integer.MAX_VALUE) { if (isNegative) { return Integer.MIN_VALUE; } return Integer.MAX_VALUE; }else { if (isNegative) { return -1*Integer.valueOf(str); } return Integer.valueOf(str); } } } return res; } 2.两数相加 话说真快被链表题搞懵了呀，这个我也是按照纯模拟加法的思路写的，先去判断哪个链表长，然后哦就把短的依次加到长的上面，还要注意进位问题。 public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode cul1 = l1; ListNode cul2 = l2; int l1_len = 0; int l2_len = 0; while (cul1 != null || cul2 != null) { if (cul1 != null) { l1_len++; cul1 = cul1.next; } if (cul2 != null) { l2_len++; cul2 = cul2.next; } } ListNode lon = l1; ListNode shor = l2; if (l2_len > l1_len) { lon = l2; shor = l1; } int yu = 0; while (shor != null) { lon.val += (shor.val+yu); if (lon.val >= 10) { yu = 1; lon.val -=10; }else { yu = 0; } shor = shor.next; if (lon.next == null && yu == 1) { lon.next = new ListNode(0); } lon = lon.next; } while (yu == 1) { lon.val += 1; if (lon.val >= 10) { yu = 1; lon.val -= 10; if (lon.next == null) { lon.next = new ListNode(0); } lon = lon.next; }else { yu = 0; } } if (l2_len > l1_len) { return l2; } return l1; } 82.删除排序链表中的重复元素 II 判断当前节点的下一个节点与下下一个节点的值，相等则不断调整当前节点的next，不相等则向后移动；这里引入头节点方便对首元节点的操作。 public ListNode deleteDuplicates(ListNode head) { if (head == null || head.next == null) { return head; } ListNode fake = new ListNode(); fake.next = head; ListNode cur = fake; while (cur.next != null && cur.next.next != null) { if (cur.next.val == cur.next.next.val) { int x = cur.next.val; while (cur.next != null && cur.next.val == x) { cur.next = cur.next.next; } }else { cur = cur.next; } } return fake.next; } 144.二叉树的前序遍历 class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> preorderTraversal(TreeNode root) { dfs(root); return list; } public void dfs (TreeNode root) { if (root != null) { list.add(root.val); dfs(root.left); dfs(root.right); } } } 148.排序链表 这道题思路是归并，但是有两个归并思路： 递归着归并，先找中点（使用快慢指针），一次分一半，递归，一次分一半，递归....然后两两合并并返回 先设归并长度为1，第一波归并完再把归并长度乘2，再归并，以此类推 （本体采用自顶向下的递归方式） class Solution { public ListNode sortList(ListNode head) { return sort(head, null); } private ListNode sort(ListNode start, ListNode end) { if (start == end) { return start; } ListNode fast = start, slow = start; while (fast != end && fast.next != end) { fast = fast.next.next; slow = slow.next; } ListNode l2 = sort(slow.next, end); slow.next = null; ListNode l1 = sort(start, slow); return mergeTwoLists(l1, l2); } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null || l2 == null) { return l1 == null ? l2 : l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l2.next, l1); return l2; } } } 31.下一个排列 倒着遍历第一次找到第一个值变小的，记录坐标为i 倒着遍历第二次找到刚好比nums[i]大的坐标j 交换i，j并翻转i+1到结尾的数字 class Solution { public void nextPermutation(int[] nums) { int i = nums.length - 2; while (i >= 0 && nums[i] >= nums[i+1]) { i--; } if (i >= 0) { int j = nums.length - 1; while (j > i && nums[j] <= nums[i]) { j--; } swap(nums, i, j); } for (int x = i+1, y = nums.length-1; x < y;) { swap(nums, x, y); x++; y--; } } private void swap (int[] nums, int i, int j) { int swap = nums[i]; nums[i] = nums[j]; nums[j] = swap; } } 76.最小覆盖子串 思路：滑动窗口（左右指针l,r），用两个常量数组判断当前字符串是否包含模式串（'a'~'Z'可以用长度60存下） 不包含，r++；包含，l++，并更新结果 （这道题虽然是困难，但是思路还是比较容易懂的） public String minWindow(String s, String t) { String res = ""; int[] sarr = new int[60]; int[] tarr = new int[60]; for (int i = 0; i < t.length(); i++) { tarr[t.charAt(i) - 'A']++; } int l = 0, r = 0; while (l <= r) { boolean isHave = true; for (int j = 0; j < 60; j++) { if (sarr[j] < tarr[j]) { isHave = false; break; } } if (isHave) { String temp = s.substring(l, r); if (res.length() == 0) { res = temp; }else { res = temp.length() < res.length() ? temp:res; } sarr[s.charAt(l) - 'A']--; l++; }else if (r < s.length()) { sarr[s.charAt(r) - 'A']++; r++; }else { break; } } return res; } 151.翻转字符串里的单词 常规字符串算法题，比较简单，借助java的trim()和split()函数，使用StringBuilder快速追加 public String reverseWords(String s) { StringBuilder sb = new StringBuilder(""); s = s.trim(); String[] arr = s.split(" "); for (int i = arr.length - 1; i > 0; i--) { if (arr[i].length() != 0) { sb.append(arr[i] + " "); } } sb.append(arr[0]); return sb.toString(); } 72. 编辑距离 这里提供了两种方法：自底向上的递归和自顶向下的动规，但是递归会超时，动规就是记录了子问题的结果避免重复计算。 dp[i][j]的意思是word1.subString(0, i)变为word2.subString(0, j)所需的步数 根据题目中给的三种操作我们可以推出核心的动态转移方程为： dp[i+1][j+1] = 1 + Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]); 这里由于下标从1开始到length，避免数组越界所以使下一个用当前的值 这是一道经典的动态规划题目，值得反复练习 class Solution { public int minDistance(String word1, String word2) { int l1 = word1.length(); int l2 = word2.length(); int[][] dp = new int[l1 + 1][l2 + 1]; for (int i = 0; i < l1 + 1; i++) { dp[i][0] = i; } for (int i = 0; i < l2 + 1; i++) { dp[0][i] = i; } for (int i = 0; i < l1; i++) { for (int j = 0; j < l2; j++) { if (word1.charAt(i) == word2.charAt(j)) { dp[i+1][j+1] = dp[i][j]; //一样则无需多余操作步数 }else { dp[i+1][j+1] = 1 + Math.min(Math.min(dp[i][j+1], dp[i+1][j]), dp[i][j]); } } } return dp[l1][l2]; } //递归（超时） public int minDistance_recursion(String word1, String word2) { if (word1.length() == 0 || word2.length() == 0) { return Math.max(word1.length(), word2.length()); } if (word1.charAt(word1.length()-1) == word2.charAt(word2.length()-1)) { return minDistance_recursion(word1.substring(0, word1.length()-1), word2.substring(0, word2.length()-1)); } return 1 + Math.min(Math.min(minDistance_recursion(word1, word2.substring(0, word2.length()-1)), minDistance_recursion(word1.substring(0, word1.length()-1), word2)), minDistance_recursion(word1.substring(0, word1.length()-1),word2.substring(0, word2.length()-1))); } } 4.寻找两个正序数组的中位数 这道题目有两个思路： 合并两个有序数组，再直接输出中位数，时间复杂度O(m+n)，空间复杂度O(m+n) 划分数组+推导，时间复杂度O(logmin(m,n)))，空间复杂度O(1)，但是这个暂时还没搞懂 class Solution { public double findMedianSortedArrays(int[] nums1, int[] nums2) { int l1 = nums1.length; int l2 = nums2.length; int l3 = l1+l2; int[] arr = new int[l3]; for (int i = 0; i < l1; i++) { arr[i] = nums1[i]; } merge(arr, l1, nums2, l2); if (l3 % 2 == 1) { return arr[l3/2]; } return ((float)(arr[l3/2-1]+arr[l3/2]))/2; } public void merge(int[] nums1, int m, int[] nums2, int n) { int n1 = m -1; int n2 = n -1; while (n2 >= 0) { if (n1 >= 0 && nums1[n1] >= nums2[n2]) { nums1[n1+n2+1] = nums1[n1]; n1--; }else { nums1[n1+n2+1] = nums2[n2]; n2--; } } } } 129.求根节点到叶节点数字之和 深度优先搜索，使用StringBuilder记录路径上节点的值，再判断左右孩子为空时，将其转换成Integer。递归返回前去除 StringBuilder的最后一个字符 class Solution { private StringBuilder sb = new StringBuilder(); private int res = 0; public int sumNumbers(TreeNode root) { if (root != null) { sb.append(root.val); if (root.left == null && root.right == null) { res += Integer.valueOf(sb.toString()); }else { sumNumbers(root.left); sumNumbers(root.right); } sb.deleteCharAt(sb.length()-1); } return res; } } 104.二叉树的最大深度 二叉树必需掌握的题，数据结构教材上的原题 public int maxDepth(TreeNode root) { if (root == null) { return 0; } else { return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; } } 105.从前序与中序遍历序列构造二叉树 前序遍历和中序遍历的概念这里就不说了，其实推的时候很容易发现是一个递归的过程，有关于递归下标的计算如图： class Solution { private HashMap<Integer, Integer> map = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { map.put(inorder[i], i); } return buildTree(preorder, 0, preorder.length - 1, 0, inorder.length - 1); } public TreeNode buildTree(int[] preorder, int preLeft, int preRight, int inLeft, int inRight) { if (preLeft > preRight || inLeft > inRight) { return null; } int val = preorder[preLeft]; TreeNode node = new TreeNode(val); int pIndex = map.get(val); node.left = buildTree(preorder, preLeft+1, pIndex - inLeft + preLeft, inLeft, pIndex - 1); node.right = buildTree(preorder, pIndex - inLeft + preLeft + 1, preRight, pIndex + 1, inRight); return node; } } 239.滑动窗口最大值 这道题一开始很容易想到使用优先队列来解决，但是写完检测却发现超时了，看题解是使用的单调队列（递增、递减的队列） 定义一个双端队列，存储数组下标，那么队首的值就是nums[queue.peekFirst()]，存下标主要就是为了方便判断队列队首元素是否已经在滑动窗口外：queue.peekFirst() < left，队首元素对应数组值最大，依次递减。 定义右指针right从 0 到nums.length()-1，就很容易计算窗口的左指针left为right - k + 1 如果一个元素入队（入队都是从队尾入），则说明它在窗口内，那么队列内比该值小的则永远不会加入到最终答案res内，直到该元素出窗口，所以我们把队列内比该元素小的值出队。保证队列的一个单调递减。 最后一个right + 1 >= k是因为这时最初的窗口才刚刚形成，满足长度为k，才能添加。 class Solution { //单调队列 public int[] maxSlidingWindow(int[] nums, int k) { int[] res = new int[nums.length-k+1]; ArrayDeque<Integer> queue = new ArrayDeque<>(); for (int right = 0; right < nums.length; right++) { while (queue.size() > 0 && nums[right] > nums[queue.peekLast()]) { queue.pollLast(); } queue.offerLast(right); int left = right - k + 1; if (left > queue.peekFirst()) { queue.pollFirst(); } if (right + 1 >= k) { res[left] = nums[queue.peekFirst()]; } } return res; } //优先队列（超时） public int[] maxSlidingWindow_PriorityQueue(int[] nums, int k) { PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)-> b-a); int[] res = new int[nums.length-k+1]; for (int i = 0; i < k; i++) { queue.offer(nums[i]); } res[0] = queue.peek(); for (int i = k, j = 0; i < nums.length; i++,j++) { queue.offer(nums[i]); queue.remove(nums[j]); res[j+1] = queue.peek(); } return res; } } 93.复原 IP 地址 一个字符串，分成四部分，我就懒省事直接暴力dfs了，枚举出来所有分割情况再做判断 class Solution { private List<String> res = new ArrayList<>(); private String param; public List<String> restoreIpAddresses(String s) { param = s; dfs("", 0, 1); return res; } public void dfs (String s, int index, int count) { if (count >= 4) { if (judge(index, param.length())) { res.add(s + param.substring(index)); } }else { for (int i = 1; i <= 3; i++) { if ((index + i) <= param.length() && judge(index, index+i)) { dfs(s+param.substring(index, index+i)+".", index+i, count + 1); } } } } public boolean judge (int start, int end) { String temp = param.substring(start, end); if (temp.length() <= 3 && temp.length() != 0) { int val = Integer.valueOf(temp); if (String.valueOf(val).length() == temp.length() && val <= 255) { return true; } } return false; } } 113.路径总和 II 这道题和前面的 129.求根节点到叶节点数字之和 基本一致，都是dfs+回溯即可 class Solution { private List<List<Integer>> res = new ArrayList<>(); private List<Integer> cur = new ArrayList<>(); private int sum = 0; private int target = 0; public List<List<Integer>> pathSum(TreeNode root, int targetSum) { target = targetSum; dfs(root); return res; } public void dfs (TreeNode root) { if (root != null) { sum += root.val; cur.add(root.val); if (root.left == null && root.right == null) { if (sum == target) { List<Integer> temp = new ArrayList<>(); for (int i = 0; i < cur.size(); i++) { temp.add(cur.get(i)); } res.add(temp); } }else { dfs(root.left); dfs(root.right); } sum -= root.val; cur.remove(cur.size()-1); } } } 110.平衡二叉树 平衡二叉树的定义本身就是一个递归的定义：左右子树深度只差的绝对值不超过1，并且左右子树也是平衡的 class Solution { public boolean isBalanced(TreeNode root) { if (root != null) { return Math.abs(height(root.left) - height(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right); } return true; } public int height (TreeNode root) { if (root == null) { return 0; } else { return Math.max(height(root.left), height(root.right)) + 1; } } } 1143.最长公共子序列 典型的二维动规，dp[i][j]代表text[0...i]和text[0...j]的最长公共子序列，所以可以推导出动态转移方程为： 其实到这里我们可以发现有关于两个字符串之间的动态规划题目，基本都是一个二维数组dp，两个for循环里面一个状态转移方程，更新数组，最后返回数组的最后一个值，这就是动规模板。 class Solution { public int longestCommonSubsequence(String text1, String text2) { int[][] dp = new int[text1.length()+1][text2.length()+1]; for (int i = 1; i <= text1.length(); i++) { for (int j = 1; j <= text2.length(); j++) { if (text1.charAt(i-1) == text2.charAt(j-1)) { dp[i][j] = dp[i-1][j-1]+1; }else { dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]); } } } return dp[text1.length()][text2.length()]; } } 470.用 Rand7() 实现 Rand10() 古典概型 第一次rand7限定[1,2]，判断奇偶性，概率是1/2，其实first的作用就是生成概率为1/2的奇偶。 （我们还可以通过限定[1,3]，再取模3进行概率为1/3的操作） 第二次rand7限定[1,5]，概率是1/5，加上5为[6,10]，概率也是1/5 二者结合可以得出10种概率相同的结果 借助这个思路我们也可以构造出其他的 /** * The rand7() API is already defined in the parent class SolBase. * public int rand7(); * @return a random integer in the range 1 to 7 */ class Solution extends SolBase { public int rand10() { int first,second; while ((first = rand7()) > 2); while ((second = rand7()) > 5); return first%2 == 0 ? second : second+5; } } 543.二叉树的直径 这道题跟计算二叉树的深度还不太一样，是求任意两个节点的最大路径，可以不过根节点。递归的同时对结果更新要注意： class Solution { private int res = 0; public int diameterOfBinaryTree(TreeNode root) { height(root); return res-1; } public int height (TreeNode root) { if (root != null) { int l = height(root.left); int r = height(root.right); res = Math.max(res, l+r+1); return Math.max(l,r)+1; } return 0; } }
【CodeTop x LeetCode】Page 2 ： 21-40面试高频算法题题解
更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 92.反转链表II 思路是记录反转部分的前一个节点和后一个节点，将其反转后再连接，思路是这个，但是我在实现上可能麻烦一些： class Solution { public ListNode reverseBetween(ListNode head, int left, int right) { ListNode curr = head; ListNode prev = null; ListNode next = curr; int flag = 1; while (flag < right) { if (flag == left - 1) { prev = curr; } curr = curr.next; flag++; } next = curr.next; if (prev == null) { head = reverse(head, left, right); prev = head; }else { prev.next = reverse(prev.next, left, right); } while ( prev.next != null && left <= right) { prev = prev.next; } if (next != null) { if (prev.next != null) { prev.next.next = next; }else { prev.next = next; } } return head; } public ListNode reverse(ListNode head, int left, int right) { if (left == right) { return head; } ListNode prev = null; ListNode curr = head; while (left <= right) { ListNode nextTemp = curr.next; curr.next = prev; prev = curr; curr = nextTemp; left++; } return prev; } } 200.岛屿数量 广搜、深搜都可以，这里是深搜+剪枝，不用回溯： class Solution { public int numIslands(char[][] grid) { int res = 0; for (int i = 0; i < grid.length; i++) { for (int j = 0; j < grid[0].length; j++) { if (grid[i][j] == '1') { res++; dfs(grid, i, j); } } } return res; } public void dfs(char[][] grid, int x, int y) { grid[x][y] = '0'; if (x < grid.length - 1 && grid[x+1][y] == '1') { dfs(grid, x+1, y); } if (x > 0 && grid[x-1][y] == '1') { dfs(grid, x-1, y); } if (y < grid[0].length - 1 && grid[x][y+1] == '1') { dfs(grid, x, y+1); } if (y > 0 && grid[x][y-1] == '1') { dfs(grid, x, y-1); } } } 33.搜索旋转排序数组 二分（我当时是懒省事直接O(n)遍历了） class Solution { public int search(int[] nums, int target) { int n = nums.length; if (n == 0) { return -1; } if (n == 1) { return nums[0] == target ? 0 : -1; } int l = 0, r = n - 1; while (l <= r) { int mid = (l + r) / 2; if (nums[mid] == target) { return mid; } if (nums[0] <= nums[mid]) { if (nums[0] <= target && target < nums[mid]) { r = mid - 1; } else { l = mid + 1; } } else { if (nums[mid] < target && target <= nums[n - 1]) { l = mid + 1; } else { r = mid - 1; } } } return -1; } } 46.全排列 经典算法，使用dfs+交换+回溯，可以当模板套用： class Solution { private List<List<Integer>> list = new ArrayList<>(); public List<List<Integer>> permute(int[] nums) { dfs(nums, 0, nums.length-1); return list; } public void dfs(int[] array,int start,int end) { if(start==end) { List<Integer> li = new ArrayList<>(); for (int i = 0; i < array.length; i++) { li.add(array[i]); } list.add(li); } else { for (int i = start; i <= end; i++) { swap(array,start,i); dfs(array,start+1,end); swap(array,start,i); } } } public void swap(int[] array,int i,int j) { int temp = array[i]; array[i] = array[j]; array[j] = temp; } } 142.环形链表 II 当快慢指针相遇之后，使用第三个指针从头开始和慢指针一起向后移动（步伐都是一步），当第三个指针与慢指针相遇时，即为环的入口： public ListNode detectCycle(ListNode head) { ListNode fast = head; ListNode slow = head; ListNode res = head; while (fast != null && slow != null) { fast = fast.next; if (fast == null) { break; } fast = fast.next; slow = slow.next; if (slow == fast) { while (slow != res) { slow = slow.next; res = res.next; } return res; } } return null; } 23.合并K个排序链表 结合前面那道合并两个链表，我们只需循环调用该方法即可： class Solution { public ListNode mergeKLists(ListNode[] lists) { if (lists.length == 0) { return null; } if (lists.length == 1) { return lists[0]; } ListNode res = lists[0]; for (int i = 0; i < lists.length-1; i++) { res = mergeTwoLists(res, lists[i+1]); } return res; } public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l2.next, l1); return l2; } } } 54.螺旋矩阵 模拟打印顺序： public List<Integer> spiralOrder(int[][] matrix) { List<Integer> list = new ArrayList<>(); int left = 0 ,up = 0; int right = matrix[0].length - 1; int down = matrix.length - 1; int size = matrix.length * matrix[0].length; while (list.size() < size) { for (int i = left; i <= right; i++) { if (list.size() < size) list.add(matrix[up][i]); } up++; for (int i = up; i <= down; i++) { if (list.size() < size) list.add(matrix[i][right]); } right--; for (int i = right; i >= left; i--) { if (list.size() < size) list.add(matrix[down][i]); } down--; for (int i = down; i >= up; i--) { if (list.size() < size) list.add(matrix[i][left]); } left++; } return list; } 704.二分查找 如题，就是考二分 public int search(int[] nums, int target) { int l = 0, r = nums.length-1, m; while (l <= r) { m = (r + l)/2; if (target == nums[m]) { return m; } if (target > nums[m]) { l = m + 1; }else { r = m - 1; } } return -1; } 232.用栈实现队列 两个栈实现，需要弹出时，将栈s1全部倒入s2，再从s2弹 class MyQueue { private Stack<Integer> s1 = new Stack<>(); private Stack<Integer> s2 = new Stack<>(); private int front; public MyQueue() {} public void push(int x) { if (s1.empty()) { front = x; } s1.push(x); } public int pop() { if (s2.empty()) { while(!s1.empty()) { s2.push(s1.pop()); } } return s2.pop(); } public int peek() { if (s2.empty()) { return front; }else { return s2.peek(); } } public boolean empty() { return s1.empty() && s2.empty(); } } 42.接雨水 动规：从左向右，记录最大高度；再从右向左记录最大高度；最后每格的积水为两个数组中较小的那个再减去这个位置的高度： public int trap(int[] height) { int res = 0; int len = height.length; int[] left = new int[len]; int[] right = new int[len]; left[0] = height[0]; for (int i = 1; i < len; i++) { left[i] = Math.max(left[i-1], height[i]); } right[len-1] = height[len-1]; for (int i = len - 2; i >= 0; i--) { right[i] = Math.max(height[i], right[i+1]); } for (int i = 0; i < len; i++) { res += Math.min(left[i], right[i]) - height[i]; } return res; } 94.二叉树的中序遍历 递归 class Solution { List<Integer> list = new ArrayList<>(); public List<Integer> inorderTraversal(TreeNode root) { dfs(root); return list; } public void dfs (TreeNode root) { if (root != null) { dfs(root.left); list.add(root.val); dfs(root.right); } } } 300.最长上升子序列 经典动规：（现在看看差不多又忘记怎么做了） public int lengthOfLIS(int[] nums) { if (nums.length == 0) { return 0; } int[] dp = new int[nums.length]; dp[0] = 1; int res = 1; for (int i = 1; i < nums.length; i++) { dp[i] = 1; for (int j = 0; j < i; j++) { if (nums[i] > nums[j]) { dp[i] = Math.max(dp[i], dp[j] + 1); } } res = Math.max(res, dp[i]); } return res; } 143.重排链表 分三步：找中点——>翻转链表——>合并链表 class Solution { public void reorderList(ListNode head) { if (head == null) { return; } ListNode mid = middleList(head); ListNode l2 = reverseList(mid); mergeList(head, l2); } public ListNode middleList(ListNode head) { ListNode slow = head; ListNode fast = head; while (fast.next != null && fast.next.next != null) { fast = fast.next.next; slow = slow.next; } return slow; } public ListNode reverseList(ListNode head) { ListNode prev = null, next; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } public void mergeList(ListNode l1, ListNode l2) { ListNode l1_t, l2_t; while (l1 != null && l2 != null) { l1_t = l1.next; l1.next = l2; l1 = l1_t; l2_t = l2.next; l2.next = l1; l2 = l2_t; } } } 199.二叉树的右视图 向右深搜，技巧点：树的深度==集合大小，所以记录每层的深度，当depth == res.size()时为第一当这一层的最右节点： class Solution { List<Integer> res = new ArrayList<>(); public List<Integer> rightSideView(TreeNode root) { dfs(root, 0); return res; } public void dfs (TreeNode root, int depth) { if (root != null) { if (depth == res.size()) { res.add(root.val); } dfs(root.right, depth+1); dfs(root.left, depth+1); } } } 70.爬楼梯 就是斐波那契数列，滚动数组解决： public int climbStairs(int n) { if (n == 1) { return 1; } int[] dp = new int[3]; dp[0] = 1; dp[1] = 1; for (int i = 2; i <= n; i++) { dp[2] = dp[0] + dp[1]; dp[0] = dp[1]; dp[1] = dp[2]; } return dp[2]; } 22.链表中倒数第k个节点 两个指针，一个从起点，另一个从正数第k个移动： public ListNode getKthFromEnd(ListNode head, int k) { ListNode fast = head; ListNode slow = head; while (k-- > 0) { fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; } 124.二叉树中的最大路径和 思路是递归，递归去找左右最大的路径和，个人觉得比较难，需重复做： class Solution { int res = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { dfs(root); return res; } public int dfs(TreeNode node) { if (node == null) { return 0; } int left = Math.max(dfs(node.left), 0); int right = Math.max(dfs(node.right), 0); res = Math.max(res, node.val + left + right); return node.val + Math.max(left, right); } } 69.x 的平方根 二分： public int mySqrt(int x) { int res = -1, l = 0, r = x,m; while (l <= r) { m = l + (r - l)/2; if ((long)m*m <= x) { l = m + 1; res = m; }else { r = m - 1; } } return res; } 56.合并区间 根据左端点排列后开始有序合并： public int[][] merge(int[][] intervals) { List<int[]> res = new ArrayList<>(); if (intervals == null || intervals.length == 0) { return res.toArray(new int[0][]); } if (intervals.length == 1) { return intervals; } Arrays.sort(intervals, (a, b) -> a[0] - b[0]); for (int i = 0; i < intervals.length-1;i++) { int left = intervals[i][0]; int right = intervals[i][1]; while (right >= intervals[i+1][1] || right >= intervals[i+1][0]) { if (right < intervals[i+1][1]) { right = intervals[i+1][1]; } i++; if (i == intervals.length - 1) { break; } } int[] temp = new int[]{left, right}; res.add(temp); } if (res.get(res.size() - 1)[1] < intervals[intervals.length -1][1]) { res.add(intervals[intervals.length -1]); } return res.toArray(new int[0][]); } 19.删除链表的倒数第 N 个结点 我的写法可能麻烦些，主要是一些边界值的判断，思路和前面寻找倒数第N个节点思路一样，只不过是找N+1个，再做删除操作即可： class Solution { public ListNode removeNthFromEnd(ListNode head, int n) { ListNode prev = findprev(head, n+1); if (prev == null) { if (head.next != null) { return head.next; } return null; } if (prev.next != null) { prev.next = prev.next.next; } return head; } public ListNode findprev (ListNode head, int k) { ListNode fast = head; ListNode slow = head; while (k-- > 0) { if (fast == null) { return null; } fast = fast.next; } while (fast != null) { fast = fast.next; slow = slow.next; } return slow; } }
【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解
之后博主会出一个系列专门记录CodeTop高频算法题的一个详解，一次更新20道，也就是一页的数量。更多答案也可以关注我的GitHub算法仓库——Algorithm （大家可以根据我每道题打的星来衡量这道题的难易，星越少越难） [scode type="green"]所有代码都是在力扣上提交通过的，保证代码的正确无误[/scode] 基础数据结构： class ListNode { int val; ListNode next; ListNode() {} ListNode(int val) { this.val = val; } ListNode(int val, ListNode next) { this.val = val; this.next = next; } } class TreeNode { int val; TreeNode left; TreeNode right; TreeNode() {} TreeNode(int val) { this.val = val; } TreeNode(int val, TreeNode left, TreeNode right) { this.val = val; this.left = left; this.right = right; } } 206.反转链表 这应该是链表里最基础、最常问的一道算法题了，相比链表简单的插入删除要复杂一些，可以根据代码把图画一遍方便理解，但还是容易忘，记住要点是一个 while 循环里四行ListNode的交换操作： public ListNode reverseList(ListNode head) { ListNode prev = null, next = null; while (head != null) { next = head.next; head.next = prev; prev = head; head = next; } return prev; } 146.LRU缓存机制 这道题在Java里可以通过LinkedHashMap实现，但是面试肯定不能这么说，需要使用 哈希表 + 双向链表 ，可以说又是一道大量链表的操作题，有助于锻炼对链表操作的理解： class LRUCache { //双向链表 class DLinkedNode { int key; int value; DLinkedNode prev; DLinkedNode next; DLinkedNode() {} DLinkedNode(int _key, int _value) { key = _key; value = _value; } } private Map<Integer, DLinkedNode> cache = new HashMap<>(); private int size; private int capacity; private DLinkedNode head, tail; public LRUCache(int capacity) { this.size = 0; this.capacity = capacity; // 使用伪头部和伪尾部节点 head = new DLinkedNode(); tail = new DLinkedNode(); head.next = tail; tail.prev = head; } public int get(int key) { DLinkedNode node = cache.get(key); if (node == null) { return -1; } moveToHead(node); return node.value; } public void put(int key, int value) { DLinkedNode node = cache.get(key); if (node == null) { if (size >= capacity) { removeTail(); size--; } addToHead(new DLinkedNode(key, value)); size++; }else { node.value = value; moveToHead(node); } } //加入头部 private void addToHead(DLinkedNode node) { node.prev = head; node.next = head.next; node.next.prev = node; head.next = node; cache.put(node.key, node); } //移动到头部 private void moveToHead(DLinkedNode node) { removeNode(node); addToHead(node); } //移除尾部 private void removeTail() { removeNode(tail.prev); } //删除节点，记者也要更新哈希表 private void removeNode(DLinkedNode node) { node.prev.next = node.next; node.next.prev = node.prev; cache.remove(node.key); } } 3.无重复字符的最长子串 这道题的最优解是使用滑动窗口，同时需要用到Set集合，我认为还是比较有难度的 public int lengthOfLongestSubstring(String s) { Set<Character> occ = new HashSet<Character>(); int n = s.length(); int rk = -1, ans = 0; for (int i = 0; i < n; i++) { if (i != 0) { occ.remove(s.charAt(i - 1)); } while (rk + 1 < n && !occ.contains(s.charAt(rk + 1))) { occ.add(s.charAt(rk + 1)); rk++; } ans = Math.max(ans, rk - i + 1); } return ans; } 215.数组中的第K个最大的数 主要考查排序，大家可以把它当作考堆排的算法题。 25.K个一组翻转链表 在第一道翻转链表的基础上难度又提升了一级，需要使用到递归（这道题我当时做了好久没做出来....） public ListNode reverseKGroup(ListNode head, int k) { // 如果头节点为null或者节点只有一个直接返回 if (head == null || head.next == null) { return head; } //保存每一段反转的头尾指针 ListNode tail = head; //循环k次，找到尾部 for (int i = 0; i < k; i++) { //如果不够k个就结束了，这一段不反转直接返回头部 if (tail == null) { return head; } tail = tail.next; } //反转后记录这一段的头部 ListNode newHead = reverse(head, tail); // [ ) //这里的head其实按这一段的顺序已经是指向尾部了 // 这里的head.next需要指向下一段的头部（就是它反转后的tail） //每一段反转后，一开始的head最后指向尾，一开始的tail最后指向头 head.next = reverseKGroup(tail, k); return newHead; } //根据头尾指针反转，每一段反转后，一开始的head最后指向尾，一开始的tail最后指向头 public ListNode reverse(ListNode head, ListNode tail) { ListNode pre = null, next = null; while (head != tail) { next = head.next; head.next = pre; pre = head; head = next; } return pre; } 补充题4. 手撕快速排序 就是考快排 15.三数之和 最优解：排序+双指针 public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); int lastA = -9999999; for (int i = 0; i < nums.length-2; i++) { if (nums[i] > 0) { return result; } if (nums[i] == lastA) { continue; } lastA = nums[i]; int lastLeft = -9999999; int right = nums.length; for (int j = i+1; j < right - 1; j++) { if (nums[j] == lastLeft) { continue; } for (int k = right - 1; k > j; k--) { if (nums[i] + nums[j] + nums[k] == 0) { List<Integer> temp = new ArrayList<>(); temp.add(nums[i]); temp.add(nums[j]); temp.add(nums[k]); result.add(temp); right = k; break; } } lastLeft = nums[j]; } } return result; } 53.最大子序和 动态规划，但是空间复杂度是O(1)，每次只保存当前的最优解 public int maxSubArray(int[] nums) { int res = nums[0]; for (int i = 1; i < nums.length; i++) { if (nums[i-1] > 0) { nums[i]+=nums[i-1]; } res = res > nums[i] ? res:nums[i]; } return res; } 1.两数之和 哈希表，空间换时间，每次存这个数，找哈希表里的另一半target-nums[i] public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { if (map.containsKey(target-nums[i])) { return new int[] {i, map.get(target-nums[i])}; } map.put(nums[i], i); } return null; } 141.环形链表 经典链表题：快慢指针，相遇则有环，任意一个为null则无环 public boolean hasCycle(ListNode head) { ListNode fast = head; while (head != null && fast != null) { head = head.next; fast = fast.next; if (fast != null) { fast = fast.next; }else { break; } if (head == fast) { return true; } } return false; } 21.合并两个有序链表 思路：递归 public ListNode mergeTwoLists(ListNode l1, ListNode l2) { if (l1 == null) { return l2; } if (l2 == null) { return l1; } if (l1.val < l2.val) { l1.next = mergeTwoLists(l1.next, l2); return l1; }else { l2.next = mergeTwoLists(l2.next, l1); return l2; } } 102.二叉树的层序遍历 典型的队列题目 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } ArrayDeque<TreeNode> queue = new ArrayDeque<>(); queue.offer(root); while (!queue.isEmpty()) { List<Integer> level = new ArrayList<>(); int curLevelSize = queue.size(); for (int i = 0; i < curLevelSize; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); } } res.add(level); } return res; } 160.相交链表 两个指针分别移动，到末尾之后移到对方链表上继续移动，相等时返回 public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if (headA == null || headB == null) { return null; } ListNode pA = headA; ListNode pB = headB; while(pA != pB) { pA = pA == null ? headB : pA.next; pB = pB == null ? headA : pB.next; } return pA; } 121.买卖股票的最佳时机 一次for循环，每次记录最小值，以及更新最大利润 public int maxProfit(int[] prices) { int res = 0; int min = Integer.MAX_VALUE; for (int i = 0; i < prices.length; i++) { if (min > prices[i]) { min = prices[i]; }else { res = Math.max(res, prices[i] - min); } } return res; } 88.合并两个有序数组 根据有序和空位这两个特点，我们从nums1末尾开始比较插入 public void merge(int[] nums1, int m, int[] nums2, int n) { int n1 = m -1; int n2 = n -1; while (n2 >= 0) { if (n1 >= 0 && nums1[n1] >= nums2[n2]) { nums1[n1+n2+1] = nums1[n1]; n1--; }else { nums1[n1+n2+1] = nums2[n2]; n2--; } } } 103.二叉树的锯齿形层次遍历 这道题我也是按自己的方法去写的，也是有些麻烦，用了队列和集合倒来倒去 public List<List<Integer>> zigzagLevelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<Object[]> queue = new ArrayDeque<>(); Object[] arr = new Object[2]; arr[0] = root; arr[1] = 1; queue.offer(arr); int cur = 1; List<Integer> list = new ArrayList<>(); List<Object[]> tempList = new ArrayList<>(); while (queue.size() != 0) { Object[] temp = queue.poll(); TreeNode tn = (TreeNode)temp[0]; Integer floor = (Integer)temp[1]; if (tn != null) { if (floor % 2 == 0) { if (tn.right != null) { tempList.add(new Object[]{tn.right, floor + 1}); } if (tn.left != null) { tempList.add(new Object[]{tn.left, floor + 1}); } }else { if (tn.left != null) { tempList.add(new Object[]{tn.left, floor + 1}); } if (tn.right != null) { tempList.add(new Object[]{tn.right, floor + 1}); } } if (cur == floor) { list.add(tn.val); }else { res.add(list); list = new ArrayList<>(); list.add(tn.val); cur = floor; } } if (queue.size() == 0) { while (tempList.size() > 0) { queue.offer(tempList.get(tempList.size() - 1)); tempList.remove(tempList.size() - 1); } } } res.add(list); return res; } 236.二叉树的最近公共祖先（LCA） 思路是递归，但是难点在于节点的判断： class Solution { private TreeNode ans; public Solution() { this.ans = null; } private boolean dfs(TreeNode root, TreeNode p, TreeNode q) { if (root == null) return false; boolean lson = dfs(root.left, p, q); boolean rson = dfs(root.right, p, q); if ((lson && rson) || ((root.val == p.val || root.val == q.val) && (lson || rson))) { ans = root; } return lson || rson || (root.val == p.val || root.val == q.val); } public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { this.dfs(root, p, q); return this.ans; } } 10.有效的括号 正常的思路是用栈来做的，但是可以取巧，把括号替换为空字符串来判断： public boolean isValid(String s) { boolean res = false; while (s.contains("()") || s.contains("[]") || s.contains("{}")) { s = s.replace("()", ""); s = s.replace("[]", ""); s = s.replace("{}", ""); } if (s.length() == 0) { res = true; } return res; } 415.字符串相加 模拟加法计算： public String addStrings(String num1, String num2) { if (num2.length() > num1.length()) { String temp = num1; num1 = num2; num2 = temp; } int yu = 0; String s = ""; for (int i = 1; i <= num1.length(); i++) { int sum = 0; int a = Integer.valueOf(num1.charAt(num1.length() - i) + ""); if (i <= num2.length()) { int b = Integer.valueOf(num2.charAt(num2.length() - i) + ""); sum = a+b+yu; }else { sum = a+yu; } if (sum >= 10) { yu = 1; s = (sum-10) + s; }else { yu = 0; s = sum + s; } } if (yu == 1) { s = 1 + s; } return s; } 5. 最长回文子串 经典动态规划，动规思路：判断一个字符串是否回文=头尾相等+中间部分回文，dp数组代表了所有长度子串是否回文： public String longestPalindrome(String s) { if (s == null || s.length() == 0) { return ""; } int len = s.length(); String res = s.charAt(0) + ""; boolean[][] dp = new boolean[len][len]; for (int j = 0; j < len; j++) { for (int i = 0; i <= j; i++) { if (i == j) { dp[i][j] = true; }else { dp[i][j] = ((dp[i + 1][j - 1]) || (j - i < 3)) && (s.charAt(i) == s.charAt(j)); } if (dp[i][j] && j - i > res.length() - 1) { res = s.substring(i, j+1); } } } return res; }
[scode type="share"]2021年06月05日中午1点比赛结束[/scode] 第6战蓝桥杯！这应该是博主大学生涯里的最后一次比赛了，总体感觉这次国赛难度比上一次的简单吧。 [scode type="blue"]填空题[/scode] 填空题一共四道，这次做出来了三道，至少做的三道不难： 第一道是输出最大的8位二进制数的十进制————255。 第二道找纯质数，就是这个数字本身是质数，它的十进制的每一位也是质数，从1~20210605一共多少个，我暴力的结果是1903。 第三道是找完全平方数，例如2012年02月02日是2+0+1+2+2+2=9，9是平方数。那么找出2001年1月1日到2021年12月31日有多少，也是一道逻辑题，注意2月28天，闰年（4的倍数）2月29天，剩下的是30/31，最后好像是977吧我暴力的。 最后一道是日常略过，是一棵树求最小权值，赛后听是一道动态规划。（蒙错了） [scode type="blue"]程序设计题[/scode] 第一题把一行字符串全大写输出，水题。 第二题叫作123，给出一个数列112123123412345....，给出两个端点L，R（L<=R），求这个数列中[L,R]的和，灵活使用累加公式Sn = n*(n+1)/2确定出L和R分别在哪个区间，之后区分下情况再通过累加公式的加减即可求出。 第三题给一个随机数列，求特殊区间的个数，这个特殊区间中的所有数字的乘积等于所有数字之后，一开始我以为是双指针，但是发现不对，有感觉像动规，想了一会干脆直接暴力了，拿一点分也行。 第四题是巧克力，一道贪心题，把巧克力价格从小到大排列之后，先从小的吃，注意过期时间，最后求出最低价格。 第五道是括号题目，给一行字符串是一个括号序列，之后给出n个操作，操作分两种，第一种将区间[L,R]内的括号反转，第二种给出左端点L，找出最大的右端点R使得[L,R]是一个合法的括号序列，我是用的暴力，能过一点是一点吧。 第六题叫作异或三角，给一个数n，找出三个数1 <= a,b,c <= n，这三个数要满足两个条件：1. (a^b^c)==0 2.a、b、c可以组成三角形，可以找出多少组。最后时间不多了就直接写了一个三层for交了，希望对一个就行了。 [scode type="blue"]总结[/scode] 总体感觉题目似乎没有去年的国赛难吧，毕竟上次国赛大题我只写了一道，而且第一道还写错了。。。 不过5月初的集训让我感觉收获颇多，很多新的知识这次也都用到了，例如现在做大题都会先留意数据的范围，该用int还是用long，使用Scanner还是BufferedReader，还有自定义比较器。 其中判断括号序列是否合法的办法还是坤坤教给我的，使用replace把"()"替换为""，如果序列合法最后这个字符串肯定会被替换成空字符串的。 之前的3周的集训确实给我这次带来了不小的提升，希望最后的这次蓝桥杯可以完美收官吧。 [scode type="green"]2021年6月8日[/scode] 下午6点多出成绩了，这次依旧是国二 ::aru:blood:: ，可见这次题目确实简单啊，去年我只写了填空题和半道大题就拿了国二。。。 人数分布是这样，国赛JAVA B组获奖人数一共1213人，一等奖62人，二等255人，三等370人，优秀奖525人。 我处在二等的第121名，算是前50%吧，总数里排在183名，在15%，就这样吧，大学里的最后一次比赛了，收官！
【ACM】第十三届ACM国际大学生程序设计竞赛感想
经过三周的算法训练，5月22日早晨我们从新乡坐高铁来到了郑州，前往位于龙子湖周围的河南农业大学，这次我们一共有六个队伍：法外狂徒、三个人的ACM、大聪明、只会心疼哥哥（我）、不写代码等于爱情、铁娘子（女队）。 观光与签到 早上9点多的郑州地铁不是那么拥挤，还有位置可坐，差不多10点左右到了河南农业大学的校门口开始进行签到，这次的队服是蓝色的，教练的衣服是粉红色的，每个参赛人员还有专门的参赛证： [album] [/album] 在校外简单签到之后就进入学校了，不得不说河农大的校门真的比河科院的高档不少，虽然新科的大门也不错，但是老大门确实比较拉跨。而且在进入校门之后有很长的一条直路，两边都是绿化的树木，看起来十分漂亮，而且学校里面交通便利，可以骑单车，学校的整体建筑风格也是偏古欧美那种的（就是有档次(๑•̀ㅁ•́ฅ)）。 [album] [/album] 校园里的街道上有专门的服务人员指路，我们很快就到了第二个签到地点，同时也是我们的比赛地点（如果说这次比赛有哪些不足，就是比赛场地没包一个室内体育馆，而是校内一个个小的实验室，拉跨了）。我们在里面换上队服，一个队站在一起拍个照片（用于最后颁奖时的屏幕展示），上午的签到工作算是结束了。 [album] [/album] 就餐与开幕式 中午在他们学校的食堂吃饭，食堂总体来说也很不错，还有露天的餐桌，我们每人发了40元的餐票，可以在指定餐厅里消费。中午饱餐一顿之后我和李老师还有光岚在室内找了一个地方休息，我同时把电脑拿出来改bug....下午两点开始举行开幕仪式，40分钟的时间暴晒在太阳下面，是真滴热啊。 [album] [/album] 热身赛 举行完开幕仪式就是模拟赛了，让每位参赛队员提前适应比赛环境。这次的比赛形式和之前我参加的ccpc一样，每次做出一道题目之后会有人员走过来给你插上一支气球，每道题都有对应的气球颜色。这次热身赛一共三道题，应该说都是热身题，但我们做的情况并不理想。 第一题就是给出一组数据，选出4个组成一个矩形，输出面积最大值，不能构成矩形输出-1。很明显是一个贪心的题，当时想也没想直接接收完全部数据后使用Arrays.sort排了个序，然后判断输出，结果超时了。行，那就不排序了，在接收的时候就比出最大的两组值，可能也是我比较紧张的问题，错误频出，第一题让我搞了一个小时，错了6次才过，直接给我心态搞炸了。 第二题是一个数论，问题说了一大堆，结果是输出一个值并对17取模，仔细一想那我可以从0试到16全部输出一遍，最坏情况是错了16遍，我便开始试，最后错了7次算是把答案试出来了。 最终我们算是A了两题。 主要还有一部分压力来自于前后两桌，半个小时后桌已经A完三道题走人了，前面那组没过多久也A完走人了（热身赛是两个小时），看着前后两桌都插满了三个气球，被夹在中间的我们着实尴尬，所以心态上有些崩。 整顿与休息 热身赛结束之后又在学校吃了顿饭就回宾馆休息了，晚上把准备好的ACM宝典打印了一份留到第二天用。晚上我们在宾馆也没怎么学习，我倒是把带的笔记本拿出来打了会游戏，要不然这个死沉死沉的玩意就白带了。 第二天早晨早早起床把房退了之后便去学校了，9点开始比赛，我们仨也只是随便吃了点煎包填填肚子。 正式赛 8点半坐在教室里，看了一下周围的墙壁上一共有13只气球，便知晓了这次比赛有13道题目。 9点钟随着哨响，比赛正式开始，我们三个人开始翻阅题册，很惊讶也很高兴的是这次的题目是全中文，不会因为英文而看不懂题目了。随着少康迅速说出某一道题特别简单之后我们开始集中看这道题。由于昨天的热身赛吃了闭门羹，我们今天的对策是三个人必须一起解题，简单题一定不能马虎，争取一遍过没有罚时。 这道题是讲给出一个坐标系（输入为几行字符串），由'*'组成的行或列代表坐标轴，'#'是目标点，求'#'相对于坐标原点(0,0)的位置，基本上可以确定为一道签到题。我们三个人不慌不忙，为了不出错花了20分钟敲出来这道题，又检查了5分钟，最后一遍过。 之后根据排行开始看做的最多的题是A，这也是一个签到题，接收完输入数据后根据题中给的公式做一些判断即可得出结果，但是我们不慌，也还是一点一点认真的敲出了这道题，最后很幸运也是一遍过，我们队的名次位于第100左右，整队的信心大涨。 接着光岚和少康开始一起看“七便士”题目，我根据排行选出另一个做出的题目最多的是最后一题“输入输出”，第一次读题我感觉这道题还是挺麻烦的，有染色端点，染色区间，最后让求最小花费，仅仅看题目给的条件和思路会感觉这道题很麻烦，但是仔细履一遍样例会发现只需把输入数据相减最后相加即可，当时我们三人还又讨论应该不会这么简单吧，但是看看过这道题的人都是一遍过，题目名字叫作“输入输出”，而且题目给的输入量确实比较大，所以当时就赌了一把，直接按一开始的简单思路写，大不了错了就错了，反正没有头绪。我拿着ACM宝典把快速输入敲上，最后写完全部思路把代码一交，过了！原来这道题就是忽悠人的，题目里给的好多条件就没用。（赛后的题解人也说这道题才是准签到题）此时我们队伍的名次来到了80左右，没有罚时。 之后光岚和少康也一起把“七便士”题目做了出来，也是一遍过，此时我们已经做出4题，由于4道都是一遍过，没有罚时，我们的名次来到了第60名！当时别提我们有多高兴了，只能说认真一点绝对没错。而且用了两个小时，还有三个小时的时间，我们认为我们还可以再冲一道题目，铜也该是没问题了，就要看银了！ 从第五题开始就来到了瓶颈期，当时的时间点做出第五题都是前几，看了一下题目是第J题——“甜甜圈” 闭幕式与颁奖典礼 每队选一位成员去参加了闭幕式 [album] [/album] 滚榜： [vplayer url="https:\/\/file.makeyourchoice.cn\/2021\/05\/30\/acm01.mp4" /] 感想 抖音： [vplayer url="https:\/\/file.makeyourchoice.cn\/2021\/05\/30\/acm02.mp4" /] （未完待续....）