字节跳动

1. 代码校正

字节跳动

 

 

package ZJTD;

import java.util.*;

/**
 * @author zzm
 * @data 2020/5/17 9:04
 * 1. 三个同样的字母连在一起,一定是拼写错误,去掉一个的就好啦:比如 helllo -> hello
2. 两对一样的字母(AABB型)连在一起,一定是拼写错误,去掉第二对的一个字母就好啦:比如 helloo -> hello
3. 上面的规则优先“从左到右”匹配,即如果是AABBCC,虽然AABB和BBCC都是错误拼写,应该优先考虑修复AABB,结果为AABCC
 */
public class StrProof {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        scanner.nextLine();

        for (int i = 0; i < n; i++) {
            String s = scanner.nextLine();
            StringBuilder sb = new StringBuilder(s.length());
            for (int j = 0; j < s.length(); j++) {
                if (helper(sb, sb.length(),s.charAt(j))) continue;
                sb.append(s.charAt(j));
            }
            System.out.println(sb.toString());
        }
    }

    private static boolean helper(StringBuilder s, int index,char c) {
        if (index < 2 || c != s.charAt(index - 1)) return false;
        if (c == s.charAt(index - 2)) return true;
        if (index >= 3 && s.charAt(index - 3) == s.charAt(index - 2)) return true;
        return false;
    }
}

2. 选择三个地点,最大间距不超过 D

字节跳动

思路:左右指针l  r(r-l>=3),确定一个区间以l 开始的最大区间,此区间总数 为 (r-l)*(r-l-1)/2, 即从 l+1 到 r 选两个出来。

package ZJTD;

import java.util.*;

/**
 * @author zzm
 * @data 2020/5/17 10:06
 * 1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
2. 为了相互照应,我们决定相距最远的两名特工间的距离不超过D。
 */
public class LocationSelect {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int len = scanner.nextInt();
        int[] nums = new int[n];
        for (int i = 0; i < n; i++) nums[i] = scanner.nextInt();
        scanner.close();

        long res = 0;
        int l = 0, r = 2;
        while (l < n-2) {
            while (r < n && nums[r] - nums[l] <= len) r++;
            if (--r - l +1 >= 3) res += (long)(r - l) * (r - l - 1) / 2;
            l++;
        }
        System.out.println(res%99997867);
    }
}

3. 麻将

还没做出来

小包最近迷上了一款叫做雀魂的麻将游戏,但是这个游戏规则太复杂,小包玩了几个月了还是输多赢少。 于是生气的小包根据游戏简化了一下规则发明了一种新的麻将,只留下一种花色,并且去除了一些特殊和牌方式(例如七对子等),具体的规则如下:  
  1. 总共有36张牌,每张牌是1~9。每个数字4张牌。
  2. 你手里有其中的14张牌,如果这14张牌满足如下条件,即算作和牌
  • 14张牌中有2张相同数字的牌,称为雀头。
  • 除去上述2张牌,剩下12张牌可以组成4个顺子或刻子。顺子的意思是递增的连续3个数字牌(例如234,567等),刻子的意思是相同数字的3个数字牌(例如111,777)
  例如: 1 1 1 2 2 2 6 6 6 7 7 7 9 9 可以组成1,2,6,7的4个刻子和9的雀头,可以和牌 1 1 1 1 2 2 3 3 5 6 7 7 8 9 用1做雀头,组123,123,567,789的四个顺子,可以和牌 1 1 1 2 2 2 3 3 3 5 6 7 7 9 无论用1 2 3 7哪个做雀头,都无法组成和牌的条件。   现在,小包从36张牌中抽取了13张牌,他想知道在剩下的23张牌中,再取一张牌,取到哪几种数字牌可以和牌。

4. 找最长的相同特征

       小明是一名算法工程师,同时也是一名铲屎官。某天,他突发奇想,想从猫咪的视频里挖掘一些猫咪的运动信息。为了提取运动信息,他需要从视频的每一帧提取“猫咪特征”。一个猫咪特征是一个两维的vector<x, y>。如果x_1=x_2 and y_1=y_2,那么这俩是同一个特征。        因此,如果喵咪特征连续一致,可以认为喵咪在运动。也就是说,如果特征<a, b>在持续帧里出现,那么它将构成特征运动。比如,特征<a, b>在第2/3/4/7/8帧出现,那么该特征将形成两个特征运动2-3-4 和7-8。 现在,给定每一帧的特征,特征的数量可能不一样。小明期望能找到最长的特征运动。   字节跳动
