今年腾讯的笔试题，求大佬解答。

Question

输入是两个正整数n和k，把从1到2n这2n个数平均分成两份(每份n个数)，每份分别排序，排序完成后的数组假设叫a和b，要求abs(ai-bi)>=k, (相同位置的数差的绝对值不少于k),输出有多少种分法。
当时没想出算法另外这种和组合方式有关的问题感觉都不太会做，有大佬指点该去哪找针对性的练习么

Answer 1

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;public class Test {
    private static int count = 0;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        System.out.println("请输入n的值：");
        int n=sc.nextInt();
        System.out.println("请输入k的值：");
        int k=sc.nextInt();
        int[] muns=new int[2*n];
        for(int i=0;i<muns.length;i++){
            muns[i]=i+1;
        }
        count(0,"",muns,n,k);
    }    //判断值是否存在于list中
    public static boolean isNumIn(List<Integer> list,int n){
        for(int i=0;i<list.size();i++){
            if(n==list.get(i))
                return true;
        }
        return false;
    }    //求出数组num的每个长度为n的子数组，并将剩下元素组成的数组与子数组进行比较，满足条件则输出
    public static void count(int i, String str, int[] num,int n,int k) {
        if(n==0){
            String strs[] = str.split(",");
            List<Integer> list = new ArrayList<>();
            for(int j=0;j<strs.length;j++){
                list.add(Integer.parseInt(strs[j]));
            }            //将剩下元素组成一个子数组
            List<Integer> list1 = new ArrayList<>();
            for(int j=0;j<num.length;j++){
                if(!isNumIn(list,num[j]))
                    list1.add(num[j]);
            }            if(isAbsNums(list,list1,k)){
                System.out.println("第"+(++count)+"种分法：");
                for(Integer e:list){
                    System.out.print(e+" ");
                }
                System.out.println();
                for(Integer e:list1){
                    System.out.print(e+" ");
                }
                System.out.println();
            }
            return;
        }
        if(i==num.length){
            return;
        }
        if(n-1==0)
            count(i+1,str+num[i],num,n-1,k);
        else
            count(i+1,str+num[i]+",",num,n-1,k);
        count(i+1,str,num,n,k);
    }    //判断两个list每个相同位置的值之差的绝对值是否大于等于k
    public static boolean isAbsNums(List<Integer> list1,List<Integer> list2,int k){
        if(list1.size()!=list2.size())
            return false;
        for(int i=0;i<list1.size();i++){
            if(Math.abs(list1.get(i)-list2.get(i))<k)
                return false;
        }
        return true;
    }
}
输入的n比较小的话，比如10以下，可以跑出来，太大了跑起来就会卡死……暂时还没想到可优化的地方……

Answer 2

不用数组比较，首先在2个数组绝对值最大相差等于n最小差等于k，也就是说k<=x<=n,这就是绝对值的范围。
所以只要 n=C1X1+C2X2+...+Cn*Xn 满足该等式 ，就能满足要求 abs(ai-bi)>=k，具体算法自行推导吧。
（其中c为一个零或正整数,X1...Xn是k到n之间的正整数，X1=k,Xn=n）
这里用一个递归程序就行了。
import java.util.Scanner;public class test25 {
public static int count=0; public static void main(String[] args) {
// TODO Auto-generated method stub

Scanner sc=new Scanner(System.in);
System.out.println("请输入n的值：");
        int n=sc.nextInt();
        System.out.println("请输入k的值：");
        int k=sc.nextInt();
        for (int i=k;i<=n;i++) {
         Count(n,i);
        }
        System.out.println("一共有"+count+"种方法");
}
public static void Count(int n,int k) {
int sum=n;
for(int i=k;i<=n;i++) {
int isTrue=sum-i;
if(isTrue==0) {
count++;
break;
}else if(isTrue<0) {
break;
}else {
Count(isTrue,i );
}
}
}
}

Answer 3

绝对值X应该是   k<=X<=2n-1    比如 n=4 k=2    1,2,3,4和8,5,6,7 就是符合的一种分法。？？？     

Answer 4

数组A 1,2,3,4 B 8,5,6,7 和 A 2,1,3,4 B 5,8,6,7  算两种分法吗，也就是数值顺序不同就是一个分法，首先不管怎么分法最少有 
（比如K=n时只有一个  A 1234 B 5678）再重新排列顺序数组行调整和AB数组值对换的排列组合数 

Answer 5

楼主高中数学怎么样？
这个不是高中数学吧，都是矩阵列的知识了，等同算出来矩阵列（nx2xm维度）有多少种变化。

Answer 6

