ARTS 打卡 -02

关注
发布于: 2020 年 06 月 05 日
AlgorithmQuestion:
Best Time to Buy and Sell Stock II
https://leetcode.com/explore/interview/card/top-interview-questions-easy/92/array/564/
My first answer:
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        int len = size(prices);
        
        if (len > 1) {
            for (int i = 0; i < len; i++) {
                int profit = 0;
                
                for (int j = i + 1; j < len; j++) {
                    profit = prices[j] - prices[i];
                    vector<int> prices_left;
                    for (int k = j + 1; k < len; k++) {
                        prices_left.push_back(prices[k]);
                    }
                    profit += maxProfit(prices_left);
                    
                    if (profit > max_profit) {
                        max_profit = profit;
                    }
                }
            }
        }
        return max_profit;
    }
};
Feedback:
Failure reason: 采用了递归的编程思想，过于复杂，导致超过了运行时间的限制要求。
My second answer:
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        int len = size(prices);
        
        if (len <= 1) {
            return 0;
        }
        
        int buy = 0;
        int sell = 0;
        bool in_trans = false;
        for (int i = 0; i < len; i++) {
            if (!in_trans) {
                bool set_buy = false;
                if ((i > 0) && (i < (len-1))) {
                    set_buy = (prices[i] <= prices[i - 1]) && (prices[i] <= prices[i + 1]);
                }
                else if (i == 0) {
                    set_buy = (prices[i] <= prices[i + 1]);
                }
                else {
                    set_buy = (prices[i] <= prices[i - 1]);
                }
                
                if (set_buy) {
                    buy = i;
                    in_trans = true;
                }                
            }
            else {
                bool set_sell = false;
                if ((i > 0) && (i < (len-1))) {
                    set_sell = (prices[i] >= prices[i - 1]) && (prices[i] >= prices[i + 1]);
                }
                else if (i == 0) {
                    set_sell = (prices[i] >= prices[i + 1]);
                }
                else {
                    set_sell = (prices[i] >= prices[i - 1]);
                }
                
                if (set_sell) {
                    sell = i;
                    max_profit += prices[sell] - prices[buy];
                    in_trans = false;
                }
            }
        }
        return max_profit;
    }
};
Note: 跟老公讨论之后，发现我们只要找到波谷和波峰，然后峰值减谷值即可。这个算法比我之前的实现简单一些，最终通过了。
Feedback: Your runtime beats 25.76 % of cpp submissions.
Refined answer:参考了别人的答案之后，我发现，其实问题只是计算profit，而我给出的第二个答案包含了具体买入和卖出的时机，所以可以更简单。
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;
        
        for (int i = 0; i < size(prices) - 1; i++) {
            if (prices[i + 1] > prices[i]) {
                max_profit += prices[i + 1] - prices[i];
            }
        }
        return max_profit;
    }
};
Feedback: Your runtime beats 97.25 % of cpp submissions.
ReviewBundle Adjustment (BA)Triggs, B., McLauchlan, P., Hartley, R., and Fitzgibbon, A. 2000. Bundle adjustment---a modern synthesis. In Vision Algorithms: Theory and Practice, Springer-Verlag, Berlin, Germany.]]
http://www.cs.jhu.edu/~misha/ReadingSeminar/Papers/Triggs00.pdf
﻿
Bundle adjustment is the problem of refining a visual reconstruction to produce jointly optimal 3D structure and viewing parameter (camera pose and/or calibration) estimates.
Optimal means that the parameter estimates are found by minimizing some cost function that quantifies the model fitting error, and jointly that the solution is simultaneously optimal with respect to both structure and camera variations.
The name refers to the ‘bundles’ of light rays leaving each 3D feature and converging on each camera centre, which are ‘adjusted’ optimally with respect to both feature and camera positions. Equivalently — unlike independent model methods, which merge partial reconstructions without updating their internal structure — all of the structure and camera parameters are adjusted together ‘in one bundle’.
 
To estimate the unknown 3D feature and camera parameters from the observations, and hence reconstruct the scene, we minimize some measure (discussed in §3) of their total prediction error. Bundle adjustment is the model refinement part of this, starting from given initial parameter estimates (e.g., from some approximate reconstruction method). Hence, it is essentially a matter of optimizing a complicated nonlinear cost function (the total prediction error) over a large nonlinear parameter space (the scene and camera parameters).
 
