近两周笔试记录

8.20 19:00——20:00 有赞
8.20 19:30——22:00 顺丰
8.21 19:00——20:45 滴滴
8.22 19:00——21:00 360
8.23 10:00——12:00 字节跳动(不准用ide，没记录，况且根本没做出来...)
8.25 19:30——21:00 完美世界
8.27 19:00——21:00 京东
8.27 20:30——22:30 吉比特

1. 有赞

回文链表

import java.util.*;
public class ListNode {
 int val;
 ListNode next = null;

 ListNode(int val) {
     this.val = val;
 }
}
public class Palindrome {
 public boolean isPalindrome(ListNode pHead) {
     // write code here

     //先快慢指针找到链表中点，分割为左右两条链表，翻转其中一条，然后while循环判断节点值

     //暂存头节点
     ListNode node = new ListNode(0);
     node.next = pHead;

     ListNode fast = node;
     ListNode slow = node;

     while(fast != null && fast.next != null){
         fast = fast.next.next;
         slow = slow.next;
     }

     //跳出循环之后，slow.next为后半部分起点，fast指向它
     fast = slow.next;

     //断开后半
     slow.next = null;
     //slow指向phead
     slow = pHead;

     //翻转后半
     ListNode pre = null;
     ListNode next = null;
     while(fast != null){
         next = fast.next;
         fast.next = pre;
         pre = fast;
         fast = next;
     }

     //while比较，翻转之后pre是头节点
     while(pre != null){
         if(slow.val != pre.val){
             return false;
         }
         pre = pre.next;
         slow = slow.next;
     }
     return true;
 }
}

能被5整除的最大和——Lc1262。有点难...，先挂着吧...

class Solution {
 public int maxSumDivThree(int[] nums) {
     /*
     能被3整除的最大和
     8.28
     */

if(nums == null || nums.length == 0){
         return 0;
     }
     int[] dp = new int[]{0,0,0};
     for(int num : nums){
         int[] temp = new int[3];
         for(int i = 0; i < 3; i++){
             temp[(num + dp[i]) % 3] = Math.max(Math.max(dp[i] + num, temp[(num + dp[i]) % 3]), dp[(num + dp[i]) % 3]);
         }
         for(int i = 0; i < 3; i++){
             dp[i] = Math.max(temp[i],dp[i]);
         }
     }
     return dp[0];
 }
}

2. 顺丰，貌似是0.18 + 0.27，反正裂开了....两题都是贪心。做太差 + 大佬代码看不太懂 = 不想复盘

3. 滴滴

设a，b，c是0到9之间的整数（其中a，b，c互不相同），
其中abc和acc是两个不同的三位数，现给定一正整数n，
问有多少对abc和acc能满足abc+acc=n（a≠0）？

样例输入
1068
样例输出
1
524 544

代码：DFS只过了55%，正在找有没有同思路的大佬代码

import java.util.ArrayList;
import java.util.Scanner;
public class Main{

 static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
 static ArrayList<Integer> list = new ArrayList<>();

 public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);

     int n = sc.nextInt();

     //n小于201都不行
     if(n < 201){
         System.out.println(0);
     }

     //类似于dfs中心扩散，从[n/2,n/2]开始，dfs(middle-10,middle+10)和dfs(middle+10,middle-1)
     int middle = n/2;

     dfs(middle,middle,n);

     if(result.size() == 0){
         System.out.println(0);
         return;
     }

     System.out.println(result.size());

     for(int i=0;i<result.size();i++){
         System.out.print(result.get(i).get(0) + " " + result.get(i).get(1));
         System.out.println();
     }
 }

 private static void dfs(int left, int right,int n) {

     //终止递归
     if(String.valueOf(left).length() < 3 || String.valueOf(right).length() < 3) {
         return;
     }

     //递归出口。如果left + right == n 并且 left != right，第一个字符相同，最后一个字符相同，其中一个数的第二和第三个字符相同，且两个数的位数相同
     // result存入list
     if(left + right == n && left != right &&
             String.valueOf(left).charAt(0) == String.valueOf(right).charAt(0) &&
             String.valueOf(left).charAt(2) == String.valueOf(right).charAt(2) &&
             (String.valueOf(left).charAt(1) == String.valueOf(left).charAt(2) || String.valueOf(right).charAt(1) == String.valueOf(right).charAt(2))){
         //list添加
         list.add(left);
         list.add(right);
         result.add(new ArrayList<>(list));
         return;
     }

     if(String.valueOf(left).length() == 3 && String.valueOf(right).length() == 3){
         //左边-10，右边+10
         dfs(left-10,right+10,n);
     }
 }
}

