本期讲思维转换类型问题，共7道题，三道简单题，四道中等题。
此部分题目是作者认为有价值去做的一些题，但是其考察的知识点不在前三篇总结系列里面。
- 例1解法：采用数组索引位置排序的思想。
- 例2解法：考察了组合数学的组合公式应用。有点类似动态规划的思想。
- 例3解法: 考察灵活运用二进制和整除余数的数学知识。
- 例4解法：动态规划思想的应用。
- 例5解法：分类讨论的数学思想。
- 例6解法：考察灵活运用哈希字典。
- 例7解法：考察闰年的数学判断公式，计算周几的细节处理能力。
例1 最大宽度坡
题号：962，难度：中等
题目描述：
解题思路：
采用索引排序的思路，使得从前往后遍历时，A[i] < A[j]。然后不断更新i的最小值，当前遍历的索引即为j。即可求取最终结果。
具体代码：
class Solution {
public int maxWidthRamp(int[] A) {
int N = A.length;
Integer[] B = new Integer[N];
for (int i = 0; i < N; ++i)
B[i] = i;
Arrays.sort(B, (i, j) -> ((Integer) A[i]).compareTo(A[j]));
int result = 0;
int i = N;
for (int j: B) {
result = Math.max(result, j - i);
i = Math.min(i, j);
}
return result;
}
}执行结果：
例2 总持续时间可被60整除的歌曲
题号:1010，难度：简单
题目描述：
解题思路：
本题考察了组合数学公式的应用，以及数学知识的转换和迁移应用。
具体代码：
class Solution {
public int numPairsDivisibleBy60(int[] time) {
int[] temp = new int[60];
int result = 0;
for(Integer t: time) {
if(t % 60 == 0)
result += temp[0];
else
result += temp[60 - (t % 60)];
temp[t % 60]++;
}
return result;
}
}执行结果：
例3 可被5整除的二进制前缀
题号：1018，难度：简单
题目描述：
解题思路：
此题需要抓住整除的核心，即个位数是5的倍数时，即可整除5。我们只需要统计当前二进制数的个位数即可。
具体代码：
class Solution {
public List<Boolean> prefixesDivBy5(int[] A) {
List<Boolean> ans = new ArrayList<>();
int num = 0;
for (int i = 0;i < A.length;i++) {
num <<= 1;
num += A[i];
num %= 10;
ans.add(num % 5 == 0);
}
return ans;
}
}执行结果：
例4 不相交的线
题号：1035，难度：中等
题目描述：
解题思路：
此题考察我们动态规划思想的应用。动态递推方程：可参考代码。
具体代码：
class Solution {
public int maxUncrossedLines(int[] A, int[] B) {
int[][] dp = new int[A.length + 1][B.length + 1];
for (int i = 1; i < dp.length; i++) {
for (int j = 1; j < dp[0].length; j++) {
if (A[i - 1] == B[j - 1])
dp[i][j] = dp[i - 1][ j - 1] + 1;
else
dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
}
}
return dp[A.length][B.length];
}
}执行结果：
例5 递减元素使数组呈锯齿状
题号：1144，难度：中等
题目描述：
解题思路：
分类讨论。按照题目的意思，分奇数偶数讨论求解最终的最小操作次数即可。
具体代码：
class Solution {
public int movesToMakeZigzag(int[] nums) {
int odd = 0;
int eve = 0;
//偶数最高
for (int i = 0; i < nums.length; i+=2) {
int temp = 0;
if(i ==0){
temp = nums [1];
}else if (i==nums.length -1){
temp= nums[nums.length -2];
}else {
temp = nums [i-1]>nums[i+1]?nums[i+1]:nums [i-1];
}
if(temp<=nums[i]){
eve+=nums[i]-temp+1;
}
}
//奇数最高
for (int i = 1; i < nums.length; i+=2) {
int temp = 0;
if (i==nums.length -1){
temp= nums[nums.length -2];
}else {
temp = nums [i-1]>nums[i+1]?nums[i+1]:nums [i-1];
}
if(temp<=nums[i]){
odd+=nums[i]-temp+1;
}
}
return eve>odd?odd:eve;
}
}执行结果：
例6 快照数组
题号：1146， 难度：中等
题目描述：
解题思路：
考察哈希字典的应用。
具体代码：
import java.util.Map.Entry;
class SnapshotArray {
int snap_id;
ArrayList<TreeMap<Integer,Integer>> list = new ArrayList<TreeMap<Integer,Integer>>();
public SnapshotArray(int length) {
list.clear();
for(int i = 0;i < length;i++) {
list.add(new TreeMap<Integer,Integer>());
}
}
public void set(int index, int val) {
TreeMap<Integer, Integer> pairMap = list.get(index);
Integer value = pairMap.getOrDefault(snap_id, val);
pairMap.put(snap_id, val);
}
public int snap() {
return snap_id++;
}
public int get(int index, int snap_id) {
Entry<Integer, Integer> entry = list.get(index).floorEntry(snap_id);
return entry == null ? 0 : entry.getValue();
}
} /**
* Your SnapshotArray object will be instantiated and called as such:
* SnapshotArray obj = new SnapshotArray(length);
* obj.set(index,val);
* int param_2 = obj.snap();
* int param_3 = obj.get(index,snap_id);
*/
执行结果：
例7 一周中的第几天
题号：1185，难度：简单
题目描述：
解题思路：
此题考察闰年的数学判定公式，以及对于月份的边界处理，对于细节的处理考察比较多。也是一道锻炼我们代码能力的经典算法题。（PS：不能调用库函数）当然，此题还可以参考LeetCode的评论中，一个名为蔡乐公式的解法，但是一般是记不住的。
具体代码：
class Solution {
public String dayOfTheWeek(int day, int month, int year) {
int[] months = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};
String[] result = {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"};
int init_y = 1999, init_m = 7, init_d = 18;
int all_days = 0;
if(year > init_y) {
all_days += 13;
for(int i = 7;i < 12;i++)
all_days += months[i];
for(int j = 2000;j < year;j++) {
if((j % 4 == 0 && j % 100 != 0) || j % 400 == 0)
all_days += 366;
else
all_days += 365;
}
for(int i = 0;i < month - 1;i++)
all_days += months[i];
all_days += day;
if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
if(month > 2)
all_days++;
return result[all_days % 7];
} else if(year == init_y) {
if(month > init_m) {
all_days += 13;
for(int i = 7;i < month - 1;i++)
all_days += months[i];
all_days += day;
return result[all_days % 7];
} else if(month == init_m) {
if(day >= init_d)
all_days += (day - init_d);
int k = all_days % 7;
if(day < init_d) {
all_days += (init_d - day);
k = (7 - all_days % 7) % 7;
}
return result[k];
}
} else {
all_days += 18;
for(int i = 0;i < 6;i++)
all_days += months[i];
for(int j = 1998;j > year;j--) {
if((j % 4 == 0 && j % 100 != 0) || j % 400 == 0)
all_days += 366;
else
all_days += 365;
}
for(int i = month;i < 12;i++)
all_days += months[i];
all_days += months[month - 1] - day;
if((year % 4 == 0 && year % 100 != 0) || year % 400 == 0)
if(month < 2)
all_days++;
all_days = (7 - all_days % 7) % 7;
return result[all_days];
}
return result[0];
}
}执行结果：