// 小白一名，0算法基础，艰难尝试算法题中，若您发现本文中错误，
或有其他见解，往不吝赐教，感激不尽，拜谢。
领扣 第915题 今日算法
题干
//给定一个数组 A，将其划分为两个不相交（没有公共元素）的连续子数组 left 和 right， 使得：
//
// left 中的每个元素都小于或等于 right 中的每个元素。
// left 和 right 都是非空的。
// left 要尽可能小。
// 在完成这样的分组后返回 left 的长度。可以保证存在这样的划分方法。
// 示例 1：
//
// 输入：[5,0,3,8,6]
// 输出：3
// 解释：left = [5,0,3]，right = [8,6]
// 示例 2：
//
// 输入：[1,1,1,0,6,12]
// 输出：4
// 解释：left = [1,1,1,0]，right = [6,12]
初次使用方法
/*
* 看到这道题的第一思路就是创建一个左数组，
* 通过一层循环赋值并求出最大数，
* 再进行一次循环来与右数组的元素依次进行比较
* 完善并测试了下代码后提交发现超出时间限制
* */
public static int partitionDisjoint(int[] A) {
//创建一个链式集合来充当左数组
LinkedList<Integer> list = new LinkedList();
//创建一个判断标记
boolean flag = true;
//外循环 循环向左数组进行添加元素
for (int a = 0; a < A.length - 1; a++) {
//向集合添加元素
list.add(A[a]);
//排序并获取最大值
Collections.sort(list);
int max = list.getLast();
//重置标记的初值
flag = true;
//被循环 进行判断
for (int b = a + 1; b < A.length; b++) {
//当右数组存在小于max的值时，标记更改
if (max > A[b]) {
flag = false;
}
}
//标记更改 继续循环 未更改 获得长度
if (flag) {
return (a + 1);
}
}
return 0;
}
第一次代码
/*
* 个人总经问题出现在了链式集合上，进行了许多没必要的操作
* 例如 添加 排序 解题的思路除了问题
* 这时感觉应该找寻一下规律
* 发现获得最大值没必要全部左数组进行比较
* 使用之前的最大值与新加入的值进行比较就可以了
* 本着这种思路测试后 58组数据处理时间6ms左右
* */
public static int partitionDisjoint1(int[] A) {
//左数组最大值
int max = A[0];
// 左数组长度
int a;
//创建标记
boolean flag;
//跳出标签
out:
//外循环为左数组长度
for (a = 0; a < A.length - 1; a++) {
//初始化标记
flag = true;
//内循环记性判断比较
for (int b = a + 1; b < A.length; b++) {
//存在小于max的元素时 更改标记 并打断本次循环
if (max > A[b]) {
flag = false;
break;
}
}
//如标记未发生更改，即左右数组已经符合条件 跳出所有循环
if (flag) {
break out;
}
/*
* 未跳出循环 当前新填入的值与之前的最大值进行比较
* 大于则互换，小于则不变
* */
if (max < A[a + 1]) {
max = A[a + 1];
}
}
//返回长度
return a + 1;
}
第二次代码
/*
* 目前最优代码的思路很清晰，考虑的跟周全
* 老实说 感觉他的代码更富有些 美感？
* 不知道是不是 因为他是目前最优的原因
* 虽然他的逻辑我能理解
* 但是总感觉有更深的细节在其中
* 作为一个刚刚踏入算法领域的小白
* 我觉得未来还有很长的路要走
* 还有很多的东西要学
* */
public static int bestMehtod(int[] A) {
//最小长度左数组的最大值
int max = A[0];
//临时最大值
int nowmax;
//
int j;
//左数组长度
int i;
//确保左右各数组合都有元素
if (A[0] == A[A.length - 1])
return 1;
//goto标签 跳出多重循环
out:
//外循环 首先判断当前的左数组的最大值和将要加入的元素大小关系
for (i = 1; i < A.length; i++) {
//判断下一个元素和之前左数组的最大值的关系
if (max > A[i]) {
//大于 直接跳过本次循环 长度增加
continue;
} else {
//小于 将下一个元素赋值给临时最大值？（为啥设置了这个临时值，优化了这个代码？）
nowmax = A[i];
//内循环
for (j = i; j < A.length; j++) {
//依次判断每个元素是否大于最大值
if (A[j] >= max) {
//大于，再判断右数组长度是否最小了
if (j == (A.length - 1))
//是 因out标签位置跳出所有循环
break out;
//否 跳过本次循环
continue;
} else {
//小于 将临时最大值赋值给max 并跳出此次循环
max = nowmax;
break;
}
}
}
}
//返回长度
return i;
}
目前答案中最优代码
我们生活在泥沼之中，但是有人依然仰望星空。
We are all in the gutter, but some of us are looking at the stars.
写于2018.11.16