来个免编译器的js版本。
直接在现在这个浏览器里，按F12或ctrl+shift+i(command+option+i)，打开console（控制台），把代码复制进去就可出结果。
方法和楼上几位差不多，回溯法，无脑递归遍历所有的排列可能。考虑到
[1,2,3]、[4,5,6]和[4,5,6]、[1,2,3]是同一种排列方式，所以把1直接强行放到第一个数组里开始递归。若不是同一种方法，算出来的总排列数*2即可。这里算出n=10,k=3总数是9，有没有一样的？//递归计数
function count( i )
{
    //排列完成，计数+1，并输出前20种排列方式
    if( i > 2*n )
    {
        ++sum;
        if( sum <= 20 ) console.log( v1, v2 );
        return;
    }
    //尝试把i放到第一个数组里，比较abs(ai-bi)是否>=k
    let t =  Math.min(v1.length+1, v2.length) - 1;
    if( v1.length < n && ( t >= 0 &&  Math.abs( i - v2[t] ) >= k || t < 0 ) )
    {
        //调用递归
        v1.push( i );
        count( i + 1 );
        v1.pop();
    }
    //尝试把i放到第二个数组里，比较abs(ai-bi)是否>=k
    t =  Math.min(v1.length, v2.length+1) - 1;
    if( v2.length < n && t >= 0 &&  Math.abs( i - v1[t] ) >= k )
    {
        v2.push( i );
        count( i + 1 );
        v2.pop();
    }
}
var sum = 0, n = 10, k = 3;  //n和k的值
var v1 = [1], v2 = [];  //初始化两个数组，先把1放到第一个数组（因为本人认为[1,2,3]、[4,5,6]和[4,5,6]、[1,2,3]是同一种方式）
count(2);    //1已经排到v1中了，调用递归直接从2开始
console.log( `总共${sum}种方法.` );

Answer 7

绝对值不可能超过n，因为要分成2组n个数的队列，当绝对值超过n的话是不可能分成2组n数列的，也就是绝对值相差最大的2组数列就是1到n和n+1到2n，因为题目本身就是要求2列后排序的。

Answer 8

选出来n个数标记不能选，把每个数k范围内的数标记不能选，最后看未被标记的数是不是n。不知道对不对

Answer 9

由于所有的数值组合都是n而且部分排序的（必须从小到大的排序比较），所以等同 从 1至2n-k数列当中拿出 n-k 个数值与剩下的数值组成新数组B，剩下的就是素组A ，AB排序后满足要求即可以成为有效解，这样编程就可以了

Answer 10

确实，你说的对。我18楼的有问题，更改后确实是2927种，但算法不好，你的算法应该更好一些……
function count( i )
{
if( i > 2*n )
    {
++sum;
//if( sum <= 10 ) console.log( v1, v2 );
return;
    }
let t =  Math.min(v1.length+1, v2.length) - 1;
if( v1.length < n && ( t >= 0 && ( v1.length < v2.length && Math.abs( i - v2[t] ) >= k || v1.length >= v2.length ) || t < 0 ) )
    {
v1.push( i );
count( i + 1 );
v1.pop();
    }
t =  Math.min(v1.length, v2.length+1) - 1;
if( v2.length < n && t >= 0 && ( v2.length < v1.length && Math.abs( i - v1[t] ) >= k || v2.length >= v1.length ) )
    {
v2.push( i );
count( i + 1 );
v2.pop();
    }
}
var sum = 0, n = 10, k = 3;
var v1 = [1], v2 = [];
count(2); //1已经排到v1中了
console.log( `总共${sum}种方法.` );
直接在现在这个浏览器里，按F12或ctrl+shift+i(command+option+i)，打开console（控制台），把代码复制进去就可出结果。输出结果是2927。

Answer 11

package jp190410;public class MyClass
{
    static int n = 8; 
    static int k=10;
    static int gCount=0;
    static int[] b=new int[100];
    static int[] a=new int[100];
    
    public static void dfs(int step)
    {
//if(gCount>=500) return;
if (step>n)
{
    int n2=n/2;
    for (int i = 1; i <=n2; i++)
    {
if(Math.abs(a[i]-a[i+n2])<k) return;
    }
    
    gCount++;
    
    StringBuffer s1=new StringBuffer();
    s1.append("答案 "+String.format("%-4d",gCount)+" 数组a:[");
    for(int i=1;i<=n2;i++)
s1.append(String.format("%-4d", a[i]));
    s1.append("] 数组b:[");     
    for(int i=n2+1;i<=n;i++)
s1.append(String.format("%-4d", a[i]));     
    s1.append("]");
    System.out.print(s1.toString());
    System.out.println();
    s1.setLength(0);
    
    return;
}

for (int i = 1; i <= n*2; i++)
{
    if (b[i]==0)
    {
a[step]=i;
 if (a[step-1]>a[step])  continue;
 b[i]=1;
dfs(step+1);
b[i]=0;
    }
}
    }
    
    public static void main(String[] args)
    {
dfs(1);
    }}

