剑指offer全集系列Java版本(1)-阿里云开发者社区

JZ3 数组中重复的数字

解法1: 暴力循环

也就是说, 直接开始从最左边的2开始遍历整个数组, 如果发现有重复的, 就直接返回这个数字, 如果没有重复的, 就选中下一个数字3, 然后开始遍历整个数组. 以此类推, 如果一直到数组最后一个数都没有重复的话就返回-1, 否则返回重复的数.

此方法没有使用额外的空间, 所以空间复杂度为O(1)

此方法经历了两层for循环, 每次循环的长度都为数组的长度n, 因此时间复杂度为O(n^2)

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        for(int i = 0; i < numbers.length; i++) {
            int tem = numbers[i];
            for(int j = i + 1; j < numbers.length; j ++) {
                if (tem == numbers[j]) {
                    return tem;
                }
            }
        }
        return -1;
    }
}

解法2: 集合Set

创建一个集合对象, 从0下标开始遍历数组, 每次遍历的时候, 看这个数是否在集合中已经存在, 如果不存在就将这个数添加到集合当中, 如果这个数在集合中已经存在, 就直接返回这个数. 如果遍历完整个数组的时候, 还没有在集合中找到重复的数, 那么就返回-1.

此方法创建了一个集合, 最坏的情况下需要存储数组里面所有的元素, 因此空间复杂度为O(n)

此方法只需要遍历一次数组即可, 因此时间复杂度为O(n)

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        Set<Integer> set = new TreeSet<>();
        for(int i = 0; i < numbers.length; i++) {
            int tem = numbers[i];
            if (set.contains(tem)) {
                return tem;
            }
            set.add(tem);
        }
        return -1;
    }
}

解法3 : 排序和遍历

根据题目所给的数组的长度为n, 然后这个数组里面的数的取值范围又是[0, n - 1], 也就是说, 如果这个数组里面没有重复的, 那么将这个数组从小到大排序之后, 如果不存在重复的, 那么数组里面的元素大小就应该和它的下标相等, 如果不等, 则说明存在重复的.

此方法没有使用额外的空间, 因此空间复杂度为O(1)

此方法需要遍历一次集合或者是排序时间复杂度为O(n)

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        if (numbers.length == 0) {
            return -1;
        }
        Arrays.sort((numbers));
        int dele = numbers[0];
        for(int i = 0; i < numbers.length; i++) {
            if ((i + dele) != numbers[i]) {
                return numbers[i];
            }
        }
        return -1;
    }
}

JZ4 二维数组中的查找

解法1 : 暴力搜索

一个很简单的方法, 就是, 把里面所有的元素全部都遍历一次, 查找里面是否存在target这个元素, 如果不存在那么就返回false, 如果存在就返回true.

由于没有用到额外的空间, 所以空间复杂度为O(1)

需要遍历整个二维数组, 所以空间复杂度为O(n * m)

此外,对于每一行, 我们除了直接从左到右进行搜索, 还可以进行二分查找, 因为每一行都是有序的.

使用二分查找:

时间复杂度：O(Mlog N ) 时间复杂度将进一步缩小

空间复杂度：O(1)

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型二维数组 
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        for(int i = 0; i < array.length; i++) {
            for(int j = 0; j < array[0].length; j++) {
                if (target == array[i][j]) {
                    return true;
                }
            }
        }
        return false;
    }
}

解法2 : 线性搜索

建立如图的坐标系, target放在左下角进行搜索, 如图, 假设现在target为7, 从左下角第一个元素6开始比较, target比6大, 往右一个元素继续比较, 也就是继续和8比较, 现在target = 7 比8小, 所以往上一个元素, 也就是和7进行比较, target = 7, 于是返回true. 假设target为3, 根据上图搜索, 依次比较的元素为: 6 -> 4 -> 2 -> 4 -> 2 -> 8, 比较完后, 最后遇到比较的元素的下标出了数组的边界, 也就是变成了-1的时候, 就结束比较.

时间复杂度：O(m+n)，遍历矩阵的时候，最多经过矩阵的一行一列
空间复杂度：O(1)，常数级变量，无额外辅助空间

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param target int整型 
     * @param array int整型二维数组 
     * @return bool布尔型
     */
    public boolean Find (int target, int[][] array) {
        if (array[0].length == 0) {
            return false;
        }
        // 空间复杂度o(1), 时间复杂度O(m + n)
        int x = 0;
        int y = array.length - 1;
        while (x != array[0].length && y != -1) {
            int now = array[y][x];
            if (target > now) {
                x++;
            } else if (target < now) {
                y--;
            } else {
                return true;
            }
        }
        return false;
    }
}

