当前位置:网站首页>Day31 LeetCode
Day31 LeetCode
2022-07-30 19:21:00 【太阳在坠落】
1. 数组序号转换
给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下:
- 序号从 1 开始编号。
- 一个元素越大,那么序号越大。如果两个元素相等,那么它们的序号相同。
- 每个数字的序号都应该尽可能地小。
分析:
先对arr进行复制并排序得到arr1,创建一个哈希表并对arr1进行遍历得到每个数字排序后的位置,然后创建一个数组res大小与arr相同,遍历arr,查找当前数字在哈希表中的value并把它value写进res的当前位置中。
class Solution {
public int[] arrayRankTransform(int[] arr) {
int[] sortedArr = new int[arr.length];
System.arraycopy(arr, 0, sortedArr, 0, arr.length);
Arrays.sort(sortedArr);
Map<Integer, Integer> ranks = new HashMap<Integer, Integer>();
int[] ans = new int[arr.length];
for (int a : sortedArr) {
if (!ranks.containsKey(a)) {
ranks.put(a, ranks.size() + 1);
}
}
for (int i = 0; i < arr.length; i++) {
ans[i] = ranks.get(arr[i]);
}
return ans;
}
}
2. 完全平方数
给你一个整数 n ,返回和为 n 的完全平方数的最少数量 。完全平方数是一个整数,其值等于另一个整数的平方;换句话说,其值等于一个整数自乘的积。例如,1、4、9 和 16 都是完全平方数,而 3 和 11 不是。
示例:
输入:n = 12
输出:3
解释:12 = 4 + 4 + 4
分析:
动态规划:
- 首先初始化长度为 n+1 的数组 dp,每个位置都为 0
- 如果 n 为 0,则结果为 0
- 对数组进行遍历,下标为 i,每次都将当前数字先更新为最大的结果,即 dp[i]=i,比如 i=4,最坏结果为 4=1+1+1+1 即为 4 个数字
- 动态转移方程为:dp[i] = MIN(dp[i], dp[i - j * j] + 1),i 表示当前数字,j*j 表示平方数
class Solution {
public int numSquares(int n) {
int[] dp = new int[n+1];
dp[0] = 0;
for (int i = 1; i < dp.length; i++) {
dp[i] = i;
for (int j = 1; i-j*j>=0; j++) {
dp[i] = Math.min(dp[i], dp[i - j*j]+1);
}
}
return dp[n];
}
}
3. 有效的正方形
给定2D空间中四个点的坐标 p1, p2, p3 和 p4,如果这四个点构成一个正方形,则返回 true 。点的坐标 pi 表示为 [xi, yi] 。输入不是按任何顺序给出的。一个有效的正方形有四条等边和四个等角(90度角)。
分析:
求出6条边,四条边长和两条对角线。边长相等的只有正方形和菱形,对角线又相等的只有正方形
所以排序判断边长以及对角线是否相等即可。
class Solution {
public long len(int[] x,int[] y){
return 1L * (x[0] - y[0]) * (x[0] - y[0]) + 1L * (x[1] - y[1]) * (x[1] - y[1]);
}
public boolean validSquare(int[] p1, int[] p2, int[] p3, int[] p4) {
if(p1[0] == p2[0] && p1[1] == p2[1]) return false;
long[] l = new long[6];
l[0] = len(p1,p2);
l[1] = len(p1,p3);
l[2] = len(p1,p4);
l[3] = len(p2,p3);
l[4] = len(p2,p4);
l[5] = len(p3,p4);
Arrays.sort(l);
return l[0] == l[1] && l[0] == l[2] && l[0] == l[3] && l[4] == l[5];
}
}
边栏推荐
- 牛客刷题系列之进阶版(组队竞赛,排序子序列,倒置字符串, 删除公共字符,修理牧场)
- OMP: Error #15: Initializing libiomp5md.dll, but found libiomp5md.dll already initialized.解决方法
- 架构师如何成长
- Google's AlphaFold claims to have predicted almost every protein structure on Earth
- Start background services across processes
- 【刷题篇】计算质数
- 在华为云,见证迷你世界的神奇觉醒
- MindSpore:npu 多卡训练自定义数据集如何给不同npu传递不同数据
- redis
- 【MindSpore1.2.0-rc1产品】num_workers问题
猜你喜欢
OMP: Error #15: Initializing libiomp5md.dll, but found libiomp5md.dll already initialized.解决方法
[hbuilder] cannot run some projects, open the terminal and cannot enter commands
The Meta metaverse division lost 2.8 billion in the second quarter!Still want to keep betting?Metaverse development has yet to see a way out!
Delay queue optimization (2)
Scrapy framework is introduced
云数据库和本地数据库有什么区别?
6 yuan per catty, why do Japanese companies come to China to collect cigarette butts?
VBA connects Access database and Excel
生物医学论文有何价值 论文中译英怎样翻译效果好
【Prometheus】Prometheus联邦的一次优化记录[续]
随机推荐
JsonUtil基于字符串操作josn
电脑死机的时候,发生了什么?
The use of @ symbol in MySql
AI Basics: Graphical Transformer
看完《二舅》,我更内耗了
LeetCode 0952. Calculate Maximum Component Size by Common Factor: Mapping / Union Search
试写C语言三子棋
Scala学习:breakable
第一次进入小程序判断
Listen to the boot broadcast
What is a RESTful API?
什么是 RESTful API?
How architects grow
MindSpore:数据处理问题
Swiper轮播图片并播放背景音乐
Perfectly Clear QuickDesk & QuickServer图像校正优化工具
ImportError:attempted relative import with no known parent package
LocalDate时间生成
After 23 years of operation, the former "China's largest e-commerce website" has turned yellow...
Scrapy framework is introduced