Answer 12

          楼主，能够讲讲你面试的是什么岗位么？
          我做Java的，快2年了，做算法，感觉还是一窍不通，虽然当初大学时学过算法设计这门课。

Answer 13

测试可用,欢迎前辈指正
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;public class Test4 {
static int total = 0;
public static void main(String[] args) {
System.out.print("请输入n:");
Scanner s1 = new Scanner(System.in);
int n = s1.nextInt();
System.out.print("请输入k:");
Scanner s2 = new Scanner(System.in);
int k = s2.nextInt();
fenpei(n, k);
} public static void fenpei(int n, int k) {
if (k > n) {
System.out.println("无分配方案");
return;
}
List<Integer> list1 = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
// 初始化两个数组,临界条件为按顺序排列
for (int i = 1; i < 2 * n + 1; i++) {
if (i <= n) {
list1.add(i);
} else {
list2.add(i);
}
}
Map map = new HashMap<>();
map.put("list1", list1);
map.put("list2", list2);
print(map, n, k);
for (int i = 2; i <= n; i++) {
for (int j = n + 1; j <= 2 * n; j++) {
Map<String, List<Integer>> exchange = exchange(list1, list2, i - 1, j - n - 1);
if (ckeck(exchange, k)) {
print(exchange, n, k);
}
}
}
} private static void print(Map<String, List<Integer>> map, int n, int k) {
total += 1;
List<Integer> list1 = map.get("list1");
List<Integer> list2 = map.get("list2");
StringBuffer buffer1 = new StringBuffer();
StringBuffer buffer2 = new StringBuffer();
for (int i = 0; i < list1.size(); i++) {
int list1value = list1.get(i);
int list2value = list2.get(i);
buffer1.append(list1value).append("\t");
buffer2.append(list2value).append("\t");
}
System.out.println("n: " + n + "\tk: " + k + "\t第" + total + "种方案");
System.out.println(buffer1.toString());
System.out.println(buffer2.toString());
} private static boolean ckeck(Map<String, List<Integer>> map, int k) {
List<Integer> list1 = map.get("list1");
List<Integer> list2 = map.get("list2");
boolean flat = true;
for (int i = 0; i < list1.size(); i++) {
int list1value = list1.get(i);
int list2value = list2.get(i);
int abs = Math.abs(list1value - list2value);
if (k > abs) {
flat = false;
break;
}
}
return flat;
} private static Map<String, List<Integer>> exchange(List<Integer> list6, List<Integer> list7, int i, int j) {
List<Integer> list1 = new ArrayList<>(list6);
List<Integer> list2 = new ArrayList<>(list7);
Integer ivalue = list1.get(i);
Integer jvalue = list2.get(j);
list1.remove(i);
list2.remove(j);
int num = 0;
num = ivalue;
ivalue = jvalue;
jvalue = num;
list1.add(ivalue);
list2.add(0, jvalue);
Map<String, List<Integer>> map = new HashMap<>();
map.put("list1", list1);
map.put("list2", list2);
return map;
} public static List<Integer> paixu(List<Integer> list) {
Collections.sort(list);
return list;
}
}

Answer 14

最简单的，n=4 k=2 时的组合数 为 7 
3456-1278
1256-3478
1246-3578
1245-3678
1236-4578
1235-4678
1234-5678
数组AB前后对调的话就是14

Answer 15

之前的算法是弄成了整个数组有序，而题目里面只是要求数组a和b有序，没要求整个数组有序。package jp190410;public class MyClass
{
    static int n = 4; 
    static int k=2;
    static int gCount=0;
    static int[] b=new int[100];
    static int[] a=new int[100];
    
    public static void dfs(int step)
    {
//if(gCount>=500) return;
if (step>n*2)
{
    for (int i = 1; i <=n; i++)
    {
if(Math.abs(a[i]-a[i+n])<k) return;
    }
    
    for(int i=2;i<=n;i++) //检查数组a和b是否有序，默认是升序
    {
      if (a[i]<a[i-1] ) return;
      if (a[i+n]<a[i+n-1]) return;
    }
    
    gCount++;
    
    StringBuffer s1=new StringBuffer();
    s1.append("答案 "+String.format("%-4d",gCount)+" 数组a:[");
    for(int i=1;i<=n;i++)
s1.append(String.format("%-4d", a[i]));
    s1.append("] 数组b:[");     
    for(int i=n+1;i<=n*2;i++)
s1.append(String.format("%-4d", a[i]));     
    s1.append("]");
    System.out.print(s1.toString());
    System.out.println();
    s1.setLength(0);
    
    return;
}

for (int i = 1; i <= n*2; i++)
{
    if (b[i]==0)
    {
a[step]=i;
 b[i]=1;
dfs(step+1);
b[i]=0;
    }
}
    }
    
    public static void main(String[] args)
    {
dfs(1);
    }}

Answer 16

刚学java懵逼中，摩拜大佬。