2019-07-27 10:04 广州大学 Java

关注

剑指offer总结（一）

1. 二维数组中的查找

题目描述

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

解题思路

暴力法，直接两层循环，时间复杂度为O（row * col），牛客网能通过，但是不推荐
优化的方法：利用有序性避免不必要的查找。对于该数组的任意一个元素来说，大于它的元素在其右下方，小于它的元素在其左上方，所以我们可以从右上角开始搜索，当目标值大于当前元素时向下走，当目标值小于当前元素时，向左走。最好情况时间复杂度为O（1），最坏情况时间复杂度为O（row + col），平均时间复杂度为 O（row + col），空间复杂度为O（1）。
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null)
            return false;

        int rows = array.length;
        int cols = array[0].length;  
        int row = 0, col = cols - 1;
        while(col >= 0 && row <= rows - 1){
            if(target > array[row][col])
                row++;
            else if(target < array[row][col])
                col--;
            else
                return true;
        }       
        return false;
    }
}

2. 替换空格

题目描述

请实现一个函数，将一个字符串中的每个空格替换成 “%20”。例如，当字符串为 We Are Happy. 则经过替换之后的字符串为 We%20Are%20Happy。

解题思路

先确定给定字符串中有几个空格，每出现一个空格，则在字符串末尾添加两个空格，因为一个空格要替换成三个字符（%20）。

令 p1 指向原字符串的末尾，p2 指向当前字符串的末尾，为了不影响 p1 遍历原字符串，我们从后往前开始遍历字符串，当遇到 p1 为空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。
public class Solution {
 public String replaceSpace(StringBuffer str) {
     if(str == null)
         return str.toString();

     int p1 = str.length() - 1;
     for(int i = 0; i <= p1; i++){
         if(str.charAt(i) == ' ')
             str.append("  ");
     }

     int p2 = str.length() - 1;
     while(p1 >= 0 && p2 > p1) {
         char c = str.charAt(p1--);
         if(c == ' '){
             str.setCharAt(p2--, '0');
             str.setCharAt(p2--, '2');
             str.setCharAt(p2--, '%');
         } else {
             str.setCharAt(p2--, c);
         }
     }

     return str.toString();
 }
}

3. 从尾到头打印链表

题目描述

输入一个链表，按链表值从尾到头的顺序返回一个 ArrayList。

解题思路

最容易想到的就是遍历链表，每次都往 ArrayList 头部添加值，但每次添加，ArrayList的所有元素都要往后移动一位，故时间复杂度为 O（n ^2^)。由于题目限制了结果存放在 ArrayList ，所以不能直接使用 LinkendList 返回结果，但可以先降结果存放在 LinkedList （可以认为是一个栈）中（每次往头部添加元素时间复杂度为O（1）），然后再遍历 LinkedList 转存在 ArrayList 中，这样时间复杂度就降为O（n）了。但额外多使用了一个 LinkedList，空间消耗大了。
//O（n ^2^)
public class Solution {
   public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> res = new ArrayList<>();
       while(listNode != null){
           res.add(0, listNode.val);
           listNode = listNode.next;
       }
       return res;
   }
}

//O(n)
public class Solution {
   public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> res = new ArrayList<>();
       LinkedList<Integer> list = new LinkedList<>();

       while(listNode != null){
           list.addFirst(listNode.val);
           listNode = listNode.next;
       }
       for(int l : list){
           res.add(l);
       }
       return res;
   }
}
与上面思想类似的是使用一个头节点（不存放数据）先逆转链表，然后顺序遍历链表，依次存在放 ArrayList 中。
public class Solution {
   public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
       ArrayList<Integer> res = new ArrayList<>();
       ListNode head = new ListNode(-1);

       while(listNode != null) {
           ListNode next = listNode.next;
           listNode.next = head.next;
           head.next = listNode;
           listNode  = next;
       }

       head = head.next;
       while(head != null) {
           res.add(head.val);
           head = head.next;
       }
       return res;
   }
}
可以使用递归思想来实现头插，感觉效率比较低
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> res = new ArrayList<>();
        if(listNode != null) {
            res.addAll(printListFromTailToHead(listNode.next));
            res.add(listNode.val);
        }
        return res;
    }
}

4. 重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列 {1,2,4,7,3,5,6,8} 和中序遍历序列 {4,7,2,1,5,3,8,6}，则重建二叉树并返回。

解题思路

前序序列第一个为根节点的值，根节点把中序遍历分为两部分，左边为左子树，右边为右子树。因为每次都要在中序序列中寻找根节点，所以用一个 HashMap 来存储中序序列的索引，查找的时候比较快

剑指offer总结（一）

1. 二维数组中的查找

题目描述

解题思路

2. 替换空格

题目描述

解题思路

3. 从尾到头打印链表

题目描述

解题思路

4. 重建二叉树

题目描述

解题思路

5. 两个栈实现队列

题目描述

解题思路

6.旋转数组的最小数字

题目描述

解题思路

7. 斐波那契数列

题目描述

解题思路

8. 跳台阶

题目描述

解题思路

9. 变态跳台阶

题目描述

解题思路

10 矩形覆盖

题目描述

解题思路

11. 二进制中1的个数

题目描述

解题思路

全站热榜