資工趴趴熊的小天地

問題描述：

給定下列遞迴函式 :

問題描述：

給定二個正整數，利用輾轉相除法求其最大公因數。

C++

/*
Input: nums = [-1,0,3,5,9,12], target = 9
Output: 4
Explanation: 9 exists in nums and its index is 4
*/ 

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left=0;
        int right=nums.size()-1;
        
        while(left<=right){
                int middle=left+((right-left)/2);//防止溢出
                        if(nums[middle]>target){
                                right=middle-1;
                        } 
                        else if(nums[middle]<target){
                                left=middle+1;
                        }
                        else return middle; //找到 
                }
                return -1; //未找到 
    }
};

python:

class Solution {
private:
        bool backtracking(vector<vector<char>>& board) {
                for (int i = 0; i < board.size(); i++){ //跑直得 
                        for (int j = 0; j < board[0].size(); j++){ //跑橫得 
                                if (board[i][j] != '.') continue; //不是要跑的空格，跑下個迴圈 
                                for (char k = '1'; k <= '9'; k++){ 
                                        if(isValid(i, j, k, board)){ // (i, j) 位置放k是否合適，若合適的話 
                                                board[i][j] = k; //就把數字填上去 
                                                if (backtracking(board)) return true; // 如果找到合适立刻返回
                        board[i][j] = '.'; // 回溯，
                                        } 
                                        
                                } 
                                return false; // 9個數字都不行，那么就返回false
                        } 
                }
                return true; // 跑完全不沒有返回false，就是找到答案了 
        }
        /*-----------------------------------------------------------------*/ 
        bool isValid(int row, int col, char val, vector<vector<char>>& board){
                //判斷橫的
                for (int i = 0; i < 9; i++) {
                if (board[row][i] == val) {
                return false;
                }
        } 
        
        //判斷直的
        for (int j = 0; j < 9; j++) { 
                if (board[j][col] == val) {
                    return false;
                }
            }
            
            //判斷小框框內9格是否重複 
            int startRow = (row / 3) * 3;  
            int startCol = (col / 3) * 3;
            for (int i = startRow; i < startRow + 3; i++) { 
                for (int j = startCol; j < startCol + 3; j++) {
                    if (board[i][j] == val ) {
                        return false;
                    }
                }
            }
            return true;
        } 
        
        
public:
    void solveSudoku(vector<vector<char>>& board) {
        backtracking(board);//引入函式 
        
        
    }
};