leetCode进阶算法题+解析（四十七）
唔，又是阔别很久的刷题。其实最近也没多忙，但是时间就是不知不觉就没了。今日目标：三道题打底。上不嫌多。
太平洋大西洋水流问题
题目：给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。
提示：输出坐标的顺序不重要.m和 n 都小于150
示例：
给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 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]] (上图中带括号的单元).
思路：先从题目开始说，我反正是静下心来读了两三遍题目才看懂这个意思。首先根据题目，可以确定这个矩阵的左下角和右上角肯定是两个洋都可以流到的。其次剩下的我觉得就是一个判断的问题。我暂时的想法是两次标记。然后类似于一层一层判断的方式，如果一个数字被标记两次说明两个洋都可以流到。我说的可能比较模糊，因为思路也还没理清。只是一个简单的想法，我去代码实现试一下。
我刚刚又仔细看了下题目。本来打算用floyd算法一个个算，但是觉得这个题可能没那么麻烦了，其实每一行每一列看错一条河流，是不是说一条河流的最高点可以往两边流水？不管是行还是列的两边都是两个洋。所以暂时觉得除了左下和右上，判断一个数的上下左右，是不是递减（相等的值也算）。如果能通向两边则这个值是true。我去代码实现下。
怎么说呢，想的很简单，做出来一直修修改改的。我在编译器上调试了n次。最后写出的代码也不尽人意。
我先直接贴出来：
class Solution {
int[][] flag = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> res = new ArrayList<>();
if (matrix == null || matrix.length == 0)
return res;
int m = matrix.length, n = matrix[0].length;
boolean[][] first = new boolean[m][n];
boolean[][] second = new boolean[m][n];
for (int i = 0; i < m; i++) {
dfs(matrix, i, 0, first);
dfs(matrix, i, n - 1, second);
}
for (int i = 0; i < n; i++) {
dfs(matrix, 0, i, first);
dfs(matrix, m - 1, i, second);
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (first[i][j] && second[i][j])
res.add(Arrays.asList(i, j));
}
}
return res;
}
public void dfs(int[][] matrix, int i, int j, boolean[][] reach) {
if (reach[i][j])
return ;
reach[i][j] = true;
for (int m = 0; m < 4; m++) {
int newX = i + flag[m][0], newY = j + flag[m][1];
if (newX < 0 || newX >= matrix.length || newY < 0 || newY >= matrix[0].length
|| matrix[i][j] > matrix[newX][newY] || reach[newX][newY])
continue;
dfs(matrix, newX, newY, reach);
}
}
}
首先说一下，这个往四个边dfs的优雅的for循环的处理办法是参考别人的答案的，我自己最开始是用四个if来判断的。代码恶心的一批，真的是写了一百多行。所以一看人家的处理办法我果断是爱了，这里直接复用了。
但是除了代码的处理细节，别的逻辑啥的还好。起码我个人来说方式方法是都想到了的。
之前我打算用数字来表示，粗略贴个我最开始想法的截图：
粗略想法截图
四个for循环，上下左右分别判断的截图
后来发现在处理的过程中，有些拐弯的地方处理的不好，所以又换成了dfs。但是四个if又真的写的恶心，并且1，2，3的调试起来自己也麻烦，所以又把两个拆开成两个boolean数组，整体来说就是上面贴的代码那样了。
重点就是从边上往里扩散。然後上下左右有能通的，则只需要判断这个能通的会通向哪里。这个逻辑是很简单，但是实现起来能明白dfs就能理解代码。
然後我之前零散的思路有的有一些用处，有的没用的我也不删除了，毕竟是我的思想过程。
刚刚看了性能排行第一的代码，只能说大体逻辑都差不多，具体的处理决定性能，我简单的附上代码，只要认真看一遍肯定能看懂：
class Solution {
//太平洋大西洋水流问题
public List<List<Integer>> pacificAtlantic(int[][] matrix) {
List<List<Integer>> listList=new ArrayList<List<Integer>>();
int m=matrix.length;
if(m==0) return listList;
int n=matrix[0].length;
if(n==0) return listList;
boolean [][] visitPacific=new boolean[m][n];
boolean [][] visitAtlantic=new boolean[m][n];
for(int j=0;j<n;j++){
dfs_Pacific(matrix,visitPacific,0,j,m,n);
}
for(int i=1;i<m;i++){
dfs_Pacific(matrix,visitPacific,i,0,m,n);
}
for(int j=0;j<n;j++){
dfs_Atlantic(matrix,visitPacific,visitAtlantic,listList,m-1,j,m,n);
}
for(int i=m-2;i>=0;i--){
dfs_Atlantic(matrix,visitPacific,visitAtlantic,listList,i,n-1,m,n);
}
return listList;
}
private void dfs_Pacific(int[][]matrix,boolean[][] visitPacific,int i,int j,int m,int n){
if(visitPacific[i][j]) return;
visitPacific[i][j]=true;
//上
if(i>0&&!visitPacific[i-1][j]&&matrix[i-1][j]>=matrix[i][j]){
dfs_Pacific(matrix,visitPacific,i-1,j,m,n);
}
//下
if(i<m-1&&!visitPacific[i+1][j]&&matrix[i+1][j]>=matrix[i][j]){
dfs_Pacific(matrix,visitPacific,i+1,j,m,n);
}
//左
if(j>0&&!visitPacific[i][j-1]&&matrix[i][j-1]>=matrix[i][j]){
dfs_Pacific(matrix,visitPacific,i,j-1,m,n);
}
//右
if(j<n-1&&!visitPacific[i][j+1]&&matrix[i][j+1]>=matrix[i][j]){
dfs_Pacific(matrix,visitPacific,i,j+1,m,n);
}
}
private void dfs_Atlantic(int[][]matrix,boolean [][]visitPacific,boolean [][]visitAtlantic,List<List<Integer>> listList,int i,int j,int m,int n){
if(visitAtlantic[i][j]) return;
visitAtlantic[i][j]=true;
if(visitPacific[i][j]){
listList.add(Arrays.asList(i,j));
}
//上
if(i>0&&!visitAtlantic[i-1][j]&&matrix[i-1][j]>=matrix[i][j]){
dfs_Atlantic(matrix,visitPacific,visitAtlantic,listList,i-1,j,m,n);
}
//下
if(i<m-1&&!visitAtlantic[i+1][j]&&matrix[i+1][j]>=matrix[i][j]){
dfs_Atlantic(matrix,visitPacific,visitAtlantic,listList,i+1,j,m,n);
}
//左
if(j>0&&!visitAtlantic[i][j-1]&&matrix[i][j-1]>=matrix[i][j]){
dfs_Atlantic(matrix,visitPacific,visitAtlantic,listList,i,j-1,m,n);
}
//右
if(j<n-1&&!visitAtlantic[i][j+1]&&matrix[i][j+1]>=matrix[i][j]){
dfs_Atlantic(matrix,visitPacific,visitAtlantic,listList,i,j+1,m,n);
}
}
}
这个题挺好的，不难，但是很复杂，下一题吧。
甲板上的战舰
题目：给定一个二维的甲板， 请计算其中有多少艘战舰。 战舰用 'X'表示，空位用 '.'表示。 你需要遵守以下规则：给你一个有效的甲板，仅由战舰或者空位组成。战舰只能水平或者垂直放置。换句话说,战舰只能由 1xN (1 行, N 列)组成，或者 Nx1 (N 行, 1 列)组成，其中N可以是任意大小。两艘战舰之间至少有一个水平或垂直的空位分隔 - 即没有相邻的战舰。
示例 :
X..X
...X
...X
在上面的甲板中有2艘战舰。
无效样例 :
...X
XXXX
...X
你不会收到这样的无效甲板 - 因为战舰之间至少会有一个空位将它们分开。
进阶:
你可以用一次扫描算法，只使用O(1)额外空间，并且不修改甲板的值来解决这个问题吗？
思路：这个题乍一看简单的出奇，仔细一看进阶条件emmmm....我是觉得难点都在进阶条件上呢。我暂时的想法就是一行一行扫描，如果下面不是0并且不是x则算是一个。否则不算。我去代码试试。
算了，反正做是做出来了，而且性能也很好，就是这个一次扫描算法我觉得也是没问题的，直接贴代码：
class Solution {
public int countBattleships(char[][] board) {
if(board.length==0 || board[0].length==0) return 0;
int res = 0;
int r = board.length-1;
int l = board[0].length-1;
for(int i = 0;i<r;i++){
for(int j = 0;j<l;j++){
//当前x后面也是x则顺着往下继续便利
if(board[i][j] == 'X' && board[i][j+1] == 'X'){
continue;
//因为肯定有效，所以这两个if/else if只会有一个成立，或者都不成立
}else if (board[i][j] == 'X' && board[i+1][j] == 'X'){
continue;
}else if (board[i][j] == 'X'){//下面和后面都不是x，这个计算在内
res++;
}
}
}
for(int i = 0;i<r;i++){
if(board[i][l] == 'X' && board[i+1][l] != 'X') res++;
}
for(int i = 0;i<l;i++){
if(board[r][i] == 'X' && board[r][i+1] != 'X') res++;
}
return board[r][l]=='X'?res+1:res;
}
}
因为这个题比较简单，所以不多说什么了，这个性能也超过百分之九十九的人了，所以也不贴性能排行第一的代码了，下一题。
数组中两个数的最大异或值
题目：给定一个非空数组，数组中元素为 a0, a1, a2, … , an-1，其中 0 ≤ ai < 231 。找到 ai 和aj 最大的异或 (XOR) 运算结果，其中0 ≤ i, j < n 。你能在O(n)的时间解决这个问题吗？
示例:
输入: [3, 10, 5, 25, 2, 8]
输出: 28
解释: 最大的结果是 5 ^ 25 = 28.
思路：怎么说呢，这个题一看就不复杂，但是涉及的二进制运算就让我头皮一紧。先说说异或，两个数的二进制，相同是0，不同是1。又因为异或两个数都是0的时候肯定是0，所以想要最大结果，其中肯定要有一个是二进制表示最长的一个（之所以没说最大值可能在位数相同的时候较小值能异或出较大的结果。）。另一个就是查缺补漏了，但是最起码的两个异或的数字长度肯定不一样。这个是第一反应的判断，具体的我再好好想想。其实没有时间复杂度的话，一个双层遍历就能解决问题.但是这个时间复杂度要求是O(n)，也就是一次遍历就要有结果。我想想有没有什么好的算法。
这个题的思路来源于贪心，代码来源于题解。对，有了思路不想自己写的结果。首先刚刚上面也说了肯定要找最高位是1的，因为10000肯定大于1111.这个应该很好理解。同样继续往下，也是能要1就不要0.高位的一个1比低位无数个1都要数值大。这个思路是没错的。然後重点是实现方式，一种是每个数用map的形式，还有一种是前缀树的方式。两种方法怎么说呢，都不难，但是建树我觉得挺麻烦的，所以这里用的map的形式。
我直接贴代码：
class Solution {
public int findMaximumXOR(int[] nums) {
int maxNum = nums[0];
for(int num : nums) maxNum = Math.max(maxNum, num);
int L = (Integer.toBinaryString(maxNum)).length();
int maxXor = 0, currXor;
Set<Integer> prefixes = new HashSet<>();
for(int i = L - 1; i > -1; --i) {
maxXor <<= 1;
currXor = maxXor | 1;
prefixes.clear();
for(int num: nums) prefixes.add(num >> i);
for(int p: prefixes) {
if (prefixes.contains(currXor^p)) {
maxXor = currXor;
break;
}
}
}
return maxXor;
}
}
下面附上一种前缀树的解题方式：
class Solution {
public static class TrieNode{
TrieNode[] path = new TrieNode[2];
}
public static class Trie{
private TrieNode root;
Trie(){
root = new TrieNode();
}
public void insert(int value){
TrieNode cur = root;
for(int i=31;i>=0;i--){
int v = value>>i&1;
if(cur.path[v]==null){
cur.path[v] = new TrieNode();
}
cur = cur.path[v];
}
}
public int getMaxXorNum(int value){
TrieNode cur = root;
int result = 0;
for(int i=31;i>=0;i--){
int v = (value>>i)&1;
int path = v;
if(i==31){
if(cur.path[v]==null){
path = 1^v;//~v
}
}else{
if(cur.path[1^v]!=null){
path = 1^v;//~v
}
}
cur = cur.path[path];
result = result | ((path^v)<<i);
}
return result;
}
}
public int findMaximumXOR(int[] nums) {
if(nums.length==0){
return 0;
}
Trie tree = new Trie();
int result = Integer.MIN_VALUE;
for(int i=0;i<nums.length;i++){
tree.insert(nums[i]);
}
for(int i=0;i<nums.length;i++){
result= Math.max(result, tree.getMaxXorNum(nums[i]));
}
return result;
}
}
这个题就这样吧，直接下一题了。
从英文中重建数字
题目：给定一个非空字符串，其中包含字母顺序打乱的英文单词表示的数字0-9。按升序输出原始的数字。
注意:
输入只包含小写英文字母。
输入保证合法并可以转换为原始的数字，这意味着像 "abc" 或 "zerone" 的输入是不允许的。
输入字符串的长度小于 50,000。
示例 1:
输入: "owoztneoer"
输出: "012" (zeroonetwo)
示例 2:
输入: "fviefuro"
输出: "45" (fourfive)
思路：这个题倒也不难，我暂时的想法就是把这个字符串变成一个26位下表代表字母。数值代表字母数的个数。有的数字是有唯一的单词的，比如z只有0才有。也就是一共几个z就会有几个0.w是2特有的，g是8特有的。把这些特殊的抛出去，再在剩下的中找规律。然後剩下怎么拼凑再说。有模糊的想法，我去实践下试试。
代码出来了，很麻烦，又是思路是自己的，但是代码是题解的（有一半是我自己写的，思路挺明确的，但是写着写着懒得写了）：
public String originalDigits(String s) {
char[] str = new char[26];
char[] check = s.toCharArray();
for(int i = 0;i < check.length;i++){
str[check[i] - 'a']++;
}
int zero = 0,one = 0,two = 0,three = 0,four = 0,five = 0,six = 0,seven = 0,eight = 0,nine = 0;
zero = str[25];
str[4] -= str[25];
str[17] -= str[25];
str[14] -= str[25];
two = str[22];
str[19] -= str[22];
str[14] -= str[22];
four = str[20];
str[5] -= str[20];
str[14] -= str[20];
str[17] -= str[20];
six = str[23];
str[18] -= str[23];
str[8] -= str[23];
eight = str[6];
str[4] -= str[6];
str[8] -= str[6];
str[7] -= str[6];
str[19] -= str[6];
three = str[17];
str[19] -= str[17];
str[7] -= str[17];
str[4] -= str[17];
str[4] -= str[17];
five = str[5];
str[8] -= str[5];
str[21] -= str[5];
str[4] -= str[5];
seven = str[21];
str[17] -= str[21];
str[4] -= str[21];
str[4] -= str[21];
str[13] -= str[21];
one = str[14];
str[13] -= str[14];
str[4] -= str[14];
nine = str[4];
// 上述为数字判断的处理过程
// 下述为字符串连接过程
int[] num = new int[]{zero,one,two,three,four,five,six,seven,eight,nine};
String ans = "";
for(int i = 0;i < num.length;i++){
for(int j = 0;j < num[i];j++){
ans += String.valueOf(i);
}
}
return ans;
}
这个怎么说呢，我觉得逻辑挺好理解的，但是代码是真的墨迹。我才把0，2手动判断完了，就直接看题解了。下面是性能排行第一的，更优雅的一种写法：
class Solution {
public String originalDigits(String s) {
int[] wordCnt = new int[26];
for (char c : s.toCharArray()) {
wordCnt[c - 'a']++;
}
int[] numCnt = new int[10];
numCnt[0] = wordCnt['z' - 'a'];
numCnt[2] = wordCnt['w' - 'a'];
numCnt[4] = wordCnt['u' - 'a'];
numCnt[6] = wordCnt['x' - 'a'];
numCnt[8] = wordCnt['g' - 'a'];
numCnt[1] = wordCnt['o' - 'a'] - numCnt[0] - numCnt[2] - numCnt[4];
numCnt[3] = wordCnt['h' - 'a'] - numCnt[8];
numCnt[5] = wordCnt['f' - 'a'] - numCnt[4];
numCnt[7] = wordCnt['s' - 'a'] - numCnt[6];
numCnt[9] = wordCnt['i' - 'a'] - numCnt[5] - numCnt[6] - numCnt[8];
int len = 0;
for (int c : numCnt) {
len += c;
}
char[] res = new char[len];
len = 0;
for (int i = 0; i <= 9; i++) {
for (int j = 0; j < numCnt[i]; j++) {
res[len++] = (char)('0' + i);
}
}
return new String(res);
}
}
思路还是那个思路，只不过代码性能好多了。因为我觉得这个题的逻辑很好理解，所以也不多说了，就这样吧。
这篇笔记就写到这里，如果稍微帮到你记得点个喜欢点个关注。也祝大家工作顺顺利利，生活健健康康！java技术交流群130031711，欢迎各位萌新大佬踊跃加入！
