剑指offer算法题

发表于 | 更新于 | 分类于 | 阅读次数：
本文字数： 9.5k | 阅读时长 ≈ 9 分钟

二维数组中的查找

题目描述

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

解题思路

要求时间复杂度 O(M + N)，空间复杂度 O(1)。其中 M 为行数，N 为列数。
该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。

My code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# -*- coding:utf-8 -*-
class Solution:
    # array 二维列表
    def Find(self, target, array):
        # write code here
        row = len(array)
        col = len(array[0])
        c = col - 1
        r = 0
        while(r <= row-1 and c >=0):
            if(target == array[r][c]):
                return True
            elif(target > array[r][c]):
                r+=1
            else:
                c-=1
        return False

替换空格

题目描述

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

解题思路

将字符串复制给一个新的列表，碰到空格则替换，没有则copy原字符串，最后对列表进行join，返回字符串。

易错点

My code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# -*- coding:utf-8 -*-
class Solution:
    # s 源字符串
    def replaceSpace(self, s):
        # write code here
        t = len(s)
        j = 0
        m = list(s)
        for i in range(0,t):
            if(s[i] == ' '):
                m[j] = '%20'
                j+=1
            else:
                m[j] = s[i]
                j+=1
                pass

        return ''.join(m)
# s = 'I want to sleep'
# solution = Solution()
# ss = solution.replaceSpace(s)
# print(ss)

从尾到头打印链表

题目描述

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

解题思路

知识点补充

python中链表的操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
class Node():
    '创建节点'
    def __init__(self,data):
        self.data = data
        self.next = None
 
class LinkList():
    '创建列表'
    def __init__(self, node):
        '初始化列表'
        self.head = node
        self.head.next = None
        self.tail = self.head
 
    def add_node(self, node):
        '添加节点'
        self.tail.next = node
        self.tail = self.tail.next
 
    def view(self):
        '查看列表'
        node = self.head
        link_str = ''
        while node is not None:
            if node.next is not None:
                link_str += str(node.data) + '-->'
            else:
                link_str += str(node.data)
            node = node.next
        print ('The Linklist is:' + link_str)
 
    def length(self):
        '列表长度'
        node = self.head
        count = 1
        while node.next is not None:
            count += 1
            node = node.next
        print ('The length of linklist are %d' % count)
        return count
 
    def delete_node(self, index):
        '删除节点'
        if index+1 > self.length():
            raise IndexError('index out of bounds')
        num = 0
        node = self.head
        while True:
            if num == index-1:
                break
            node = node.next
            num += 1
        tmp_node = node.next
        node.next = node.next.next
        return tmp_node.data
 
    def find_node(self, index):
        '查看具体节点'
        if index+1 > self.length():
            raise IndexError('index out of bounds')
        num = 0
        node = self.head
        while True:
            if num == index:
                break
            node = node.next
            num += 1
        return node.data

My code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# -*- coding:utf-8 -*-
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # 返回从尾部到头部的列表值序列，例如[1,2,3]
    def printListFromTailToHead(self, listNode):
        # write code here
        res=[]
        while listNode:
            res.append(listNode.val)
            listNode=listNode.next
        return res[::-1]  #逆序打印

重建二叉树

题目描述

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

解题思路

  • 递归

    整体思路就是：利用递归的思想，跟归并和快排有异曲同工之妙。抓住第一个节点是根节点，然后在中序遍历中定位该节点，左边即为根节点的左子树，右边即为根节点的右子树。然后对左子树和右子树分别进行递归即可，直到左子树和右子树都没了。

  • 非递归

    整体思路：我还没认真看呢！！！！！！！！

    用两个堆栈来分别存储二叉树和先序中序序列索引值，跟递归思路一样，先找到根节点，然后分别判断在中序遍历中是否还有左右子树，如果有则计数值count+=1,当找到一个节点之后就将计数值count-=1，直到中序遍历中再也没有左右子树。

