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日

悬赏问题

  • ¥50 如何使用js去调用vscode-js-debugger的方法去调试网页
  • ¥15 376.1电表主站通信协议下发指令全被否认问题
  • ¥15 物体双站RCS和其组成阵列后的双站RCS关系验证
  • ¥15 复杂网络,变滞后传递熵,FDA
  • ¥20 csv格式数据集预处理及模型选择
  • ¥15 部分网页页面无法显示!
  • ¥15 怎样解决power bi 中设置管理聚合,详细信息表和详细信息列显示灰色,而不能选择相应的内容呢?
  • ¥15 QTOF MSE数据分析
  • ¥15 平板录音机录音问题解决
  • ¥15 请问维特智能的安卓APP在手机上存储传感器数据后,如何找到它的存储路径?