作者：whisper

链接：http://proprogrammar.com:443/article/226

声明：请尊重原作者的劳动，如需转载请注明出处

    本章节中，我们提供了你可能希望在将来知道的与数组相关的更多数据结构或技术的列表。我们将继续发布更多的卡片并更新本文中的链接，以帮助你逐一征服这些主题。

    我们也为你准备了一些与数组/字符串相关的练习。请试着自己动手解决这些问题。

    数组相关的技术

    你可能想要了解更多与数组相关的数据结构或技术。我们不会深入研究这张卡片中的大多数概念，而是在本文中提供相应卡片的链接。

    1. 这里有一些其他类似于数组的数据结构，但具有一些不同的属性：

• 字符串（已包含在本卡片中）
• 哈希表
• 链表
• 队列
• 栈

    2. 正如我们所提到的，我们可以调用内置函数来对数组进行排序。但是，理解一些广泛使用的排序算法的原理及其复杂度是很有用的。

    3. 二分查找也是一种重要的技术，用于在排序数组中搜索特定的元素。

    4. 我们在这一章中引入了双指针技巧。想要灵活运用该技技巧是不容易的。这一技巧也可以用来解决：

• 链表中的慢指针和快指针问题
• 滑动窗口问题

    5. 双指针技巧有时与贪心算法有关，它可以帮助我们设计指针的移动策略。 在不久的将来，我们会提供更多的卡片来介绍上面提到的这些技术，并更新链接。

    旋转数组

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释: 
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]

说明:

• 尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
• 要求使用空间复杂度为 O(1) 的 原地 算法。

// 想法：直观想法：每次移动k个数，移动若干轮，移动nums.length次，使用一个辅助数组和辅助变量
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        if(k == 0)
        {
            return;
        }
        int round = nums.length / k;
        if(nums.length % k != 0)
        {
            round++;
        }

        int[] aidArr = new int[k];
        int switchTime = 0;
        int temp;
        for(int i = 0; i < k; i++)
        {
            aidArr[i] = nums[i];
        }

        for(int i = 0; round > i; i++)
        {
            for(int j = i * k; j < k * (i + 1) && switchTime < nums.length; j++, switchTime++)
            {
                temp = nums[(j + k) % nums.length];
                nums[(j + k) % nums.length] = aidArr[j % k];
                aidArr[j % k] = temp;
            }
        }
    }

    看一个更好的算法

public void rotate(int[] nums, int k) {
        k = k%nums.length;
        int[] newlist= new int[nums.length];
        System.arraycopy(nums,nums.length-k,newlist,0,k);
        System.arraycopy(nums,0,newlist,k,nums.length-k);
        System.arraycopy(newlist,0,nums,0,nums.length);
    }

    利用现有api，整体移动子数组，简单，效率高

    杨辉三角 II

给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。

在杨辉三角中，每个数是它左上方和右上方的数的和。

示例:

输入: 3
输出: [1,3,3,1]

进阶：

你可以优化你的算法到 O(k) 空间复杂度吗？

import java.math.BigInteger;

class Solution {
    // 想法：查相关资料可知：第n行的m个数可表示为 C(n-1，m-1)，第m行有m个数，第一，最末为1
    public List<Integer> getRow(int rowIndex) {
        List<Integer> result = new ArrayList<Integer>();
        
        if(rowIndex == 0){
            result.add(1);
            return result;
        }else if(rowIndex == 1){
            result.add(1);
            result.add(1);
            return result;
        }
        
        result.add(1);
        
        for(int i = 1; i <= rowIndex / 2; i++){
            result.add(zuhe(rowIndex, i));
        }
        
        for(int i = 0; i <= (rowIndex-1)/2; i++){
            result.add(result.get((rowIndex-1)/2 - i));
        }
        
        return result;
    }
    
    private int zuhe(int n, int m) {
		BigInteger bi = new BigInteger("1");
		
		for(int i = n; i > n - m; i--) {
			bi = bi.multiply(new BigInteger(String.valueOf(i)));
		}
		
		for(int i = m; i > 0; i--) {
			bi = bi.divide(new BigInteger(String.valueOf(i)));
		}
		
		return bi.intValue();
	}
}

    注意，要导入一个额外的包

    再看一种更好的算法

