牛客刷题-1

小米2019秋招安卓开发笔试题（B）

21. 最少立方数之和

给出一个数字N（0<N<1000000）,将N写成立方数和的形式，求出需要的最少立方数个数。
例如N=17，1+8+8 = 17，最少需要3个立方数，则输出3。
N= 28,1+1+1+1+8+8+8=28, 需要7个立方数，1+27=28,需要2个立方数，所以最少立方数为2，则输出2。

import java.util.*;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    private static final List<Integer> cubs;
    private static final int cubNum;
    static {
        cubs = new ArrayList<Integer>();
        for(int i = 1; i*i*i <= 1000000; i++) {
            cubs.add(i*i*i);
        }
        cubNum = cubs.size();
    }
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            int index = Collections.binarySearch(cubs, n);
            if(index < 0) {
                index = -index - 2;
            }
            if(index < 0) {
                throw new RuntimeException("unreachable");
            }
            int[] dp = new int[n+1];
            Arrays.fill(dp, Integer.MAX_VALUE);
            dp[0] = 0;
            for(int j = 1; j <= index+1; j++) {
                for(int i = cubs.get(j-1); i <= n; i++) {
                    dp[i] = Math.min(dp[i], dp[i - cubs.get(j-1)] + 1);
                }
            }
            System.out.println(dp[n]);
        }
    }
}

完全背包，从所有立方数里选数，取数目最小的情况

资产包打包

在金融资产交易中，经常涉及到资产包的挑选打包。在资产包打包过程中，每种类型的资产有固定的数量与价值，需选择某几种资产打包，使得资产包总价值最大。打包时每种资产只能整体打包，不能分割。假设现有可容纳M条资产的资产包，另外有N种资产。资产Na数量为Ta条，总价值为Va元；资产Nb数量为Tb条，总价值为Vb元；资产Nc数量为Tc条，总价值为Vc元…；资产Nn数量为Tn，总价值为Vn。编写算法，挑选哪些类型资产放入资产包可使得资产包总价值最大？

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String[] input = in.nextLine().split(",");
            int index = 0;
            int W = Integer.parseInt(input[index++], 10);
            int N = Integer.parseInt(input[index++], 10);
            int[][] properties = new int[N][2];
            String[] weights = input[index++].split(" ");
            for (int i = 0; i < N; i++) {
                properties[i][0] = Integer.parseInt(weights[i], 10);
            }
            String[] values = input[index++].split(" ");
            for (int i = 0; i < N; i++) {
                properties[i][1] = Integer.parseInt(values[i], 10);
            }
            int[] dp = new int[W + 1];
            for (int i = 1; i <= N; i++) {
                for (int j = W; j >= properties[i - 1][0]; j--) {
                    dp[j] = Math.max(dp[j],
                                        dp[j - properties[i - 1][0]] + properties[i - 1][1]);
                }
            }
            System.out.println(dp[W]);
        }
    }
}

0-1背包，要注意0-1背包和完全背包的区别

• 无压缩情况
  • 0-1背包转移方程为：
    • dp[i][j] = max(dp[i][j], dp[i-1][j-wi]+vi) (当j >= wi时)
    • dp[i][j] = dp[i][j] (当j < wi时)
  • 完全背包转移方程为：
    • dp[i][j] = max(dp[i][j], dp[i][j-wi]+vi) (当j >= wi时) 这里是dp[i]
    • dp[i][j] = dp[i][j] (当j < wi时)
• 有压缩情况
  • 0-1背包对容量是逆向遍历
  • 完全背包是正向遍历

super和this关键字

• this()和super()不可以同时出现在同一个构造函数中
• this()或super()要放在构造函数第一行

Android数据存储方式

• SharedPreference
• File
• SQLite
• Content Provider
• 网络

题目中说Bundle也可以，但是应该不对
Bundle是可以序列化，但是一般不作为存储数据的方式

广播

× 当静态注册的广播设置的优先级高于动态注册的广播时，静态注册将先接收到广播

• 动态广播跟随Activity/Application的生命周期，静态广播不受限制。
• 非有序广播的情况下，动态广播总是要优先于静态广播
• 每次广播被接收后会重新创建BroadcastReceiver对象，并在onReceive方法中执行完时销毁

Android动画分类

IntentService（已经弃用）