裂开，直接暴力三个for循环就能A...为什么我这么沙雕

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main{
 public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);

     int n = sc.nextInt();
     List<String> list = new ArrayList<>();

     //a不能为0
     for(char a = '1';a <= '9';a++){
         for(char b = '0';b <= '9';b++){
             for(char c = '0';c <= '9';c++){
                 //a不能等于b，b不能等于c，a不能等于c
                 if(a != b && b != c && a != c){
                     int abc = (a - '0') * 100 + (b - '0') * 10 + (c - '0');
                     int acc = (a - '0') * 100 + (c - '0') * 10 + (c - '0');

                     //判断abc + acc是否等于n
                     if(abc + acc == n){
                         list.add(abc + " " + acc);
                     }
                 }
             }
         }
     }

     System.out.println(list.size());
     for(int i=0;i<list.size();i++){
         System.out.println(list.get(i));
     }
 }
}

斐波那契蛇

样例输入
3
样例输出
34 21 13
1 1 8
2 3 5

代码：

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        //先计算n*n的斐波那契数列
        long[] nums = new long[n*n];
        //遍历len，计算斐波那契数列(我已经裂开了，这里我想着要倒序存，结果太紧张了没看到传入的是i...刚考完，一复盘，懵了)
        for(int i=0;i<nums.length;i++){
            nums[i] = Cal(i);
            System.out.println(nums[i]);
        }

        //螺旋构建矩阵，和螺旋打印同一思想
        int up = 0;
        int right = n-1;
        int down = n-1;
        int left = 0;
        long[][] matrix = new long[n][n];

        int index = nums.length-1;

        while(true){
            //上边界，从left到right
            for(int row=left;row<=right;row++){
                matrix[up][row] = nums[index--];
            }
            //上边界缩进一行
            up++;
            if(up > down){
                break;
            }

            //右边界，从up到down
            for(int col=up;col<=down;col++){
                matrix[col][right] = nums[index--];
            }
            //右边界缩进一列
            right--;
            if(right < left){
                break;
            }

            //下边界，从right到left
            for(int row=right;row>=left;row--){
                matrix[down][row] = nums[index--];
            }
            //下边界往上缩进一行
            down--;
            if(down < up){
                break;
            }

            //左边界，从down到up
            for(int col=down;col>=up;col--){
                matrix[col][left] = nums[index--];
            }
            left++;
            if(left > right){
                break;
            }
        }

        for(int i=0;i<matrix.length;i++){
            for(int j=0;j<matrix[0].length;j++){
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }

    private static long Cal(int len) {

        long[] temp = new long[len+2];
        temp[0] = 1;
        temp[1] = 1;

        for(int i=2;i<=len;i++){
            temp[i] = temp[i-1] + temp[i-2];
        }

        return temp[len];
    }
}

4. 360

有效名字

import java.util.Scanner;
public class Solution{
 /*
 有效名字：仅由大小写英文字母组成且长度不超过10

 输入：由大小写英文字母，数字，下划线组成的字符串。字符串长度不超过100。

 输入第一行包含一个正整数n，表示收到的问卷数量。(1<=n<=2000)
  */
 public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);

     int len = sc.nextInt();
     sc.nextLine();
     String[] str = new String[len];
     for(int i=0;i<str.length;i++){
         str[i] = sc.nextLine();
     }

     int result = 0;
     //暴力遍历字符串数组的每一个字符串
     for(int i=0;i<str.length;i++){

         //当前字符串
         String curStr = str[i];
         boolean valiable = true;
         //先判断当前字符串长度是否小于10
         if(curStr.length() > 10){
             continue;
         }

         char[] cstr = curStr.toCharArray();

         //否则遍历当前字符串，判断是否只包含大小写英文字母
         for(int j=0;j<cstr.length;j++){

             //如果当前字符不是大小写字母，break
             if(Character.isLowerCase(cstr[j]) || Character.isUpperCase(cstr[j])){
                 continue;
             }else{
                 valiable = false;
                 break;
             }
         }

         if(valiable) {
             result++;
         }
     }

     System.out.println(result);
 }
}

奇偶操作
给定一个1到N的排列P1到PN（N为偶数），初始时Pi=i（1≤i≤N），现在要对排列进行M次操作，每次操作为以下两种中一种：
①将排列的第1个数移到末尾；
②交换排列的第1个数与第2个数、第3个数与第4个数、…、第N-1个数与第N个数。
求经过这M次操作后得到的排列。

输入：
6 3
1 2 1
输出：
2 5 4 1 6 3

只过了55%

import java.util.Scanner;
public class Solution{

