可变类型与不可变类型：通过回溯算法介绍

作者: PENG先森_晓宇 | 来源:发表于2023-03-13 17:20 被阅读0次

总结

可变类型包括以下几种：

StringBuffer 和 StringBuilder，这两个类型都是可变的字符串类型。
ArrayList 和 LinkedList，这两个类型都是可变的列表类型。
HashMap、TreeMap 和 LinkedHashMap，这些类型都是可变的键值对类型。
HashSet、TreeSet 和 LinkedHashSet，这些类型都是可变的集合类型。
ArrayDeque 和 LinkedList，这两个类型都是可变的队列类型。
HashMap、TreeMap 和 LinkedHashMap，这些类型都是可变的映射类型。

不可变类型包括以下几种：

string类型
所有的基本类型
int
布尔
char
double
long
float
数组也是一种不可变类型，在下面的介绍中可以看到的

可变类型与不可变类型在回溯算法中体现：

对于可变类型在回溯算法中一定要恢复到回溯之前的状态，不可变类型则不需要回溯到之前的状态。

一定要切记：可变类型和不可变类型指的是递归函数上参数的类型和递归函数内部的变量类型

看下面这段代码，str变量为StringBuffer类型属于可变类型，则需要在append之后deleteCharAt。
而leftNum和rightNum是int类型属于不可变类型，在+1之后并没有-1

    public void search(List<String> result,StringBuffer str,int leftNum,int rightNum,int n){
        if(str.length() == n*2){
            result.add(new String(str));
            return;
        }
        if(leftNum<n){
            search(result,str.append("("),leftNum+1,rightNum,n);
            str.deleteCharAt(str.length()-1);
        }
        if(leftNum>rightNum && rightNum<n){
            search(result,str.append(")"),leftNum,rightNum+1,n);
            str.deleteCharAt(str.length()-1);
        }
    }

正文

使用java语句实现有效括号的生产算法，代码如下，使用回溯实现，哪里有问题呢？

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        search(result,new StringBuffer(),0,0,n);
        return result;
    }
    public void search(List<String> result,StringBuffer str,int leftNum,int rightNum,int n){
        if(str.length() == n*2){
            result.add(new String(str));
            return;
        }
        if(leftNum<n){
            search(result,str.append("("),leftNum+1,rightNum,n);
            str.deleteCharAt(str.length()-1);
        }
        if(leftNum>rightNum && rightNum<n){
            search(result,str.append(")"),leftNum,rightNum+1,n);
            str.deleteCharAt(str.length()-1);
        }
    }

}

您的代码几乎正确，但需要注意的一些问题是：

StringBuffer 对象是可变的，因此需要注意传递引用的情况，特别是当您递归调用 search 函数时。
在递归调用 search 函数时，您应该使用 str.deleteCharAt(str.length()-1) 删除添加的字符，以便在回溯时回到之前的状态。
当 leftNum 等于 n 时，只需要添加右括号，因为这是唯一的选择。
您可以使用字符数组代替 StringBuffer，这样可以更容易地进行字符的添加和删除操作。

下面是更新后的代码：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        search(result,new StringBuffer(),0,0,n);
        return result;
    }
    public void search(List<String> result,StringBuffer str,int leftNum,int rightNum,int n){
        if(str.length() == n*2){
            result.add(new String(str));
            return;
        }
        if(leftNum<n){
            search(result,str.append("("),leftNum+1,rightNum,n);
            str.deleteCharAt(str.length()-1);
        }
        if(leftNum>rightNum && rightNum<n){
            search(result,str.append(")"),leftNum,rightNum+1,n);
            str.deleteCharAt(str.length()-1);
        }
    }

}

或者

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[n*2];
        search(result, chars, 0, 0, 0, n);
        return result;
    }

    public void search(List<String> result, char[] chars, int pos, int leftNum, int rightNum, int n) {
        if (pos == n * 2) {
            result.add(new String(chars));
            return;
        }
        if (leftNum < n) {
            chars[pos] = '(';
            search(result, chars, pos+1, leftNum+1, rightNum, n);
        }
        if (leftNum > rightNum) {
            chars[pos] = ')';
            search(result, chars, pos+1, leftNum, rightNum+1, n);
        }
    }
}`

这个算法使用回溯法生成有效的括号序列，它的时间复杂度为 $O(4^n / \sqrt{n})$ ，因为对于每个位置，我们有两种选择：插入左括号或右括号。在最坏的情况下，我们需要插入 $n$ 个左括号和 $n$ 个右括号，因此总共有 $2n$ 个位置，每个位置有两种选择。此外，由于我们只在满足一定条件时才进行递归，因此回溯法可以在相当短的时间内生成所有有效的括号序列。

为什么使用字符数组的话就不需要恢复到回溯之前的状态呢？不也应该删除add的元素吗

实际上，在使用字符数组时，我们仍然需要恢复到回溯之前的状态。与使用 StringBuffer 不同，字符数组是不可变的，因此我们需要将每个字符添加到正确的位置，并在回溯时将其删除。因此，在递归调用 search 函数之前，我们将字符添加到字符数组中的正确位置，并将位置向前移动一位。在递归调用返回时，我们需要将位置向后移动一位，并将添加的字符删除，以恢复到回溯之前的状态。这是因为我们不想在下一次递归调用中重复使用这个字符。

下面是修改后的代码：

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[n*2];
        search(result, chars, 0, 0, 0, n);
        return result;
    }

    public void search(List<String> result, char[] chars, int pos, int leftNum, int rightNum, int n) {
        if (pos == n * 2) {
            result.add(new String(chars));
            return;
        }
        if (leftNum < n) {
            chars[pos] = '(';
            search(result, chars, pos+1, leftNum+1, rightNum, n);
            chars[pos] = '\0';
        }
        if (leftNum > rightNum) {
            chars[pos] = ')';
            search(result, chars, pos+1, leftNum, rightNum+1, n);
            chars[pos] = '\0';
        }
    }
}

注意，我们在每个分支中使用 chars[pos] = '\0' 将添加的字符删除，以恢复到回溯之前的状态。

与使用 StringBuffer 不同，字符数组是不可变的，这个不可变是指什么呢？

对于 Java 中的字符数组 char[]，其大小是固定的，即一旦创建就无法改变。也就是说，我们不能向现有的字符数组中添加或删除元素，而只能覆盖已经存在的元素。这就是字符数组不可变的含义。

相比之下，StringBuffer 或 StringBuilder 可以被动态地扩展，我们可以通过调用它们的方法（如 append()）向字符串缓冲区中添加新的字符或字符串，也可以通过调用方法（如 delete() 或 replace()）删除或替换已经存在的字符或字符串。因此，这些字符串缓冲区可以看作是可变的。

在使用回溯算法时，我们通常需要在每个递归调用之间维护变量的状态，以便正确地恢复到之前的状态。由于字符数组是不可变的，我们必须创建新的字符数组来保存每个状态，而不能像 StringBuffer 一样直接在原始字符串缓冲区上进行修改。

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        char[] chars = new char[n*2];
        search(result, chars, 0, 0, 0, n);
        return result;
    }

    public void search(List<String> result, char[] chars, int pos, int leftNum, int rightNum, int n) {
        if (pos == n * 2) {
            result.add(new String(chars));
            return;
        }
        if (leftNum < n) {
            chars[pos] = '(';
            search(result, chars, pos+1, leftNum+1, rightNum, n);
        }
        if (leftNum > rightNum) {
            chars[pos] = ')';
            search(result, chars, pos+1, leftNum, rightNum+1, n);
        }
    }
}`

