命令

安装

1

npm install -g typescript

973. 最接近原点的K个点 K Closest Points to Origin

• We have a list of points on the plane. Find the K closest points to the origin (0, 0)
• Input: points = [[1,3],[-2,2]], K = 1 Output: [[-2,2]]

运行java程序

Hello.java =>(编译 javac) Hello.class =>(执行) Run on JVM

两数之和

• 给一个整数数组nums和目标值target，找出和为目标值的两个整数的下标
• [2,7,11,15] 9 => [0,1]

思路：

1. 使用一个map将遍历过的数字存起来，{key: value}中，key是值，value是下标。
2. 每次遍历在map中查找是否有key为target-nums[i]的值
3. 如果取到，则条件成立，返回
4. 如果没有取到，则将当前值为key，下标作为value存入map

每次用它都会有各种奇奇怪怪的问题，每隔一段时间就要解决一下上不去网的问题。。

贪心算法

• 对问题求解的时候，总是做出在当前看来是最好的做法
• 适用场景：问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解
• 与动态规划的不同：对每个子问题的解决方案都做出选择，不能回退

比较

1. 回溯算法：重复计算
2. 贪心算法：永远局部最优
3. 动态规划：记录局部最优子结构，多种记录值

回溯算法

暴力求解！列出所有，根据需要剪枝！

• 适合由多个步骤组成的问题，并且每个步骤都有多个选项
• 从某一步的所有可能选项里选择出一个可行方案，不满足约束条件，回溯到上一步，尝试其他选项
• 所有状态均不满足，无解

链表

• 用一组任意存储的单元来存储线性表的数据元素，一个对象存储着本身的值和下一个元素的地址
• 需要遍历才能查询到元素，查询慢
• 插入元素只需要断开连接重新赋值，插入快

1
2
3
4

function ListNode(x){
  this.val = x;
  this.next = null;
}

二叉树

每个节点最多有两个子树的树结构，左子树和右子树

1
2
3
4
5
6
7

class TreeNode {
  constructor(val) {
    this.val = val;
    this.left = null;
    this.right = null;
  }
}

排序算法

快速排序

排序方法

选择一个目标值，比目标值小的放在左边，比目标值大的放在右边，目标值的位置已经排好，将左右两侧再进行排序

实现思路

1. 记录一个索引l从数组最左侧开始，记录一个索引r从数组最右侧开始，记录一个target（选第一位为目标值）
2. while循环：在l<r的条件下，找到右侧小于target的值array[r]，并将其赋值到array[l]
   在l<r的条件下，找到左侧大于target的值array[l]，并将其赋值到array[r]
3. 这样当l=r时，左侧的值全部小于target，右侧的值全部大于target，将target放到该位置