当前位置:网站首页>Day31 LeetCode
Day31 LeetCode
2022-07-30 19:41:00 【the sun is falling】
1. 数组序号转换
给你一个整数数组 arr ,请你将数组中的每个元素替换为它们排序后的序号.
序号代表了一个元素有多大.序号编号的规则如下:
- 序号从 1 开始编号.
- 一个元素越大,那么序号越大.如果两个元素相等,那么它们的序号相同.
- 每个数字的序号都应该尽可能地小.
分析:
先对arrDuplicate and sort to getarr1,Create a hash table and comparearr1Iterate over to get the sorted position of each number,然后创建一个数组res大小与arr相同,遍历arr,Find the current number in the hash tablevalue并把它value写进resin the current location of.
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] .Inputs are not given in any order.A valid square has four equal sides and four equal angles(90度角).
分析:
求出6条边,Four side lengths and two diagonals.Only squares and rhombus have sides of equal length,Only squares have equal diagonals
Therefore, the sorting can determine whether the side lengths and the diagonals are equal.
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];
}
}
边栏推荐
猜你喜欢
【PyTorchVideo教程01】快速实现视频动作识别
HCIP --- 企业网的三层架构
MySQL six-pulse sword, SQL customs clearance summary
牛客刷题系列之进阶版(组队竞赛,排序子序列,倒置字符串, 删除公共字符,修理牧场)
SimpleOSS third-party library libcurl and engine libcurl error solution
Zabbix 5.0 监控教程(一)
Download and installation of the latest version of MySQL 8.0 under Linux (detailed steps)
ELK日志分析系统
Linux下载安装mysql5.7版本教程最全详解
【MindSpore】多卡训练保存权重问题
随机推荐
部分分类网络性能对比
启动前台Activity
Brush questions record----string
VBA batch import Excel data into Access database
[hbuilder] cannot run some projects, open the terminal and cannot enter commands
MySQL sub-database sub-table
Alibaba Cloud Martial Arts Headline Event Sharing
【MindSpore】多卡训练保存权重问题
Difference between Object and Map
解决终极bug,项目最终能顺利部署上线。
Cesium loads offline maps and offline terrain
MindSpore:【MindSpore1.1】Mindspore安装后验证出现cudaSetDevice failed错误
Scala学习:类和对象
.eslintrc.js for musicApp
VS Code connects to SQL Server
The advanced version of the Niu Ke brushing series (team competition, sorting subsequences, inverting strings, deleting common characters, repairing pastures)
已删除
What is a RESTful API?
MindSpore:对image作normalize的目的是什么?
阿里云武林头条活动分享