1.数组中重复的数字

【题目】

 【思路】

• 排序法：调用JDK中的排序算法，然后遍历数组，两两进行比较，遇到重复，返回结果（时间复杂度：O(nlogn)用在排序上，空间复杂度O(1)）空间复杂度O(1)意为算法执行所需要的临时空间不随着某个变量n的大小而变化
• 哈希表：准备一个哈希表，将数组中的第一个元素存入此表，后来的元素依次与哈希表进行判断，不过不存在那就存入该表，如果存在，那就返回该值(时间复杂度：O(n),空间复杂度O(n))
• 下标法1（用到了题目中给到的条件）：通过不断的交换元素，使得元素和它所对应的下标相等，因为有多个相同元素，所以会有多个元素对应同一个下标。
• 下标法2：建立一个新的数组长度为n，初始化所有元素，将第一个元素对应下标加一，后面的每一个元素对应的下标先进行判断，如果是0，那么加一，如果非0，那么返回该元素

 【代码】

下标法1

 class Solution {
    public int findRepeatNumber(int[] nums) {
        int sw;
        for(int i=0;i<nums.length;i++){
            while(nums[i]!=i){
                if(nums[i]==nums[nums[i]])
                return nums[i];
                sw=nums[i];
                nums[i]=nums[sw];
                nums[sw]=sw;
            }
        }
        return -1;
    }
}

下标法2

class Solution {
    public int findRepeatNumber(int[] nums) {
        int[] arr = new int[nums.length];
        for(int i = 0; i < nums.length; i++){
            arr[nums[i]]++;
            if(arr[nums[i]] > 1) return nums[i];
        }
        return -1;
    }
}

2.二位数组中的查找

【思路】

• 暴力法：两层循环遍历寻找

• 二分查找：利用题目中有序这个条件，每行进行二分查找（时间复杂度：O(nlogn)用在排序上，空间复杂度O(1)）

• 换位思考，从左下角向右上角看，是一个二叉树

【代码】

换位思考

class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix==null||matrix.length<=0||matrix[0].length<=0)
            return false;
        int cols=matrix.length;
        int rows=matrix[0].length;

        int col=cols-1;
        int row=0;

        while(col>=0&&row<rows){
            if(target<matrix[col][row]){
                col--;
            }else if(target>matrix[col][row]){
                
                row++;
            }else{
                return true;
            }

        }
        return false;
    }
}

书写注意：

• 查找前先排除极端条件（数组为空，行为空，列为空）
• 注意数组的长度的数字和数组的下标的数字细节描写（数组的长度是从1开始，数组下标是从0开始）

3.替换空格

【题目】

【思路】

• Java：String类
• C++：原地扩容

【代码】

Java：

class Solution {
    public String replaceSpace(String s) {
        StringBuilder stringBuilder=new StringBuilder();
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)==' ')
            stringBuilder.append("%20");
            else{
                stringBuilder.append(s.charAt(i));
            }
        }
        return stringBuilder.toString();
    }
}

C++

class Solution {
    public String replaceSpace(String s) {
        int count=0;
        for(int i=0;i<s.length();i++){
             if(s.charAt(i)==' ')
             count++;
        }
        //创建数组
        char[] chars=new char[s.length()+count*2];
        //进行倒序遍历
        int n=s.length()+count*2-1;
         for(int i=s.length()-1;i>=0;i--){
             
             if(s.charAt(i)==' '){
                chars[n--]='0';
                chars[n--]='2';
                chars[n--]='%';
             }
            else{
                chars[n--]=s.charAt(i);
            }
         }
        return new String(chars);
    }
}

4.从头到尾打印链表

【题目】

 【思路】

• 栈：利用栈先进后出的性质，对链表进行正向的遍历，反向的存储。
• 反转：将该链表进行反转
  • 递归方法
  • 原地反转
• 反向数组存贮：将链表进行正向的遍历，在数组中的存储从后向前。

 【代码】

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if(head==null)
            return new int[0] ;
        int count=0;
        ListNode point=head;
        while(point!=null){
            count++;
            point=point.next;
        }
        int[] nums=new int[count];
        int k= count - 1;
        while(head!=null||k>0){
            nums[k--]=head.val;
            head=head.next;
        }
        return nums;

    }
}