剑指 Offer 04. 二维数组中的查找

https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/
摘录题解如下(https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof/solution/mian-shi-ti-04-er-wei-shu-zu-zhong-de-cha-zhao-b-3/)：
方法二：线性查找
由于给定的二维数组具备每行从左到右递增以及每列从上到下递增的特点，当访问到一个元素时，可以排除数组中的部分元素。
从二维数组的右上角开始查找。如果当前元素等于目标值，则返回 true。如果当前元素大于目标值，则移到左边一列。如果当前元素小于目标值，则移到下边一行。
可以证明这种方法不会错过目标值。如果当前元素大于目标值，说明当前元素的下边的所有元素都一定大于目标值，因此往下查找不可能找到目标值，往左查找可能找到目标值。如果当前元素小于目标值，说明当前元素的左边的所有元素都一定小于目标值，因此往左查找不可能找到目标值，往下查找可能找到目标值。

• 代码如下：

  class Solution {
      public boolean findNumberIn2DArray(int[][] matrix, int target) {
          if(matrix==null||matrix.length==0||matrix[0].length==0){
              return false;
          }
          int rows = matrix.length;
          int row =0,column = matrix[0].length-1;
          while(row<rows&&column>=0){
              int nums = matrix[row][column];
              if(nums==target){
                  return true;
              }else if(nums>target){
                  column--;
              }else{
                  row++;
              }
          }
          return false;
      }
  }

剑指 Offer 11. 旋转数组的最小数字

https://leetcode-cn.com/problems/xuan-zhuan-shu-zu-de-zui-xiao-shu-zi-lcof/

1. 二分查找

• 代码如下：

  class Solution {
      public int minArray(int[] numbers) {
          int low =0,hight=numbers.length-1;
          while(low<=hight){
              int mid = low + (hight-low)/2;
              if(numbers[mid]<numbers[hight]){
                  hight = mid;
              }else if(numbers[mid]>numbers[hight]){
                  low = mid + 1;
              }else {
                  hight -=1;
              }
          }
          return numbers[low];
      }
  }

• 二分查找的详解：https://www.cnblogs.com/kyoner/p/11080078.html

剑指 Offer 50. 第一个只出现一次的字符

https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
1.思路主要有两类：额外空间记录频数，如HashMap(需要循环找出第一个)，LinkHashMap有序的，返回第一个元素
2.使用26个字母循环遍历存储计算

• 代码如下：

  class Solution {
      public char firstUniqChar(String s) {
          int[] count=new int[26];
          char[] chars=s.toCharArray();
          //计数
          for (char ch:chars) 
              count[ch-'a']++;
          //遍历查找
          for (char ch:chars) 
              if(count[ch-'a']==1) return ch;
          return ' ';
  }

遍历26个字母在字符串数组中是否存在；首位索引和末位索引是否一致；当前索引值是否是最小的。

• 代码如下：

  public char firstUniqChar(String s) {
      char res = ' ';
      int min = Integer.MAX_VALUE;
      for (char c = 'a'; c <= 'z'; c++) {
          int index = s.indexOf(c);
          if (index != -1 && index == s.lastIndexOf(c) && index < min) {
              min = index;
              res = c;
          }
      }
      return res;
  }