package y2019.Algorithm.array; /**
* @ClassName FindUnsortedSubarray
* @Description TODO 581. Shortest Unsorted Continuous Subarray
*
* Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order,
* then the whole array will be sorted in ascending order, too.
* You need to find the shortest such subarray and output its length.
*
* Input: [2, 6, 4, 8, 10, 9, 15]
* Output: 5
* Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
*
* 求最短未排序的子串
* 求最短的无序连续子数组
*
* @Author xiaof
* @Date 2019/7/9 19:58
* @Version 1.0
**/
public class FindUnsortedSubarray { public int solution(int[] nums) {
//1.这里应该保障前后都是有序的，中间无序
int begin = -1, end = -2;
int max = nums[0], min = nums[nums.length - 1];
for(int i = 1; i < nums.length; ++i) {
max = Math.max(max, nums[i]);
min = Math.min(min, nums[nums.length - i - 1]);
//每次判断是否获取到最大值
if(nums[i] < max) end = i; //如果当前位置比最大的值小，那么乱序的末尾移动到这里（Math.max(max, nums[i])）前面有比较，难么i肯定在max之后
//判断开始的位置是，比最小的值大的再前面
if(nums[nums.length - i - 1] > min) begin = nums.length - 1 - i; } return end - begin + 1;
} }
package y2019.Algorithm.array; import java.util.*; /**
* @ClassName LargeGroupPositions
* @Description TODO 830. Positions of Large Groups
* In a string S of lowercase letters, these letters form consecutive groups of the same character.
* For example, a string like S = "abbxxxxzyy" has the groups "a", "bb", "xxxx", "z" and "yy".
* Call a group large if it has 3 or more characters. We would like the starting and ending positions of every large group.
* The final answer should be in lexicographic order.
*
* Input: "abbxxxxzzy"
* Output: [[3,6]]
* Explanation: "xxxx" is the single large group with starting 3 and ending positions 6.
*
* @Author xiaof
* @Date 2019/7/9 20:37
* @Version 1.0
**/
public class LargeGroupPositions { public List<List<Integer>> solution(String S) {
//1.用list存放分组（字符，长度），然后遍历分组中最长的那个
Map<Character, int[]> group = new IdentityHashMap<>();
int begin = 0, end = 0, maxLen = 3;;
char[] ss = S.toCharArray();
Character curC = ss[0];
for(int i = 1; i < ss.length; ++i) {
if (curC != ss[i]) {
//如果产生了变化
if(group.get(curC) != null) {
int[] temp = group.get(curC);
int len = temp[1] - temp[0];
if(len < (end - begin)) {
group.remove(curC);
group.put(curC, new int[]{begin, end});
}
} else {
group.put(curC, new int[]{begin, end});
}
// maxLen = Math.max(maxLen, end - begin + 1);
curC = ss[i];
begin = i;
end = i;
} else {
//如果不为空，并且是相同的字符，那么递增
end = i; }
} //最后放入最后一个元素
if(group.get(curC) != null) {
int[] temp = group.get(curC);
int len = temp[1] - temp[0];
maxLen = Math.max(maxLen, len);
if(len < (end - begin)) {
group.remove(curC);
group.put(curC, new int[]{begin, end});
}
} else {
group.put(curC, new int[]{begin, end});
} //获取其中最大的，并进行反馈
List<List<Integer>> result = new ArrayList<>(); if(maxLen < 3) {
return result;
} for(Map.Entry entry : group.entrySet()) {
int temp[] = (int[]) entry.getValue();
int curLen = temp[1] - temp[0] + 1;
if(curLen >= maxLen) {
result.add(Arrays.asList(temp[0], temp[1]));
}
} return result;
} public List<List<Integer>> solution2(String S) {
List<List<Integer>> res = new ArrayList<>();
//寻遍比那里所有字符，并把i赋值为j
for (int i = 0, j = 0; i < S.length(); i = j) {
//循环遍历到第一个不相等的位置
while (j < S.length() && S.charAt(j) == S.charAt(i)) ++j;
if (j - i >= 3)
res.add(Arrays.asList(i, j - 1));
}
return res;
} public static void main(String args[]) {
int A1[] = {1,4,3,2};
String s = "abbxxxxzzy";
s = "abc";
s = "abcdddeeeeaabbbcd";
s = "babaaaabbb";
LargeGroupPositions fuc = new LargeGroupPositions();
System.out.println(fuc.solution(s));
}
}
package y2019.Algorithm.array; /**
* @ClassName NumPairsDivisibleBy60
* @Description TODO 1010. Pairs of Songs With Total Durations Divisible by 60
*
* In a list of songs, the i-th song has a duration of time[i] seconds.
* Return the number of pairs of songs for which their total duration in seconds is divisible by 60.
* Formally, we want the number of indices i < j with (time[i] + time[j]) % 60 == 0.
*
* Input: [30,20,150,100,40]
* Output: 3
* Explanation: Three pairs have a total duration divisible by 60:
* (time[0] = 30, time[2] = 150): total duration 180
* (time[1] = 20, time[3] = 100): total duration 120
* (time[1] = 20, time[4] = 40): total duration 60
*
* 题目的意思是找出数组中两数之和能被60整除的数对，数组最大的长度是60000，如果使用暴力求解需要两层循环，
* 需要进行59999+5998+…+2+1=1799910001次计算和判断的，很显然会超时。
*
* @Author xiaof
* @Date 2019/7/9 21:39
* @Version 1.0
**/
public class NumPairsDivisibleBy60 { public int solution(int[] time) { //由于和可以被60整除，也就是说，这些数的余数和为60
int[] occu = new int[60];
int result = 0;
for(int t : time) {
//这里组合的时候，注意我们按照后加入的和前面的数据进行配对,这样就可以出现不同的位置相同的数据可以被多次匹配
int index = t % 60 == 0 ? 0 : 60 - t % 60;
result += occu[index];
occu[t % 60]++;
} return result; } public int solution2(int[] time) {
int result = 0;
int[] occured = new int[60]; for(int i = 0;i < time.length;i++){
time[i] %= 60;
int index = time[i] == 0 ? 0 : 60 - time[i];
result += occured[index];
occured[time[i]]++;
} return result;
} public static void main(String args[]) {
int A1[] = {30,20,150,100,40};
NumPairsDivisibleBy60 fuc = new NumPairsDivisibleBy60();
System.out.println(fuc.solution2(A1));
} }
package y2019.Algorithm.array; /**
* @ClassName CheckPossibility
* @Description TODO 665. Non-decreasing Array
* Given an array with n integers, your task is to check if it could become non-decreasing by modifying at most 1 element.
* We define an array is non-decreasing if array[i] <= array[i + 1] holds for every i (1 <= i < n).
*
* Input: [4,2,3]
* Output: True
* Explanation: You could modify the first 4 to 1 to get a non-decreasing array.
*
* 题目给了我们一个nums array， 只允许我们一次机会去改动一个数字，使得数组成为不递减数组。可以实现的话，return true；不行的话，return false。
* 这个题目关键在于，当遇见一个 nums[i] > nums[i+1] 的情况，我们是把 nums[i]降为nums[i+1] 还是 把nums[i+1]升为nums[i]。
* 如果可行的话，当然是选择优先把 nums[i]降为nums[i+1]，这样可以减少 nums[i+1] > nums[i+2] 的风险。
*
* @Author xiaof
* @Date 2019/7/9 22:08
* @Version 1.0
**/
public class CheckPossibility { public boolean solution(int[] nums) {
//也就是说这个数组要瞒住该表一个数据之后变成非递减数组
//这里需要对数组边遍历边修改
int needChangeTimes = 0;
for(int i = 0; i < nums.length - 1 && needChangeTimes <= 1; ++i) {
if(nums[i] > nums[i + 1]) {
++needChangeTimes;
if(i - 1 < 0 || nums[i - 1] <= nums[i + 1]) {
nums[i] = nums[i + 1];
} else {
nums[i + 1] = nums[i];
} }
} return needChangeTimes <= 1;
} public static void main(String args[]) {
int A1[] = {3,4,2,3};
CheckPossibility fuc = new CheckPossibility();
System.out.println(fuc.solution(A1));
} }