JZ5 替换空格

依次遍历字符串, 从字符串的第一个字符开始, 然后新建一个StringBuilder sb, 如果遍历的字符不是空格则直接将其添加到sb中, 如果是空格, 就添加 %20 到sb中去. 然后返回sb.toString();

时间复杂度O(n)
空间复杂度O(n)

import java.util.*;
 
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

JZ6 从尾到头打印链表

方法一: 使用数组来记录链表里面所有的元素, 然后新建一个链表, 将数组里面的元素反向添加到新建的链表中去.

空间复杂度为O(n)
时间复杂度为O(n)

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        int[] arr = new int[10000];
        int size = 0;
        ListNode tem = listNode;
        while (tem != null) {
            arr[size++] = tem.val;
            tem = tem.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        for(int i = size - 1; i >= 0; i--) {
            list.add(arr[i]);
        }
        return list;
    }
}

方法二: 使用堆栈, 其实总体上的思想其实和方法一差不多的, 只是换了一个形式.

时间复杂度为O(n)
空间复杂度为O(n)

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        ListNode tem = listNode;
        while (tem != null) {
            stack.push(tem.val);
            tem = tem.next;
        }
        ArrayList<Integer> list = new ArrayList<>();
        while (!stack.isEmpty()) {
            int topElement = stack.pop();
            list.add(topElement);
        }
        return list;
    }
}

方法三: 递归, 既然我们正向不能直接得出结果, 那我们就可以使用递归, 先将标记结点递归到最后一位, 然后从最后一位开始反方向遍历元素:

时间复杂度为O(n)
空间复杂度为O(n)

import java.util.*;
/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<>();
        function(list, listNode);
        return list;
    }
 
    public static void function(ArrayList<Integer> list, ListNode node) {
        if (node == null) {
            return;
        }
        function(list, node.next);
        list.add(node.val);
    }
}

JZ18 删除链表的节点

这题比较简单, 我们直接使用遍历然后删除结点即可, 也就是使用双指针的形式, 一个指针用来记录后面的结点, 方式丢失, 一个指针用来连接记录结点. 但是要注意空指针的问题. 以及元素比较少的时候该怎么判断.

时间复杂度O(n)
空间复杂度O(1)

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode deleteNode (ListNode head, int val) {
        ListNode l = head;
        ListNode r = head.next;
        if (l.val == val) {
            return head.next;
        }
        while (r != null) {
            if (r.val == val) {
                l.next = r.next;
                break;
            }
            r = r.next;
            l = l.next;
        }
        return head;
    }
}

JZ22 链表中倒数最后k个结点

方法一: 直接遍历, 利用性质, 先遍历出链表里面所有的元素的总个数, 然后再计算出需要走的步数,

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int size = 0;
        ListNode tem = pHead;
        while (tem != null) {
            size ++;
            tem = tem.next;
        }
        if (size < k) {
            return null;
        }
        for(int i = 0; i < size - k; i++) {
            pHead = pHead.next;
        }
        return pHead;
    }
}

方法二: 快慢指针, 一个快一个慢:

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        ListNode slow = pHead;
        ListNode fast = pHead;
        if (slow == null) {
            return null;
        }
        for(int i = 0; i < k; i++) {
            fast = fast.next;
            if (i != k - 1 && fast == null) {
                return null;
            }
        }
        while (fast != null) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}

方法三 : 使用堆栈, 将所有的结点, 从pHead开始, 全部压入栈中, 然后取出第k个结点, 就是倒数第k个结点了:

import java.util.*;
 
/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
 
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param pHead ListNode类 
     * @param k int整型 
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        Stack<ListNode> stack = new Stack<>();
        while (pHead != null) {
            stack.push(pHead);
            pHead = pHead.next;
        }
        if (stack.isEmpty()) {
            return null;
        }
        ListNode result = null;
        for(int i = 0; i < k; i++) {
            result = stack.pop();
            if (i != k - 1 && stack.isEmpty()) {
                return null;
            }
        }
        return result;
    }
}

剑指offer全集系列Java版本(1)

JZ3 数组中重复的数字

JZ4 二维数组中的查找

JZ5 替换空格

JZ6 从尾到头打印链表

JZ18 删除链表的节点

JZ22 链表中倒数最后k个结点

热门文章

最新文章

相关课程

相关电子书

相关实验场景