79. 單詞搜索

題目描述

給定一個(gè)二維網(wǎng)格和一個(gè)單詞镰惦，找出該單詞是否存在于網(wǎng)格中栗精。
單詞必須按照字母順序十厢，通過(guò)相鄰的單元格內(nèi)的字母構(gòu)成，其中“相鄰”單元格是那些水平相鄰或垂直相鄰的單元格枝缔。同一個(gè)單元格內(nèi)的字母不允許被重復(fù)使用。

解題思路

深度優(yōu)先遍歷 + 回溯。

代碼實(shí)現(xiàn)

class Solution {
    char[] target;

    public boolean exist(char[][] board, String word) {
        if(word.length() == 0){
            return false;
        }
        target = word.toCharArray();

        //遍歷矩陣行列
        int rows = board.length, cols = board[0].length;
        for(int i = 0; i < rows; i++){
            for(int j = 0; j < cols; j++){
                if(check(board, i, j, 0)){
                    return true;
                } 
            }
        }
        return false;
    }

    //判斷從board[i][j]出發(fā)是否存在路徑word.subString(index, length - 1)
    public boolean check(char[][] board, int i, int j, int index){
        if(index >= target.length){
            //已找完全部
            return true;
        }

        if(outOfBound(board, i, j) || board[i][j] != target[index]){
            return false;
        }
        
        //防止重復(fù)查找
        board[i][j] = '0';

        if(check(board, i + 1, j, index + 1) || check(board, i - 1, j, index + 1)
        || check(board, i, j + 1, index + 1) || check(board, i, j - 1, index + 1)){
            return true;
        }

       //還原數(shù)組元素（撤銷選擇）
        board[i][j] = target[index];

        return false;
    }

    //判斷數(shù)組下標(biāo)是否越界
    public boolean outOfBound(char[][] board, int i, int j){
        if(i < 0 || i >= board.length || j < 0 || j >=board[0].length){
            return true;
        }
        return false;
    }

}

153. 尋找旋轉(zhuǎn)排序數(shù)組中的最小值

問(wèn)題描述

假設(shè)按照升序排序的數(shù)組在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)骤素。例如，數(shù)組 [0,1,2,4,5,6,7] 可能變?yōu)?[4,5,6,7,0,1,2] 愚屁。
請(qǐng)找出其中最小的元素济竹。

• 1 <= nums.length <= 5000
• -5000 <= nums[i] <= 5000
• nums 中的所有整數(shù)都是 唯一 的
• nums 原來(lái)是一個(gè)升序排序的數(shù)組，但在預(yù)先未知的某個(gè)點(diǎn)上進(jìn)行了旋轉(zhuǎn)

解題思路1-暴力法

從頭到尾遍歷數(shù)組霎槐，找到最小值送浊。

代碼實(shí)現(xiàn)1-暴力法

class Solution {
    public int findMin(int[] nums) {
        int min = nums[0];
        for(int i = 1; i < nums.length; i++){
            if(nums[i] < min){
                min = nums[i];
            }
        }
        return min;
    }
}

• 時(shí)間復(fù)雜度O(n)，n為數(shù)組中的元素

解題思路2-二分查找

使用左閉右開(kāi)區(qū)間丘跌，保證最小值始終在這里面袭景。

代碼實(shí)現(xiàn)2-二分查找

class Solution {
    public int findMin(int[] nums) {
        int left = 0, right = nums.length - 1;
        if(nums[left] < nums[right]){
            //數(shù)組未被旋轉(zhuǎn)，直接返回最小值
            return nums[left];
        }

        while(left < right){
            int mid = left + (right - left) / 2;
            if(nums[right] < nums[mid]){
                left = mid + 1;
            }else{
                right = mid;
            } 
        }

        return nums[left];
    }
}