1.数组序号转换
题目描述
给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下：
序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。
示例 1：
输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。
示例 2：
输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。
示例 3：
输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]
提示：
0 <= arr.length <= 105
-109 <= arr[i] <= 109
个人思路
- 先开个一维数组ar复制一遍arr的元素
- 排序原数组
- 用map记录排序后各元素的位置（用map能保证元素不重复且序号是唯一的）
- 再遍历一遍ar数组，依次取出map中与ar[i]对应的value值
AC代码
class Solution {
public int[] arrayRankTransform(int[] arr) {
int []ar = new int [arr.length];
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < arr.length; i++) {
ar[i] = arr[i];
}
Arrays.sort(arr);
int index = 1;
for (int i = 0; i < arr.length; i++) {
if (map.get(arr[i]) == null) {
map.put(arr[i], index++);
}
}
for (int i = 0; i < ar.length; i++) {
ar[i] = map.get(ar[i]);
}
return ar;
}
}
题目链接：https://leetcode-cn.com/problems/rank-transform-of-an-array
2.破坏回文串
题目描述
给你一个回文字符串 palindrome ，请你将其中 一个 字符用任意小写英文字母替换，使得结果字符串的字典序最小，且 不是 回文串。
请你返回结果字符串。如果无法做到，则返回一个空串。
示例 1：
输入：palindrome = "abccba"
输出："aaccba"
示例 2：
输入：palindrome = "a"
输出：""
提示：
- 1 <= palindrome.length <= 1000
- palindrome 只包含小写英文字母。
个人思路
暴力枚举，由于回文串长度只有1000，那么将每个位置的字符依次替换成26个小写字母，判断替换后是否还是回文串，不是的话，加入集合，最后对集合进行排序，取出第一个就是字典序最小的
AC代码
class Solution {
public String breakPalindrome(String palindrome) {
if (palindrome == null || palindrome == "" || palindrome.length() == 1) {
return "";
}
StringBuffer sb = new StringBuffer();
List<String> list = new ArrayList<String>();
for (int i = 0; i < palindrome.length(); i++) {
for (int j = 1; j <= 26; j++) {
char ch = (char)(96 + j);
String s = sb.append(palindrome.substring(0, i)).append(ch).append(palindrome.substring(i + 1, palindrome.length())).toString();
if (!isPalindrome(s)) {
list.add(s);
}
sb.setLength(0);
}
}
Collections.sort(list);
return list.get(0);
}
private boolean isPalindrome(String s) {
StringBuffer sb = new StringBuffer();
return sb.append(s).reverse().toString().equals(s);
}
}
题目链接：https://leetcode-cn.com/problems/break-a-palindrome/
3.将矩阵按对角线排序
题目描述
给你一个 m * n 的整数矩阵 mat ，请你将同一条对角线上的元素（从左上到右下）按升序排序后，返回排好序的矩阵。
示例 1：
输入
输入：mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
输出：[[1,1,1,1],[1,2,2,2],[1,2,3,3]]
提示
- m == mat.length
- n == mat[i].length
- 1 <= m, n <= 100
- 1 <= mat[i][j] <= 100
个人思路
- 从右上角出发，标记两个点A(aR, aC)，B(bR, bC)
- A点的行动轨迹是：向左走，直到A点的列(aC)为零，再向下走，结束位置再左下角
- B点的行东轨迹是：向下走，直到B点的行(bR == 矩阵的行数)，再向左走，结束位置也在左下角
- A，B两点每次走一步
- 取出左上方A点到右下方B点这条对角线的所有元素，排序后沿对角线赋值
AC代码
class Solution {
public int[][] diagonalSort(int[][] mat) {
int aR = 0, aC = mat[0].length - 1, bR = 0, bC = mat[0].length - 1;
int endR = mat.length - 1;
int endC = mat[0].length - 1;
while (aR != endR + 1) {
function(mat, aR, aC, bR, bC);
aR = (aC == 0) ? aR + 1 : aR;
aC = (aC == 0) ? aC : aC - 1;
bR = (bR == endR) ? bR : bR + 1;
bC = (bR == endR) ? bC - 1 : bC;
}
return mat;
}
private void function(int [][]mat, int aR, int aC, int bR, int bC) {
List<Integer> list = new ArrayList<Integer>();
int a = aR, b = aC, c = bR, d = bC;
while (a != c + 1) {
list.add(mat[a++][b++]);
}
Collections.sort(list);
int index = 0;
while (aR != bR + 1) {
mat[aR++][aC++] = list.get(index++);
}
}
}
题目链接：https://leetcode-cn.com/problems/sort-the-matrix-diagonally/
4.翻转子数组得到最大的数组值
题目描述
给你一个整数数组 nums 。「 数组值」定义为所有满足 0 <= i < nums.length-1 的 |nums[i]-nums[i+1]| 的和。
你可以选择给定数组的任意子数组，并将该子数组翻转。但你只能执行这个操作 一次 。
请你找到可行的最大 数组值 。
示例 1：
输入：nums = [2,3,1,5,4]
输出：10
解释：通过翻转子数组 [3,1,5] ，数组变成 [2,5,1,3,4] ，数组值为 10 。
示例 2：
输入：nums = [2,4,9,24,2,1,10]
输出：68
提示
- 1 <= nums.length <= 3*10^4
- -105 <= nums[i] <= 105
个人思路
没有思路，没做出来
AC代码
题目链接：https://leetcode-cn.com/problems/reverse-subarray-to-maximize-array-value/
Q.E.D.