public List<Integer> getRow(int rowIndex) {
        List<Integer> list = new ArrayList<>(rowIndex+1);
        long cur = 1;
        for(int i=0;i<=rowIndex;i++){
            list.add((int)cur);
            cur = cur * (rowIndex-i)/(i+1);
        }
        return list;
    }

    也是利用我给的C(n-1, m-1)的公式，不同的是不是直接计算，而是利用上一项与当前项的关系计算，即C(n-1, m-1)与C(n-1, m)的关系来计算，效率很高

    翻转字符串里的单词

给定一个字符串，逐个翻转字符串中的每个单词。

示例 1：

输入: "the sky is blue"
输出: "blue is sky the"

示例 2：

输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

示例 3：

输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

说明：

• 无空格字符构成一个单词。
• 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
• 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

进阶：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

// 想法：利用jdk中的api
    public String reverseWords(String s) {
        if(s == null){
            return null;
        }else if(s.trim().length() == 0){
            return "";
        }
        
        s = s.trim();
        String[] sArr = s.split("[ ]+");
        
        StringBuilder sb = new StringBuilder();
        for(int i = sArr.length - 1; i >= 0; i--){
            sb.append(sArr[i]).append(" ");
        }
        sb.setLength(sb.length() - 1);
        
        return sb.toString();
    }

     String.split参数可以是正则表达式

    看另一种方法

public String reverseWords(String s) {
        if (null == s || s.length() == 0)
            return "";
        final char[] c = s.toCharArray();
        final int len = c.length;
        int i = len - 1;
        
        while (i >= 0 && c[i] == ' ') i--;

        int left = i + 1;
        int right = i + 1;
        StringBuffer sb = new StringBuffer(i + 1);
        
        
        for (; i >= 0; i--) {
            if (c[i] == ' ') {
                if (right != left) sb.append(c, left, right - left).append(" ");
                left = i;
                right = i;
                continue;
            }
            left = i;
        }
        if (right != left)
            return sb.append(c, left, right - left).toString();
        return sb.length() > 0 ? sb.substring(0, sb.length() - 1) : "";

    }

    比较常规的做法，一个字符一个字符处理，用到了StringBuffer（StringBuilder）中的append方法（三参数，处理字符数组）和substring方法

    反转字符串中的单词 III

给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。

示例 1:

输入: "Let's take LeetCode contest"
输出: "s'teL ekat edoCteeL tsetnoc" 

注意：在字符串中，每个单词由单个空格分隔，并且字符串中不会有任何额外的空格。

// 想法：利用jdk中的api
    public String reverseWords(String s) {
        if(s == null){
            return null;
        }else if(s.length() == 0){
            return s;
        }
        
        String[] sArr = s.split(" ");
        StringBuilder sb, result = new StringBuilder();
        
        for(int i = 0; i < sArr.length; i++){
            sb = new StringBuilder(sArr[i]);
            sb.reverse();
            result.append(sb.toString()).append(" ");
        }
        
        result.setLength(result.length() - 1);
        return result.toString();
    }

    利用现有api，StringBuilder的reverse,setLength,append；String的split

    看另一种算法

public static String reverseWords(String s) {
        char[] chars = s.toCharArray();
        int startIndex = 0;
        while (startIndex < s.length()){
            int endIndex = s.indexOf(' ', startIndex + 1);
            if(endIndex == -1){
                endIndex = s.length();
            }
            reverse(startIndex, endIndex, chars);
            startIndex = endIndex + 1;
        }
        return String.valueOf(chars);

    }

    private static void reverse(int startIndex, int endIndex, char[] chars) {
        for(int i = startIndex, k= endIndex-1; i < k; i++, k--){
            char temp = chars[i];
            chars[i] = chars[k];
            chars[k] = temp;
        }

    }

    没有充分利用api，直接处理字符数组，但效率较高，用到了String.valueOf(char[])方法，String.toCharArray()方法

    删除排序数组中的重复项

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以“引用”方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

 

     本算法已经介绍过，文章地址：leetcode探索之数组类算法学习 做好初始定义

    移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

说明:

1. 必须在原数组上操作，不能拷贝额外的数组。
2. 尽量减少操作次数。

     本算法已经介绍过，文章地址：leetcode探索之数组类算法学习 做好初始定义

亲爱的读者：有时间可以点赞评论一下