2018-10 - karynsong|BMFE|eros

算法

有效的括号

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串。

var isValid = function(s) {
    if(!s.length) return true;
    if(s.length % 2 !== 0) return false;
    var res = [];
    const map = {'(': ')', '{': '}', '[': ']'}
    for(var i=0; i<s.length; i++){
        if(map[s[i]]){
            res.push(s[i]);
            continue;
        }
        if(map[res.pop()] !== s[i]){
            return false;
        }
    }
    return res.length ? false : true;
};

缺失数字

给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

示例 1:

输入: [3,0,1]
输出: 2

let missingNumber = function(nums) {
    let res = 0;
    for (let i = 0; i <= nums.length; i++) {
        res ^= i ^ nums[i];
    }
    return res;
};


let missingNumber = function(nums) {
    let res = nums.length * (nums.length + 1) / 2;
    nums.forEach(num => res -= num);
    return res;
};

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

示例:

输入: 43261596
输出: 964176192
解释: 43261596 的二进制表示形式为 00000010100101000001111010011100 ，
     返回 964176192，其二进制表示形式为 00111001011110000010100101000000 。

var reverseBits = function(n) {
    var num = n.toString(2).split('');
    while(num.length < 32){num.unshift('0')};
    return parseInt(num.reverse().join(''), 2);
};

帕斯卡三角形

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

输入: 5
输出:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

var generate = function(numRows) {
    var res = [];
    var beforeNums = [];
    for(var i=1; i<=numRows; i++){
        var nums = new Array(i);
        if(i < 3){
            nums = nums.fill(1);
            
        }else{
            nums[0] = 1;
            nums[i-1] = 1;
            for(var j=1; j<i-1; j++){
                nums[j] = beforeNums[j-1] + beforeNums[j];
            }
        }
        beforeNums = nums;
        res.push(nums)
    }
    return res;
};

三数之和

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

var threeSum = function(nums) {
    nums.sort(function(a,b){
        return a-b;
    })
    var target,result=[],len=nums.length;
    for(var i=0;i<len;i++){
        if (target===nums[i]){
            continue;
        }
        else{
            target=nums[i];
        }
        var low=i+1,high=len-1;
        while(low<high){
            if(nums[low]+nums[high]===-target){
                result.push([target,nums[low],nums[high]]);
                do{
                   low++; 
                }while(nums[low]===nums[low-1]);
            }
            else if(nums[low]+nums[high]<-target){
                low++;
            }
            else{
                high--;
            }
        }
    }
    return result;
};

canvas 方法

rect

绘制矩形路径

context.rect(x, y, width, height);

xNumber：矩形路径的起点横坐标。
yNumber：矩形路径的起点纵坐标。
widthNumber：矩形的宽度。
heightNumber：矩形的高度。

restore

从对战的上方弹出存储的 canvas 状态，Canvas状态的存储使用的是save()方法。

context.restore();

rotate

旋转矩阵，顺时针方向

context.rotate(angle);

save

保存当前Canvas画布状态并放在栈的最上面，绘图效果本身不会被保存，保存的只是绘图状态

context.save();

scale

用来缩放Canvas画布的坐标系，只是影响坐标系，之后的绘制会受此方法影响，但之前已经绘制好的效果不会有任何变化。默认缩放中心点是Canvas的左上角(0, 0)坐标点，如果希望改变缩放中心点

context.scale(x, y);

xNumber：Canvas坐标系水平缩放的比例。支持小数，如果值是-1，表示水平翻转。
yNumber：Canvas坐标系垂直缩放的比例。支持小数，如果值是-1，表示垂直翻转。

setLineDash

设置虚线样式

ctx.setLineDash(segments);

segmentsArray：数值列表数组。例如[5, 5]，表示虚线的实线和透明部分长度是5像素和5像素。如果此参数值适合空数组[]，则表示实线，常用来重置虚线设置。

transform

方法可以对当前坐标系进行进一步变换，拉伸或者位移效果。

context.transform(a, b, c, d, e, f);

aNumber：水平缩放。
bNumber：水平斜切。
cNumber：垂直斜切。
dNumber：垂直缩放。
eNumber：水平位移。
fNumber：垂直位移。