package ZJTD;

import java.util.*;


/**
 * @author zzm
 * @data 2020/5/21 8:22
 */
public class FeatureSel {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        HashMap<String, Integer> pre = new HashMap<>();
        HashMap<String, Integer> now = new HashMap<>();

        int max = Integer.MIN_VALUE;
        for (int i = scanner.nextInt(); i > 0; i--) {
            for (int j = scanner.nextInt(); j > 0; j--) {
                for (int k = scanner.nextInt(); k > 0; k--) {
                    String node = scanner.nextInt()+"-"+scanner.nextInt();
                    now.put(node, 1 + pre.getOrDefault(node, 0));
                    max = Math.max(now.get(node), max);
                }
                pre.clear();
                pre.putAll(now);
                now.clear();
            }
            System.out.println(max);
        }
        scanner.close();
    }
}

5. 最少的车票

小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。

字节跳动

以下代码为深度遍历,超时,后续更改

package ZJTD;

import java.util.*;

/**
 * @author zzm
 * @data 2020/5/17 11:00
 */
public class Tickets {
    static int res = Integer.MAX_VALUE;
    static int[][] tickets;
    static boolean[] used;

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        tickets = new int[n][n];
        used = new boolean[n];
        used[0] = true;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                tickets[i][j] = scanner.nextInt();
            }
        }
        scanner.close();
        dfs(0, 1, 0);
        System.out.println(res);
    }

    private static void dfs(int pre, int len, int totle) {
        if(totle>res) return;
        for (int i = 1; i < used.length; i++) {
            if (!used[i]) {
                if (len == used.length - 1) {
                    totle += tickets[pre][i] + tickets[i][0];
                    res = Math.min(res, totle);
                    return;
                }
                used[i] = true;
                dfs(i, len + 1, totle + tickets[pre][i]);
                used[i] = false;
            }
        }
    }
}

6. 找零钱

Z国的货币系统包含面值1元、4元、16元、64元共计4种硬币,以及面值1024元的纸币。现在小Y使用1024元的纸币购买了一件价值为字节跳动的商品,请问最少他会收到多少硬币?

package ZJTD;

import java.util.*;

/**
 * @author zzm
 * @data 2020/5/18 19:40
 */
public class ChangeMoney {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = 1024 - scanner.nextInt();
        scanner.close();

        int res = 0;

        res += n >> 6;
        n -= (n >> 6) << 6;
        res += n >> 4;
        n -= (n >> 4) << 4;
        res += n >> 2;
        n -= (n >> 2) << 2;
        res += n;
        System.out.println(res);
    }
}

7. 机器人跳建筑

机器人正在玩一个古老的基于DOS的游戏。游戏中有N+1座建筑——从0到N编号,从左到右排列。编号为0的建筑高度为0个单位,编号为i的建筑的高度为H(i)个单位。  起初, 机器人在编号为0的建筑处。每一步,它跳到下一个(右边)建筑。假设机器人在第k个建筑,且它现在的能量值是E, 下一步它将跳到第个k+1建筑。它将会得到或者失去正比于与H(k+1)与E之差的能量。如果 H(k+1) > E 那么机器人就失去 H(k+1) - E 的能量值,否则它将得到 E - H(k+1) 的能量值。 游戏目标是到达第个N建筑,在这个过程中,能量值不能为负数个单位。现在的问题是机器人以多少能量值开始游戏,才可以保证成功完成游戏?

 思路: 每一次跳跃后  E  = 2E - H;  从后往前,设最终E=0, 则 每一次往前  E = (E+H +1)/2; 注意:+1 是因为最后可能剩一个而不是刚好能量用尽,即 2E-H = 1 

package ZJTD;

import java.util.*;

/**
 * @author zzm
 * @data 2020/5/21 10:13
 * 输入描述:第一行输入,表示一共有 N 组数据.
 * 第二个是 N 个空格分隔的整数,H1, H2, H3, ..., Hn 代表建筑物的高度
 * 输出描述:输出一个单独的数表示完成游戏所需的最少单位的初始能量
 * 输入例子1:
 * 5
 * 3 4 3 2 4
 * 输出例子1:
 * 4
 */
public class RobotsJump {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) h[i] = scanner.nextInt();
        scanner.close();

        int e = 0;
        for (int i = n - 1; i >= 0; i--) e = (e + h[i] + 1) / 2;

        System.out.println(e);
    }
}

  

 

 

 
上一篇:矩阵乘积


下一篇:考试策略, 美团笔试题