2021.9.6 笔试     80道选择题（40min）：数据库知识点+数据库代码+计算机网络+数据结构+Java/C  10道行测题（10min）：数学计算+逻辑运算  3道编程题（90min）：很简单的三道阅读理解编程题         2021.9.15 一面  1.自我介绍： 2.final finally finalize区别 3.讲一下知道的数据结构： 4.BFS用的是什么数据结构？递归用的是什么数据结构 5.怎么判断一个对象是否可以被回收？ 6.Minor GC和Full GC的区别 7.讲一下Java中的内存泄漏 8.疯狂怼项目：  2021.9.18 体检   2021.9...

题目1：叠积木    给出一个列表如[[6,7,],[5,4],[3,2]],表示木块的长和宽，当木块的长和宽不大于另个木块的长和宽时，就可以放在上面，此外数组还可以左右翻转。当长宽都大于等于上一个积木时才可以搭到上一个积木上，此外数组还可以左右翻转。求最多能搭多少层。（与leetcode354：俄罗斯套娃相似，不过添加了翻转，增加了难度）。  输入： [[5,4], [6,3], [6,7], [6,6], [4,6]] 输出： 4 解析：    积木数据处理，大的做长，小的做宽  所有积木从大到小排序  动态规划求最大：可以定义一个 dp 数组，dp[i] 表示如果积木为 i 时，最大积木...

题目1：最大岛屿体积    输入： 5 5 0 1 1 0 0 0 1 1 0 0 0 0 0 0 0 0 0 1 2 3 0 0 1 3 9 输出： 19 注意先输入宽度，再输入高度    import java.util.*; public class code1 {     static ArrayList<Integer> list=new ArrayList<Integer>();     public static void main(String[] args){         Scanner sc=new Scanner(System.in);    ...

解法1：暴力求解 public static ArrayList<Integer> maxInWindows(int[] nums,int size){ ArrayList<Integer> res=new ArrayList<>(); int len=nums.length; if(size==0 || size>len){ return res; } for(int i=0;i<=len-size;i++){ int max=nums[i]; for(int j=i+1;j<size+i;j++){ if(nums[j]>max)...

方法1：递归的方法： 如果表1当前值小于表2当前值，表1当前值成为新链表的表头，否则返回表2的当前值作为新链表的表头。比较当前链表的值，较小的取其子链表继续递归。当有一个链表取到子链表为空时，说明已经比较完成，可以直接返回非空的链表，返回值赋给了l1.next或者l2.next，但无论如何，最终还是沿着递归链不断返回，最终返回的是新有序链表的表头。 public ListNode MergeTwoList1(ListNode list1,ListNode list2){ if(list1==null){ return list2; } if(list2==null){ return list1...

解法1：归并排序 思路：先利用快慢指针找出链表的中点，然后分为两个链表，一直分，知道无法分为止，然后自底而上排序归并 public ListNode sortInList (ListNode head) { // write code here return mergerSort(head); } public ListNode mergerSort(ListNode head){ if(head == null || head.next == null){ return head; } ListNode slow = head; ListNode fast = head; ListNode ...

解法1：双指针法 pre先走m-1步到达位置m的前驱节点，pre不动，然后令cur等于pre->next也就是位置m的起始节点（不变），将[m+1,n]这段链表由前至后的插入到位置m的前面，也就是pre的后面即：我们每次循环就是将cur的next节点插入到pre的后面，这样插了n-m次后，就完成反转了  public ListNode reverseBetween (ListNode head, int m, int n) { // write code here // 设置哑节点的好处： //在m=1时，我们也有前驱节点，也可以将cur的next节点依次插入到pre的后面 ListNo...

解法1：模拟   public ListNode partition (ListNode head, int x) { // write code here ListNode small=new ListNode(0); ListNode smallHead=small; ListNode large=new ListNode(0); ListNode largeHead=large; while(head!=null){ if(head.val<x){ small.next=head; small=small.next; } else{ large.next=head; large=l...

二叉搜索树：每个节点左边节点小于右边节点，左子树的最大值一定小于根节点，小于右子树的最大值；通过中序遍历，严格递增 完全二叉树：层序遍历，除了最后的一层，每层都是满的 import java.util.*; /* * public class TreeNode { * int val = 0; * TreeNode left = null; * TreeNode right = null; * } */ public class Solution { /* * @param root TreeNode类 the root * @return bool布尔型一维数组 */ public bool...

解法1：动态规划 设置一个状态转移数组dp，dp[i]表示数组中前i个元素所能偷的最大金额是多少状态转移表达式：(1)对于当前的元素arr[i],如果偷，那么dp[i] = dp[i-2] + arr[i](2)如果不偷，那么dp[i] = dp[i-1]  public long subsequence (int n, int[] array) { // write code here long[] dp=new long[n+1];// dp[i] 表示当前 i 个最大和 dp[0]=0; dp[1]=array[0]; for(int i=2;i<=n;i++){ // 当前的最大...

贪心算法：每次取局部最优解 解法1：从左向右逼近终点 一个记录当前位置，一个记录最远跳跃位置，一个记录跳跃次数，遍历数组（不需要遍历到最后一位，如果遍历到最后一位，那么正好跳到最后一位的时候就会多加一次跳跃次数），每当当前位置和索引i相等时（即当前位置最后一种跳法跳完时），将最远跳跃位置赋值给当前位置，跳跃次数加1；如果在索引中没找到当前位置，就说明已经跳出去了1.然后从第一格到最后面n-1依次进行遍历,每经过之处都要求出最大可达到的位置maxStep;2.如果index位置大于等于长度n,则表示已经跳出了;3.如果index位置等于i,表示遍历到了最后一步跳法跳完时候,此时index需要更改...

res=-1，首先找到中间的数  nums[mid]==target说明右边都是>=target的数、更新res,right=mid-1 nums[mid]>target说明右边都是>target的数,right=mid-1 nums[mid]<target说明左边都是<target的数,left=mid+1;public int search (int[] nums, int target) { // write code here if(nums.length==0){ return -1; } int res=-1; int left=0,right=num...

解法1：暴力递归 对于给定的单词 A 和 B，从左向右逐个匹配：①对于 A 中当前遍历到的字符 A[i]，如果和 B[j] 相同，则不需要任何操作，继续向右遍历 i+1, j+1②如果 A[i] != B[j]，则可以删除 A[i]，或者替换 A[i]，或者插入和 B[j] 相同的字符，因此存在三种选项所以每次遍历匹配时，都存在 4 种可能的逻辑分支，设函数为dfs  A[i] == B[j]dfs(str1,i+1,str2,j+1,ic,dc,rc)，i+1和j+1继续比较 A[i] != B[j]   dfs(str1,i,str2,j+1,ic,dc,rc)+ic 说明str1中在i前...

思路1：动态规划 在给定的模式 p 中，只会有三种类型的字符出现：  小写字母 a-z，可以匹配对应的一个小写字母； 问号 ?，可以匹配任意一个小写字母； 星号 *∗，可以匹配任意字符串，可以为空，也就是匹配零或任意多个小写字母其中「小写字母」和「问号」的匹配是确定的，而「星号」的匹配是不确定的，因此我们需要枚举所有的匹配情况。为了减少重复枚举，我们可以使用动态规划来解决本题 public class Solution { public boolean isMatch(String s, String p) { int slen=s.length(); int plen=p.length();...