My code

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre, int [] in) {
        if(pre == null || in == null || pre.length == 0 || in.length == 0){
            return null;
        }
        return constructBinaryTree(pre,in,0,pre.length-1,0,in.length-1);
        // 首先看先序遍历的第一个数，这是根节点，然后根据中序遍历然后分为左右两个节点块
        // 再看左边的第一个数，这个肯定是根节点，然后定位到中序遍历该数的位置，再将其分为左右两个节点块，以此类推。

    }

    private TreeNode constructBinaryTree(int[] pre, int[] in, int preStart, int preEnd, int inStart, int inEnd) {
        if(preStart > preEnd || inStart > inEnd){
            return null;
        }
        TreeNode node = new TreeNode(pre[preStart]);
        int mid = inStart;
        while (pre[preStart] != in[mid])
            mid++;
        int preNumber = mid - inStart;
        node.left = constructBinaryTree(pre,in,preStart + 1,preStart + preNumber,inStart,mid - 1);

        node.right = constructBinaryTree(pre,in,preStart + preNumber + 1,preEnd,mid + 1,inEnd);
        return node;
    }
}

非递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
import java.util.*;
public class Solution {
 public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
    //p用来保存两个序列的索引值
    Stack<Integer> p = new Stack<Integer>();
    Stack<TreeNode> l = new Stack<TreeNode>();
    TreeNode cur = null;
    p.push(0);
    p.push(pre.length - 1);
    p.push(0);
    p.push(in.length - 1);
    int count = 1;
    int pStart = 0;
    int pEnd = pre.length - 1;
    int iStart = 0;
    int iEnd = in.length - 1;
    TreeNode root = new TreeNode(-1);
    l.push(root);
    while( count != 0){

      iEnd = p.pop();
      iStart = p.pop();
      pEnd = p.pop();
      pStart = p.pop();
      cur = l.pop();
      count -= 1;
      int index = find(pre[pStart], in, iStart, iEnd);
      cur.val = pre[pStart];

      int lenL = index - iStart;
      if(lenL == 0){

      }else{
        p.push(pStart + 1);
        p.push(pStart + lenL);
        p.push(iStart);
        p.push(index - 1);
        count += 1;
        cur.left = new TreeNode(-1);
        l.push(cur.left);
      }
      int lenR = iEnd - index;
      if(lenR == 0){

      }else{
        p.push(pStart + lenL + 1);
        p.push(pEnd);
        p.push(index + 1);
        p.push(iEnd);
        count += 1;
        cur.right = new TreeNode(-1);
        l.push(cur.right);
      }

    }
    return root;

  }

  int find(int target, int[] all, int start , int end){
    for(int i = start; i <= end; ++i){
      if(all[i] == target) return i;
    }
    return -1;
  }
}

知识点补充

Tips: 二叉树的前序，中序，后序遍历方法总结

前序递归和非递归算法

前序递归

递归的方法很容易实现，也很容易理解：我们先访问根节点，然后递归访问左子树，再递归访问右子树，即实现了根->左->右的访问顺序，因为使用的是递归方法，所以每一个子树都实现了这样的顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        preorderHelper(root, result);
        return result;
    }

    private void preorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        result.add(root.val); // 访问根节点
        preorderHelper(root.left, result); // 递归遍历左子树
        preorderHelper(root.right, result); //递归遍历右子树
    }
}

前序非递归

在迭代法中，我们使用栈来实现。由于出栈顺序和入栈顺序相反，所以每次添加节点的时候先添加右节点，再添加左节点。这样在下一轮访问子树的时候，就会先访问左子树，再访问右子树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        if (root == null) return result;

        Stack<TreeNode> toVisit = new Stack<>();
        toVisit.push(root);
        TreeNode cur;

        while (!toVisit.isEmpty()) {
            cur = toVisit.pop();
            result.add(cur.val); // 访问根节点
            if (cur.right != null) toVisit.push(cur.right); // 右节点入栈
            if (cur.left != null) toVisit.push(cur.left); // 左节点入栈
        }
        return result;
    }
}

中序递归和非递归算法

中序递归

无论对于哪种方式，递归的方法总是很容易实现的，也是很符合直觉的。对于中序遍历，就是先访问左子树，再访问根节点，再访问右子树，即 左->根->右：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        inorderHelper(root, result);
        return result;
    }
    
    private void inorderHelper(TreeNode root, List<Integer> result) {
        if(root == null) return;
        inorderHelper(root.left, result); // 递归遍历左子树
        result.add(root.val); // 访问根节点
        inorderHelper(root.right, result); // 递归遍历右子树
    }
}

中序非递归

