LeetCode 996. 正方形数组的数目

截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

LeetCode 996. 正方形数组的数目
这题是让打乱数组的顺序,打乱之后的数组如果所有的前后两个数字之和是一个完全平方数,那么这个打乱的数组就是正方形数组,这里让求的是正方形数组是个数。


这里我们可以使用回溯算法来解决,我之前专门讲过450,什么叫回溯算法,一看就会,一写就废,回溯算法我们可以把它看做是一棵N叉树,也就是说每个节点最多有N个子节点,然后使用DFS进行遍历。对于这道题我们以示例1为例来看个视频
视频链接
LeetCode 996. 正方形数组的数目
看懂了这个,这题就非常简单了,之前在讲450题回溯算法的时候,总结了一个模板

private void backtrack("原始参数") {
    //终止条件(递归必须要有终止条件)
    if ("终止条件") {
        //一些逻辑操作(可有可无,视情况而定)
        return;
    }

    for (int i = "for循环开始的参数"; i < "for循环结束的参数"; i++) {
        //一些逻辑操作(可有可无,视情况而定)

        做出选择

        //递归
        backtrack("新的参数");
        //一些逻辑操作(可有可无,视情况而定)

        撤销选择
    }
}

这道题完全可以使用这个模板,每次从数组中选择元素的时候,只能选择未使用的,使用过的则直接跳过,模板的终止条件就是所有元素都访问完了。我们来看下完整代码

//统计正方形数组的个数
int count = 0;

public int numSquarefulPerms(int[] nums) {
    //先对数组进行排序,目的是过滤掉重复的
    Arrays.sort(nums);
    backtrack(nums, new boolean[nums.length], 0, -1);
    return count;
}

/**
 * @param nums
 * @param visited 标记某个数字是否被使用过
 * @param index   当前数字的下标
 * @param preNum  打乱数组的前一个数字
 */
private void backtrack(int[] nums, boolean[] visited, int index, int preNum) {
    //如果数字都访问完了,说明这个打乱的数组是一个正方形数组
    if (index == nums.length) {
        count++;
        return;
    }
    for (int i = 0; i < nums.length; i++) {
        //如果当前数字被访问过,直接跳过
        if (visited[i])
            continue;
        //如果当前数字和前一个数字不能构成完全平方数,直接跳过
        if (preNum > 0 && !isSquare(preNum + nums[i]))
            continue;
        //这里是为了过滤掉重复的,比如数组[2,2,7,9],我们选择了
        //[2,7(第一个2)]和[2,7(第二个2)],剩下的数字都是一样的,
        //所以他们的组合也是一样的,会出现重复,我们需要过滤掉
        if ((i > 0 && nums[i] == nums[i - 1] && !visited[i - 1]))
            continue;
        //选择当前数字,标记为已经被使用过
        visited[i] = true;
        //递归,进行到下一层
        backtrack(nums, visited, index + 1, nums[i]);
        //回到上一层,撤销选择
        visited[i] = false;
    }
}

//判断数字num是否是完全平方数
private boolean isSquare(int num) {
    int sqr = (int) Math.sqrt(num);
    return sqr * sqr == num;
}

上面有一行代码过滤掉重复的,其实就是剪枝,我们看一下如果相同的数字,在前一个分支遍历过,那么在当前分支就不要再次遍历了,否则会出现重复的,如下图所示。上面代码过滤的时候使用

!visited[i-1]和使用visited[i-1]都是可以的,只不过这两种剪枝方式是不一样的,一个是把整个大枝剪掉,一个是在每个大枝下面不停的剪小枝,这个后面讲有重复数据的全排列的时候在详细介绍。

LeetCode 996. 正方形数组的数目

上一篇:“运愁维卧”,决胜千里 | TcaplusDB 724运维日致敬每一位运维人


下一篇:Android经典面试题详解:Android热修复原理