小白的LeetCode日记记录Day1（持续更新ing

1. 数组中重复的数字

找出数组中重复的数字。

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

解法一：利用HashSet元素不可重复的性质。遍历数组当元素有重复，覆盖该元素并用一个变量储存它，之后返回该变量

class Solution {
    public int findRepeatNumber(int[] nums) {
        Set<Integer> set = new HashSet<Integer>();
        int repeat = -1;
        for (int num : nums) {
            if (!set.add(num))
                repeat = num;
                break;
        }
        return repeat;
    }
}

解法二：原地置换。本着一个萝卜一个坑的原则，遍历整个数组，如果下标与元素相等就下一个，如果下标与元素不相等就把他换到下标相等的位置，此时如果该位置已经有一个数了，那么该数是那个重复的数哦⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

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

        }
        return -1;
    }
}

2.二维数组的查找

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

解法：由于行和列的元素都是递增的。于是可以从右上角开始查找，当目标数大于右上角时，说明大于第一行，于是跳到下一行；若小于右上角时，说明不在这一列，于是跳到他左边那一列，照此循环往复。

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

3.替换空格

请实现一个函数，把字符串 s 中的每个空格替换成"%20"。

偷懒解法：利用可变数组StringBuffer，在一个字符丢到数组前进行判断，如果该字符为空格则替换成%20（（⁄(⁄ ⁄•⁄ω⁄•⁄ ⁄)⁄

class Solution {
    public String replaceSpace(String s) {
        StringBuffer sb = new StringBuffer();
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c==' ')
                sb.append("%20");
            sb.append(c);
        }
        return s;
    }
}

4.反转链表

输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。

解法：这里可以利用栈的先进后出特性实现，将节点压入栈里，之后再一个个弹出来保存在数组里就ok啦！

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }

class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<ListNode> s = new Stack<>();
        ListNode temp = head;
        while (temp != null){
            s.push(temp);
            temp = temp.next;
        }
        int size = s.size();
        int Print[] = new int[size];
        for (int i = 0; i < size; i++) {
            Print[i] = s.pop().val;
        }
        return Print;
    }
}

5.用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

解法：还是利用栈先进后出的特点，将栈一压入整数弹出压入栈二中之后弹出。首先声明一个计数器，插入操作就是将整数压入栈一中并计数，删除操作的话首先判断计数器是否已经为0，然后判断栈二是否为空，若为空将栈一的整数通过循环压入栈二，之后计数器-1并弹栈。

class CQueue {
    Deque<Integer> stack1;
    Deque<Integer> stack2;
    int size;
    public CQueue() {
        stack1 = new LinkedList<>();
        stack2 = new LinkedList<>();
    }

    public void appendTail(int value) {
        stack1.push(value);
        size++;
    }

    public int deleteHead() {
        if (size==0)
            return -1;
        if (stack2.isEmpty()){
            while (!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
        }
        size--;
        return stack2.pop();
    }
}

本文地址：https://blog.csdn.net/weixin_47707204/article/details/111934494