当前位置：网站首页>Offer brush questions - 1

Offer brush questions - 1

2022-08-01 06:32:00 【Curry won't shoot 3-pointers】

剑指 Offer 03. 数组中重复的数字
class Solution {
         public int findRepeatNumber(int[] nums) {
        Map<Integer,Integer> map=new HashMap<>();
        for (int i = 0; i <nums.length; i++) {
            if (!map.containsKey(nums[i])){
                map.put(nums[i],1);
            }else {
                map.put(nums[i],map.get(nums[i])+1);
            }
        }
        for (Map.Entry<Integer,Integer> entry:map.entrySet()) {
            if (entry.getValue()>1){
                return entry.getKey();
            }
        }
        return -1;
    }


}
My idea is to use onehashmap来存储
One point to note is thatmap的遍历方式,用Entryto traverse in this formMap的元素
也可以用Set,因为其Set的唯一性,If it is encountered, it will directly return to this finger

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

class Solution {
   public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows=0;
        int columns=matrix[0].length-1;
        if (target>matrix[matrix.length-1][columns]||target<matrix[0][0]){
            return false;
        }else {
            return helper(matrix,rows,columns,target);//从左上角开始递归
        }
    }

    private boolean helper(int[][] matrix, int rows, int columns,int target) {
        if (rows<0||rows>matrix.length-1||columns<0||columns>matrix[0].length){
            return false;
        }
        if (matrix[rows][columns]==target){
            return true;
        }else if(matrix[rows][columns]>target){
            return helper(matrix,rows,columns-1,target);
        }else {
            return helper(matrix,rows+1,columns,target);
        }
    }
}

剑指 Offer 05. 替换空格
class Solution {
    public String replaceSpace(String s) {
        return s.replace(" ", "%20") ;
    }
}
大概思路,创建一个新字符串,Add any spaces%20,If other characters are encountered,就直接添加

剑指 Offer 06. 从尾到头打印链表

stack solution

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
      public int[] reversePrint(ListNode head) {
        LinkedList<Integer> stack=new LinkedList<>();
        while (head!=null){
            stack.addLast(head.val);
            head=head.next;
        }
        int arr[]=new int[stack.size()];
        for (int i = 0; i < arr.length; i++) {
            arr[i]=stack.removeLast();
        }
        return arr;
    }

}

递归解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
   LinkedList<Integer> list=new LinkedList<>();
    public int[] reversePrint(ListNode head) {
       helper(head);
       int arr[]=new int[list.size()];
        for (int i = 0; i <list.size(); i++) {
            arr[i]=list.get(i);
        }
        return arr;
    }

    private void helper(ListNode head) {
        if (head==null) return;
        helper(head.next);
        list.add(head.val);
    }
}