算法
从排序数组中删除重复项
var removeDuplicates = function(nums) {
var i = 1;
while(i < nums.length){
if(nums[i-1] === nums[i]){
nums.splice(i, 1);
}else{
i++;
}
}
return nums.length
};
买卖股票的最佳时机
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
设计一个算法来计算你所能获取的最大利润
var maxProfit = function(prices) {
var total = 0;
var min = prices[0];
for(var i=1; i<prices.length; i++){
if(prices[i] < prices[i-1]){
total += prices[i-1] - min;
min = prices[i];
}
if(i === prices.length - 1){
total += prices[i] - min;
}
}
return total
};
数组是否存在重复元素
var containsDuplicate = function (nums) {
const set = new Set(nums)
return set.size != nums.length
};
只出现一次的数字
var singleNumber = function(nums) {
let result = 0;
nums.forEach(el => (result ^= el));
return result;
};
有效数独 判断一个 9x9 的数独是否有效。
var isValidSudoku = function(board) {
var pieceMap = {};
columnsMap = {}
var res = board.some((arr, index1) => {
var numMap = {};
return arr.some((item, index2) => {
pieceKey = Math.floor(index1/3) + '' + Math.floor(index2/3);
if(!pieceMap[pieceKey]){
pieceMap[pieceKey] = {}
}
if(item === '.'){
return false
}
if(numMap[item]){
return true;
}else{
numMap[item] = true;
}
if(pieceMap[pieceKey][item]){
return true;
}else{
pieceMap[pieceKey][item] = true;
}
if(!columnsMap[index2]){
columnsMap[index2] = {};
}
if(columnsMap[index2][item]){
return true
}else{
columnsMap[index2][item] = true;
}
})
});
if(res){
return false
}
return true
};
n*n 数组矩阵旋转
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
]
// 转换成
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]
const rotate = (matrix) => {
matrix.reverse()
for (let i = 0; i < matrix.length; i++) {
for (let j = i + 1; j < matrix[0].length; j++) {
let tmp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = tmp
}
}
};
字符串反转
s = "hello" => "olleh"
/*
* 思路1：反向遍历字符串
*/
var s1 = "";
for (var i = s.length-1; i >= 0; i--) {
s1 += s[i];
}
return s1;
/*
* 思路2:1.建立两个指针，分别指向首尾，遍历数组，直至指针相遇；
2.将两个指针值交换
超出时间
*/
// var s1 = Array.from(s);
// var left = 0;
// var right = s.length-1;
// while (left < right) {
// temp = s1[left];
// s1[left] = s1[right];
// s1[right] = temp;
// }
// return s1.join("");
颠倒整数
给定一个 32 位有符号整数，将整数中的数字进行反转。-123 => -321 120 => 21
var reverse = function(x) {
var minn = -(1 << 30) * 2;
var maxn = (1 << 30) * 2 - 1;
var tag = x < 0 ? -1 : 1;
var s = x * tag + '';
var s1 = ''
for (var i = s.length; i--;) {
s1 += s[i];
}
var res = (s1 - 0) * tag;
if (res < minn || res > maxn)
return 0;
else
return res;
};
字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1
var firstUniqChar = function(s) {
var str = s.toLowerCase();
for(var i=0;i<str.length;i++){
var ch = str.charAt(i);
//如果后面没有该字符，且前面也没有出现过
if(str.indexOf(ch) == i && str.lastIndexOf(ch) == i){
return i;
}
}
return -1;
};
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的一个字母异位词
var isAnagram = function(s, t) {
var codeMap = {};
if(s.length !== t.length) return false;
for(var i=0; i<s.length; i++){
var code = s.charCodeAt(i)
codeMap[code] = codeMap[code] ? ++codeMap[code] : 1;
}
for(var i=0; i<t.length; i++){
var code = t.charCodeAt(i)
if(!codeMap[code]) return false;
codeMap[code]--;
}
for(var i in codeMap){
if(codeMap[code] !== 0) return false;
}
return true
};
动画
css 动画
早期动画是通过 setInterval 或者 setTimeout 来修改对应的 css 属相来做动画，这样做的动画偶尔会出现跳帧，动画复杂了之后也会卡顿，主要是性能的瓶颈。
后来有了 requestAnimate 方法，允许在每一帧的空闲时间里调用，还是用 js 去调用 CSSOM 的 API 来做动画。
css3 添加了两个属性：transition 和 animation 来控制动画，我们经常说这两个属性会启动 GPU 加速来调用性能更高的动画。
GPU 加速
以 translate 为例，使用 translate3D 其实是将当前 DOM 层级提高到最上层，使得这个 DOM 的重排都不会影响其他 DOM 的布局，减少重排影响提高重绘
不关注重排之后，只关注重绘。此时就可以用 GPU 单纯来绘制页面，所以加速的并不是说 GPU 本身。而是避免了重排了之后整体绘制性能增强了。
transition
过渡动画：我们把动画如果分成简单的两个状态，起始状态和终止状态，从起始状态平滑的变成终止状态的过程就是动画。transition 就是完成这个平滑过渡的动画
// 示例
transition: property duration timing-function delay;
classA {
width: 100px;
transition: width 2s;
}
classB {
width: 200px;
}
上面这个简单的动画就是两个状态，使用过渡动画将两个状态进行平滑过渡。可以说 transition 是面向结果的，就是两个状态，不能控制动画过程中的变化。
animation
那如果我们期望控制动画过程怎么做呢。使用 animation，animation 会将动画分成 0-100%(或者 from to, from = 0，to = 100%) 这么多帧。
@keyframes
要使用动画之前，首先需要定义动画。将整个动画分成多个动画帧。然后对每个动画帧的状态进行定义。
@keyframes rainbow {
0% { background: #c00 }
50% { background: orange }
100% { background: yellowgreen }
}
@keyframes rainbow {
from { background: #c00 }
50% { background: orange }
to { background: yellowgreen }
}
上面是定义了一个动画 rainbow，两种定义的方法效果是一样的。
animation
animation: name duration timing-function delay iteration-count direction;
animation: rainbow 1s linear 3s 3 normal;
这是使用动画的方式。动画会根据定义的 keyframes 定义的动画那一帧的状态进行设定。
js 动画
首先问自己一个问题有了 css 动画为什么还需要用 js 的动画？
两者其实会有自己的适用场景。
css 动画：适用于两个简单状态的平滑过度，或者是几个关键帧的处理。第一个是用 transition。第二个是用 animation。而且 css 做的动画偏自动化一些。中途如果需要根据状态来判断就不适用了
js 动画：适用于复杂场景的动画，如果需要交互介入就需要 js 的动画了。更高级一些的是现在的 3D 动画。
setTimeout、setInterval
将动画分成诊之后，其实就是每隔多少秒调用一次，上述两个方法在 js 中就是每隔多久调用一次。早期使用这两个方法每隔多少时间进行一次状态的改变。调用 DOM 或者调用 CSSOM，改变当前元素的状态。高度、宽度的改变就是动画
但是如果单个 setInterval 计算太多。就会出现有些 setInterval 丢帧。因为上一个 setInterval 还没有执行，后面的就已经执行过了，造成某些过程跳过，就是跳帧了。
用 setTimeout 模拟 setInterval 这样会防止丢帧，因为下一次 setTimeout 一定要等上一次执行完了才会执行。但是 setTimeout 中的计算太过集中的话就会出现动画卡顿，因为下一帧动画迟迟没有来。
requestAnimationFrame
上述的问题都是因为 js 的执行是分片的。会把执行放在每一个运行单元里，因为 js 是自动 GC，并且页面会有每隔一个 FPS 进行一次屏幕重绘，所以所有的状态都会在那个时刻绘上去。所以 setTimeout 和 setInterval 的问题其实是出在或快或慢于每帧的绘制
后来就有了 requestAnimationFrame API，由于上述问题，所以需要在每次执行动画刷新帧之前执行一帧的状态。如果执行超过当前帧的执行时间，浏览器会停止计算执行，去执行重绘和重排页面。以保证用户看到的页面不会被卡顿。
所以 requestAnimationFrame 用来做 js 的动画是最适合的。但是每次回调里的内容不宜太多涉及到计算。如果有计算最好以异步的方式去执行，而 API 里只是去获取当前应该展示的状态。
GreenSock 的 TweenMax
这是一个动画库，用户自动处理 js 动画的库。用于指定一个 dom 在一段时间点里，将状态改成另一个的状态，实际上就是将两个状态取出来，用时间除一下次时间段里变化的状态，然后每隔一段时间叠加。
TweenMax.to(this.$refs.mask, 0.3, {
opacity: 1
});
还可以将动画分解成一个时间段，将每个状态分成百分比，然后设置当前的进度
var tl = new TweenMax.TimelineLite();
var aaa = { x: 100 }
tl.to(aaa, 1, {
x: 300,
// autoAlpha: 0
})
.to($box, 1, {
x: '+=200px',
// autoAlpha: 1
});
tl.pause();
tl.progress(20%);
gsap 里还有很多动画值得探索，常规的动画都能找到
主轴动画
在这里我自创了一个概念，主轴动画，在做动画时。先找到当前动画中时间线最长的动画，将这个动画的过程作为主轴。将这个动画的时间分成 1-100%，甚至粒度可以更细。然后其他的动画的进度也做成 1-100% 的进度，称为附属动画。
主轴动画随着某些条件来动。比如时间、滚动条。随着时间的变动来设置百分比。附属动画监听主轴动画的百分比变化来设置自己的动画时机。
这个动画就变得可控。更加大型的动画，也可以再分模块，一个主轴附属几个小的主轴，然后更小动画再随着小主轴再动。
3D 动画
canvas.getContext(contextType, contextAttributes);
// canvas 获取绘图上下文
var context = canvas.getContext('2d');
// WebGL 获取绘图上下文
var gl = canvas.getContext('webgl') // 或 experimental-webgl
Canvas 是浏览器封装好的一个绘图环境，在实际进行绘图操作时，浏览器仍然需要调用 OpenGL API。而 WebGL API 几乎就是 OpenGL API 未经封装，直接套了一层壳，threejs 是一个 webGL 框架。
webGL 整体就是用来在 canvas 上绘制 3D 效果的 API。目前封装的比较好的是 threejs。
首先一个 3D 动画由这么几部分元素组成。容器、舞台、演员、天空、相机、控制器等
容器
动画需要有个承载的体现，这个我们一般称为容器，在这里我们一般认为 canvas 标签就是容器。这个容器是用来展示动画的载体。整个容器可以认为是一个无边无际的三维坐标系，并且有正有负。
舞台
舞台就是一个动画的场景，如果我们认为动画是一个 3D 的场景，一个小的动画只用一个场景就可以，但是一个复杂的大型的动画是由一个一个场景组合起来的。每个场景又有自己的动画，区分场景是为了将大的动画分成几组来完成，降低复杂度。
一个舞台就是在这个无边无际的坐标系中的其中一块立体空间。
演员
有了舞台就需要演员来完成动画，动画场景中的每一个动画元素都可以称为一个演员，演员也可以分组，一个复杂的演员可以由多个小的动画元素组成，而每一个动画元素也可以称为一个演员，主要是看其相关性，将演员分组也是降低复杂度的一种。
演员基本上就是场景中的动画元素了，一个复杂的场景动画演员有自己的运动轨迹，演员在场景中完成自己的动画轨迹就完成了自己的动画，如果演员的运动轨迹是由其他因素所决定的，那就根据自己的轨迹去完成。
天空
我们可以理解为整个 3D 动画的场景是被放在一个立体的盒子中的，天空就是盒子内部的内表皮，盒子内部的六个面都可以有自己的颜色图片，我们在盒子内部的舞台中，看起来这个就像是动画的天空。
当然外表皮也是可以着色的，但我们一般是把相机放在舞台内部，所有外表皮的意义并不大。
相机
这个是非常重要的，与其说相机不如说是镜头摆放的位置，threejs 中有两种摄像机方式，正交投影和透视投影两种，最好自己有过实际的 demo 来体会一下两种相机的不同。
相机摆放在不同的位置就能看到不同角度位置的动画，在立体坐标系中，将相机让在某一个舞台面前就能看到这个舞台上的动画。主要是看动画想以哪种形式进行展现，然后设置好相机的位置。动画场景的切换也是通过移动相机，将摄像机放到下一个场景的位置。
控制器
一般情况下我们动画只是播放，很少有交互，简单的交互点击，拖动这些是不用设计到控制器的。控制器是控制动画展现的位置的东西，其实就是控制摄像头的摆放，根据不同的交互类型让摄像头按照某种规律进行运动，主要用于游戏中的交互，可以自行写个 demo 试试每种控制器都有什么方式，分为下面几类：
- OrbitControls：旋转控制器
- FlyControls：飞行控制器
- PointerLockControls：指针控制器
- TrackballControls：轨迹球控制器
- TransformControls：变换物体控制器
动画刷新
动画实际上是由一帧一帧的静态图片连贯组合出来的，也就是说我们想要看到动画，需要不断的刷新页面，然后展现当前动画场景的不同状态，不断的变化的状态连贯起来就是动画了。fps 就不说了，动画是需要 requestAnimationFrame 不断执行，每次执行都去 render 当前动画的状态。
实例
现在动画的实际讲解还是很少，很多都要去翻看很多资料才能收获一点点知识，包括我自己也是一知半解，能做出实际的动画 demo，也做过几个线上的大型场景动画，但是自己要去建模设计还是不是很懂的。下面是相关这些讲解的实际例子。
动画实例
介绍几个 3D 动画框架，threejs 就不说了。
pixi.js
这个是一个国外做动画的第三方框架，可以支持 2D 和 webGL 的渲染，非常容易上手，适合做平面的场景动画。
网易出的好几个动画都是用的 pixi 来做的，网易的动画感觉不错，质量很高，我也模仿过几个。主轴动画的柯南和哈利波特。一镜到底的年度动画
Aframe
是 FF 浏览器出的一套 VR 的组件化方案，通过标签的方式 a-scene 原生支持场景动画，用来做 VR 特别方便。
hilo
hilo 是阿里出的一套动画方案，支持过淘宝双十一动画，万花筒的那个一镜到底的项目，按照官网一步一步走也能搭建出一个 flappy brid，为了看自己是否理解，改变了运动轨迹，让 flappy bird 能永久通关