第18天--算法（Leetcode 33,34,36）
33.搜索旋转排序数组
public int search(int[] nums, int target) { if(nums == null || nums.length == 0) { return -1; } int left = 0; int mid = 0; int right = nums.length - 1; while(left <= right) { mid = (left + right) >> 1; if(nums[mid] == target) { return mid; } if(nums[left] == nums[mid] && nums[mid] == nums[right]) { while(left < mid && nums[left] == nums[mid]) { left ++; } if(left == mid) { left = mid + 1; continue; } }else { if(nums[left] < nums[mid]) { if(target >= nums[left] && target <= nums[mid]) { right = mid - 1; continue; }else { left = mid + 1; continue; } }else if(nums[left] > nums[mid]){ if(target >= nums[mid] && target <= nums[right]) { left = mid + 1; continue; }else { right = mid - 1; continue; } }else { left = mid + 1; } } } return -1; } 34. 在排序数组中查找元素的第一个和最后一个位置 public int[] searchRange(int[] nums, int target) { int res[] = {-1,-1}; if(nums == null || nums.length == 0) { return res; } res[0] = f(nums,target); res[1] = g(nums,target); return res; } public int f(int nums[],int target) { int left = 0; int right = nums.length - 1; int mid = 0; int ans = -1; while(left <= right) { mid = (left + right) >> 1; if(nums[mid] > target) { right = mid - 1; }else if(nums[mid] < target) { left = mid + 1; }else { ans = mid; right = mid - 1; } } return ans; } public int g(int nums[],int target) { int left = 0; int right = nums.length - 1; int mid = 0; int ans = -1; while(left <= right) { mid = (left + right) >> 1; if(nums[mid] > target) { right = mid - 1; }else if(nums[mid] < target) { left = mid + 1; }else { ans = mid; left = mid + 1; } } return ans; } 36.有效的数独 public boolean isValidSudoku(char[][] board) { boolean row[][] = new boolean[9][10]; boolean col[][] = new boolean[9][10]; boolean ge[][] = new boolean[9][10]; for(int i = 0;i < 9;i ++) { for(int j = 0;j < 9;j ++) { if(board[i][j] != '.') { int num = board[i][j] - '0'; int k = 3 * (i / 3) + j / 3; if(row[i][num] || col[j][num] || ge[k][num]) { return false; } row[i][num] = true; col[j][num] = true; ge[k][num] = true; } } } return true; }