开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 【解题报告】《LeetCode零基础指南》(第五讲) 指针 - Java -> 正文阅读

[数据结构与算法]【解题报告】《LeetCode零基础指南》(第五讲) 指针 - Java

在这里插入图片描述

一、1470. 重新排列数组

1.题目

1470. 重新排列数组

给你一个数组 nums ，数组中有 2n 个元素，按 [x1,x2,…,xn,y1,y2,…,yn] 的格式排列。
请你将数组按 [x1,y1,x2,y2,…,xn,yn] 格式重新排列，返回重排后的数组。

2.分析

定义两个变量 $j$ 和 $k$ ，分别记录遍历到的下标位置，初始化为：
$j = 0 ， k = l e n g t h > > 1 (表示 k 从 y 1 开始)$
创建一个与原数组相等长度的新数组。
遍历新数组，当前遍历的下标是偶数，将原数组 $j$ 位置的元素赋值给新数组，然后 $j$ 自增；
反之，当前遍历的下标是奇数，将原数组 $k$ 位置的元素赋值给新数组，然后 $k$ 自增。

3.代码

class Solution {
    public int[] shuffle(int[] nums, int n) {
        int length = nums.length;
        int[] res = new int[length];
        int i,j = 0,k = length >> 1;
        for (i = 0;i < length;i++){
            //偶数下标
            if ((i & 1) == 0){
                res[i] = nums[j++];
            } else {
                res[i] = nums[k++];
            }
        }
        return res;
    }
}

在这里插入图片描述

二、1929. 数组串联

1.题目

1929. 数组串联

给你一个长度为 n 的整数数组 nums 。请你构建一个长度为 2n 的答案数组 ans ，数组下标从 0 开始计数，对于所有 0 <= i < n 的 i ，满足下述所有要求：
ans[i] == nums[i]
ans[i + n] == nums[i]
具体而言，ans 由两个 nums 数组串联形成。
返回数组 ans 。

2.分析

创建一个原数组2倍长度的新数组，按题目给定的规则将元素赋值即可。

3.代码

class Solution {
    public int[] getConcatenation(int[] nums) {
        int i,length = nums.length;
        int[] res = new int[length << 1];
        for (i = 0;i < length;i++){
            res[i] = nums[i];
            res[i + length] = nums[i];
        }
        return res;
    }
}

在这里插入图片描述

三、1920. 基于排列构建数组

1.题目

1920. 基于排列构建数组

给你一个从 0 开始的排列 nums（下标也从 0 开始）。请你构建一个同样长度的数组 ans ，其中，对于每个 i（0 <= i < nums.length），都满足 ans[i] = nums[nums[i]] 。返回构建好的数组 ans 。
从 0 开始的排列 nums 是一个由 0 到 nums.length - 1（0 和 nums.length - 1 也包含在内）的不同整数组成的数组。

2.分析

题目的核心是 $a n s [i] = n u m s [n u m s [i]]$ ，创建相等长度新数组后，根据规则赋值即可。

3.代码

class Solution {
    public int[] buildArray(int[] nums) {
        int i,length = nums.length;
        int[] ans = new int[length];
        for (i = 0;i < length;i++){
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
}

在这里插入图片描述

四、1480. 一维数组的动态和

1.题目

1480. 一维数组的动态和

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。
请返回 nums 的动态和。

2.分析

从计算公式 $r u n n i n g S u m [i] = s u m (n u m s [0] \dots n u m s [i])$ 可以看出：
- 新数组当前下标对应的值=新数组前一个下标对应的值+原数组当前下标对应的值
- 即： $r u n n i n g S u m [i] = r u n n i n g S u m [i ? 1] + n u m s [i];$
这里要多考虑一个特殊情况：当 $i = 0$ 时， $r u n n i n g S u m [0] = n u m s [0];$

3.代码

class Solution {
    public int[] runningSum(int[] nums) {
        int i,length = nums.length;
        int[] runningSum = new int[length];
        runningSum[0] = nums[0];
        for (i = 1;i < length;i++){
            runningSum[i] = runningSum[i - 1] + nums[i];
        }
        return runningSum;
    }
}

在这里插入图片描述

五、剑指 Offer 58 - II. 左旋转字符串

1.题目

剑指 Offer 58 - II. 左旋转字符串

字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。

限制：
1 <= k < s.length <= 10000

2.分析

注意：因为Java中String是不可变的，所以每次对字符串的修改，都会产生新的字符串。
思路：先把要左旋的子串截出来，再拼接到原字符串的尾部。

3.代码

class Solution {
    public String reverseLeftWords(String s, int n) {
        String s1 = s.substring(0, n);
        String s2 = s.substring(n);
        return s2 + s1;
    }
}

在这里插入图片描述

六、1108. IP 地址无效化

1.题目

1108. IP 地址无效化

给你一个有效的 IPv4 地址 address，返回这个 IP 地址的无效化版本。
所谓无效化 IP 地址，其实就是用 “[.]” 代替了每个 “.”。

2.分析

Java中要对字符串进行比较灵活的操作，可以考虑以下两种方式：

将字符串转换成Char[] 数组的形式，然后用操作数组的方式进行操作。
通过StringBuilder来对字符串中的字符或子串进行增删操作。

3.代码

class Solution {
    public String defangIPaddr(String address) {
        StringBuilder sb = new StringBuilder();
        int i;
        for (i = 0;i < address.length();i++){
            if (address.charAt(i) == '.'){
                sb.append("[.]");
            } else {
                sb.append(address.charAt(i));
            }
        }
        return sb.toString();
    }
}

在这里插入图片描述

七、剑指 Offer 05. 替换空格

1.题目

剑指 Offer 05. 替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

2.分析

方法一
一行代码解决，调用String替换字符串的API： $s . r e p l a c e ()$
方法二
通过 $S t r i n g B u i l d e r$ 来进行拼接新字符串的操作

3.代码

方法一： $s . r e p l a c e ()$

class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "%20");
    }
}

