皆非的万事屋 - 力扣
type: channel
link: http://makeyourchoice.cn/tag/%E5%8A%9B%E6%89%A3/
items: 【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解
items: 【leetcode】SQL编程题题解
items: 【leetcode】shell编程题题解
items: 【leetcode】多线程编程题题解
items: 【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解
items: 【CodeTop x LeetCode】Page 3 ： 41-60面试高频算法题题解
items: 【CodeTop x LeetCode】Page 2 ： 21-40面试高频算法题题解
items: 【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解

【CodeTop x LeetCode】Page 5 ： 81-100面试高频算法题题解
type: item
date: 2021-11-20T13:37:00+00:00
description: 更多答案也可以关注我的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]…

【leetcode】SQL编程题题解
type: item
date: 2021-11-18T02:02:00+00:00
description: 本文将记录力扣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)

【leetcode】shell编程题题解
type: item
date: 2021-11-18T01:50:00+00:00
description: 本文将记录力扣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

【leetcode】多线程编程题题解
type: item
date: 2021-11-15T07:53:00+00:00
description: 本文将记录力扣多线程下的题目： 每道题基本都有很多种解法，基本都可以使用变量、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(Runnabl…

【CodeTop x LeetCode】Page 4 ： 61-80面试高频算法题题解
type: item
date: 2021-11-10T12:59:00+00:00
description: 更多答案也可以关注我的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.回文链表 时间…

【CodeTop x LeetCode】Page 3 ： 41-60面试高频算法题题解
type: item
date: 2021-11-03T07:50:00+00:00
description: 更多答案也可以关注我的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) { …

【CodeTop x LeetCode】Page 2 ： 21-40面试高频算法题题解
type: item
date: 2021-10-29T13:01:00+00:00
description: 更多答案也可以关注我的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); } } …

【CodeTop x LeetCode】Page 1 ： 1-20面试高频算法题题解
type: item
date: 2021-10-29T12:56:00+00:00
description: 之后博主会出一个系列专门记录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 moveT…