网站设计想法,显示佣金的网站是怎么做的,网站建设管理相关规定,查询网站信息某店铺将用于组成套餐的商品记作字符串 goods#xff0c;其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。 返回结果 无顺序要求#xff0c;但不能含有重复的元素。 示例 1: 输入#xff1a;goods “agew” 输出#xff1a;[“aegw”,“aewg”,“ag… 某店铺将用于组成套餐的商品记作字符串 goods其中 goods[i] 表示对应商品。请返回该套餐内所含商品的 全部排列方式 。 返回结果 无顺序要求但不能含有重复的元素。 示例 1: 输入goods “agew” 输出[“aegw”,“aewg”,“agew”,“agwe”,“aweg”,“awge”,“eagw”,“eawg”,“egaw”,“egwa”,“ewag”,“ewga”,“gaew”,“gawe”,“geaw”,“gewa”,“gwae”,“gwea”,“waeg”,“wage”,“weag”,“wega”,“wgae”,“wgea”] 我的原始人解法遍历回溯其实就相当于有几个字母就进行几重循环用 set 记录每种结果来去重用另一个 set 来排除已使用字母并在使用后回溯 char[] data;// 结果 setSetString ans new HashSet();// 回溯 setSetInteger set new HashSet();public String[] goodsOrder(String goods) {data goods.toCharArray();dfs(,0);String[] res new String[ans.size()];res ans.toArray(res);return res;}// cur:当前组合的字符串从空字符串开始拼接public void dfs(String cur){// 根据字符串长度判断是否已经组成一个可能// 是就记录到结果 setif(cur.length()data.length){ans.add(cur);return;}for(int i0;idata.length;i){// 递归到下一层时依旧从 0~data.length 遍历但是不能使用上一层已使用过的字符if(set.contains(i))continue;// 排除已使用的set.add(i);dfs(curdata[i]);// 复原保证每个字符都有机会成为头部字符即无遗漏set.remove(i);}}他人题解为了方案不遗漏我们还可以通过固定第一位字符再考虑剩下的字符的所有排列情况再固定下一位考虑剩下的所有情况…而所有情况的排列我们通过原地交换字符来实现这个算法的核心有一点固定某位字符也可以看做交换比如第 0 位和第 0 位交换所以本质上我们就是通过从字符第 0 位到末尾第 n 位都尝试交换0与0,0与1,0与2,0与3…递归后尝试第 1 位到第 n 位的所有交换1与1,1与2,1与3…再递归尝试第 2 位到第 n 位交换的所有可能以此保证每种可能性都不遗漏例如 abc我们先固定 a交换 0,0再固定 b交换 1,1最后剩下一位自然是直接可以返回一种结果了即 abc回溯到 b 时我们这次选择交换 1,2得到 acb再回溯到 a 时我们上次是交换 0,0这次我们选择交换 0,1即交换 ab此时为 [b,a,c]然后第二位的 a 也是从 1,1 开始交换再递归直接返回结果 bac再回溯到 a我们选择交换 1,2 了最终得到 bca然后又回溯到了最开始的 a这次要选择交换 0,2 得到 [c,b,a]…为了排除重复方案我们在固定某个字符时只需要保证它在某一位固定一次就够了比如 aab你在最外层遍历到第二个 a其实就不需要再固定第二个 a 去递归了因为得到的结果一定是重复的固定 aa 其实就包含在固定 a 的结果中不是吗因此我们同样需要一个 set 来记录即剪枝操作防止重复记录 char[] data;ListString res new LinkedList();public String[] goodsOrder(String goods) {data goods.toCharArray();dfs(0);return res.toArray(new String[res.size()]);}public void dfs(int x){// 只剩一个字符了还组合什么直接返回if(xdata.length-1){res.add(String.valueOf(data));return;}SetCharacter set new HashSet();for(int ix;idata.length;i){if(set.contains(data[i]))continue;set.add(data[i]);// 交换以保证每种可能性不遗漏swap(i,x);// 开启下层递归即固定了第 0~x 位字符要去固定第 x1 位了dfs(x1);// 复原交换等别人用来进行其他的交换方式swap(i,x);}}void swap(int a, int b) {char tmp data[a];data[a] data[b];data[b] tmp;}
