美团2022.3.12笔试

题目1.

1、算法分析：

这些数字至少满足以下两个特征中的一种：

* 数字是11的整数倍。
* 数字中至少包含两个1。
2、代码：
import java.io.*; import java.util.*; class Test{ public static void
main(String[] args) { Scanner sc = new Scanner(System.in); String s =
sc.nextLine(); int n =Integer.parseInt(s); for(int i=0;i<n;i++){ String str
=sc.nextLine(); int count=0; for(int j=0;j<str.length();j++){
if(str.charAt(j)=='1' && count<=2){ //统计一下输入字符串是否包含>=2个“1” count++; } } int num
= Integer.parseInt(str); if(num<11 || num%11 != 0 || count<2){
System.out.println("no"); }else{ System.out.println("yes"); } } } }

题目2：

1、算法分析

其实，拿到这题，我们可以很容易想到这种求组合的问题，常用动态规划和前缀和的方法来做。

1.1 动态规划

根据题目，要满足子序列乘积为正，我们需要考虑当前元素是正1 还是负1，1的正负不同，我们考虑的递推公式也不同。

1）确定递推公式

        因为存在正负两种情况，我们定义如下：

        dp[i][0]

 

• « 上一篇：建设智慧城市，少不了这些关键技术保驾护航
• » 下一篇：一个后端因为项目而干上前端，是系统学习还是胜任工作即可