括号区间匹配 给定一个由 ‘[’ ，‘]’，‘(’，‘)’ 组成的字符串，请问最少插入多少个括号就能使这个字符串的所有括号左右配对。 例如当前串是 “([[])”，那么插入一个’]‘即可满足。 数据范围：字符串长度满足 1≤n≤100 输入描述： 仅一行，输入一个字符串，字符串仅由 ‘[’ ，’]’ ，‘(’ ，‘)’ 组成 输出描述： 输出最少插入多少个括号 示例： 输入：([[]) 输出：1 输入：([])[] 输出：0 这道题是一个区间dp问题，我看了各种c++代码，最后理解还是靠自己画方格图一点一点通过网上的代码倒推理解的。先上正确代码：...

利用01背包问题的变形： 1.首先求和后确定是否奇数，是则返回false； 2.我们要求这道题可以变形成求一个背包能否被装满，而背包容量为bag=sum/2； 3.如果背包能被装满则剩下的值之和也是sum/2，所以要求背包能否被装满利用01背包问题，建dp[bag+1]， 我们可以想象，变形成求最少或者最多需要多少个物品让背包装满。这里是最多多少物品能让背包装满。所以dp初值为Integer.MIN_VALUE; 我们利用背包问题模型，解出来的dp[bag]如果等于Integer.MIN_VALUE;说明没有办法让背包装满。返回false，反之返回true。 im...

借鉴左神的思路： 采用方法一： 根据四平方和定理： 1.一个数最多可以被4个平方和累加得到。 2.任何数消掉4的因子结论不变。 3.如果一个数模8等于7，则这个数一定被4个平方数累加得到 import java.util.*; public class Main{     //四平方和定理     //任何数消掉4的因子结论不变     public static int p...

贪心算法： 每次用cur表示当前走的最远距离，遍历数组，用next表示最大位置，当随着i走的时候next也会跟着要么不变要么变大。如果变大了在cur<i的时候又跑到了最远的位置。直到跑到最终位置： public class Main{ public static int process2(int[]arr,int n){ int step=0; int cur=0; int next=0; for(int i=0;i<n;i++){ if(cur<i){ ...

跳跃游戏二： 有没有人感觉牛客网的题解都是只上代码，不给思路的。只上代码总觉得是在直接抄答案。 这道题我先找了leetcode发现没有这道题。于是我想到了leetcode的跳跃游戏一的视频题解。上面说到了方法2用倒推的方式。我们在这道题上用倒推变形。 首先最后一个数组元素一定是包含在最大分数中的。然后就考虑前面的每个是否能到达最后一个位置。如果能的话将pos向前推，只考虑当前跳跃位置能不能跳到pos。最初pos在n-1位置，即最终位置。随着往前遍历，pos也跟着往前。 比如1,2,3,0,0,1,4数组中：最终位置为数组下标6（arr[6]）位置。考虑下标5位置能不能到，5可以到6，所以pos...

在一的基础上改进，做两个dp分别是代表arr[0 ~ n-2],arr[1 ~ (n-1)]. import java.util.*; public class Main{ public static int process(int[] arr,int n){ int[]dp1=new int[n]; int[]dp2=new int[n]; dp1[1]=arr[0]; dp2[1]=arr[1]; int res=Math.max(arr[0],arr[1]); for(int i=2;i<n;i++){ dp1[i]=...

类似打家劫舍一： 就是dp[i]表示以i-1结尾的数组的最大值： import java.util.*; public class Main{ public static int process(int[] arr,int n){ int[]dp=new int[n+1]; dp[1]=arr[0]; int res=dp[1]; for(int i=2;i<=n;i++){ dp[i]=Math.max(dp[i-2]+arr[i-1],dp[i-1]); res=Math.max(res,dp[i]); } ...

public class Main{ public static boolean process(String str,String pattern){ if (str == null || pattern == null) { return false; } char[] s = str.toCharArray(); char[] p = pattern.toCharArray(); int N = s.length; int M = p.length; ...

一面 1.自我介绍 2.问项目背景和具体做的啥 3.写代码吧，自己实现一个LinkedList，传int值，实现增删，保证增删都保证链表有序，删除会将链表中相同的数字都删除。如：增3,1,5得到1,3,5   如删除1，3，5，5，7中的5会得到1，3,7.要求15分钟，我也不知道写了多久，反正写完了，然后让检查一遍，将不要的变量清理了，最后居然没让跑，我说要不跑一遍吧，他说不用跑了。 接着就问：用到了哪些java工具，我说了javacv的一些东西，然后他补充：其实mybatisplus也是。 4.用来干嘛？做视频处理。 5.并发编程知道多少：doge lea的JUC，里面有线程池，参数干嘛的...

一面经： 1类加载过程：有一个extclassloader和appclassloader，前者是系统的一些类加载，后者是用户定义的类加载。。。不太整的明白乱说了一些。 2。jvm内存模型，扯到GC上，后来感觉自己偏题了，索性说不太会。 3.单例如何实现线程安全：加synchronized或者Lock锁，你写一下，S Y N C H。。。不是不是，算了。下一个。 4.hashcode与equals的区别：这个说了些区别，hashMap中hashcode不一样能找到值吗，能，因为hashcode经过hash函数找到对应的地址存放值巴拉巴拉。。其实有点虚。因为还没细看到那里。说了点hashMa...

动态规划： 利用题题目DP5（连续自数字最大和）的思路，首先将矩阵分为第一列，第二列... 用字母表示：m0,m1,m2...m(n-1)，得到n个数组，然后： 先求第一个数组的最大子数组值a1。 求第一个数组+第二个数组得到的数组的最大子数组值a2。 m0+m1+m2的最大子数组值a3 m0+...+m(n-1)的最大子数组值an 在这些个a1...an中找到最大值为有包含第一列子数组的情况下的最大子矩阵。 第二次从第二列子数组作为起始数组，再循环上述步骤。 得到的是最大值包含有第二列子数组的情况下的最大子矩阵。 以此类推到最后一个子数组。 public class Main{ ...

方法：递归回溯：这里得到的结果通过排序再去重 public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串一维数组 */ public String[] generatePermutation (String s) { // write code here ArrayList<String> res=new ...

1