This is the 19th day of my participation in the August More Text Challenge

Rotate the smallest number in the array

11. Rotate the smallest number in the array

Moving the beginning elements of an array to the end of the array is called array rotation. Take a rotation of an incrementally sorted array and print the smallest element of the rotation array. For example, array [3,4,5,1,2] is a rotation of [1, 2, 3, 4, 5], whose minimum value is 1.

Example 1:

Input: [3,4,5, 2] Output: 1Copy the code

Example 2:

Input: [2,2,2,0,1] output: 0Copy the code

Answer key

Violence law

We can use a variable to record the minimum value encountered in the current traversal process, and then return the minimum value when the traversal is over.

But this violence is not good enough because the array is rotated, so any number less than numbers[0] must be the minimum in the loop.

 function minArray(numbers){
   for(let i=0; i<numbers.length; i++){if(numbers[i]<numbers[0]) {return numbers[i]
     }
   }
   return numbers[0]}Copy the code

But violence is not the goal, the goal should be to reduce the complexity of the algorithm, so dichotomy is better.

dichotomy

Create two Pointers (left and right) to ‘numbers’, middle (‘ middle’);

  1. Middle > right: indicates that the minimum value must be to the right of middle, so left moves to middle+1.
  2. Middle < right: indicates that the minimum value must be to the left of middle or middle, so right moves to middle.
  3. Middle is neither greater than the left pointer nor less than the value of the right pointer, meaning that middle may be equal to the value of the left pointer or the value of the right pointer.
 / * * *@param {number[]} numbers
  * @return {number}* /
 var minArray = function(numbers){
   let left = 0, right = numbers.length-1;
   while(left < right){
     let middle = left + ~~((right - left) / 2); // Avoid (left+right) overflow
     if(numbers[middle] > numbers[right]){
       left = middle + 1;
     }else if(numbers[middle] < numbers[right]){
       right = middle;
     }else{ right--; }}return numbers[left];
 }
Copy the code

Path in matrix

Refer to the path in the Offer 12 matrix

Given an M x N two-dimensional character grid board and a string word. Return true if Word exists in the grid; Otherwise, return false.

Words must be formed in alphabetical order by letters in adjacent cells, where “adjacent” cells are those that are horizontally or vertically adjacent. Letters in the same cell are not allowed to be reused.

For example, the 3×4 matrix below contains the word “ABCCED” (the letters in the word are highlighted).

Example 1:

Input: board = [[" A ", "B", "C", "E"], [" S ", "F", "C", "S"], [" A ", "D", "E", "E"]], the word = "ABCCED" output: trueCopy the code

Example 2:

Input: board = [[" a ", "b"], [" c ", "d"]], the word = "abcd" output: falseCopy the code

Tip:

  • 1 <= board.length <= 200
  • 1 <= board[i].length <= 200
  • Board and Word consist only of uppercase and lowercase English letters

Answer key

Typical matrix search problems can be solved by depth first search (DFS) + pruning.

  • Depth-first search: Can be interpreted as a brute force method to traverse all string possibilities in a matrix. DFS recursively searches in one direction, goes back to the last node, searches in another direction, and so on.
  • Pruning:In the search, encounteredThis path cannot successfully match the target stringFor example, the matrix element is different from the target character, and the element has been accessedFeasible pruning.

DFS resolution:

  • Recursive parameters: the current element is indexed x and y in the matrix board, and the current target character is indexed K in Word.

  • Termination Conditions:

    1. Returns false:

      • The row or column index is out of bounds
      • The current matrix element is different from the target character
      • The current matrix element has been accessed

    2. Return true:

      • K === word. Length-1, that is, word is all matched.

  • Recursive work:

    1. Mark the current matrix element: Change board[x] [y] to the string ‘-‘ to indicate that this element has been accessed and prevent repeated access during subsequent searches.
    2. Search for the next cell: turn on the lower level recursion up, right, down, and left of the current element, use or join (meaning just find a viable path and go straight back, no further DFS), and record the result to RES.
    3. Restore current matrix element: Restore board [I] [j] element to its initial value
 / * * *@param {character[][]} board
  * @param {string} word
  * @return {boolean}* /
 var exist = function(board, word){
   var xLen = board.length;
   var yLen = board[0].length;
   var k = 0;
   
   var dfs = function(x,y,k){
     if(x < 0 || x >= xLen || y < 0|| y >= yLen || board[x][y] ! == word[k])return false;
     if(k === word.length - 1) // word is done
       return true;
     let temp = board[x][y]; // Record the value of board
     board[x][y] = The '-';      // 
     let res = dfs(x - 1, y, k + 1) || dfs(x, y + 1, k + 1) || dfs(x + 1, y,  k + 1) || dfs(x, y - 1,  k + 1); // Up right down left
     board[x][y] = temp;
     return res;
   }
   
     for(let i = 0; i < xLen; i++){
       for(let j = 0; j < yLen; j++){
         if(dfs(i,j,k)) return true; }}return false;
 }
Copy the code

Practice every day! The front end is a new one. I hope I can get a thumbs up