一、NC128 接雨水问题
描述
给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)
数据范围：数组长度 0≤n≤2×10……5
，数组中每个值满足 0 < val \le 10^90
，保证返回结果满足 0≤val≤10 9
要求：时间复杂度 O(n)O(n)
示例1
输入：[3,1,2,5,2,4]
返回值：5
说明：数组 [3,1,2,5,2,4] 表示柱子高度图，在这种情况下，可以接 5个单位的雨水，蓝色的为雨水 ，如题面图。
示例2
输入：[4,5,1,3,2]
返回值：2
题解示例：
思路：
这题让求柱子中间能盛多少水，首先可以肯定两边的两个柱子是不能盛水的，只有两边之间的柱子有可能会盛水。最简单的一种方式就是使用3个指针，先找到最高的柱子，用一个指针top指向最高柱子，然后最高柱子左边用两个指针，一个left，一个right（这里的left和right指向柱子的高度）。
如果left大于right，那么肯定是能盛水的，因为left是小于等于最高柱子top的，并且right指向的柱子是在left和最高柱子top之间，根据木桶原理盛水量由最矮的柱子决定，所以盛水是left-right。
如果left不大于right，是不能盛水的，这时候我们要让left等于right。因为right是不能超过最高柱子的，我们增加left的高度，有利于后面计算的时候盛更多的水。
import java.util.*; public class Solution { /** * max water * @param arr int整型一维数组 the array * @return long长整型 */ public long maxWater(int[] arr) { if (arr.length <= 2) return 0; //找到最高的柱子的下标 int max = Integer.MIN_VALUE; int maxIndex = -1; for (int i = 0; i < arr.length; i++) { if (arr[i] > max) { max = arr[i]; maxIndex = i; } } //统计最高柱子左边能接的雨水数量 int left = arr[0]; int right = 0; long water = 0; for (int i = 1; i < maxIndex; i++) { right = arr[i]; if (right > left) { left = right; } else { water += left - right; } } //统计最高柱子右边能接的雨水数量 right = arr[arr.length - 1]; for (int i = arr.length - 2; i > maxIndex; i--) { left = arr[i]; if (arr[i] > right) { right = left; } else { water += right - left; } } //返回盛水量 return water; } }
二、NC44 通配符匹配
描述
请实现支持’?‘and’*'.的通配符模式匹配
‘?’ 可以匹配任何单个字符。
‘*’ 可以匹配任何字符序列（包括空序列）。
返回两个字符串是否匹配
函数声明为：
bool isMatch(const char *s, const char *p)
只有p字符串包含通配符
下面给出一些样例：
isMatch(“aa”,“a”) → false
isMatch(“aa”,“aa”) → true
isMatch(“aaa”,“aa”) → false
isMatch(“aa”, “") → true
isMatch(“aa”, "a”) → true
isMatch(“ab”, “?") → true
isMatch(“aab”, "da*b”) → false
数据范围：字符串长度满足10000≤n≤1000
进阶：空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)
示例1
输入：“ab”,“?*”
返回值：true
示例2
输入：“ab”,“*”
返回值：true
题解示例：
贪心算法：
如果i和j标记的字符正好相等或者j字符是’?'匹配成功，则"移除"i和j元素，即自增i、j。
否则如果j字符是✳(*号)依然可以匹配成功，则用istart和jstart分别标记i元素和j元素之后自增j。
否则如果istart>-1说明之前匹配过✳，因为✳可以匹配多个字符，所以这里要再次利用这个最近匹配过的✳匹配更多的字符，移动i标记istart的下一个字符，再让istart重新标记i元素同时移动j标记jstart的下一个字符。
上述三种情况都不满足，则匹配失败，返回false。
最后当s中的字符都判断完毕，则认为s为空，此时需要p为空或者p中只剩下星号的时候，才能成功匹配。
public class Solution { public boolean isMatch(String s, String p) { if (p==null||p.isEmpty())return s==null||s.isEmpty(); int i=0,j=0,istart=-1,jstart=-1,slen=s.length(),plen=p.length(); //判断s的所有字符是否匹配 while (i<slen){ //三种匹配成功情况以及匹配失败返回false if (j<plen&&(s.charAt(i)==p.charAt(j)||p.charAt(j)=='?')){ i++; j++; }else if (j<plen&&p.charAt(j)=='*'){ istart=i; jstart=j++; }else if (istart>-1){ i=++istart; j=jstart+1; }else { return false; } } //s中的字符都判断完毕，则认为s为空，此时需要p为空或者p中只剩下星号的时候，才能成功匹配。 while (j<plen&&p.charAt(j)=='*')j++; return j==plen; } }
