剑指 offer day5

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

题目：

在一个n*m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个高效的函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

题解：

从最右上角的数据开始判断：

-如果target值小于当前值，则向左移动，纵坐标-1；

-如果target值大于当前值，则向下移动，横坐标+1。

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    if (matrix.length==0){
    return false;}int n=matrix[0].length;int m=matrix.length;int i=0,j=n-1;while (i<=m-1&&j>=0){
    if (target==matrix[i][j]){
    return true;}else if (target<matrix[i][j]){
    j=j-1;}else {
    i=i+1;}}return false;}

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

题目：

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小元素。例如，数组 [3,4,5,1,2] 为 [1,2,3,4,5] 的一个旋转，该数组的最小值为1。

题解：

1. 直接遍历或者排序之后输出第一个，这样的面试的话基本上就是回去等通知吧！
2. 官方题解–该睡觉了www

 public int minArray(int[] numbers) {
    int low = 0;int high = numbers.length - 1;while (low < high) {
    int pivot = low + (high - low) / 2;if (numbers[pivot] < numbers[high]) {
    high = pivot;} else if (numbers[pivot] > numbers[high]) {
    low = pivot + 1;} else {
    high -= 1;}}return numbers[low];}

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

题目：

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

题解(两次遍历)：

1. 第一次遍历记录所有字符出现的次数；
2. 第二次遍历返回出现一次的字符。

注意：map接口的getOrDefault方法

public char firstUniqChar(String s) {
    Map<Character,Integer> map = new HashMap<>();char[] array = s.toCharArray();for (int i=0;i<array.length;i++){
    map.put(array[i], map.getOrDefault(array[i],0)+1);}for (int i = 0; i < array.length; ++i) {
    if (map.get(array[i]) == 1) {
    return array[i];}}return ' ';}

好困！