 public static void main(String[] args) {
     Scanner sc = new Scanner(System.in);

     //len为偶数
     int len = sc.nextInt();
     int mark = sc.nextInt();
     sc.nextLine();

     int[] nums = new int[len];
     for(int i=0;i<len;i++){
         nums[i] = i+1;
     }

     int[] marks = new int[mark];
     for(int i=0;i<marks.length;i++){
         marks[i] = sc.nextInt();
     }

     //1. 当marks[i]为1时，swap(nums,nums[0],nums[nums.length-1])
     //2. 当marks[i]为2时，swap(nums,nums[0],nums[1])，swap(nums,nums[2],nums[3])，.....
     for(int i=0;i<marks.length;i++){
         if(marks[i] == 1){
             nums = insert(nums,0);
         }else if(marks[i] == 2){
             for(int j=0;j<nums.length/2;j++){
                 nums = swap(nums,2*j,2*j+1);
             }
         }
     }

     for(int i=0;i<nums.length;i++){
         System.out.print(nums[i] + " ");
     }
 }

 private static int[] swap(int[] nums, int left, int right) {
     int temp = nums[left];
     nums[left] = nums[right];
     nums[right] = temp;
     return nums;
 }

 private static int[] insert(int[] nums, int index) {
     //将index插入到nums[nums.length]
     int[] temp = new int[nums.length];
     //temp从1开始存
     int j = 1;
     for(int i=0;i<temp.length-1;i++){
         temp[i] = nums[j++];
     }
     temp[temp.length-1] = nums[index];
     nums = temp;
     return nums;
 }
}

5. 完美世界

0-1背包，题目忘了

 private static int method(int knapsackCapacity, int[] volumes, int[] values) {

     //背包问题，0-1背包

     //限制条件未背包容量
     int bag = knapsackCapacity;

     //物品数量为道具的数量
     int num = volumes.length;

     //创建一个bag+1的背包
     int[] dp = new int[bag+1];

     //0-1背包，倒序遍历，外层为数量
     for(int i=0;i<num;i++){
         //内存为限制条件，倒序遍历
         for(int j=bag;j>=volumes[i];j--){
             dp[j] = Math.max(dp[j],dp[j-volumes[i]] + values[i]);
         }
     }

     return dp[knapsackCapacity];
 }

图的最小路径和：要自己根据矩阵判断路径是否可行，有点子难，有大佬说是迪杰克斯...不懂啊

6. 京东

2，3，5组成的第n个最小数(剑指offer丑数改题)

class Solution {
 public int nthUglyNumber(int n) {

     long a = 0;
     long b = 0;
     long c = 0;

     //用long防止溢出
     long[] dp = new long[n];

     for(int i=1;i<n;i++){
         long n2 = dp[a] * 2;
         long n3 = dp[b] * 3;
         long n5 = dp[c] * 5;
         //提取本次最小
         dp[i] = Math.min(n2,Math.min(n3,n5));

         //继续下一个
         if(dp[i] == n2){
             a++;
         }
         if(dp[i] == n3){
             b++;
         }
         if(dp[i] == n5){
             c++;
         }
     }
     return dp[n-1];
 }
}

三角形最大路径和(LC120改题，烦就烦在读入三角形矩阵....弄了好久...)

import java.util.*;
public class Main{
 public static void main(String[] args) {

     Scanner sc = new Scanner(System.in);
     int n = sc.nextInt();

     //n行，2*n-1列
     int[][] nums = new int[n][2*n-1];

     //读入三角形矩阵
     //第一行2，第二行123，第三行01234。
     for(int i=0;i<n;i++){
         //按照规律，从[n-i-1,n+i]
         for(int j=n-i-1;j<n+i;j++){
             nums[i][j] = sc.nextInt();
         }
     }

     //创建二维dp数组
     int[][] dp = new int[n][2*n-1];

     //初始化最底层
     for(int j=0;j<2*n-1;j++){
         dp[n-1][j] = nums[n-1][j];
     }

     int result = 0;

     //从底往上，倒推
     for(int i=n-2;i>=0;i--){
         for(int j=n-i-1;j<n+i;j++){
             dp[i][j] = Math.max(dp[i+1][j-1], Math.max(dp[i+1][j], dp[i+1][j+1])) + nums[i][j];
             result = dp[i][j];
         }
     }

     System.out.println(result);
 }
}

7. 吉比特：两题0.1，第二题貌似是内部循环时没有取余，裂开了。投的Java，结果填空题都是C++，服了。

总结：笔试时状态真的很重要，自己也是笔试经历少，有时遇到难题做不出来心态就容易崩，其实这么多场笔试看下来，难题基本就是动态规划、贪心或者是dfs，很多简单的题目其实都是LC原题变种，要么直接暴力就能搞定。还是得搞定动态规划、贪心啊，dfs也要不定时的复习。

近两周的笔试记录(惨痛经历)