极客时间《左耳听风》发起的ARTS挑战怎么参加？
左耳朵耗子专栏《左耳听风》 用户自发每周完成一个ARTS
非常抱歉，上周因为事情比较多，一直在加班，没来及做，争取补上
感谢耗子叔上次指出的问题
1.Algorithm：每周至少做一个 leetcode 的算法题
第一道算法题：
https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
3.无重复字符的最长子串
自己看完题后的思路：
第一种，将所有的子串找出，然后筛选出无重复字符的，然后再对比长度
第二种，
字符串：ABCDECDEFGIF
A
AB
ABC
ABCD
ABCDE
ABCDEC => ABCDE DEC maxLength = 5;
DECD => DEC ECD maxLength = 5;
ECDE => ECD CDE maxLength = 5;
CDEF
CDEFG
CDEFGI
CDEFGIF =>CDEFGI GIF maxLength = 6;
最开始的代码：
public int lengthOfLongestSubstring(String s) {
if(s.length()<=1){
return s.length();
}
int maxLength = 0;
Set<Character> set = new LinkedHashSet();
Set<Character> tmpSet;
int length = s.length();
Boolean isEqual;
for (int index =0 ;index<length;index++) {
char c = s.charAt(index);
if(!set.add(c)){
maxLength = Math.max(maxLength,set.size());
tmpSet = new LinkedHashSet();
isEqual = false;
for(char ch : set ){
if(ch==c){
isEqual = true;
continue;
}
if(isEqual){
tmpSet.add(ch);
}
}
tmpSet.add(c);
set = tmpSet;
}
}
maxLength = Math.max(maxLength,set.size());
return maxLength;
}
再细想一下，可以采用滑动窗口的方式：
/**
* 滑动窗口方式：
* [leftIndex,rightIndex]
* 开始leftIndex不动，rightIndex往右移动，并将值添加到set中。
* 如果添加成功，次数计算 Math.max(maxLength,rightIndex-leftIndex)，（注意：此时的rightIndex已经++）。
* 如果添加失败，说明已经存在，从leftIndex开始移除，直到添加再次成功，说明set重复值之前的数据已经全部删除。
*/
public int lengthOfLongestSubstring1(String s) {
int maxLength = 0;
Set<Character> set = new HashSet();
int length = s.length();
for (int leftIndex = 0, rightIndex = 0 ;rightIndex< length && leftIndex<length;){//此处可以换成while
if(set.add(s.charAt(rightIndex))){
rightIndex++;
maxLength = Math.max(maxLength,rightIndex-leftIndex);
}else{
set.remove(s.charAt(leftIndex++));
}
}
return maxLength;
}
第二道算法题：
https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
4.寻找两个有序数组的中位数
思路：将两个数组合并排序，到一半结束
问题：时间复杂度不是题目要求的 O(log(m + n))
/**
* 支持 ，两个都是正序，两个都是倒序，或者一个正序一个倒序
* @param nums1
* @param nums2
* @return
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
double result= 0d;
if(nums1==null){
nums1 = new int[]{};
}
if(nums2==null){
nums2 = new int[]{};
}
if(nums1.length==0 && nums2.length==0){ // 处理两个都是0的情况
return result;
}
// 奇数/偶数 是否是奇数
boolean isOdd = (nums1.length+nums2.length)%2 !=0;
int medianIndex1 = isOdd ? (nums1.length+nums2.length)/2 : (nums1.length+nums2.length)/2 -1;
int medianIndex2 = isOdd ? -1 : (nums1.length+nums2.length)/2;
int[] nums3 = new int[isOdd ? medianIndex1+1 :medianIndex2+1];
// 倒序，正序？？
boolean nums1Asc = true;
boolean nums2Asc = true;
for(int i=0 ;i<nums1.length-1;i++){
if(nums1[i]!=nums1[i+1]){
nums1Asc = nums1[i] < nums1[i+1];
break;
}
}
for(int i=0 ;i<nums2.length-1;i++){
if(nums2[i]!=nums2[i+1]){
nums2Asc = nums2[i] < nums2[i+1];
break;
}
}
int i = nums1Asc ? 0 : nums1.length-1;
int j = nums2Asc ? 0 : nums2.length-1;;
int index =0;
while ((nums1Asc ? i<nums1.length : i>=0) || (nums2Asc ? j<nums2.length : j>=0)){
if((nums1Asc ? i<nums1.length : i>=0) && (nums2Asc ? j<nums2.length : j>=0)){
if(nums1[i]<nums2[j]){
nums3[index] = nums1[i];
i = nums1Asc ? i+1 : i-1;
}else{
nums3[index] = nums2[j];
j = nums2Asc ? j+1 : j-1;
}
}else if(nums1Asc ? i<nums1.length : i>0){
nums3[index] = nums1[i];
i = nums1Asc ? i+1 : i-1;
}else if(nums2Asc ? j<nums2.length : j>0){
nums3[index] = nums2[j];
j = nums2Asc ? j+1 : j-1;
}
if(isOdd ){
if(index == medianIndex1){
break;
}
}else{
if(index == medianIndex2){
break;
}
}
index++;
}
if(isOdd ){
result = (double)nums3[nums3.length-1];
}else{
result = ((double)nums3[nums3.length-1]+(double)nums3[nums3.length-2])/2;
}
return result;
}
2.Review：阅读并点评至少一篇英文技术文章
How to think like a programmer — lessons in problem solving
如何像程序员一样思考问题-解决问题的经验教训
从本质上讲， 这是解决问题的一种更有效的方法
一般解决问题的方式：
- 尝试一个方案
- 如果方案不成功，尝试另一个方案
- 如果还不起作用，重复步骤2，直到解决
运气好可以解决，运气不好，可能浪费很多时间也没有解决
推荐的方法：
- 首先得有一个框架
- 多实践
Almost all employers prioritize problem-solving skills first.
Problem-solving skills are almost unanimously the most important qualification that employers look for….more than programming languages proficiency, debugging, and system design.
几乎所有雇主都首先优先考虑解决问题的技能。
解决问题的技能几乎是雇主寻求的最重要的资格...不仅仅是编程语言的熟练程度，调试和系统设计
一、框架
作者建议："The 4-Hour Chef"
“The biggest mistake I see new programmers make is focusing on learning syntax instead of learning how to solve problems.” — V. Anton Spraul
我看到新程序员犯下的最大错误就是专注于学习语法，而不是学习如何解决问题。
遇到新问题时应该怎么做？
- 理解
首先你的理解问题，才能很好的解决问题。
怎么算理解呢？引用一下：
“If you can’t explain something in simple terms, you don’t understand it.” — Richard Feynman
如果你不能用简短的文字描述一件事情，那么不算理解它。
- 制定计划
处理问题是一定要花时间先去理解问题，分析问题，然后制定执行计划。有了计划再去执行。
- 拆解问题
不要试图去一下解决一个大问题。
应该将大问题拆解成一个个的小问题，甚至可以把小问题继续拆解。
然后，从解决拆解后的小问题开始处理。
当所有小问题解决后，把小问题串联起来，大问题自然就解决了。
将问题减少到知道如何解决问题并编写解决方案的程度。
二、坚持了吗？
解决小问题试，遇到问题，卡住了，怎么办？
- 调试
- 重新评估，是不是换另一中思路（有时我们会在问题的细节上迷失方向，而忽略了在更一般的层面上解决问题的一般原则）
- 研究，比如，谷歌等
三、实践
不要期望短时间内就会有一个很好的改变。
如果你想成为一个好的问题解决者，你需要不断的去解决问题。
当然，解决的问题有很多：国际象棋谜题，数学问题，数独，围棋，大富翁，视频游戏，密码等等
事实上，成功人士的共同模式是他们练习“解决微观问题”的习惯。
3.Tip：学习至少一个技术技巧
uptime
11:07 up 5 days, 19:58, 5 users, load averages: 2.90 2.96 2.76
显示内容说明：
11:07 # 系统当前时间
up 5 days, 19:58 # 系统已运行时间
5 users # 登录用户数
load averages: 2.90 2.96 2.76 # 系统平均负载，统计最近1，5，15分钟的系统平均负载
平均负载：是指单位时间内，系统处于可运行状态下和不可中断状态的平均进程数，也就是平均活跃进程数，它和CPU使用率没有直接关系。
4.Share：分享一篇有观点和思考的技术文章
个人刚经历的一个创业公司，公司成立已经快一年了，有一个后台的统计程序，所有逻辑全部用sql写到了controller中。
因为之前没经历过创业公司，所以不清楚这样做是不是对。
欢迎同学给建议。
