Day7

最大子序和

1. 题目：给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入: [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

2. 题目解析：

   • 动态规划，维护一个数表示以其为端点的最大子序列和，满足如下表达式
   \[f(n) = max(f(n-1) + a[i], a[i]) \]

   class Solution {
       public int maxSubArray(int[] nums) {
           int pre = 0, max = nums[0];
           for(int num : nums){
               pre = Math.max(pre + num, num);
               max = Math.max(pre, max);
           }
           return max;
       }
   }
   

   • 分治法，线段树的方法，维护一个对象，包含 \(lSum\)，\(rSum\)，\(iSum\)，\(mSum\) 四个变量，分别表示以某一点为左端点的最大子段和，以某一点为右端点的最大子段和，区间和，最大子段和，分治为左区间 \([l, mid]\) 和 \([mid + 1, r]\) 合成后满足如下的关系表达式：

   关系表达式
   iSum = l.iSum + r.iSum
   lSum = max(l.lSum, l.iSum + r.lSum)
   rSum = max(r.rSum, l.rSum + r.iSum)
   mSum = max(max(l.mSum,r.mSum),l.rSum + r.lSum)

   class Status{
       public int lSum, rSum, iSum, mSum;
       public Status(int lSum, int rSum, int iSum, int mSum){
           this.lSum = lSum;
           this.rSum = rSum;
           this.iSum = iSum;
           this.mSum = mSum;
       }
   }
   class Solution {
       public int maxSubArray(int[] nums) {
           return tree(0, nums.length - 1, nums).mSum;
       }
       public Status tree(int l, int r, int[] nums){
           if(l >= r)
               return new Status(nums[l], nums[l], nums[l], nums[l]);
           int mid = l + r >> 1;
           //区间划分
           Status p = tree(l, mid, nums);
           Status q = tree(mid + 1, r, nums);
           return push_up(p, q);
       }
       public Status push_up(Status l, Status r){
           int lSum, rSum, mSum, iSum;
           iSum = l.iSum + r.iSum;
           lSum = Math.max(l.lSum, l.iSum + r.lSum);
           rSum = Math.max(r.rSum, l.rSum + r.iSum);
           mSum = Math.max(Math.max(l.mSum, r.mSum), l.rSum + r.lSum);
           return new Status(lSum, rSum, iSum, mSum);
       }
   }
   

   移动零

   1. 题目：给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

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

   2. 解析：采用一个变量记录 0 的个数，将每位数字进行相关的移动。

   class Solution {
       public void moveZeroes(int[] nums) {
           //使用 cnt 记录 0 的个数
           int cnt = 0;
           for(int i = 0; i < nums.length; i ++){
               //数组内的元素前移，并改变记录的元素的值
               nums[i - cnt] = nums[i];
               if(nums[i] == 0)
                   cnt ++;
           }
           //扫尾工作，将 cnt 个扫尾位置的元素置为 0 
           for(int i = nums.length - cnt; i < nums.length; i ++)
               nums[i] = 0;
       }
   }
   

   最小栈

   1. 题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

      push(x) —— 将元素 x 推入栈中。
      pop() —— 删除栈顶的元素。
      top() —— 获取栈顶元素。
      getMin() —— 检索栈中的最小元素。

   2. 题目解析：很明显的数据结构类型的问题，难度较小，细心做即可。

   class MinStack {
       private List<Integer> stack;
       //要求常数时间复杂度，因此直接类内记录最小值，查询时直接返回
       private int min;
       private int minIndex = 0;
       public MinStack() {
           stack = new ArrayList<Integer>();
           min = Integer.MAX_VALUE;
       }
       
       public void push(int x) {
           stack.add(x);
           if(min > x){
               min = x;
               minIndex = stack.size() - 1;
           }
       }
       
       public void pop() {
           if(minIndex == stack.size() - 1){
               min = Integer.MAX_VALUE;
               //一旦删去的最后一个位置的元素恰好是最小元素，只能使用O（n）的复杂度重新查询
               for(int i = 0; i < stack.size() - 1; i ++){
                   if(min > stack.get(i)){
                       min = stack.get(i);
                       minIndex = i;
                   }
               }
           }
           stack.remove(stack.size() - 1);
       }
       
       public int top() {
           return stack.get(stack.size() - 1);
       }
       
       public int getMin() {
           return min;
       }
   }
   
   /**
    * Your MinStack object will be instantiated and called as such:
    * MinStack obj = new MinStack();
    * obj.push(x);
    * obj.pop();
    * int param_3 = obj.top();
    * int param_4 = obj.getMin();
    */
   

   单词搜索

   1. 题目：给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。

   board =
   [
     ['A','B','C','E'],
     ['S','F','C','S'],
     ['A','D','E','E']
   ]
   
   给定 word = "ABCCED", 返回 true
   给定 word = "SEE", 返回 true
   给定 word = "ABCB", 返回 false
   

   2. 题目解析：很明显的搜索回溯问题，但尤其注意一点，搜索过程中因为避免单元格内字母被重复使用，所以应当使用一个 visit 数组记录，但 visit 数组为避免被递归函数影响，必须判度完后撤销操作，否则 visit 数组沿线的所有被访问的节点都将设置为已经访问。

   class Solution {
       public int [][]dv = new int[][]{{0, 1}, {1, 0}, {-1, 0}, {0, -1}};
       public boolean exist(char[][] board, String word) {
           int m = board.length;
           int n = board[0].length;
           int [][] visit = new int[m][n];
           for(int i = 0; i < m; i ++){
               for(int j = 0; j < n; j ++){
                   //寻找起点，并调用函数 search
                   if(board[i][j] == word.charAt(0) && search(board, i, j, 1, word, visit))
                       return true;
               }
           }
           return false;
       }
       // search 函数参数的具体意义，i,j表示搜索的起点，k 表示需要搜索的字符在字符串中的位置，visit数组表示访问情况，原有的单元格是否已经被访问。
       public boolean search(char[][] board, int i, int j, int k, String word,int[][] visit){
           //递归的终止条件
           if(k == word.length())
               return true;
           //搜索的起点标记为已经访问
           visit[i][j] = 1;
           boolean res = false;
           for(int[] di : dv){
               int x = i + di[0];
               int y = j + di[1];
               //判度条件，x,y 坐标的节点还未被访问过，该节点字母等于字符串第 k 个字母，搜索以 x,y 节点为坐标的节点周围是否有等于 k + 1 个字母的字符
               if(x >= 0 && x < board.length
                 && y >= 0 && y < board[0].length
                 && visit[x][y] == 0 && board[x][y] == word.charAt(k)
                 && search(board, x, y, k + 1, word, visit)){
                   res = true;
                   break;
                 }
           }
           //记住，判断完后，撤销 visit 数组，否则不能回溯
           visit[i][j] = 0;
           return res;
       }
   }