所谓A(Algorithm)R(Review)T(Tips)S(Share):
- 每周至少做一个 leetcode 的算法题
- 阅读并点评至少一篇英文技术文章
- 学习至少一个技术技巧
- 分享一篇有观点和思考的技术文章
Algorithm
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
进阶:如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。
1. 动态规划
思路：遍历数组求和，如果和小于0，那么下一轮遍历重新计算求和值，并与之前的最大子序和对比，求最大值。
public int maxSubArray(int[] nums) {
int ans = nums[0];
int max = nums[0];
int length = nums.length;
for (int i = 1; i < length; i++) {
ans = ans < 0 ? 0 : ans;
ans += nums[i];
max = Math.max(max, ans);
}
return max;
}
2. 分治法
思路：
- 找到中间位置，所求子串不是在中间位置的左边，就是右边，还有中间位置两边；
- 中间位置左边右边的和最大的子串可以递归地求得；
- 再求中间位置往左挨个加的最大和以及中间位置往右挨个数的最大和，这两个和就是子串跨越中间位置时的最大和；
- 这三个最大和中的最大值就是所求最大值；
- 这里要注意left = divide(nums, l , mid)，这里的右边界不是mid-1，而是mid，因为边界是l==r的时候返回arr[L]，而且我们计算中间位置最大值的时候包括了arr[mid]，就不需要再加上arr[mid]。
public int maxSubArray1(int[] nums) {
if (nums.length == 0 ) {
return 0;
}else {
return divide(nums, 0, nums.length-1);
}
}
private int divide(int[] nums,int l, int r){
if (l == r) {
return nums[l];
}
int mid = (l + r)/2;
int left = divide(nums, l , mid);
int right = divide(nums, mid+1, r);
int maxLeftBord = nums[mid];
int leftBordSum = 0;
for (int i = mid; i >= l ; i--){
leftBordSum += nums[i];
maxLeftBord = Math.max(leftBordSum,maxLeftBord);
}
int maxRightBord = nums[mid + 1];
int rightBordSum = 0;
for (int i = mid+1; i <= r; i++){
rightBordSum += nums[i];
maxRightBord = Math.max(rightBordSum, maxRightBord);
}
return Math.max(Math.max(left, right), (maxLeftBord + maxRightBord));
}
Review
3 Best Practices Java Programmers Can Learn From Spring Framework
这篇文章作者分享了学习spring源码学到的三个最佳实践：
- Coding for Interfaces
- Favor Unchecked Exceptions Over Checked Exceptions
- Use of Template Design Patterns
Tips
关于json转实体类，记录一次踩坑事件。
实体类有多层集合嵌套时，不能使用Gson的new Gson().fromJson()方法来将json转换成实体类，这样会导致第二层集合属性值为null.
可以使用fastJson的JSON.parseObject()方法来转换或者直接将json转换成JSONObject，然后使用JSONObject.toBean()来转换成实体类。
Share
Java中的移位运算符总结
java中有三种移位运算符：
- <<:左移运算符，num << 1,相当于num乘以2
- >>:右移运算符，num >> 1,相当于num除以2
- >>>:无符号右移，忽略符号位，空位都以0补齐
public class Test {
public static void main(String[] args) {
int number = 10;
//原始数二进制
printInfo(number);
number = number << 1;
//左移一位
printInfo(number);
number = number >> 1;
//右移一位
printInfo(number);
number = number >>> 1;
printInfo(number);
}
/**
* 输出一个int的二进制数
* @param num
*/
private static void printInfo(int num){
System.out.println(Integer.toBinaryString(num));
}
}
运行结果
1010
10100
1010
101
对于：>>>
无符号右移，忽略符号位，空位都以0补齐
value >>> num -- num 指定要移位值value 移动的位数。
无符号右移的规则只记住一点：忽略了符号位扩展，0补最高位 无符号右移运算符>>> 只是对32位和64位的值有意义
