门户网站建设为企业带来的好处,wordpress首页标题分隔符修改,深圳网站制作公司售后服务,flask公司网站开发检查「好数组」
题目描述
给你一个正整数数组 nums#xff0c;你需要从中任选一些子集#xff0c;然后将子集中每一个数乘以一个 任意整数#xff0c;并求出他们的和。
假如该和结果为 1#xff0c;那么原数组就是一个「好数组」#xff0c;则返回 True#xff1b;否则… 检查「好数组」
题目描述
给你一个正整数数组 nums你需要从中任选一些子集然后将子集中每一个数乘以一个 任意整数并求出他们的和。
假如该和结果为 1那么原数组就是一个「好数组」则返回 True否则请返回 False。
样例
样例输入 nums [12,5,7,23] nums [29,6,10] nums [3,6] 样例输出 true 解释挑选数字 5 和 7。 5 * 3 7 * (-2) 1 true 解释挑选数字 29, 6 和 10。 29 * 1 6 * (-3) 10 * (-1) 1 false 提示
1nums.length1051 nums.length 10^51nums.length1051nums[i]1091 nums[i] 10^91nums[i]109
思路
期初最能排除的是只要数组中出现了数字1就一定存在“好数组”然后直接给特判。然后又慢慢的发现其实只要数组中所有数的最大公约数为1存在好数组。反之不为1即为不存在好数组。
代码实现
class Solution {public boolean isGoodArray(int[] nums) {int divisor nums[0];for(int num : nums){divisor gcd(divisor, num);if(divisor 1) break;}return divisor 1;}private int gcd(int x, int y){ return y 0 ? gcd(y, x % y) : x;}
}染色时间
题目描述
小蓝有一个 n 行 m 列的白色棋盘, 棋盘的每一个方格都可以被染成彩色。
每个方格有一个染色时间 tijt_{ij}tij, 不同方格的染色时间可能不同。如果一个方 格被触发了染色, 这个方格就会在 tijt_ijtij 秒之后变成彩色, 然后将自己上下左右四 个方向相邻的方格触发染色。每个方格只能被触发染色一次, 第一次触发之后 的触发为无效触发。
给定每个方格的染色时间, 在时刻 0 触发第一行第一列的方格染色, 请问 多长时间后整个棋盘完成染色。
输入格式
输入的第一行包含两个整数 n,m, 分别表示棋盘的行数和列数。
接下来 n 行, 每行 m 个正整数, 相邻的整数之间用一个空格分隔, 表示每 个方格的染色时间。该部分的第 i 行第 j 个整数表示 tijt_{ij}tij, 即第 i 行第 j 列的方 格的染色时间
输出格式
输出一行包含一个整数, 表示整个棋盘完成染色的时间。
样例
样例输入 2 3 1 2 3 4 5 6 样例输出 12 评测用例规模与约定
对于30的评测用例 1 n, m 10; 对于60的评测用例1 n, m 50; 对于所有评测用例1 n,m 500; 1 tijt_{ij}tij 1000
思路
第一时间看到题目想到两种解法bfs和动态规划。但是通过一些代码的实践发现动态规划没那么容易然后写了一个bfs模拟。
代码实现
import java.util.*;
// 1:无需package
// 2: 类名必须Main, 不可修改public class Main {static int[][] assist {{-1, 0}, {0, -1}, {1, 0}, {0, 1}}; public static void main(String[] args) {Scanner sc new Scanner(System.in);//在此输入您的代码...int n sc.nextInt(), m sc.nextInt();int[][] matrix new int[n][m];boolean[][] vis new boolean[n][m];for(int i 0; i n; i){for(int j 0; j m; j){matrix[i][j] sc.nextInt();}}int ans 0, time 0;// 优先队列矩阵中数值较小的在堆顶PriorityQueueint[] queue new PriorityQueueint[]((a,b) - matrix[a[0]][a[1]] - matrix[b[0]][b[1]]);queue.offer(new int[]{0, 0});while(!queue.isEmpty()){int[] cur queue.poll();time matrix[cur[0]][cur[1]];for(int i 0; i 4; i){int x cur[0] assist[i][0];int y cur[1] assist[i][1];if(x 0 x n y 0 y m !vis[x][y]){queue.offer(new int[]{x, y});vis[x][y] true;matrix[x][y] matrix[cur[0]][cur[1]];} }}System.out.println(time);sc.close();}
}
