建信金科秋招笔试

建信金科秋招笔试

作为建行的金融科技岗位，相对较稳定，也是不少应届生想去的地方。秋招目前做了两份笔试（10/16和11/04，私下找的）；难度一般，考察细节。

​

1016.T1

1. 题目说明

假设我们有一个字符串myster，字符串中只包含英文的大小写字母。

我们每次可都以从字符串里随机选一个字符，但是选中的字符不能再使用。

请问，选中的字符里最多能组成多少个字符串“ccbft”?(大小写都可以)

示例1

输入

"ACBTMfxcc"

输出

1

说明

可以拼成一个字符串"ccbft"

2. 解答分析

• 输入一个字符串，判断该字符串中的字符能够组成多少个"ccbft"

  仅使用数组来存储每个目标字符出现的次数

• 简单的模拟题目，注意读入c,b,f,t各自出现的次数就行。最后将次数减少操作就行。

  ​

3. 具体代码

import java.util.Scanner;

public class title1 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        String str1 = str.toLowerCase();
        int[] count = new int[4];
        for (int i = 0; i < str1.length(); i++) {
            char ch = str1.charAt(i);
            if (ch == 'c') {
                count[0]++;
            }
            if (ch == 'b') {
                count[1]++;
            }
            if (ch == 'f') {
                count[2]++;
            }
            if (ch == 't') {
                count[3]++;
            }
        }
        int res = 0;
        //满足下面条件的时候，对上述的c,b,f,t的数量依次-2，-1，-1，-1，此时是可以拼接成目标字符串的
        while (count[0] > 1 && count[1] > 0 && count[2] > 0 && count[3] > 0) {
            count[0] -= 2;
            count[1] -= 1;
            count[2] -= 1;
            count[3] -= 1;
            res++;
        }
        System.out.println(res);
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$

    ​

1016.T2

1. 题目说明

给定一个字符串s，现在想让你删除掉一些字符，使得这个字符串每个字符出现的次数均不相同，想知道最少需要删除多少个字符?

示例1

输入

"aab"

输出

0

说明

我们不需要删除任何字符，a出现了2次，b出现了1次

​

2. 解答分析

• 简单的思路，但是需要注意到的是利用了HashSet不重复的特性进行操作。

• 首先采用长度为26的int数组来统计字符串s中不同字符出现的次数。

• 然后利用HashSet元素不重复的特性进行删除操作：

  • 遍历int数组，当a[i]不为0且set中不存在a[i]，直接添加到set中；
  • 当a[i]不为0，a[i]在set中已存在的情况下，对a[i]–，操作数res++，直到a[i]在set中不存在，此时判断a[i]是否大于0，大于0才加入set集合中即可。

• 比较重要的：这里的a[i]始终表示的是字符出现的次数值，我们要保证的只是每个字符次数不一样，不是字符不一样！！！

  ​

3. 具体代码

import java.util.HashSet;
import java.util.Scanner;