• 对Service的包装
• 默认实现onBind，返回null
• 包含一个HandlerThread(的looper)，（Service本身不包括线程，运行在主线程）
• 持有一个handler，每次start把intent放入msg的obj里，用handler发送

@Deprecated
public abstract class IntentService extends Service {

private final class ServiceHandler extends Handler {
    public ServiceHandler(Looper looper) {
        super(looper);
    }

    @Override
    public void handleMessage(Message msg) {
        onHandleIntent((Intent)msg.obj);
        stopSelf(msg.arg1);
    }
}

@WorkerThread
protected abstract void onHandleIntent(@Nullable Intent intent); //运行在WorkerThread中

@Override
public void onStart(@Nullable Intent intent, int startId) {
    Message msg = mServiceHandler.obtainMessage();
    msg.arg1 = startId;
    msg.obj = intent;
    mServiceHandler.sendMessage(msg);
}

@Override
public int onStartCommand(@Nullable Intent intent, int flags, int startId) {
    onStart(intent, startId);
    return mRedelivery ? START_REDELIVER_INTENT : START_NOT_STICKY;
}

小米2019秋招安卓开发笔试题（A）

进制间转换

设计一个函数， 可以将任意十进制的数， 转换成任意2到9的进制表示的形式

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNext()) { // 注意 while 处理多个 case
            long n = in.nextLong();
            int base = in.nextInt();
            if(n == 0) {
                System.out.println("0");
                continue;
            }
            StringBuilder sb = new StringBuilder();
            while(n > 0) {
                sb.append(n % base);
                n /= base;
            }
            sb.reverse();
            System.out.println(sb);
        }
    }
}

CCNumber

CC最近对一种整数比较感兴趣，我们暂且把这种整数称为C Number, C Number是指一个整数
{C0, C1 … Cn-1} (C0 > 0 , n >= 3)， 存在一个Cm（0<m<n-1）满足以下条件:

• Ci-1 < Ci (0<i<=m), Ci代表这个整数中的第i位数字
• Ci>Ci+1(m<=i<n-1)
• 如果一个整数里面有相邻的2个C Number的话，我们称这个整数为CC Number（2个C Number不可以有公用的数字Ci，并且2个C Number要紧紧相邻）。

请在[A,B]区间内找出找出score最大的CCNumber 并输出这个score.(score：CC Number中所有数字的和)

Activity跳转

FirstActivity跳转到SecondActivity后，然后点击返回键，以下执行顺序不可能出现的是：

SecondActivity的onPause()->SecondActivity的onStop()->SecondActivity的onDestroy()->FirstActivity的onRestart()->FirstActivity的onResume()

不会在下一个Activity可见前，把当前Activity变成不可见的，（进入stop/destroy）

ANR

input事件在5s内没有处理完成会发生ANR
前台广播的onReceive处理事务时超过10s会发生ANR
后台Service在200s内没有处理完成会发生ANR
前台Service在20s内没有处理完成会发生ANR
在Activity中，Main线程消息队列中的消息在5秒内没有得到响应

APP进程

• 一个APP可以运行在多个进程
  • 在Activity/Service中添加不同的进程名android:process="processName"
  • 每个进程会有一个Application对象
• 多个APP可以运行在同一进程
  • 在Manifest中添加android:sharedUserId=<java package>
  • 在Manifest中添加android:sharedUserLabel=@string/id
  • 在Application中添加android:process="processName"

顺丰科技2019秋招安卓开发工程师笔试客观题合集

select into和insert into

SELECT xxx INTO target_table FROM origin_table

• 要求执行前表不存在，会自动创建

INSERT INTO target_table (filed1, field2, ...) VALUES (val1, val2, ...)

• 要求执行前表已经存在

EventBus

简单实现一套view的注入框架（）

度小满校招Android研发工程师第2批

近似周期串