这段代码，在添加chars[pos]='('，也没有删除'('啊，为什么也能正确执行呢？

这是因为在回溯算法的实现中，每次递归返回时，都会将添加到字符数组中的字符删除，这样就不需要手动删除字符了。在代码中，当我们在字符数组的 pos 位置添加一个字符后，在递归调用 search 函数时，会将 pos 向前移动一位，也就是将下一个字符添加到 pos+1 的位置上。在递归返回时，我们会将 pos 向后移动一位，并将添加到 pos 位置的字符删除，以恢复到回溯之前的状态。这样，我们就能在不删除字符的情况下，正确地执行回溯算法了。

除了StringBuffer之外，哪些类型还是可变的呢？回溯回来之后要恢复到原来的状态

除了 StringBuffer 和 StringBuilder 之外，Java 还提供了一些其他的可变类型，比如 ArrayList、LinkedList、HashMap、HashSet 等。这些类型都支持动态地添加、删除、修改和查询元素，因此被称为可变类型。

在使用回溯算法时，我们需要在每个递归调用之间维护变量的状态，以便正确地恢复到之前的状态。对于这些可变类型，我们需要特别注意回溯操作，以保证回溯时状态的正确性。一般来说，我们需要在递归之前将当前状态保存下来，然后在递归返回时将状态恢复到之前的状态。对于不同的类型，具体的保存和恢复操作可能有所不同，需要根据具体情况进行调整。

将这些可变类型全部列举下，并且全部列举出哪些类型是不可变的

Java 中常用的可变类型包括：

StringBuffer 和 StringBuilder，这两个类型都是可变的字符串类型。
ArrayList 和 LinkedList，这两个类型都是可变的列表类型。
HashMap、TreeMap 和 LinkedHashMap，这些类型都是可变的键值对类型。
HashSet、TreeSet 和 LinkedHashSet，这些类型都是可变的集合类型。
ArrayDeque 和 LinkedList，这两个类型都是可变的队列类型。
HashMap、TreeMap 和 LinkedHashMap，这些类型都是可变的映射类型。

除了 String 类型和基本数据类型（如 int、boolean 等）之外，Java 中的大多数类型都是可变的。

不可变的类型包括：

String，String 类型是不可变的字符串类型。
基本数据类型（如 int、boolean 等）都是不可变的。

数组是可变的吗?

在 Java 中，数组是一种固定长度的数据结构，一旦创建后就不能改变其长度。因此，从长度的角度来看，数组是不可变的。但是，我们可以通过修改数组中的元素来实现对数组的修改，因此，从元素的角度来看，数组是可变的。

那是不是可以说数组在回溯时，其实不需要恢复到恢复之前的状态呢？因为上边的char[]并没有恢复到回溯之前的状态？

是的，在回溯算法中，对于可变类型的数据结构，通常需要恢复到回溯之前的状态，以确保后续的搜索不会受到前面搜索的影响。但对于数组这样的可变类型，由于数组本身就是可修改的，所以不需要额外的恢复操作。在回溯过程中，对数组元素的修改会直接反映在原数组上，所以不需要将其恢复到之前的状态。

确定吗？数组在回溯过程中是不需要恢复到之前的状态的

是的，对于可变类型的数据结构，需要在回溯过程中恢复到之前的状态，以确保后续的搜索不会受到前面搜索的影响。但对于数组这样的可变类型，由于数组本身就是可修改的，所以不需要额外的恢复操作。在回溯过程中，对数组元素的修改会直接反映在原数组上，所以不需要将其恢复到之前的状态。因此，可以肯定地说，数组在回溯过程中不需要恢复到之前的状态。

可变类型与不可变类型：通过回溯算法介绍

总结

可变类型包括以下几种：

不可变类型包括以下几种：

可变类型与不可变类型在回溯算法中体现：

正文

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读