setTransform

矩阵变换重置当前的坐标系。此方法和transform()方法的区别在于，后者不会完全重置已有的变换，而是累加。

context.setTransform(a, b, c, d, e, f);

aNumber：水平缩放。
bNumber：水平斜切。
cNumber：垂直斜切。
dNumber：垂直缩放。
eNumber：水平位移。
fNumber：垂直位移。

stroke

描边

context.stroke();
context.stroke(path);

pathObject：指Path2D对象。IE浏览器不支持。

strokeRect

矩形描边

context.strokeRect(x, y, width, height);

xNumber：描边矩形的起点横坐标。
yNumber：描边矩形的起点纵坐标。
widthNumber：描边矩形的宽度。
heightNumber：描边矩形的高度。

strokeText

文字描边

context.strokeText(text, x, y [, maxWidth]);

textString：用来描边的文本信息。
xNumber：描边文本的起点横坐标。
yNumber：描边文本的起点纵坐标。
maxWidth（可选）Number：当文本占据宽度超过此最大宽度时候，填充文本占据的最大宽度，通过压缩每个文本宽度进行适合，而非换行。

translate

方法可以对Canvas坐标系进行整体位移，实际开发常用来改变其它变换方法的变换中心点。

context.translate(x, y);

xNumber 坐标系水平位移的距离。 yNumber 坐标系垂直位移的距离。

数据可视化

科学可视化（Scientific Visualization）、信息可视化（Information Visualization）和可视分析学（Visual Analytics）三个学科方向通常被看成可视化的三个主要分支。而将这三个分支整合在一起形成的新学科 “数据可视化”

科学可视化

科学可视化（Scientific Visualization）是科学之中的一个跨学科研究与应用领域，主要关注三维现象的可视化，如建筑学、气象学、医学或生物学方面的各种系统，重点在于对体、面以及光源等等的逼真渲染。科学可视化是计算机图形学的一个子集，是计算机科学的一个分支。科学可视化的目的是以图形方式说明科学数据，使科学家能够从数据中了解、说明和收集规律。

信息可视化

信息可视化（Information Visualization）是研究抽象数据的交互式视觉表示以加强人类认知。抽象数据包括数字和非数字数据，如地理信息与文本。信息可视化与科学可视化有所不同：科学可视化处理的数据具有天然几何结构（如磁感线、流体分布等），信息可视化处理的数据具有抽象数据结构。柱状图、趋势图、流程图、树状图等，都属于信息可视化，这些图形的设计都将抽象的概念转化成为可视化信息。

可视分析学

可视分析学（Visual Analytics）是随着科学可视化和信息可视化发展而形成的新领域，重点是通过交互式视觉界面进行分析推理。

区别

科学可视化处理具有自然几何结构（磁场、MRI 数据、洋流）的数据。
信息可视化处理抽象数据结构，如树或图形。
可视分析学将交互式视觉表示与基础分析过程（统计过程、数据挖掘技术）结合，能有效执行高级别、复杂的活动（推理、决策）。

为什么需要数据可视化

快：视觉是人类获取外界信息最高速，最主要也是最重要渠道。
有效：利用人眼的感知和模式识别能力，可视化可以帮助我们增强认知，发现常规统计方法难以得到的洞察。
美：数据可视化是创造性的设计美学、缜密的数据算法和严谨的工程技术结合的产物，用形象、有趣的形式呈现沉闷繁杂的数据。
持久：人类的记忆被认为并不靠谱，但最近认知科学家发现，我们的大脑所捕捉的视觉细节比曾经所认为的要多得多。

数据可视化过程

数据可视化分析原则

准确：从数据转化到可视表达时不歪曲，不误导，不遗漏，忠实反映数据里包含的信息。
有效：信息传达有重点，克制不冗余，避免信息过载，用最适量的数据-油墨比（Data-ink Ratio）表达对用户最有用的信息。
清晰：表现方式清楚易读，具条理性，可以帮助用户快速达成目标，在最少的时间内获取更多的信息。
美：对数据的完美表达，合理利用视觉元素进行艺术创作，不过度修饰，给用户优雅的体验。

任务层次

可以简单的理解成数据呈现，信息加工，辅助决策。