小明发现有的字符串中蕴含着一些规律，但是它们又和普通的周期串有点不一样。例如:ABCABDABDABE。如果以3为周期，可以看到其中 包含“ABC”、“ABD”和“ABE”等子串，其中“ABD”出现了两次。 这些子串两两之间最多只有某一位上的字符不相同，其他位置上的字符都一样。小明将其称为“近似串”，由多个“近似串”组成的字符串称为“近 似周期串”。“近似周期串”中的每一个“近似串”的长度需大于等于2。 需要注意的是“ABCABBACD”并不是一个“近似周期串”。如果以3为周期，其子串包 括“ABC”、“ABB”和“ACD”，“ABB”与“ACD”、“ABC”与“ACD”均存在两个位置上的字符不相同，因此不是“近似周期串”。特别 的，“AAAAAA”也是一个“近似周期串”，因为它满足上述“近似周期串”的定义。 现在给你一个字符串，请编写一个程序判断该字符串是否是以3为周期的“近似周期串”。

import java.util.Scanner;
 
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            int n = in.nextInt();
            while(n-- > 0) {
                String s = in.nextLine();
                int i = 0;
                int ans = 0;
                while(i < s.length()) {
                    ans = ans ^ ((s.charAt(i) - 'A') << 2) + ((s.charAt(i+1) - 'A') << 1) + (s.charAt(i+2) - 'A');
                    i += 3;
                }
                if((ans & (ans-1)) != 0) {
                    System.out.println("No");
                } else {
                    System.out.println("Yes");
                }
            }
        }
    }
}

DNS

DNS辅助服务器与DNS主服务器通讯时使用TCP协议

Android题库

onNewIntent()的触发时机

设备管理器权限

sleep,wait,yield,join的区别

sleep,yield: 让渡cpu使用权，不释放锁
wait: 相当于条件变量，释放锁
join: 底层调用了wait

Hook框架

xposed,Substrate,Cydia,frida

dex

焦点

toast没有焦点

View绘制流程

ContentProvider

drawable-xxhdpi等目录

携程笔试

算法1

• 给n个数1 <= ai <= 1e6， 求PI(ai!)ai的阶乘的积中因数的个数

• 分解质因数

• 质因数出现次数+1的积就是原来数字的因数个数

• 对数组排序，计算每个数在阶乘中出现的次数，计算每个数的质因数，质因数个数为出现次数

• 计算所有数的质因数出现次数*该数在阶乘中出现的次数

import java.util.*;
import java.util.function.UnaryOperator;

public class Main {
    private static final int MOD = 1000000000 + 7;
    private static final int MAX_VAL = 1000000;
    private static <K, V> void mapReplace(Map<K, V> map, K key, V def, UnaryOperator<V> operator) {
        V old = map.get(key);
        map.put(key, operator.apply(old == null ? def : old));
    }
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        List<Integer> primes = new ArrayList<>(List.of(2, 3));
        for(int i = 5; i <= MAX_VAL; i+=2) {
            boolean flag = true;
            for(int j = 3; j*j <= i; j++) {
                if(i % j == 0) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                primes.add(i);
            }
        }
        while(scanner.hasNext()) {
            int n = scanner.nextInt();
            int[] arr = new int[n];
            Map<Integer, Integer> cnt = new HashMap<>();
            for(int i = 0; i < n; i++) {
                arr[i] = scanner.nextInt();
            }
            Arrays.sort(arr);
            for(int j = 1; j <= arr.length; j++) {
                final int incr = (arr.length - j + 1);
                if(Collections.binarySearch(primes, arr[j-1]) >= 0) {
                    mapReplace(cnt, arr[j-1], 0, (old) -> (old + incr) % MOD);
                    continue;
                }
                for(int i = 1; i <= primes.size(); i++) {
                    int val = arr[j-1];
                    int prime = primes.get(i-1);
                    while(val % prime == 0) {
                        val = val / prime;
                        mapReplace(cnt, prime, 0, (old) -> (old + incr) % MOD);
                    }
                }
            }
            long ans = 1;
            for(var entry : cnt.entrySet()) {
                ans = (ans * (entry.getValue() + 1)) % MOD;
            }
            System.out.println(ans);
        }
    }
}

刷题

账号

塔子哥有n个账号，每个账号粉丝数为ai

这天他又创建了一个新账号，他希望新账号的粉丝数恰好等于x。
为此他可以向自己已有账号的粉丝们推荐自己的新账号，这样以来新账号就得到了之前粉丝的关注。
他想知道，他最少需要在几个旧账号发“推荐新账号”的文章，可以使得他的新账号粉丝数恰好为 x，除此以外，他可以最多从中选择一个账号多次发“推荐新账号”的文章。

