排序 + 模拟 算法思路 比较容易想到的是先按照每个区间的起始值排序，再采用模拟法，将区间进行合并。 代码实现 import java.util.*; /** * Definition for an interval. * public class Interval { * int start; * int end; * Interval() { start = 0; end = 0; } * Interval(int s, int e) { start = s; end = e; } * } */ public class Solution ...

动态规划dp函数 + 记忆数组 算法思路先定义状态，匹配与不匹配两种。当不匹配时，有三种选择: 插入，删除，替换。dp(i, j)为str1[0...i]和str2[0..j]字符串为了匹配做出的代价。对于给定的字符串str1，str2，从右到左，即自顶向下进行匹配。会出现两种情况： 当前字符匹配时，dp(i, j)沿用dp(i-1, j-1)的代价。 当前字符不匹配时，有三种选择。 dp(i, j-1) + 插入的代价 dp(i-1, j) + 删除的代价 dp(i-1, j-1) + 替换的代价当我们每个选择在向下递归时，只有三种选择，第一个选择结束又返回，进行第二个选择时，必定...

这是一道很经典的动态规划题目。 求解步骤 确定状态与选择 状态是LCS的长度。 如果S[i] == T[j]，LCS的长度 + 1; 当不等时，必须选择一个存在于LCS中的字符，但是我们当前肯 定不知道哪个是属于LCS里的字符，所以就拿LCS的长度来比较。这里就有两个选择。 明确dp的含义，定义base casedp[i][j]指的是S[0...i-1]和T[0...j-1]中LCS的长度，因为数组的索引是从0开始的，而我们的dp数组是从1开始的，所以base case将dp[0][...]和dp[...][0]置为0。 找出状态方程从我们的选择中，可以推出状态转移方程...

前言 本人是双非二本的大三生，很幸运三月份春招第一次投了两个大厂顺利通关拿到offer。不得不说，BAT大厂的效率是真的高！面试时间都约得很紧凑，并且很快就发offer了！在3月24号这一天拿到了梦寐以求的大厂双offer，双倍的惊喜！在此再次感谢内推我的大佬们~ 也特别感谢牛客这个平台上的战友们给我提供了大量面经~ 整理了下三月份的面试经历，前来还愿。 关于本人 大一修的专业是金融学，并不是很感兴趣这个专业。大一下自学C语言参加转专业考试加面试，大二成功到转计算机专业。 大二同时补修大一课程并自学技术做项目。在暑假开始投递找实习，最后于八月去了一...

吃掉n个橘子的最少天数 直接使用动态规划 dp[i]表示吃掉i个橘子所需要的最少天数。 可以先花一天吃1个，剩余 i-1个橘子，dp[i] = dp[i-1] + 1; 可以先花一天吃i / 2个，剩余i / 2个橘子， dp[i] = dp[i/2] + 1; 可以先花一天吃 2i / 3个，剩余i / 3个橘子，dp[i] = dp[i/3] + 1; dp[1] = 1; dp[2] = 2; for(i = 3; i <= n; i++){ dp[i] = dp[i -1] + 1; if(i % 2 == 0){ dp[i] =...

小美的送花路线 https://www.nowcoder.com/questionTerminal/a9980f73060545ca923344098750af18?f=discussion 可以转换成图论，以花店为中心，骑手肯定会选择最长路径只需走一次，其他短路径走两次的方案，这样才能保证实际走的路程最短。使用并查集将有路径的两个节点相连起来，再构建最长路径。 import java.util.*; import java.io.*; public class Main{ public static void main(String[] args) throws IOExc...

许愿快点来offer！

并查集 它适合于解决连通分量的问题，就是一个工具类。难点在于如何将原问题转化为图的动态连通性问题。实现的关键点有3个： 用parent数组记录每个节点的父节点，相当于指向父节点的指针，所以parent数组内实际存储着一个森林。 用size记录每颗树的重量，目的是为了调用union后树依然保持平衡性，而不会退化成链表。 在find函数中进行路径压缩，保证任意树的高度维持在常树，使得union和connected函数的时间复杂度为O(1) 实现代码如下： class UnionFind{ public int count; public int[] parent; p...

遍历每一个节点，以每一个节点为中心点计算最长路径（左子树边长+右子树边长），更新全局变量max。 class Solution { int max = 0; public int diameterOfBinaryTree(TreeNode root) { if(root == null) return 0; maxDepth(root); return max; } public int maxDepth(TreeNode root){ if(root.left == nu...

许愿三面！！！

class Solution { public int removeDuplicates(int[] nums) { if(nums.length == 0){ return 0; } int slow = 0, fast = 0; while(fast < nums.length){ if(nums[fast] != nums[slow]){ slow++; nums[slow] = nums[fast]...

暴力解法 class Solution { public int[] shortestToChar(String s, char c) { int len = s.length(); ArrayList<Integer> index = new ArrayList<>(); int i = 0; for(i = 0; i < len; i++){ if(s.charAt(i) == c){ index.add(i); ...

有效的字母异位词 class Solution { public boolean isAnagram(String s, String t) { int slen = s.length(); int tlen = t.length(); if(slen != tlen){ return false; } //借助一个数组，下标为字符 int[] c = new int[26]; for(int i =0; i < slen; i++){ ...

贪心算法 每次寻找当前最优解去更新 import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int m = sc.nextInt(); String s = sc.next(); int max = 0; System.out.println(Math.max(solve...