[豆包MarCode AI 刷题] 算法题解 Java 青训入营考核 五题打卡第一天

目录

8 易 找出整型数组中占比超过一半的数

20 易 比赛配对问题

29 易 小D的 'acb' 变换问题​编辑

25 易 DNA序列编辑距离

1 易 找单独的数

欢迎你报名豆包MarsCode 青训营-寒假专场！非常开心你加入这个充满活力和创新的大家庭。在这里，你将遇到一群和你一样对技术充满热情的小伙伴，一起学习、成长、分享～我们准备了丰富的课程内容，还有各种实战项目等你来挑战，相信你一定会收获满满

青训营是字节跳动技术团队发起的技术系列培训 & 人才选拔项目；面向高校在校生，旨在培养优秀且具有职业竞争力的开发工程师。
本期青训营由豆包MarsCode 团队联合掘金社区主办，课程包含前端、后端和大数据方向，在这个飞速发展的 AI 时代，我们将和豆包MarsCode 一起深入探索，在青训营的技术氛围中，学习技术，高效写码～

8 易 找出整型数组中占比超过一半的数

import java.util.*;

public class Main {
    public static int solution(int[] array) {
        // Edit your code here

        Map<Integer,Integer>map=new HashMap<>();
        for(int i=0;i<array.length;i++){
            map.put(array[i],map.getOrDefault(array[i], 0)+1);
            if(map.getOrDefault(array[i], 0)>array.length/2){
                return array[i];
            }
        }

        return 0;
    }

    public static void main(String[] args) {
        // Add your test cases here

        System.out.println(solution(new int[]{1, 3, 8, 2, 3, 1, 3, 3, 3}) == 3);
    }
}

20 易 比赛配对问题

class Main {

    static int cnt=0;

    public static int solution(int n) {
        rec(n);
        int ans=cnt;
        cnt=0;
        return ans;
    }

    public static int rec(int n){
        if(n==1){
            return 0;
        }
        if(n%2==0){
            // 偶数
            cnt+=(n/2);
            rec(n/2);
        }else{
            // 奇数
            cnt+=( (n-1)/2 ); 
            rec( (n-1)/2+1 );
        }
        return 0;
    }

    public static void main(String[] args) {
        // System.out.println(solution(7) == 6);
        // System.out.println(solution(14) == 13);
        // System.out.println(solution(1) == 0);
        System.out.println(solution(7) );
        System.out.println(solution(14) );
        System.out.println(solution(1) );
    }
}

29 易 小D的 'acb' 变换问题

public class Main {

    public static String solution(String s, int k) {
        String str=s;
        while(k-->0){
            StringBuilder sb = new StringBuilder("");
            for(int i=0;i<str.length();i++){
                if(str.charAt(i)=='a'){
                    sb.append("bc");
                }
                if(str.charAt(i)=='b'){
                    sb.append("ca");
                }
                if(str.charAt(i)=='c'){
                    sb.append("ab");
                }
            }
            str=sb.toString();
        }        
        return str;
    }

    public static void main(String[] args) {
        System.out.println(solution("abc", 2).equals("caababbcbcca"));
        System.out.println(solution("abca", 3).equals("abbcbccabccacaabcaababbcabbcbcca"));
        System.out.println(solution("cba", 1).equals("abcabc"));
    }
}

25 易 DNA序列编辑距离

public class Main {

    public static int solution(String dna1, String dna2) {
        int m = dna1.length();
        int n = dna2.length();
        =
        int[][] dp = new int[m + 1][n + 1];
        
        for (int i = 0; i <= m; i++) {
            dp[i][0] = i;
        }
        for (int j = 0; j <= n; j++) {
            dp[0][j] = j; 
        }
        
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (dna1.charAt(i - 1) == dna2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1]; 
                } else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                  
                }
            }
        }
        
        return dp[m][n];
    }

    public static void main(String[] args) {
        //  You can add more test cases here
        System.out.println(solution("AGCTTAGC", "AGCTAGCT") == 2);
        System.out.println(solution("AGCCGAGC", "GCTAGCT") == 4);
    }
}

1 易 找单独的数

import java.util.*;

public class Main {
    public static int solution(int[] cards) {
        // Edit your code here
        int arr[]=new int[1001];
        
        for(int i:cards){
            arr[i]++;
        }
        for(int i=1;i<arr.length;i++){
            if(arr[i]==1){
                System.out.print(i);
                return i;
            }
        }
        return 1;
    }

    public static void main(String[] args) {
        // Add your test cases here
        
        System.out.println(solution(new int[]{1, 1, 2, 2, 3, 3, 4, 5, 5}) == 4);
        System.out.println(solution(new int[]{0, 1, 0, 1, 2}) == 2);
    }
}