假设一个旧账号粉丝数为ai，如果仅推荐一次，那么新账号粉丝数增加ai/2，如果多以推荐，则粉丝数增加ai

读题读错了，只能选一个账号推广多次

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, x;
    while(cin >> n >> x) {
        vector<int> accounts(n);
        for(int i = 0; i < n; i++) {
            cin >> accounts[i];
        }
        vector<int> dp(x+1, n+1); // 一次
        vector<int> dp1(x+1, n+1); // 有某一个账号是多次的情况
        dp[0] = 0;
        dp1[0] = 0;
        for(int i = 1; i <= n; i++) {
            for(int j = x; j >= 1; j--) {
                if(j >= accounts[i-1]) dp1[j] = min(dp1[j], dp[j - accounts[i-1]] + 1); // 该账号多次发布
                if(j >= accounts[i-1]/2) dp1[j] = min(dp1[j], dp1[j - accounts[i-1]/2] + 1); // 上一个账号多次发布，该账号不多次发布
                if(j >= accounts[i-1]/2) dp[j] = min(dp[j], dp[j - accounts[i-1]/2] + 1);
            }
        }
        cout << (min(dp[x], dp1[x]) > n ? -1 : min(dp[x], dp1[x])) << "\n";
    }
    return 0;
}

题目

一个正整教x，在区间[l, r]中选样一个数y，满定x*y是完全平万数。想知道有多少种选择方案?
一共有q次询问

1 <= q <= 1e4
1 <= x <= 1e14
1 <= l, r <= 1e14

思路

• 我们要找所有y*x == t*t的数y，也就是找所有的y=t*t/x 且 t*t%x == 0
• 所有满足t*t%x == 0的数(t*t/x)，(t*t/x)在[1, 1e14]范围内
• 也就是t*t=q*x 因为t,q,x都是整数，所以sqrt(q*x)是整数也就是q可以写成i*i*x的形式
• 也就是t=i*x
• 也就是找到所有i*i*x，且在[1, 1e14]范围内

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            int q = scanner.nextInt();
            long x = scanner.nextLong();
            List<Long> isSquare = new ArrayList<>();
            for(long i = 1; i*i*x <= 1e14; i++) {
                isSquare.add(i*i*x);
            }
            for(int i = 0; i < q; i++) {
                long l = scanner.nextLong();
                long r = scanner.nextLong();
                int leftIndex = Collections.binarySearch(isSquare, l);
                int rightIndex = Collections.binarySearch(isSquare, r);
                if(leftIndex < 0) leftIndex = -leftIndex-1;
                if(rightIndex < 0) rightIndex = -rightIndex-1;
                else rightIndex++;
                System.out.println(rightIndex - leftIndex);
            }
        }
    }
}

2024.3.31

问题5

方阵里面上下左右走找tencent

问题4

数组分成k组，每组内部异或，求k组异或和最大

问题3

一个图，加一个边恰好可以连通有几种加法

问题2

一个数组，分成两段（可空），是否恰好可以重新排列成递增

问题1

边有RW两色
如果一个点周围的边全都是R，则是好点，统计好点的个数

import java.util.*;
import java.util.stream.IntStream;
import java.util.stream.Stream;

