1.Z 字形变换（6）

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P A H N

A P L S I I G

Y I R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例1：

输入：s = "PAYPALISHIRING", numRows = 3

输出："PAHNAPLSIIGYIR"

解题思路：使用二维数组mat[r][c]存储排好序的字母，每一个周期t中有r+r-2=2r-2个字符，占用r-1列。一共有n/t个周期，列数c 等于n/t*(r-1)。遍历整个字符串，当下标i mod t < r-1时向下移动，否则向右上方移动，最后将mat中的字符拼接在一个字符串里即为答案。

class Solution {    public String convert(String s, int numRows) {        int n = s.length();        if(numRows==1 || numRows>=n){            return s;        }        int t = 2*numRows-2;        //(n+t-1)/t是为了保证周期数可以向上取整        int c = (n+t-1)/t*(numRows-1);        char[][] mat = new char[numRows][c];        int x=0, y=0;        for(int i=0; i<n; i++){            mat[x][y] = s.charAt(i);            if(i % t < numRows-1){                x++;            }            else{            x--;            y++;            }        }        StringBuffer ans = new StringBuffer();        for(char[] row: mat){            for(char col: row){                if(col != 0){                    ans.append(col);                }            }        }        return ans.toString();    }}

2.分发饼干（455）

假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。

对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

示例 1:

输入: g = [1,2,3], s = [1,1]

输出: 1 解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。

虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。 所以你应该输出1。

解题思路：使用贪心算法，先将两个数组g和s都从小到大排序，每次选取能够满足第i个孩子的尺寸最小的饼干，就可以得到能满足孩子的最大数量，从下标为0开始，每找到一个饼干可以满足小孩，就将g和s的下标往前移动一位，直到遍历整个数组。

class Solution {    public int findContentChildren(int[] g, int[] s) {        Arrays.sort(g);        Arrays.sort(s);        int gi = 0, si = 0, res = 0;        while(gi<g.length && si<s.length){            if(s[si]>=g[gi]){                gi++;                si++;                res++;            }            else{                si++;            }        }        return res;    }}

3.判断子序列（392）

给定字符串 s 和 t ，判断 s 是否为 t 的子序列。

字符串的一个子序列是原始字符串删除一些（也可以不删除）字符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。

示例 1：

输入：s = "abc", t = "ahbgdc"

输出：true

解题思路：使用贪心算法，对于每一个在s和t中都出现的元素，都选择第一个在t中出现的元素，因为第一个元素出现的位置可以包含后面第N次出现的位置之后的元素，而反过来确不行。使用两个指针从前往后分别遍历两个字符串，如果发现s中的元素与t中相等，则两个指针都往前移动一位，否则只有t的指针右移一位，遍历结束后，判断s中的指针是否遍历结束即可得到答案。

class Solution {    public boolean isSubsequence(String s, String t) {        int n = s.length();        int m = t.length();        int i=0, j=0;        while(i<n && j<m){            if(s.charAt(i)==t.charAt(j)){                i++;            }            j++;        }        return i == n;    }}

4.无重叠区间（435）

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回 需要移除区间的最小数量，使剩余区间互不重叠 。

示例 1:

输入: intervals = [[1,2],[2,3],[3,4],[1,3]]

输出: 1 解释: 移除 [1,3]后，剩下的区间没有重叠。

解题思路：先将数组通过右端点从小到大排序，得到区间结束值的最小顺序，排完序之后的首个区间即为选择的首个区间。遍历所有区间，使用贪心策略，如果当前区间的起始点大于等于首个区间的结束点，则增加一个不重叠区间，使用当前的区间替换首个区间，直到遍历结束得到最大的不重叠区间数。使用数组长度减去最大的不重叠区间数就可以得到需要移除区间的最小数量。

class Solution {    public int eraseOverlapIntervals(int[][] intervals) {        if(intervals.length == 0 ){            return 0;        }        Arrays.sort(intervals, new Comparator<int[]>(){            public int compare(int[] i1, int[] i2){                return i1[1] - i2[1];            }        });        int right = intervals[0][1];        int res = 1;        for(int i=1; i<intervals.length; i++){            if(intervals[i][0] >= right){                res++;                right = intervals[i][1];            }        }        return intervals.length-res;    }}