阅读本文大概需要 8 分钟。
每周完成一个 ARTS
Algorithm 来源LeetCode 238. Product of Array Except Self。
Review 分享一个动画浏览 GitHub 文件的神操作。
Tip 分享关于微服务的一些记录 。
Share 总结一下牛逼的人一般的三个特点。
PS:由于公众号不支持添加外链,所以大家遇到有链接的地方滑到文章最下面点击阅读原文就可以访问了哈,如果觉得文章不错,欢迎分享给周围的朋友们哈
1.Algorithm
238. Product of Array Except Self 难度 [Medium]
【题意】
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]
Note: Please solve it without division and in O(n).
Follow up:
Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
【思路】
这道题给定我们一个数组,让我们返回一个新数组,对于这个新数组来说,对于每一个位置上的数是其他位置上数的乘积,而且限定了时间复杂度 O(n),不能用除法。如果让用除法做的话,那这样做就没有多大意义了,我们接着思考。
这里有一个关键在于,如果我们知道了每一个数之前所有的数的乘积和之后所有的数的乘积,那么二者相乘就是给每一个数贡献的答案。如此一来,我们只需分别创建两个数组分别从数组的前面和后面遍历累积数组,最后两个数组相乘就是结果。
【解法一】(C++)
/*
Author: https://github.com/rongweihe
Time: 2019-03-03
*/
// Time complexity : O(n).
// Space complexity : O(n).
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
if( n<=0 ) return {};
vector<int> preArr(n, 1), backArr(n, 1), res(n);
for (int i = 0; i < n - 1; ++i) {
preArr[i + 1] = preArr[i] * nums[i];
}
for (int i = n - 1; i > 0; --i) {
backArr[i - 1] = backArr[i] * nums[i];
}
for (int i = 0; i < n; ++i) {
res[i] = preArr[i] * backArr[i];
}
return res;
}
};
【解法一】(Java)
/*
Author: https://github.com/rongweihe
Time: 2019-03-03
*/
// Time complexity : O(n).
// Space complexity : O(n).
public class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
if( n<=0 ) return {};
int[] res = new int[n];
int[] preArr = new int[n], backArr = new int[n];
preArr[0] = 1; backArr[n - 1] = 1;
for (int i = 1; i < n; ++i) {
preArr[i] = preArr[i - 1] * nums[i - 1];
}
for (int i = n - 2; i >= 0; --i) {
backArr[i] = backArr[i + 1] * nums[i + 1];
}
for (int i = 0; i < n; ++i) {
res[i] = preArr[i] * backArr[i];
}
return res;
}
}
其实还可以对上面的方法进行空间上的优化,由于最终的结果都是要乘到结果 res 中,所以我们可以不用单独的数组来保存乘积,而是直接累积到 res 中。
【解法二】(C++)
/*
Author: https://github.com/rongweihe
Time: 2019-03-03
*/
// Time complexity : O(n).
// Space complexity : O(n).
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
if( n<=0 ) return {};
vector<int> res(nums.size(), 1);
for (int i = 1; i < nums.size(); ++i) {
res[i] = res[i - 1] * nums[i - 1];
}
int k = 1;
for (int i = nums.size() - 1; i >= 0; --i) {
res[i] *= k;
k *= nums[i];
}
return res;
}
};
Java 代码也是类似。
2.Review
一个动画浏览 GitHub 文件的神操作!
我们都知道,GitHub 上可以查看某个文件的历史修改记录。一般我们的做法是在命令行里通过 Git 命令来查看,有的人习惯直接在 GitHub 点击该文件的 History 查看 commit 历史记录。这几天在twitter上看到有人分享一个一个新方法,这种方法可以在浏览器里直接浏览任意GitHub 文件的历史,而且还是以动画的形式,简直不能太 6 。
这里贴两张效果图给大家看一看
重点:我这篇文章也是非常有幸能得到皓哥(骨灰级程序员巨佬,昵称:左耳朵耗子)的认可,并且在皓哥的公众号 CoolShell 上发表,大家感兴趣的可以扫码关注一下酷壳公众号(CoolShell),回复 new 即可看到最新的文章。
3 Tip
昨天非常有幸旁听了皓哥和别人的一次技术交流,说实话,比较兴奋,毕竟皓哥在我心里那是神一般的存在。全程旁听,一遍听一遍记录笔记,虽然大部分说的东西都未曾听说过,但是从另一个方面来说,拓展了我的知识面,也暴露了我的知识盲区,这里将昨天的笔记稍微整理下,一方面给自己提供进一步学习的路径,同时也能给感兴趣的朋友提供一些参考。
1、何为 ESB ?
ESB 全称为 Enterprise Service Bus,即企业服务总线。它是传统中间件技术与 XML、Web 服务等技术结合的产物。ESB 提供了网络中最基本的连接中枢,是构筑企业神经系统的必要元素。
2、ESB 存在的问题?
esb 中间件存在两个东西:服务发现和服务注册,可以实现限流,熔断,负载均衡,甚至消息编排。但是可以带来另外的问题,当你编程需要跟别人去通信必须使用 esb,必须把服务注册到 esb 上。
当批量服务注入就会出现工作量大的问题,而且当 esb 一旦出问题,所有的通信都会受到影响。协议乱,越做越重。反而代码改动不大的情况下,会越做越稳定了。
3、为什么要有服务发现?它的作用是怎样?
皓哥:主要用来解耦。
4、有了服务发现之后如何做负载均衡?
DNS 一个域名配置多个 DNS ,后台轮询。
网关:API 的编排。
5、微服务的三个指标
第一个指标:高可用。
第二个指标:健康检查。
第三个指标:变更通知。
4 Share
最近的一些思考,人与人为什么会有这么大的差距?难道那些牛逼的人有什么不一样的经历吗?,最近我发现牛逼的人好像都有一些共性的特点
1. 执行力很强。
2. 对自己定位清晰,目标明确。
3. 做事情讲究方法和策略,不是蛮干,死干这种,有战略和规划。