剑指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个结点

热门文章

最新文章

相关课程

相关电子书

相关实验场景

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

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

JZ3 数组中重复的数字

JZ4 二维数组中的查找

JZ5 替换空格

JZ6 从尾到头打印链表

JZ18 删除链表的节点

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

热门文章

最新文章

相关课程

相关电子书

相关实验场景