LeetCode-第 18 场双周赛

LeetCode-第 18 场双周赛

Scroll Down

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
  • -10^5 <= nums[i] <= 10^5

个人思路

没有思路,没做出来

AC代码


题目链接:https://leetcode-cn.com/problems/reverse-subarray-to-maximize-array-value/

支付宝 微信