Searching专题 2016-08-03

[wolfogre]

79 Word Search

74 Search a 2D Matrix

[wolfogre]

// [AC] 79 Word Search
public class Solution {
    public boolean exist(char[][] board, String word) {
        if(board.length <= 0)
            return false;
        isUsed = new boolean[board.length][board[0].length];
        for(int i = 0; i < board.length; ++i)
            for(int j = 0; j < board[0].length; ++j)
                isUsed[i][j] = false;
        this.board = board;
        this.word = word;
        for(int i = 0; i < board.length; ++i)
            for(int j = 0; j < board[0].length; ++j)
                if(existHelp(0, i, j))
                    return true;
        return false;
    }

    private boolean[][] isUsed;
    private char[][] board;
    private String word;

    private boolean existHelp(int index, int row, int col){
        if(index >= word.length())
            return true;
        if(row < 0 || row >= board.length || col < 0 || col >= board[0].length || isUsed[row][col] || word.charAt(index) != board[row][col])
            return false;
        isUsed[row][col] = true;
        if(existHelp(index + 1, row + 1, col))
            return true;
        if(existHelp(index + 1, row - 1, col))
            return true;
        if(existHelp(index + 1, row, col + 1))
            return true;
        if(existHelp(index + 1, row, col - 1))
            return true;
        isUsed[row][col] = false;
        return false;
    }

}

[wolfogre]

// [AC] 74 Search a 2D Matrix
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int start = 0, end = matrix.length - 1;
        while(start <= end){
            int mid = (start + end) / 2;
            if(matrix[mid][0] <= target && (mid + 1 >= matrix.length || matrix[mid + 1][0] > target)){
                int row = mid;
                start = 0;
                end = matrix[0].length - 1;
                while(start <= end){
                    mid = (start + end) / 2;
                    if(matrix[row][mid] == target)
                        return true;
                    if(matrix[row][mid] > target){
                        end = mid - 1;
                    } else {
                        start = mid + 1;
                    }
                }
                return false;
            }
            if(matrix[mid][0] > target){
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        return false;
    }
}

[dayang]

/**
 * [AC] LeetCode 79 Word Search
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
    if (board.length === 0 || word.length === 0) return false;
    let m = board.length, n = board[0].length;
    function isIn(x, y) {
        return x >= 0 && x < m && y >= 0 && y < n;
    }

    let dir = [[0, 1], [0, -1], [1, 0], [-1, 0]];
    let flag;
    let visited;

    function initVisited() {
        visited = [];
        for (let i = 0; i < m; i++) {
            visited.push([]);
            for (let j = 0; j < n; j++) {
                visited[i].push(false);
            }
        }
    }

    function dfs(x, y, index) {
        if (flag) return;
        if (board[x][y] === word[index]) {
            visited[x][y] = true;
            if (index === word.length - 1) {
                flag = true;
                return;
            }
            for (let i = 0; i < 4; i++) {
                let x1 = x + dir[i][0];
                let y1 = y + dir[i][1];
                if (isIn(x1, y1) && !visited[x1][y1]) {
                    dfs(x1,y1,index + 1);
                }
            }
            visited[x][y] = false;
        }
    }

    for (let i = 0; i < m; i++) {
        for (let j = 0; j < n; j++) {
            if (board[i][j] === word[0]) {
                flag = false;
                initVisited();
                dfs(i, j, 0);
                if (flag)
                    return true;
            }
        }
    }

    return false;
};

[SnackMen]

/*
*[AC] LeetCode 79 Word Search
*/
public class Solution {
    public boolean [][]isVisited;
    public boolean exist(char[][] board, String word) {
        if(board.length==0 || board==null)
            return false;
        int rowlength=board.length;
        int cellLength=board[0].length;
        isVisited=new boolean[rowlength][cellLength];
        for(int i=0;i<rowlength;i++){
            for(int j=0;j<cellLength;j++){
                if(dfs(board,word,i,j,0))
                    return true;
            }
        }
        return false;
    }
    public boolean dfs(char[][] board,String word,int i,int j,int id){
        if(id>=word.length())
            return true;
        if(i<0 || j<0 || i>=board.length || j>=board[0].length)
            return false;
        if(isVisited[i][j])
            return false;
        if(board[i][j]!=word.charAt(id))
            return false;
        isVisited[i][j]=true;
        if(dfs(board,word,i+1,j,id+1) || dfs(board,word,i-1,j,id+1) || dfs(board,word,i,j+1,id+1) || dfs(board,word,i,j-1,id+1))
            return true;
        isVisited[i][j]=false;
        return false;
    }
}