Bundle adjustment is essentially a parameter estimation problem. Any parameter estimation paradigm could be used, but we will consider only optimal point estimators, whose output is by definition the single parameter vector that minimizes a predefined cost function designed to measure how well the model fits the observations and background knowledge. This framework covers many practical estimators including maximum likelihood (ML) and maximum a posteriori (MAP), but not explicit Bayesian model averaging. Robustification, regularization and model selection terms are easily incorporated in the cost.
Tips 刘超，《趣谈Linux操作系统》，极客时间APP
《03 | 你可以把Linux内核当成一家软件外包公司的老板》我认为这个比方十分恰当，生动形象，有利于理解Linux内核的职能。
《04 | 快速上手几个Linux命令》
﻿
《05 | 学会几个系统调用：咱们公司能接哪些类型的项目？》重点知识总结：
操作系统启动时，会先创建一个所有用户进程的“祖宗进程”，然后父进程调用fork创建子进程。子进程复制了父进程的程序代码和数据结构，通过fork系统调用的返回值不同区分父进程和子进程，产生分支（fork）。
在Linux中，一切皆文件。
网络服务通过套接字Socket（含义为“插口”or“插槽”）来提供。所以，要实现通信，双方都要建立一个Socket，这样通信的网线才能插入两头的插槽里。
Glibc充当了中介的作用，提供了丰富的API，封装了系统调用。
﻿
《06 | x86架构：有了开放的架构，才能打造开放的营商环境》
﻿
Share这是我阅读金戈大王3篇文章总结的
如何从两张2D图像，计算出配对特征点的3D位置﻿
提取特征点，并匹配《OpenCV提取ORB特征并匹配》https://www.jianshu.com/p/420f8211d1cb
什么是图片特征点？
图像的特征（Feature），是图像上最具代表性的一些点。
所谓最具代表性，就是说这些点包含了图像表述的大部分信息。即使旋转、缩放，甚至调整图像的亮度，这些点仍然稳定地存在，不会丢失。找出这些点，就相当于确定了这张图像，它们可以用来做匹配、识别等等有意义的工作。
 
通常来说，角点容易成为特征点。角点是指图案中处于角落的点，这些点附近像素值变化剧烈，因而容易被检测出。
 
特征点由关键点（Key-point）和描述子（Descriptor）两部分组成。
 
其他常用特征：
SIFT特征以精确著称，但计算量极大，无法在CPU上实时计算。
SURF特征降低了SIFT的精确度，但提高了性能。
ORB特征是目前计算最快的特征，非常适合于实时SLAM，因此受到广大研究者的喜爱。提取ORB特征其实包括了提取关键点和计算描述子两件事情。
 
ORB特征
ORB全名为Oriented FAST and Rotated BRIEF，它采用改进的FAST关键点检测方法，使其具有方向性，并采用具有旋转不变性的BRIEF特征描述子。FAST和BRIEF都是非常快速的特征计算方法，因此ORB具有非同一般的性能优势。
筛选后的匹配点对
﻿
利用至少需要5对匹配点确定两个相机的位姿《2D-2D相机位姿估计》https://www.jianshu.com/p/fbf56587a268
根据相机在不同位置拍摄的两张图片恢复出相机的运动。在多视图几何学中，这被称为对极几何。
 
利用两张图片中特征点对的像素坐标可以恢复相机运动和地图点X的深度。
数学上可以证明，至少需要5对匹配点才可以唯一确定两个相机的位姿。
而实际应用中通常使用8对以简化计算过程，称为“八点法”。
﻿
通过三角测量的方法计算出配对特征点的3D位置《三角测量（Triangulation）》https://www.jianshu.com/p/96d3b832330e
在得到了两张图片对应的相机位姿之后，就可以通过三角测量的方法计算出配对特征点的3D位置。
 
在两个不同地方观测同一个点，只要知道两个观测地点的距离和观测角度，就可以确定观测点到两地的距离。这是因为一条边和两个内角可以完全确定一个三角形，仅此而已。
﻿