剑指offer 1-80

面试题03. 数组中重复的数字

找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字

/**
方法一：排序后，遍历数组，判断条件：连续两个元素相等
方法二：遍历放入哈希表。时间复杂度O（n）
方法三：遍历元素，与它大小相等的数组下标元素位置交换，如果相同返回这个重复值
**/
class Solution {
    //自己第一次写的，建立了一个数组来保存原始数组的信息，复杂度太高
    // public int findRepeatNumber(int[] nums) {
    //     int []a=new int[nums.length];
    //     for(int i=0;i<nums.length;i++){
    //         a[nums[i]]++;
    //         if(a[nums[i]]>1)
    //             return nums[i];
    //     }
    //     return -1;
    // }
     public int findRepeatNumber(int[] nums) {
       for(int i=0;i<nums.length;){
           if(nums[i]!=i&&nums[i]!=nums[nums[i]]){
               swap(nums,nums[i],i);
           }
           else if(nums[i]==i){
               i++;
           }
           //这个else if必须放在上一个后面，否则不能判断0
           else if(nums[i]==nums[nums[i]]){
               return nums[i];
           }
       }
       return -1;
    }
    //交换元素
    public void swap(int[]nums,int i,int j){
        int temp;
        temp=nums[i];
        nums[i]=nums[j];
        nums[j]=temp;
    }
}

面试题04. 二维数组的查找

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

/**
思路一：暴力遍历
思路二：将数组左下当做flag值，target小于flag就删除行，target大于flag就删除列，等于就返回。
**/
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        //i是二维数组的行数
        int i=matrix.length-1;
        int j=0;
        //j是二维数组的列数
        while(i>=0&&j<matrix[0].length){
            if(target==matrix[i][j]){
                return true;
            }
            int c=(target<matrix[i][j])?--i:++j;
        }
        return false;
    }
}

面试题05. 替换空格

因为strng在java里是定长的，需要构造 StringBuilder对象。

class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        // for(Character c : s.toCharArray())
        // {
        //     if(c == ' ') res.append("%20");
        //     else res.append(c);
        // }
        // return res.toString();
        // }
        int i=0;
        while(i<s.length()){
            char a=s.charAt(i);
            if(a==32)
                res.append("%20");
            else
                res.append(a);
            i++;
        }
        return res.toString();
    }
   
}

剑指offer 1-80

原文：https://www.cnblogs.com/cmg219/p/12323639.html