在这里插入图片描述

方法二： $S t r i n g B u i l d e r$

class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        int i;
        for (i = 0;i < s.length();i++){
            char c = s.charAt(i);
            if (c == ' '){
                sb.append("%20");
            } else {
                sb.append(c);
            }
        }
        return sb.toString();
    }
}

在这里插入图片描述

八、1365. 有多少小于当前数字的数字

1.题目

1365. 有多少小于当前数字的数字

给你一个数组 nums，对于其中每个元素 nums[i]，请你统计数组中比它小的所有数字的数目。
换而言之，对于每个 nums[i] 你必须计算出有效的 j 的数量，其中 j 满足 j != i 且 nums[j] < nums[i] 。
以数组形式返回答案。

2.分析

复制原数组，产生新数组 $a n s$
对原数组 $n u m s$ 进行排序
遍历数组 $a n s$ ，通过二分查找，找出当前遍历的元素在原数组中的左边界（即小于目标值的最大值的下标值 + 1）
将左边界赋值给数组 $a n s$

3.代码

class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int i,length = nums.length;
        //复制数组
        int[] ans = new int[length];
        for (i = 0;i < length;i++){
            ans[i] = nums[i];
        }
        //将数组排序
        Arrays.sort(nums);
        for (i = 0;i < length;i++){
            //二分查找，小于当前数的下一个下标
            int count = binarySearch(ans[i],nums);
            ans[i] = count;
        }
        return ans;
    }

    private int binarySearch(int a, int[] nums) {
        int l = 0,r = nums.length - 1;
        int mid;
        while (l <= r){
            mid = l + (r - l) / 2;
            if (nums[mid] < a){
                l = mid + 1;
            } else if (nums[mid] >= a){
                r = mid - 1;
            }
        }
        return l;
    }
}

在这里插入图片描述

九、剑指 Offer 17. 打印从1到最大的n位数

1.题目

剑指 Offer 17. 打印从1到最大的n位数

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

2.分析

过程还是比较清晰的：

获取n位最大十进制数 $m a x$
新建长度为 $m a x$ 的新数组，遍历新数组，进行赋值： $a n s [i] = i + 1;$

那么，如何获取n位最大数呢？

可以看几组数据：
n max
1 0 * 10 + 9 = 9
2 9 * 10 + 9 = 99
3 99 * 10 + 9 = 999
4 999 * 10 + 9 = 9999
可以看出：求 $n$ 位数即循环 $n$ 次，每次都用 上一次循环得到的值 * 10 + 9。

3.代码

class Solution {
    public int[] printNumbers(int n) {
        int i,max = 0;
        for (i = 0;i < n;i++){
            max = max * 10 + 9;
        }
        int[] ans = new int[max];
        for (i = 0;i < ans.length;i++){
            ans[i] = i + 1;
        }
        return ans;
    }
}

在这里插入图片描述

十、1389. 按既定顺序创建目标数组

1.题目

1389. 按既定顺序创建目标数组

给你两个整数数组 nums 和 index。你需要按照以下规则创建目标数组：
目标数组 target 最初为空。
按从左到右的顺序依次读取 nums[i] 和 index[i]，在 target 数组中的下标 index[i] 处插入值 nums[i] 。
重复上一步，直到在 nums 和 index 中都没有要读取的元素。
请你返回目标数组。
题目保证数字插入位置总是存在。

2.分析

因为题目需要在任意位置插入元素，所以大体步骤分为两步：

通过 $A r r a y L i s t$ 集合来进行插入元素的操作： $l i s t . a d d (i n d e x [i], n u m s [i]);$
再将 $A r r a y L i s t$ 转换为一维数组返回

3.代码

class Solution {
    public int[] createTargetArray(int[] nums, int[] index) {
        int i,length = nums.length;
        List<Integer> list = new ArrayList<>();
        for (i = 0;i < length;i++){
            list.add(index[i],nums[i]);
        }
        int[] target = new int[length];
        for (i = 0;i < length;i++){
            target[i] = list.get(i);
        }
        return target;
    }
}