2043. 简易银行系统

你的任务是为一个很受欢迎的银行设计一款程序，以自动化执行所有传入的交易（转账，存款和取款）。银行共有 n 个账户，编号从 1 到 n 。每个账号的初始余额存储在一个下标从 0 开始的整数数组 balance 中，其中第 (i + 1) 个账户的初始余额是 balance[i] 。

请你执行所有有效的交易。如果满足下面全部条件，则交易有效：

指定的账户数量在 1 和 n 之间，且取款或者转账需要的钱的总数小于或者等于账户余额。

实现 Bank 类：

Bank(long[] balance) 使用下标从 0 开始的整数数组 balance 初始化该对象。
boolean transfer(int account1, int account2, long money) 从编号为 account1 的账户向编号为 account2 的账户转帐 money 美元。如果交易成功，返回 true ，否则，返回 false 。
boolean deposit(int account, long money) 向编号为 account 的账户存款 money 美元。如果交易成功，返回 true ；否则，返回 false 。
boolean withdraw(int account, long money) 从编号为 account 的账户取款 money 美元。如果交易成功，返回 true ；否则，返回 false 。

标着中等其实与大一时的OOP难度差不多。
Transfer可以重用Deposit和Withdraw来实现，提高代码重用性。
额外封装一个Check函数来进行有效交易的校验。

public class Bank {
    long[] balance;
    public Bank(long[] balance) {
        this.balance = balance;
    }
    public bool Transfer(int account1, int account2, long money) {
        if(check(account2)&&Withdraw(account1,money)) 
            return Deposit(account2,money);
        return false;
    }
    public bool Deposit(int account, long money) {
        if(!check(account)) return false;
        balance[account-1] += money;
        return true;
    }
    public bool Withdraw(int account, long money) {
        if(!check(account) || balance[account - 1] < money) return false;
        balance[account - 1]-=money;
        return true;
    }
    private bool check(int account){
         return account>0 && account<=balance.Length;
    }
}

606. 根据二叉树创建字符串

你需要采用前序遍历的方式，将一个二叉树转换成一个由括号和整数组成的字符串。空节点则用一对空括号 “()” 表示。而且你需要省略所有不影响字符串与原始二叉树之间的一对一映射关系的空括号对。

原本打算用先根遍历，但这样做不好处理括号的插入。
最直接使用暴力破解。

public class Solution {
  StringBuilder stringBuilder = new StringBuilder();
  public string Tree2str(TreeNode root) {
    pre_order(root);
    return stringBuilder.ToString();
  }

  private void pre_order(TreeNode node){
    if(node != null) {
      stringBuilder.Append(node.val);
      if(node.left != null || node.right != null) {
        stringBuilder.Append("(");
        pre_order(node.left);
        stringBuilder.Append(")");
        if(node.right != null){
          stringBuilder.Append("(");
          pre_order(node.right);
          stringBuilder.Append(")");
        }
      } 
    }
  }
}

587. 安装栅栏

在一个二维的花园中，有一些用 (x, y) 坐标表示的树。由于安装费用十分昂贵，你的任务是先用最短的绳子围起所有的树。只有当所有的树都被绳子包围时，花园才能围好栅栏。你需要找到正好位于栅栏边界上的树的坐标。

示例 1: 输入: [[1,1],[2,2],[2,0],[2,4],[3,3],[4,2]] 输出: [[1,1],[2,0],[4,2],[3,3],[2,4]] 解释: 示例 2: 输入: [[1,2],[2,2],[4,2]] 输出: [[1,2],[2,2],[4,2]] 解释: 即使树都在一条直线上，你也需要先用绳子包围它们。

注意: 所有的树应当被围在一起。你不能剪断绳子来包围树或者把树分成一组以上。输入的整数在 0 到 100 之间。花园至少有一棵树。所有树的坐标都是不同的。输入的点没有顺序。输出顺序也没有要求。

（Andrew 算法）

Andrew 算法正是用于求解凸包上的所有点（围成所有点的最小周长），其算法逻辑将凸包分为「上凸壳」和「下凸壳」，并分别画出（蓝色分割线将凸包分为两部分）：

对所有点进行双关键字排序，先根据 x 坐标排升序，后根据 y 排升序；根据 x 排升序的目的，是为了我们能够往一个方向画出凸包边缘（从左往后画出一半凸壳，从右往左画出另外一半），而将 y 升序目的是可以确保一旦我们现在从 a 到 b 进行连线，那么 a 到 b 之间的所有点能够确保被围住；
使用栈来维护所有凸包上的点，或者说凸包上的边，会更为准确，凸包起点元素会在栈中出现两次（首尾），因此更为准确的描述应该是使用栈维护凸包的所有的边，栈中相邻元素代表凸包上的一条边；
分别「从前往后」和「从后往前」处理排序好的所有点，来分别画出凸包的上下两部分，根据画的是第一部分还是第二部分，维护栈内元的处理逻辑稍有不同：
1. 画的是凸包的第一部分：
  
  若栈内元素少于 2 个，组成一条线至少需要两个点，说明此时第一条边都还没画出，直接将元素添加到栈中；
  若栈内元素不少于 2 个，考虑是否要将栈顶的边删掉（由栈顶前两个元素组成的边）假设栈顶元素为 b，栈顶元素的下一位为 a，即栈顶存在一条 a 到 b 的边，当前处理到的点为 c，此时我们根据 ac 边是否在 ab 边的时针方向来决定是否要将 ab 边去掉：
  按照上述逻辑处理完所有点，凸包第一部分的点（边）都存在于栈中。
