实际上就是一个最长上升子序列的问题：设dp[i]为数组arr从0到i的最长上升子序列的长度，那么dp[i] = max(dp[j]+1,dp[i]);其中，j是从i开始向前寻找的每个满足arr[j]<arr[i]的元素。 public class Main{ public static void main(String[]args){ Scanner sc = new Scanner(System.in); while(sc.hasNextInt()){ int n = sc.nextInt(); i...

思路：多定义几个变量记录即可。 public class Main{ public static void main(String [] args){ Scanner sc = new Scanner(System.in); double num1 = 0; int count1 = 0; int count2 = 0; while(sc.hasNextInt()){ int temp = sc.nextInt(); if(temp>=0){ ...

分两步：1是找到断链的地方（开始反转的第一个节点），2是反转链表。 public class Solution { public ListNode reverseBetween (ListNode head, int m, int n) { ListNode newh = new ListNode(0); newh.next = head; ListNode p = head; ListNode pre = newh; for(int i = 1;i<m;++i){ pre = p; ...

思路：Map记录字符串出现的次数，然后进行排序，最后截取前K个数据即可。 public class Solution { public String[][] topKstrings (String[] strings, int k) { Map<String,Integer> map = new HashMap<>(); for(String s:strings){ if(map.containsKey(s))map.put(s,map.get(s)+1); else map.put(s,1...

简单思路：采用递归，每次把匹配到的前缀给去掉，然后进入下一层次的递归。直到把s变成空串，说明能够组成该单词。否则不能组成该单词。 //该版本仅能通过牛客的测试案例，但仍需完善，比如当测试用例是 //"nowcoder",["no","now","coder"]时，则会返回错误的结果，原因是没有回溯。 import java.util.*; public class Solution { public boolean wordDiv (String s, String[] dic) { if(s.equals(""))return true; for(in...

4行代码搞定：采用滑动窗口方法，每次截取k位字符，转换成数字，再比较最大的数字即可。 public class Solution { public int maxValue (String s, int k) { int res = 0; for(int i = 0;i <= s.length() - k; ++i){ res = Math.max(res,Integer.parseInt(s.substring(i,i+k))); } return res; } }

这个题可以参考最长公共子序列。最长回文子序列可以通过构造两个相反的字符串求最长子序列的方式求出。采用动态规划，时间复杂度O(n^2)空间复杂度O（n^2)。进一步的，还能求出这个最长的子序列具体的结果。 public class Solution { public int longestPalindromeSubSeq (String s) { // write code here int dp[][] = new int[s.length()+1][s.length()+1]; String s1 = new StringBuilder...

思路:题目要求出现的字母均为小写，那么可以创建一个PreTriee的类，其属性成员包括node：单词的下一个字母,isWorld：表示该前缀是否为单词,worldCount：表示该单词插入的数量，prefixCount：表示该前缀插入了多少次。要进行对字段树的插入删除以及查询操作，大体上代码和插入类似：使用循环进行判断即可。值得注意的是，每次插入操作需要把前缀数量+1，因为该题目可可以执行重复插入。 public class Solution { class PreTriee{ PreTriee [] node = new PreTriee[26]; b...

这个题解答方式多种多样。本题解的一种思路，把IP按分隔符分割成字符串数组，然后对数组的每个元素挨个验证是否符合规则就行。时间复杂度O（N）。 public class Solution { public String solve (String IP) { if(IP.endsWith(".")||IP.endsWith(":"))return "Neither"; boolean flag = IP.contains(".");//如果flag为真，则是IPV4的规则，否则就是IPV6的规则。 String[] ips = flag?I...

空间O（1）时间O（N）解法:只需用一个count记录上一个字符出现的次数即可，如果count=1则直接向结果追加字母，不加数字，如果count>1才追加出现的次数。 public class Solution { public String compressString (String param) { // write code here StringBuilder res = new StringBuilder(); if(param.length()<=1)return param; int count...

思路：把链表分成两个部分，左边是比目标x小的，断链即可，最后再连接起来。 public class Solution { public ListNode partition (ListNode head, int x) { ListNode left = new ListNode(0);//左链表的尾节点 ListNode leftHead = left;//左链表的头节点 ListNode rightHead = new ListNode(0); rightHead.next = head; List...

建议背住，匹配的过程和求next的过程很相似。 public class Solution { public int kmp (String S, String T) { // write code here int count = 0; int[] next = new int[S.length()]; getNext(S, next); for (int i = 0, j = 0; i < T.length(); ++i) { if (j > 0 &&...

有实习的吗？后端实习薪资一般什么价位？

二分删除头部法：每次删除两个数组头部中长度为k/2，（k为中位数索引),直到k=1时，返回较小元素即可。 public class Solution { /** * find median in two sorted array * @param arr1 int整型一维数组 the array1 * @param arr2 int整型一维数组 the array2 * @return int整型 */ public int findMedianinTwoSortedAray (int[] arr1, int[] arr2)...