2020-05-07 20:32 已编辑安全工程师

关注

趋势科技5,7笔试

第一题：约瑟夫环变种，K个人，每次淘汰从d开始d =（1，2，3，4,5...k）。想了下最优解无果，直接一把梭哈，下面是代码

package qushi;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class p1 {
    public static int findIndex(List<Integer> result,int v){
        int index = 0;
        for(Integer tmp : result){
            if(tmp == v){
                return index;
            }else{
                index++;
            }
        }
        return -1;
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int start = 0;
        int dk = 1;
        int len = k;
        List<Integer> list = new LinkedList<>();
        for(int i = 1 ;i <= k; i++){
            list.add(i);
        }
        for(int i = 1 ;i <= k-1 ;i++){
            int dz = (start+dk)%len;
//            System.out.println("dz为"+dz);
//            System.out.println("删除元素为"+list.get(dz));
//            findIndex(list,list.get(dz+1));
            int value = list.get((dz+1)%len);
            list.remove(dz);
            dk++;
            len--;
            start = findIndex(list,value);
        }
//        System.out.println("list长度"+list.size());
        System.out.println(list.get(0));

    }
}

第二题，求字符串中最长的回文串，这题一把梭，先扩散法求出所有回文串，求最大长度，然后输出等于最大长度的回文串，附代码

package qushi;

import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;

public class p2 {
    static List<String> result = new LinkedList<>();
    public static void solu(int index, int right,char res []){
        int i = index-1;
        int j = right+1;
        String s = "";
        if(right ==  index){
            s+=res[index];
        }else{
            if(res[index] == res[right]){
                s+=res[index];
                s+=res[index];
            }
        }
        while ( i >= 0 && j < res.length&&res[i] == res[j] ){
            s = res[i]+s;
            s = s +res[j];
            i--;
            j++;
        }
        if(s.length() > 1)result.add(s);
    }
    public static void Solutionh(char res []){
        for(int i = 0;i < res.length-1; i++){
            solu(i,i,res);
            solu(i,i+1,res);
        }
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String h = in.nextLine();
        Solutionh(h.toCharArray());
        int maxlen = -1;
        if(result.isEmpty()){
            System.out.println("null");
            return;
        }
        for(String tmp : result){
           if(tmp.length() > maxlen){
               maxlen = tmp.length();
           }
        }
        for(String tmp:result){
            if(tmp.length() == maxlen){
                System.out.println(tmp);
            }
        }

    }
}

求大佬们的更优解。

#趋势科技##笔试题目#

全部评论

推荐最新楼层

开玩笑我超勇的啦

Java

我第一题直接暴力的，第二题用中心扩张

送花回复

发布于 2020-05-07 20:33

我心踏雪了无痕

Java

第一道题用链表 import java.util.Scanner; public class 环状链表 { static class Node { int val; public Node(int val) { this.val = val; } Node next; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); System.out.println(getN(n)); } public static int getN(int n) { if (n < 2) { return n; } Node head = new Node(1); Node headtmp = head; for (int i = 2; i <= n ; i++) { head.next = new Node(i); head = head.next; } head.next = headtmp; head = headtmp; for (int i = 0; i < n - 1; i++) { for (int j = 0; j < i; j++) { head = head.next; } head.next = head.next.next; head = head.next; } return head.val; } }

送花回复

发布于 2020-05-07 20:33

网易互娱

校招火热招聘中

官网直投

我心踏雪了无痕

Java

第二道题马拉车 package 数组; import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class manacher算法 { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); List<String> strings = maxLength(str); if (strings.size() == 0 || strings.get(0).length() == 1) { System.out.println("null"); } else { for(String s : strings) { System.out.println(s); } } } public static char[] getManacherString(String str) { char[] arr = str.toCharArray(); char[] newArr = new char[arr.length * 2 + 1]; int index = 0; for (int i = 0; i < newArr.length; i++) { newArr[i] = (i & 1) == 1 ? arr[index++] : '#'; } return newArr; }

送花回复

发布于 2020-05-07 20:34

我心踏雪了无痕

Java

public static List<String> maxLength(String str) { if (str == null || str.length() == 0) { return new ArrayList<>(); } char[] arr = getManacherString(str); int[] pArr = new int[arr.length]; int center = -1; int right = -1; int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { pArr[i] = right > i ? Math.min(pArr[2 * center - i], right - i) : 1; while (i + pArr[i] < arr.length && i - pArr[i] > -1) { if (arr[i + pArr[i]] == arr[i - pArr[i]]) { pArr[i]++; }else { break; } } if (i + pArr[i] > right) { right = i + pArr[i]; center = i; } max = Math.max(max,pArr[i]); }

送花回复

发布于 2020-05-07 20:34

我心踏雪了无痕

Java

List<String> res = new ArrayList<>(); for (int i = 0; i < pArr.length; i++) { if (pArr[i] == max) { StringBuilder sb = new StringBuilder(); for (int j = i - pArr[i] + 1 ; j < i + pArr[i]; j++) { if (arr[j] != '#') { sb.append(arr[j]); } } res.add(sb.toString()); } } return res; } }

送花回复

发布于 2020-05-07 20:34

少年又年少

Java

这是第一题最简单的递归解法，约瑟夫环变种 public static void main(String[] args) { Scanner in = new Scanner(System.in); int n = in.nextInt(); k = 1; int res = circle(n, k) + 1; System.out.println(res); } private static int circle(int n, int m) { if(n == 0) return -1; if(n == 1) return 0; int res = (circle(n-1, m+1) + m + 1) % n; return res; }

送花回复

发布于 2020-05-07 20:39

青柠年少201906032022868

华为_中央硬件工程院_软件开发工程师

楼上个各位老哥，收到面试通知了，告诉一声，全AC了看看能不能收到面试

送花回复

发布于 2020-05-07 21:02

小试牛刀闯天下

Java

楼上个各位老哥，收到面试通知了，告诉一声，全AC了看看能不能收到面试！

送花回复

发布于 2020-05-07 21:09

七年金陵梦

算法工程师

***就搞不懂，考的客观题都是什么玩意儿

送花回复

发布于 2020-05-07 22:01

失落的突尼斯海怪拿到了ssp

Java

第二题只过了80%是不是没希望了,我到现在也不知道问题出在哪？哪位大佬指点指点 public class Main2 { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.next(); if(str == null || str.length() == 1 || str.length() == 0){ System.out.println("null"); return; } }

送花回复

发布于 2020-05-07 22:40

中超第一大背头顾超

C++

我第一题100 第二题40 收到面试通知了 ac这么点，选择填空好多不会，这也能收到面试...

送花回复

发布于 2020-05-08 17:37

噢喔哦

字节跳动_后端开发

我今天收到面试通知 过了一个小时又说系统出问题还在阅卷 服了

送花回复

发布于 2020-05-08 21:37

牛客955234005号

信息技术岗

大家都是什么岗位的，有没有投AI工程师的

送花回复

发布于 2020-05-09 18:20

牛客很忙·生

Java

private static int yue(int k, int num) { //命中就置为0 int[] peoples = new int[k]; Arrays.fill(peoples, 1); int count = 1; int leave = k; int idx = 1; int flag = 1; while (leave > 1) { if (count == num && peoples[idx - 1] == 1) { //命中 peoples[idx - 1] = 0; leave--; count = 1; } else { if (peoples[idx - 1] == 1) { count++; flag = idx; } } if (idx == k) idx = 1; else idx++; } return flag; }

送花回复

发布于 2022-02-26 22:23