剑指offer第二天

1. 滑动窗口的最大值

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int size)
    {
        if(size == 0)
            return new ArrayList<Integer>();
          // 用队列存放窗口
           PriorityQueue <Integer>pq = new PriorityQueue<Integer>(new Comparator<Integer>(){
               @Override
               public int compare(Integer o1,Integer o2){
                   return o2-o1;
               }
           }) ;
        ArrayList<Integer> result = new ArrayList<Integer>();
        for(int i=0; i<num.length-size+1; i++){
            for(int j=0; j<size; j++){
                pq.add(num[i+j]);
            }
            //取出窗口最大值
            result.add(pq.poll());
            pq.clear();//清空窗口
        }
        return result;
        
    }
}

2. 矩阵中的路径，只过了60%，迷茫

public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(str == null || str.length == 0)
            return false;
        char myMatrix[][] = new char[rows][cols];
        boolean tag[][] = new boolean[rows][cols];
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                myMatrix[i][j] = matrix[i*cols+j];
            }
        for(int i=0; i<myMatrix.length; i++){
            for(int j=0; j<myMatrix[0].length;j++){
                if(myMatrix[i][j] == str[0]){                    
                    if(dfs(myMatrix,i,j,str,0,tag))
                        return true;
                }
            }
            
        }
        return false;
    }
        private boolean dfs(char matrix[][],int i,int j,char []str,int index,boolean [][]tag){
            if(tag[i][j] == true)
                return false;
              if(index == str.length)
                    return true;
           
            if( matrix[i][j] == str[index]){
                 tag[i][j] = true;
                if(i>0 && !tag[i-1][j] &&dfs(matrix,i-1,j,str,index+1,tag)){
                    return true;
                }
                if(j>0 && !tag[i][j-1] &&dfs(matrix,i,j-1,str,index+1,tag))
                    return true;
                if(i<matrix.length-1 && !tag[i+1][j] &&dfs(matrix,i+1,j,str,index+1,tag))
                    return true;
                if(j<matrix[0].length-1 && !tag[i][j+1] &&dfs(matrix,i,j+1,str,index+1,tag))
                    return true;
                tag[i][j] = false;
                return false;
           } else{
               tag[i][j] = false;
               return false;
            }
           
      }
            
}

后面借鉴了别人的代码
link

import java.util.*;
class Solution {
       public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        int[] flag = new int[matrix.length];
        for(int i = 0; i < rows; i ++){
            for(int j = 0; j < cols; j ++){
                if(helper(matrix, rows, cols, i, j, str, 0, flag)){
                    return true;
                }
            }
        }
        return false;
    }
    public static boolean helper(char[] matrix, int rows, int cols, int i, int j, char[] str, int k, int[] flag){
        int index = i * cols + j;
        if(i < 0 || i >= rows || j < 0 || j >= cols || matrix[index] != str[k] || flag[index] == 1){
           //下标不符合，index对应的值不为和字符数组中的不一致，或者该index已经被访问，这些情况只要有符合的就返回false
            //只有上面的所有情况都不符合，也就是值相等，且没有访问过，下标不符合
            return false;
        }
        if(k == str.length - 1){
            return true;
        }
        flag[index] = 1;
        if(helper(matrix, rows, cols, i - 1, j, str, k + 1, flag)
          ||helper(matrix, rows, cols, i + 1, j, str, k + 1, flag)
          ||helper(matrix, rows, cols, i, j - 1, str, k + 1, flag)
          ||helper(matrix, rows, cols, i , j + 1, str, k + 1, flag)){
            return true;
        }
        flag[index] = 0;
        return false;
    }


}

然后改了下，就通过了，可能之前的代码存在什么逻辑漏洞，但是我没看出来

import java.util.*;
public class Solution {
    public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
    {
        if(str == null || str.length == 0)
            return false;
        char myMatrix[][] = new char[rows][cols];
        boolean tag[][] = new boolean[rows][cols];
        for(int i=0; i<rows; i++)
            for(int j=0; j<cols; j++){
                myMatrix[i][j] = matrix[i*cols+j];
            }
        for(int i=0; i<myMatrix.length; i++){
            for(int j=0; j<myMatrix[0].length;j++){
                if(myMatrix[i][j] == str[0]){                    
                    if(dfs(myMatrix,i,j,str,0,tag))
                        return true;
                }
            }
            
        }
        return false;
    }
        private boolean dfs(char matrix[][],int i,int j,char []str,int index,boolean [][]tag){

            if(tag[i][j] ||i<0||j<0||i>=matrix.length||i>=matrix[0].length||matrix[i][j] != str[index])
                return false;
             if(index == str.length-1)
                 return true;
                 tag[i][j] = true;
                if(i>0&&dfs(matrix,i-1,j,str,index+1,tag)){
                    return true;
                }
                if(j>0 &&dfs(matrix,i,j-1,str,index+1,tag))
                    return true;
                if(i<matrix.length-1  &&dfs(matrix,i+1,j,str,index+1,tag))
                    return true;
                if(j<matrix[0].length-1 &&dfs(matrix,i,j+1,str,index+1,tag))
                    return true;
                tag[i][j] = false;
               return false;
            }
           
}

3. 机器人的运动范围
   这题看了好久，因为有个bug一直没发现，就是通过两个while循环，i,j已经都变为0了，需要用变量暂存，就是因为这个导致一直不通过，还是找朋友看才找到bug

 public int movingCount(int threshold, int rows, int cols)
        {
            boolean[][] flag = new boolean[rows][cols];
            int result = 0;
             result = dfs(0,0,threshold,flag);
       
            return result;
            
        }
        private int dfs(int i, int j, int threshold, boolean[][]flag){
            //System.out.print(i+" ");
            //System.out.print(j+" ");
            
            if(i<0 || i>=flag.length || j<0 || j>=flag[0].length  )
                return 0;
           
            
            if(flag[i][j])
                return 0;
            flag[i][j] = true;
            int count = 0;
            int tmpI=i,tmpJ=j;
            while(i!=0){
                count = count + i%10;
                i = i/10;
            }
            while(j!=0){
                count = count + j%10;
                j = j/10;
            }
           //System.out.println(count);
            if(count <= threshold){
                  return 1+dfs(tmpI-1,tmpJ,threshold,flag)+dfs(tmpI,tmpJ-1,threshold,flag)
                    +dfs(tmpI,tmpJ+1,threshold,flag)+dfs(tmpI+1,tmpJ,threshold,flag);     
            }
            else
              return 0;
        }