2. 画的是凸包的第二部分：

逻辑同理，唯一需要注意的是，第一部分的凸包边我们不能删去，假定处理完第一部分凸包，我们栈内有 m 个元素，我们需要将上述「栈顶元素不少于 2 个」的逻辑替换为「栈顶元素大于 m 个」，同时已参与到凸包第一部分的点，不能再考虑，因此需要额外使用一个 vis 数组来记录使用过的点。
一些细节，为了方便取得栈顶的前两位元素，我们使用数组实现栈，stk 代表栈容器，tp 代表栈顶元素下标。

正如刚刚讲到，起点会被入栈两次（对应第一条边和最后一条边），因此输出方案时，栈顶和栈底我们只选其一即可。

public class Solution {
    int[] SubVector(int[] a,int[] b){
        return new int[] {a[0]-b[0],a[1]-b[1]};
    }
    double Cross(int[] a,int[] b){
        return (a[0] * b[1] - a[1] * b[0]);
    }
    double GetArea(int[] a, int[] b, int[] c){
        return Cross(SubVector(b,a),SubVector(c,a));
    }
    public int[][] OuterTrees(int[][] trees) {
        Array.Sort(trees,(a,b)=>{
            return a[0] != b[0] ? a[0] - b[0]:a[1] - b[1];
        });
        int n = trees.Length, tp = 0;
        int[] stk = new int[n + 10];
        bool[] vis = new bool[n + 10];
        stk[++tp] = 0;
        for(int i = 1; i < n; i ++){
            int[] c = trees[i];
            while(tp >= 2){
                int[] a = trees[stk[tp-1]], b = trees[stk[tp]];
                if(GetArea(a,b,c) < 0) vis[stk[tp--]] = false;
                else break;
            }
            stk[++tp] = i;
            vis[i] = true;
        }
        int size = tp;
        for(int i = n - 1; i >=  0; i--){
            if(vis[i]) continue;
            int[] c = trees[i];
            while(tp > size){
                int[] a = trees[stk[tp - 1]],b = trees[stk[tp]];
                if(GetArea(a,b,c) < 0) tp--;
                else break;
            }
            stk[++tp] = i;
        }
        int[][] ans = new int[tp - 1][];
        for(int  i = 1; i < tp; i++) ans[i - 1] = trees[stk[i]];
        return ans;
    }
}

417. 太平洋大西洋水流问题

有一个 m × n 的矩形岛屿，与太平洋和大西洋相邻。 “太平洋” 处于大陆的左边界和上边界，而 “大西洋” 处于大陆的右边界和下边界。这个岛被分割成一个由若干方形单元格组成的网格。给定一个 m x n 的整数矩阵 heights ， heights[r][c] 表示坐标 (r, c) 上单元格高于海平面的高度。岛上雨水较多，如果相邻单元格的高度小于或等于当前单元格的高度，雨水可以直接向北、南、东、西流向相邻单元格。水可以从海洋附近的任何单元格流入海洋。返回网格坐标 result 的 2D列表，其中 result[i] = [ri, ci] 表示雨水可以从单元格 (ri, ci) 流向太平洋和大西洋。示例 1：输入: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]] 输出: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]

示例 2：输入: heights = [[2,1],[1,2]] 输出: [[0,0],[0,1],[1,0],[1,1]]

public class Solution {
    int[][] dirs = 
    new int[][]{
        new int[]{-1,0},
        new int[]{1,0},
        new int[]{0,-1},
        new int[]{0,1}
    };
    int [][] heights;
    int m,n;
    public IList<IList<int>> PacificAtlantic(int[][] heights) {
        this.heights = heights;
        this.m = heights.Length;
        this.n = heights[0].Length;
        bool[][] Pacific = new bool[m][];
        bool[][] Atlantic = new bool[m][];
        for(int i = 0; i < m; i++){
            Pacific[i] = new bool[n];
            Atlantic[i] = new bool[n];
        }
        for(int i = 0; i < m; i++){
            DFS(i,0,Pacific);
        }
        for(int j = 0; j < n; j++){
            DFS(0,j,Pacific);
        }
        for(int i = 0; i < m; i++){
            DFS(i,n-1,Atlantic);
        }
        for(int j = 0; j < n; j++){
            DFS(m-1,j,Atlantic);
        }
        IList<IList<int>> result = new List<IList<int>>();
        for(int i = 0; i < m; i++)
            for(int j = 0; j < n; j++)
                if(Pacific[i][j] && Atlantic[i][j]){
                    IList<int> cell = new List<int>();
                    cell.Add(i);
                    cell.Add(j);
                    result.Add(cell);
                }
        return result;
    }

    public void DFS(int row, int col, bool[][] ocean){
        if(ocean[row][col]) return;
        ocean[row][col] = true;
        foreach(int[] dir in dirs){
            int newRow = row + dir[0],newCol = col + dir[1];
            if(newRow >= 0 && newRow < m && newCol >= 0 && newCol < n && heights[newRow][newCol] >= heights[row][col]){
                DFS(newRow,newCol,ocean);
            }
        }
    }
}

leetcode刷题

每日一题

2043. 简易银行系统

606. 根据二叉树创建字符串

587. 安装栅栏

（Andrew 算法）

417. 太平洋大西洋水流问题