public class Main {
    private static final Scanner scanner = new Scanner(System.in);
    private static final String match = "tencent";
    private static final int[] pos = {0, 1, 0, -1, 0};
    private static int dfs5(int i, int j, int n, int m, int len, String[] map) {
        if(i >= n || j >= m || i < 0 || j < 0) return 0;
        if(match.charAt(len) != map[i].charAt(j)) return 0;
        if(len == 6) return 1;
        int ans = 0;
        for(int k = 0; k < pos.length - 1; k++) {
            ans += dfs5(i + pos[k], j + pos[k+1], n, m, len + 1, map);
        }
        return ans;
    }
    private static void problem5() {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        String[] map = new String[n];
        scanner.nextLine();
        for(int i = 0; i < n; i++) {
            map[i] = scanner.nextLine();
        }
        int ans = 0;
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < m; j++) {
                ans += dfs5(i, j, n, m, 0,map);
            }
        }
        System.out.println(ans);
    }
    private static class UnionSet  {
        private final int[] set;
        public UnionSet(int n) {
            set = IntStream.iterate(0, (prev)->prev+1).limit(n).toArray();
        }
        public int find(int i) {
            return i == set[i] ? i : (set[i] = find(set[i]));
        }
        public void union(int i, int j) {
            set[find(i)] = find(j);
        }
    }
    private static void problem3() {
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        UnionSet unionSet = new UnionSet(n);
        for(int i = 0; i < m; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            unionSet.union(u-1, v-1);
        }
        Map<Integer, Integer> setCnt = new HashMap<>();
        for(int i = 0; i < n; i++) {
            int part = unionSet.find(i);
            if(!setCnt.containsKey(part)) {
                setCnt.put(part, 0);
            }
            setCnt.put(part, setCnt.get(part) + 1);
        }
        if(setCnt.size() != 2) {
            System.out.println(0);
        } else {
            int ans = 0;
            int diff = 0;
            for (var entry : setCnt.entrySet()) {
                diff += entry.getValue();
                ans += (n - diff) * entry.getValue();
            }
            // a1 a2 a3 ... an
            // a1*(a2 + a3 + a4 + ... + an)
            // a2*(a3 + a4 + a5 + ... + an)
            System.out.println(ans);
        }
    }
    private static void problem2() {
        char[] input = scanner.nextLine().toCharArray();
        int i = 0;
        while(i < input.length) {
            if(input[i] == '[' || input[i] == ']') {
                System.out.print(input[i]);
                i++;
                continue;
            }
            List<Integer> list = new ArrayList<>();
            if(input[i] == '{') {
                i++;
                while (i < input.length) {
                    int cur = 0;
                    while(i < input.length && input[i] >= '0' && input[i] <= '9') {
                        cur *= 10;
                        cur += input[i] - '0';
                        i++;
                    }
                    list.add(cur);
                    if(i < input.length) {
                        i++;
                        if(input[i-1] == '}') {
                            if(input[i] == ',') i++;
                            break;
                        }
                    }
                }
            }
            int seg1 = 1, seg2;
            while(seg1 < list.size() && list.get(seg1) > list.get(seg1-1)) {
                seg1++;
            }
            seg2 = seg1 + 1;
            while(seg2 < list.size() && list.get(seg2) > list.get(seg2-1)) {
                seg2++;
            }
            if(seg1 == list.size()) {
                System.out.print("true");
            } else if (seg2 != list.size()){
                System.out.print("false");
            } else {
                if(list.get(list.size() - 1) < list.get(0)) {
                    System.out.print("true");
                } else {
                    System.out.print("false");
                }
            }
            if(i < input.length) {
                if(input[i] != ']') {
                    System.out.print(",");
                }
            }
        }
        System.out.println();
    }
    private static void problem1() {
        int node = scanner.nextInt();
        int edge = scanner.nextInt();
        boolean[] res = new boolean[node];
        Arrays.fill(res, true);
        for(int i = 0; i < edge; i++) {
            int u = scanner.nextInt();
            int v = scanner.nextInt();
            String c = scanner.next();
            if(c.equals("R")) {
            } else {
                res[u-1] = res[v-1] = false;
            }
        }
        int ans = 0;
        for(int i = 0; i < res.length; i++) {
            if(res[i]) ans++;
        }
        System.out.println(ans);
    }
    private static void problem4() {
        int n = scanner.nextInt();
        int k = scanner.nextInt();
        int[] arr = new int[n];
        int[][] dp = new int[n+1][k+1];
        int[] xorSum = new int[n+1];
        for(int i = 0; i < n; i++) {
            arr[i] = scanner.nextInt();
            xorSum[i+1] = arr[i] ^ xorSum[i];
            dp[i+1][1] = xorSum[i+1];
        }
        for(int j = 2; j <= k; j++) {
            for(int i = j; i <= n; i++) {
                for(int m = j-1; m < i; m++) {
                    dp[i][j] = Math.max(dp[i][j], dp[m][j-1] + (xorSum[i] ^ xorSum[m]));
                }
            }
        }
        int ans = 0;
        for(int i = k; i <= n; i++) {
            ans = Math.max(ans, dp[i][k]);
        }
        System.out.println(ans);
    }
    public static void main(String[] args) {
        while(scanner.hasNext()) {
            problem5();
            problem4();
            problem3();
            problem2();
            problem1();
        }
    }
}