数据获取：该层解决用户的第一是问题“是什么”，用户主要通过浏览查看来获取数据，其通用交互范式为 Overview + Detail（概览+细节），常见于传统数据报表、汇报型图表、大屏等，比如流量监控、区域销售大盘。

信息加工：该层解决用户的第二个问题“为什么”，当图上有看不懂的信息时，用户期望有人告诉他为什么会这样，或者自己查探明究竟，其通用交互范式为 Focus + Context（聚焦+关联），常见于富交互的统计报表，或海量、高维、多源的可视分析系统。

知识流转：该层解决用户的第三个问题“怎么办”，当获取洞见通用交互范式为 Annote + Guide（标记+指引），常见于可视分析系统、智能分析、智能决策系统，比如运营专员对异常点进行标记辅助管理员进行决策，智能系统对整体趋势进行解读与归因分析。

webGL

着色器是什么

定点着色器：顶点着色器是用来描述顶点特性（如：位置、颜色等）的程序。顶点是指二维或三维空间中的一个点，比如二维或三维图形的端点或交点。

片元着色器：进行逐片元处理过程如光照的程序。片元可以理解成像素。

var canvas = this.$refs.canvas
canvas.width = window.innerWidth - 200;
canvas.height = window.innerHeight - 56;
var VSHADER_SOURCE = `
    void main() {
        gl_Position = vec4(0.0, 0.0, 0.0, 1.0);
        gl_PointSize = 10.0;
    }
`;
var FSHADER_SOURCE = `
    void main() {
        gl_FragColor = vec4(1.0, 0.0, 0.0, 1.0);
    }
`;
var gl = canvas.getContext('webgl');
initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE);
gl.clearColor(0.0, 0.0, 0.0, 1.0);
gl.clear(gl.COLOR_BUFFER_BIT);
gl.drawArrays(gl.POINTS, 0, 1);

存储限定符

var VSHADER_SOURCE = `
    attribute vec4 a_Position;
    attribute float a_PointSize;
    void main() {
        gl_Position = a_Position;
        gl_PointSize = a_PointSize;
    }
`;
var FSHADER_SOURCE = `
    precision mediump float;
    uniform vec4 u_FragColor;
    void main() {
        gl_FragColor = u_FragColor;
    }
`;
var gl = canvas.getContext('webgl');
initShaders(gl, VSHADER_SOURCE, FSHADER_SOURCE);
var a_Position = gl.getAttribLocation(gl.program, 'a_Position');
var a_PointSize = gl.getAttribLocation(gl.program, 'a_PointSize');
var u_FragColor = gl.getUniformLocation(gl.program, 'u_FragColor');

gl.vertexAttrib3f(a_Position, 0.5, 0.0, 0.0);
gl.vertexAttrib1f(a_PointSize, 100);
gl.uniform4f(u_FragColor, `${Math.round(Math.random())}.0`, `${Math.round(Math.random())}.0`, `${Math.round(Math.random())}.0`, 1.0)

gl.clearColor(0.0, 0.0, 0.0, 1.0);
gl.clear(gl.COLOR_BUFFER_BIT);
gl.drawArrays(gl.POINTS, 0, 1);

<存储限定符> <类型> <变量名> attribute vec4 a_Position <存储限定符> <类型> <变量名> uniform vec4 u_FragColor ### 总结 webGL 整体是在 canvas 上进行绘制的，主要靠操作顶点着色器和片源着色器进行绘制，顶点着色器绘制位置，片源着色器绘制颜色。绘制过程大致是通过 initShaders 对着色器代码进行执行，然后先进行顶点着色器得到位置，然后用片源着色器进行染色。如果是变量，则需要再定义着色器时定义好参数，在 initShaders 之后获取对应着色器参数的缓存位置，getAttribLocation（顶点着色器）、getUniformLocation（片源着色器）；获取参数之后，通过 vertexAttrib3f（顶点着色器）和 uniform4f（片源着色器）进行传参。最后通过 drawArrays 进行绘制。 webGL 符合右手坐标系，坐标系以 canvas 宽高的一半作为 1，canvas 的中心点作为起始点，屏幕的坐标系到 webGL 坐标系就会有个转换。