zhug 2022-01-09 21:31 采纳率: 66.7%
浏览 47
已结题

请用JAVA解决这个算法问题?

把数组[1,1,1,0,-1,-1,-1]通过交换元素位置,变成[-1,-1,-1,0,1,1,1]。要求只能遇到以下四种情况才可以交换位置:
(1,0)→(0,1)
(0,-1)→(-1,0)
(1,-1,0)→(0,-1,1)
(0,1,-1)→(-1,1,0)
比如第一步可以是[1,1,0,1,-1,-1,-1] 或者[1,1,1,-1,0,-1,-1]。
请用Java解决这个问题,要求输出每次交换后的数组。

  • 写回答

2条回答 默认 最新

  • 俺不理解 2022-01-10 10:38
    关注

    暴力遍历

    import java.util.Arrays;
    import java.util.Calendar;
    import java.util.LinkedList;
    import java.util.List;
    
    public class Test {
        public static void main(String[] args) {
            long startTime = Calendar.getInstance().getTimeInMillis();
    
            int[] origin = {1, 1, 1, 0, -1, -1, -1};
            List<String> list = new LinkedList<>();
            boolean rst = doChange(list, origin, 3);
            if (rst) {
                for (String str : list) {
                    System.out.println(str);
                }
            }
    
            System.out.println("共耗时:" + (Calendar.getInstance().getTimeInMillis() - startTime) + "ms");
        }
    
        private static boolean doChange(List<String> list, int[] val, int p) {
            if (p == 3 && val[0] + val[1] + val[2] == -3 && val[4] + val[5] + val[6] == 3) {
                return true;
            }
            if (p + 1 < val.length && val[p + 1] == -1) {
                if (check(list, val, p, 1)) {
                    return true;
                }
            } else if (p + 2 < val.length && val[p + 2] == -1) {
                if (check(list, val, p, 2)) {
                    return true;
                }
            }
    
            if (p - 1 >= 0 && val[p - 1] == 1) {
                return check(list, val, p, -1);
            } else if (p - 2 >= 0 && val[p - 2] == 1) {
                return check(list, val, p, -2);
            }
            return false;
        }
    
        private static boolean check(List<String> list, int[] val, int p, int offset) {
            int np = swap(val, p, p + offset);
            list.add(Arrays.toString(val));
            boolean rst = doChange(list, val, np);
            if (rst) {
                return true;
            }
            list.remove(list.size() - 1);
            swap(val, p, p + offset);
            return false;
        }
    
        private static int swap(int[] val, int p1, int p2) {
            int t = val[p1];
            val[p1] = val[p2];
            val[p2] = t;
            return val[p1] != 0 ? p2 : p1;
        }
    }
    

    运行结果:

    img

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 8月25日
  • 已采纳回答 8月17日
  • 创建了问题 1月9日

悬赏问题

  • ¥15 CMAKE+VS2019+QT5.15.2组合进行二次编译
  • ¥15 nginx 配置静态html访问 ,后台登录时页面始终被重定向到登录页,无法访问到后台的静态html页
  • ¥20 自动登录的j2ee程序编译
  • ¥15 维纳滤波器的实验题及计算机实现,求解
  • ¥15 fluent模拟静态气体扩散
  • ¥15 java根据模板,生成word文档,需要带目录
  • ¥15 广告联盟的兜底广告是什么意思
  • ¥15 如何证明高斯噪声的包络公式
  • ¥150 寻找王者荣耀开发作者,合作或者解答
  • ¥15 关于cpci总线的几个问题,别用人工智能回答