[dayang]

/**
 * [AC] LeetCode 74 Search a 2D Matrix
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function (matrix, target) {
    if (matrix.length === 0 || (matrix.length === 1 && matrix[0].length === 0)) return false;

    let m = matrix.length, n = matrix[0].length;

    function binarySearch(arr, num) {
        let low = 0, high = arr.length - 1;
        while (low <= high) {
            let mid = (low + high) >>> 1;
            if (arr[mid] === target) {
                return true;
            }
            else if (arr[mid] < target) {
                low = mid + 1;
            }
            else {
                high = mid - 1;
            }
        }
        return false;
    }

    for (let i = 0; i < m; i++) {
        if (target < matrix[i][0])
            return false;
        if (target >= matrix[i][0] && target <= matrix[i][n - 1]) {
            return binarySearch(matrix[i], target);
        }
    }

    return false;
};

[SnackMen]

/*
*[AC] LeetCode 74 Search a 2D Matrix
*/
public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(matrix==null)
            return false;
        int row=0;
        int cell=matrix[0].length-1;
        while(row<matrix.length && cell>=0){
            if(matrix[row][cell]==target)
                return true;
            if(matrix[row][cell]>target){
                cell--;
            }else{
                row++;
            }

        }
        return false;
    }
}

[zhaokuohaha]

79 - C# - 深搜

public class Solution
{

    StringBuilder sb = new StringBuilder();
    char[,] board;
    int[,] dir = { { 0, -1, 0, 1 }, { -1, 0, 1, 0 } }; 
    public bool Exist(char[,] b, string word)
    {
        this.board = b;
        if (board == null || word == null) return false;
        bool[,] vis = new bool[board.GetLength(0), board.GetLength(1)];
        int wordLen = word.Length;
        for(int i=0; i<board.GetLength(0); i++)
        {
            for(int j=0; j<board.GetLength(1); j++)
            {
                if (board[i, j] == word[0] && dfs(word,i,j,wordLen,vis))
                    return true;
            }
        }
        return false;
    }

    private bool isIn(int i, int j)
    {
        return i >= 0 && j >= 0 && i < board.GetLength(0) && j < board.GetLength(1);
    }

    private bool dfs(string word, int i, int j, int depth, bool[,] vis)
    {
        sb.Append(board[i, j]);
        vis[i, j] = true;
        if (sb.ToString().Equals(word)) return true;
        if (word.Contains(sb.ToString())){
            depth--;
            if(depth > 0)
            {
                for(int x=0; x<4; x++)
                {
                    int mx = i + dir[0,x];
                    int my = j + dir[1,x];
                    if (isIn(mx,my) && !vis[mx,my] && dfs(word, mx, my, depth,vis))
                    {
                        return true;
                    }
                }
            }
        }
        sb.Remove(sb.Length - 1,1);
        vis[i, j] = false;
        depth++;
        return false;
    }
}

[zhaokuohaha]

74 - C# - 两次二分

public class Solution
{
    public bool SearchMatrix(int[,] matrix, int target)
    {
        int width = matrix.GetLength(1);
        int height = matrix.GetLength(0);
        int min = 0, max = height - 1;
        int row=0;
        while (min <= max)
        {
            int mid = (min + max) / 2;
            if (matrix[mid, width - 1] == target)
                return true;
            if(mid == 0)
            {
                row = matrix[0, width - 1] > target ? 0 : 1;
                break;
            }
            if (matrix[mid, width - 1] > target && (matrix[mid-1, width - 1] < target))
            {
                row = mid;
                break;
            }
            if (matrix[mid, width - 1] > target)
                max = mid;
            else min = mid + 1;
        }
        if (row > height - 1) return false;
        min = 0;max = width-1;
        while(min <= max)
        {
            if (min == max) return matrix[row, min] == target;
            int mid = (max + min) / 2;
            if (matrix[row, mid] == target)
                return true;
            if (matrix[row, mid] < target)
                min = mid+1;
            else
                max = mid;
        }
        return false;
    }
}