[数据结构与算法]LeetCode.526 优美的排列

原题

https://leetcode-cn.com/problems/beautiful-arrangement/

思路

递归回溯
但是在做递归回溯之前一定要定义好数据模型
也就是递归的数据是什么，怎么判断是否满足题意，回溯的标识符是什么

定义一个boolean[]来表示当前数据是否被使用过，也就是回溯的标识符
定义一个map<Integer, List<Integer>>来表示当前位置现有满足题意的元素，也就是需要递归的数据


题解

package com.leetcode.code;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Code526 {

    public static void main(String[] args) {

    }

    static Map<Integer, List<Integer>> map;
    static boolean[] vis;
    static int num;

    public static int countArrangement(int n) {
//        定义一个标识，标识每个数字是否被使用过
        vis = new boolean[n+1];
//        定义一个map
//        key : index 表示当前位置
//        val : List<Integer> 表示当前位置满足题意的数字集合
        map = new HashMap<>();

//        为map准备数据，i表示下表，从j获取当前i这个位置满足题意的数字
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i%j==0 || j%i==0) {
                    List<Integer> list = map.getOrDefault(i, new ArrayList<>());
                    list.add(j);
                    map.put(i, list);
                }
            }
        }

        backtrack(1, n);
        return num;
    }

    private static void backtrack (int index, int n) {
        if (index == n+1) {
            num++;
            return;
        }
        for (int x : map.get(index)) {
            if (!vis[x]) {
                vis[x] = true;
                backtrack(index+1, n);
                vis[x] = false;
            }
        }
    }

}

写在最后，由于个人原因，懈怠了，6月份、7月份、8月份，刷题都是短短续续的，没有了以前的坚持！
昨天晚上痛定思痛，还是要坚持下去，不管能不能进大厂，都要养成良好的代码习惯学习习惯！
努力不一定有收获，但是不努力一定没有收获！
坚持吧！



看到6月份、7月份、8月份这些没提交的记录，都悔恨不已！