public class title2 {
    public static void main(String[] args){
        Scanner in=new Scanner(System.in);
        String str=in.next();

        //统计出现的次数
        int[] a=new int[26];
        char[] ss=str.toCharArray();
        for(char c:ss){
            if(Character.isLowerCase(c)) {//判断此时读入的字符是否为小写的英文字符，而不是其余空格等
                a[c - 'a']++; //相同的字符，次数值++
            }
        }
        HashSet<Integer> set=new HashSet<>();
        int res=0;
        for(int i=0;i<a.length;i++){
            if(a[i]!=0){

                while(set.contains(a[i])){//遇到重复的次数，减去1，此时保证输入set中的值都是不一样的。
                    a[i]--;
                    res++;
                }
                if(a[i]!=0){
                    set.add(a[i]);//放入的是数值，也就是a[i]的值，和是a是b没关系
                }
            }
        }
        System.out.println(res);
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$

  • 空间复杂度：$O(1)$ ,使用的集合空间是固定的。

    ​

1104.T1

1. 题目说明

小红拿到了一个链表，她需要把所有偶数节点合并到该节点前面和它相邻的奇数节点上(新节点权值为两个节点权值之和)，直到剩余的节点无法合并为止。你能帮帮她吗?

示例1

输入

{2,3,4,1,2,2,3}

输出

{2,7,5,3}

说明

对于链表2->3->4->1->2->2->3，先将4合并到3上面，形成2->7->1->2->2->3，然后将2合并到1上面，形成2->7->3->2->3，最后将2合并到3上面，形成2->7->5->3。此时无法合并，合并结束。

​

2. 解答分析

• 简单地说，就是需要找到奇数值节点，（注意是奇数值，不是奇数节点），将其和后面的偶数值节点进行合并即可。

  • 需要链表的当前位置和指针cur和cur.next以及后续的节点位置和指针np和np.next。

• 在循环中，首先跳过当前节点和后续的所有偶数值节点，直到找到一个奇数值节点或到达链表末尾。

  ​

3. 具体代码

import java.awt.*;
import java.util.List;

public class title1 {
    public static ListNode mergNode(ListNode head){
        ListNode dummy=new ListNode();
        dummy.next=head;
        ListNode cur=head;
        while(cur!=null){
            while(cur!=null && cur.val%2==0){ //如果不是末尾，当前不是偶数值节点的话
                cur=cur.next; //后移
            }
//            if(cur==head){ //当处理完链表中的所有节点后，会回到起始节点，跳出循环
//                break;
//            }
            ListNode np=cur.next; //后一个位置
            while(np!=null && np.val%2==0){ //后一个位置是偶数
                cur.val+= np.val; //将值和当前的节点值相加
                np=np.next; //更新后一个偶数值的位置
            }
            cur.next=np; //当前节点next指针移动到下一个非偶数节点的位置，跳过全部偶数值节点
            cur=np; //移动判断的位置，移动到下一个非偶数值节点
        }
        return dummy.next; //返回最初的头结点
    }

    //测试用例
    public static void main(String[] args){
        ListNode node1=new ListNode(2);
        ListNode node2=new ListNode(3);
        ListNode node3=new ListNode(4);
        ListNode node4=new ListNode(1);
        ListNode node5=new ListNode(2);
        ListNode node6=new ListNode(2);
        ListNode node7=new ListNode(3);


        node1.next=node2;
        node2.next=node3;
        node3.next=node4;
        node4.next=node5;
        node5.next=node6;
        node6.next=node7;

        //调用合并的函数
        ListNode res=mergNode(node1);
        //输入的是：
        System.out.println("输入的是： 2，3，4，1，2，2，3");
        //输出结果
        System.out.print("输出的是： ");
        while(res!=null){
            System.out.print(res.val+" ");
            res=res.next;
        }
    }
}
    class ListNode{
        int val;
        ListNode next;
        ListNode(){
        }
        ListNode(int val){
            this.val=val;
        }
        ListNode(int val,ListNode next){
            this.val=val;
            this.next=next;
        }
    }

​

1104.T2

1. 题目说明

小红拿到了一个链表。她每次操作会随机选择一个节点，将该节点、该节点下一个节点和该节点上一个节点同时删除。请注意，如果选择的节点是头节点，则不存在上一个节点，若是尾节点，则不存在下一个节点。

小红希望你计算将链表删成空链表的操作次数的期望 1<=n<=10^5

如果你返回的答案和正确答案的相对误差不超过10^-3，则认为你的答案正确。

示例1

输入

3

输出

1.66666667

说明

如果第一次击打最左边或者最右边的弹珠，则还需要一次击打。

如果第一次击打中间的弹珠，则直接打出全部弹珠。答案是1/3* 1+2/3*2=5/3

​

2. 解答分析

• 比较有意思的一道题，这里的链表节点可以转化为弹珠，对于中间的弹珠，每次弹一下，周围的两个就没了；但是如果是在两边的边界值的话，只能对一侧的一个做出反应，所以这里想到的是动态规划，对于i个弹珠的级数和值分为两步。

• 动态规划数组含义：f[i]表示的总共有i颗珠子时候级数的期望值（这里为了好理解，可以将期望值替换成选择数，不改变最后的结果，毕竟只是数学运算上的差别…）

• 递推公式定义：拆分成左、中、右三部分，相当于以3为单位进行动态规划

• 存在两种分步选择：

  1. 选择考虑中间三球的部分，有i-2个三球的部分，也就有i-2种选择。剩余的两个边角球有f[i-3] 种选择；

  2. 选择边角的两个，2种，剩余f[i-2]个选择；

• 举例验证：

  i=5,共有5个小球的时候：

  O O O O O

  | [] [] [] |

  1. 对中间：中间的3(5-2)个球由于两边都有小球，所以存在3种选择打法； 此时每打出的球，剩余f[i-3]个球选择（总共球个数减3了嘛）~
  2. 对两侧：左右的每个球只能对各自一侧的1个球打，先是1； 此时每打出的球，剩余的有f[i-2]个球选择（同上理解）~

  ​

3. 具体代码

import com.sun.source.doctree.SystemPropertyTree;

public class title2 {
    //说明: 3个球的情况
    //如果第一次击打最左边或者最右边的弹珠，则还需要一次击打
    //如果第一次击打中间的弹珠，则直接打出全部弹珠。答案是1/3* 1+2/3*2=5/3

    // 利用的是动态规划进行判断，对级数的期望值，在最后打印出来
    public static double get_expect(int n){
        if(n==1 || n==2){
            return (double) 1;
        }
        //f[i]表示的总共有i颗珠子时候级数的（期望值）
        //递推的公式是拆分成左、中、右三部分，相当于以3为单位进行动态规划
        //存在两种分步选择：1. 选择考虑中间三球的部分，有i-2个三球的部分，也就有i-2种选择，剩余的两个边角球有f[i-3]种
        // 2.选择边角的两个，2种，剩余f[i-2]个选择
        double[] f=new double[n+1];
        for(int i=3;i<=n;i++){
            f[i]+=(double) (i-2)/i *(1+f[i-3]); //中间部分
            f[i]+=(double) 2/i*(1+f[i-2]);// 最左、最右1个球部分
        }
        double ans=f[n];
        String str=String.format("%.8f",ans); //保留8位小数
        ans=Double.parseDouble(str);
        return ans;
    }
    //test
    public static void main(String[] args){
        int n=3;
        System.out.println(get_expect(n));
    }
}

• 复杂度分析：

  • 时间复杂度：$O(n)$

    遍历过程中需要计算级数的期望值，所以整个代码的时间复杂度为O(n)，其余的循环都是O(1)复杂度。

  • 空间复杂度：$O(n)$

    使用一个大小为n+1的数组f来保存每个节点数量对应的期望值，所以需要的额外空间为O(n)。

    ​

最近除了刷题，也开始看项目了。先是数据库redis的实战项目，挺有意思的。从项目出发学习、完善技术栈，抓紧时间，做好安排；同时基础八股也要复习，后续开个板块记录基础知识点吧~

又是新的一周了~继续努力😊