中序遍历的迭代法要稍微复杂一点，因为最先遇到的根节点不是最先访问的，我们需要先访问左子树，再回退到根节点，再访问根节点的右子树，这里的一个难点是从左子树回退到根节点的操作，虽然可以用栈来实现回退，但是要注意在出栈时保存根节点的引用，因为我们还需要通过根节点来访问右子树：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根节点
                cur = cur.left; // 循环添加左节点
            }
            cur = toVisit.pop(); // 当前栈顶已经是最底层的左节点了，取出栈顶元素，访问该节点
            result.add(cur.val);
            cur = cur.right; // 添加右节点
        }
        return result;
    }
}

在看这部分代码中，脑海中要有一个概念：当前树的根节点的左节点，是它的左子树的根节点。因此从不同的层次上看，左节点也是根节点。另外，LeetCode上也提供了关于中序遍历的动态图的演示，感兴趣的读者可以去看一看。

后序递归和非递归算法

后序递归

无论对于哪种方式，递归的方法总是很容易实现的，也是很符合直觉的。对于后序遍历，就是先访问左子树，再访问右子树，再访问根节点，即 左->右->根：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        postorderHelper(root, result);
        return result;
    }

    private void postorderHelper(TreeNode root, List<Integer> result) {
        if (root == null) return;
        postorderHelper(root.left, result); // 遍历左子树
        postorderHelper(root.right, result); // 遍历右子树
        result.add(root.val); // 访问根节点
    }
}

后序非递归

前面说过，与中序遍历不同的是，后序遍历在访问完左子树向上回退到根节点的时候不是立马访问根节点的，而是得先去访问右子树，访问完右子树后在回退到根节点，因此，在迭代过程中要复杂一点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> result = new LinkedList<>();
        Stack<TreeNode> toVisit = new Stack<>();
        TreeNode cur = root;
        TreeNode pre = null;

        while (cur != null || !toVisit.isEmpty()) {
            while (cur != null) {
                toVisit.push(cur); // 添加根节点
                cur = cur.left; // 递归添加左节点
            }
            cur = toVisit.peek(); // 已经访问到最左的节点了
            //在不存在右节点或者右节点已经访问过的情况下，访问根节点
            if (cur.right == null || cur.right == pre) { 
                toVisit.pop();
                result.add(cur.val);
                pre = cur;
                cur = null;
            } else {
                cur = cur.right; // 右节点还没有访问过就先访问右节点
            }
        }
        return result;
    }
}

这里尤其注意后续遍历和中序遍历中对于从最左侧节点向上回退时的处理：
中序遍历与后序遍历的对比

在后序遍历中，我们首先使用的是：

1
cur = toVisit.peek();

注意，这里使用的是peek而不是pop，这是因为我们需要首先去访问右节点，下面的：

1
if (cur.right == null || cur.right == pre)

就是用来判断是否存在右节点，或者右节点是否已经访问过了，如果右节点已经访问过了，则接下来的操作就和中序遍历的情况差不多了，所不同的是，这里多了两步：

1
2
pre = cur;
cur = null;

这两步的目的都是为了在下一轮遍历中不再访问自己，cur = null很好理解，因为我们必须在一轮结束后改变cur的值，以添加下一个节点，所以它和cur = cur.right一样，目的都是指向下一个待遍历的节点，只是在这里，右节点已经访问过了，则以当前节点为根节点的整个子树都已经访问过了，接下来应该回退到当前节点的父节点，而当前节点的父节点已经在栈里了，所以我们并没有新的节点要添加，直接将cur设为null即可。

pre = cur 的目的有点类似于将当前节点标记为已访问，它是和if条件中的cur.right == pre配合使用的。注意这里的两个cur指的不是同一个节点。我们假设当前节点为C，当前节点的父节点为A，而C是A的右孩子，则当前cur是C，但在一轮中，cur将变成A，则：

1
2
3
  A 
 / \
B   C (pre)
  • pre = cur 就是 pre = C
  • if (cur.right == null || cur.right == pre) 就是 if (A.right == null || A.right == pre)

这里，由于A是有右节点的，它的右节点就是C，所以A.right == null不成立。但是C节点我们在上一轮已经访问过了，所以这里为了防止进入else语句重复添加节点，我们多加了一个A.right == pre条件，它表示A的右节点已经访问过了，我们得以进入if语句内，直接访问A节点。

用两个栈实现队列

旋转数组的最小数字

tips：只要是关于有序数组，基本就在考察二分法

斐波那契数列

变态跳台阶

Thank you for your accept. mua！
-------------本文结束感谢您的阅读-------------