1. 机器人运动范围

地上有一个m行n列的方格，从坐标 [0,0] 到坐标 [m-1,n-1] 。一个机器人从坐标 [0, 0] 的格子开始移动，它每次可以向左、右、上、下移动一格（不能移动到方格外），也不能进入行坐标和列坐标的数位之和大于k的格子。例如，当k为18时，机器人能够进入方格 [35, 37] ，因为3+5+3+7=18。但它不能进入方格 [35, 38]，因为3+5+3+8=19。请问该机器人能够到达多少个格子？

  1. 示例 1：
  3. 输入：m = 2, n = 3, k = 1
  4. 输出：3
  5. 示例 2：
  7. 输入：m = 3, n = 1, k = 0
  8. 输出：1

思路：

  • 给定一个矩阵网格，机器人按照对应索引位置的数字各位数之和小于指定值k，表示可以找到。

  • 思考：

如果使用全局for循环遍历每个位置，然后求取每个位置的数字的各位数之和与k进行比较，进而判断是否能到达。

  • 出现的问题：
    • 由于当索引数字从类似于“9”走到“10”位置，这时位数之和会发生突变，从9变成1；也就是说如果使用单纯的暴力遍历每一个位置，很容易造成多结果（不可达解）。image.png
  • 考虑使用深度优先搜索（DFS），从一个位置开始进行递归搜索，然后每一个位置处理完成会将当前为能够搜索到的点的个数全部返回给上一级（上一个点）。
    • 只需要处理好 “10”的倍数的突变位置即可。
      • 做一个条件判断
    • 实现剪枝操作，将搜索到了的位置进行记录，以便于不会出现重复所搜重复记录。使用
      • 使用一个与给定的二维数组规模一样的boolean数组进行记录，true表示搜索过，并可达。
class Solution {
    // 设置全局变量,dfs()方法就不需要进行多个参数传递了
    int m,n,k;
    boolean[][] visited;
    public int movingCount(int m, int n, int k) {
        // 初始化全局变量
        this.m = m;
        this.n = n;
        this.k = k;
        this.visited = new boolean[m][n];
        return dfs(0,0,0,0);
    }

    private int dfs(int i,int j,int si,int sj){
        // 设置递归结束条件
        if(i>=m || j>=n || si+sj>k || visited[i][j]) return 0;
        // 未搜索过,未越界,满足可搜索范围k
        visited[i][j] = true; // 标记为已搜索可达
        // 进一步搜索(由于从(0,0)位置开始,只需要进行向下和向右搜索即可)
        return 1 + dfs(i+1,j,(i+1)%10==0? si-8 : si+1,sj) + dfs(i,j+1,si,(j+1)%10==0? sj-8 : sj+1);
    }
}

2. 搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5
输出: 2
示例 2:

输入: [1,3,5,6], 2
输出: 1
示例 3:

输入: [1,3,5,6], 7
输出: 4
示例 4:

输入: [1,3,5,6], 0
输出: 0

思路：

  • 关键词“排序数组”，基于已排序的数组的搜索，必然优先想到的是简单又快速的二分查找算法。

  • 同时，题目中要求如果数组中没有该元素，需要将返回元素应当被插入的位置。

    class Solution {
  public int searchInsert(int[] nums, int target) {
      // 使用搜索算法: 二分查找法
      // 以二分查找法为基础,进行改进,让其能够返回为插入的元素的应该被插入位置
      return binarySeach(0,nums.length-1,target,nums);
  }

  // 改进的二分查找算法
  private int binarySeach(int left,int right,int target,int[] nums){
      int mid = (left+right)/2;
      int midValue = nums[mid];
      if(midValue==target){
          return mid;
      }else if(target < midValue){
          if(mid-1<left || target>nums[mid-1]) return mid;
          return binarySeach(left,mid-1,target,nums);
      }else {
          if(mid+1>right || target<nums[mid+1]) return mid+1;
          return binarySeach(mid+1,right,target,nums);
      }
  }
}