- 滑动窗口的最大值
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;
}
}
- 矩阵中的路径，只过了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;
}
}
- 机器人的运动范围
这题看了好久，因为有个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;
}
网友评论