X

LEETCODE 1243. Array Transformation 解题思路分析

题目大意:

数组变换

首先,给你一个初始数组 arr。然后,每天你都要根据前一天的数组生成一个新的数组。

第 i 天所生成的数组,是由你对第 i-1 天的数组进行如下操作所得的:

  • 假如一个元素小于它的左右邻居,那么该元素自增 1。
  • 假如一个元素大于它的左右邻居,那么该元素自减 1。
  • 首、尾元素永不改变。

过些时日,你会发现数组将会不再发生变化,请返回最终所得到的数组。

示例 1:

输入:[6,2,3,4]
输出:[6,3,3,4]
解释:
 第一天,数组从 [6,2,3,4] 变为 [6,3,3,4]。
 无法再对该数组进行更多操作。

示例 2:

输入:[1,6,3,4,3,5]
输出:[1,4,4,4,4,5]
解释:
 第一天,数组从 [1,6,3,4,3,5] 变为 [1,5,4,3,4,5]。
 第二天,数组从 [1,5,4,3,4,5] 变为 [1,4,4,4,4,5]。
 无法再对该数组进行更多操作。

提示:

  • 1 <= arr.length <= 100
  • 1 <= arr[i] <= 100

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1243

解题思路分析:

这道题除了暴力解我没想到什么更好的算法。既然是暴力解,那么我们就跟着题目的叙述来一步一步的变换数组,变换的条件是,当前数如果小于左右两边的数字,当前数加一,反之则减一,需要注意一点,当前数变换之后可能会影响到后一个数字,因此在当天的变换中,为了不影响其他数字的变换,我们应该copy出一个新的数组,按照原数组的状态,更新新的数组,在当天的变换全部完成之后,再将这个新的数组赋值给原数组,直到不能再变换为止,返回最后的数组即可。

实现代码:

public List<Integer> transformArray(int[] arr) {
    while(true){ // 循环每一天
        boolean hasFixed = false; // 记录当天是否有能改变的数字
        // 拷贝一份原数组
        int[] temp = Arrays.copyOf(arr, arr.length);
        // 除去首尾,循环原数组的每一个数字
        for(int i=1;i<arr.length-1;i++){
            int current=arr[i]; // 当前数字
            int left=arr[i-1]; // 左边的数字
            int right=arr[i+1]; // 右边的数字
            // 如果当前数大于左右两边
            if(current>left&&current>right){
                temp[i] = arr[i]-1; // 当前数减一赋值给新数组
                hasFixed = true; // 当天出现数字更改
            }
            // 如果当前数小于左右两边
            else if(current<left&&current<right){
                temp[i] = arr[i]+1; // 当前数加一赋值给新数组
                hasFixed = true; // 当天出现数字更改
            }
        }
        arr = temp; // 将新数组赋值给原数组
        if(!hasFixed) break; // 如果当天没有更改数字,退出
    }
    // 将数组变为list返回
    List<Integer> res = new ArrayList<>();
    for(int n : arr) res.add(n);
    return res;
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 95.06% of Java online submissions for Array Transformation.

Memory Usage: 34.9 MB, less than 100.00% of Java online submissions for Array Transformation.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-1243-array-transformation-解题思路分析/
Categories: leetcode
kwantong: