Fork me on GitHub
image frame

且听风吟

剑指offer JZ6

刷题 / 数组

JZ6

原题链接

题目

把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

核心

看似简单，实则考虑数组查找的优化问题

思路

傻乎乎遍历 2分

$T:O(\frac{n}{2} )$

$S:O(1)$

要不就不转，第一个元素是最小，要不就转，那突然下落的地方肯定是最小元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    int minNumberInRotateArray(vector<int> rotateArray) {
        if (rotateArray.empty()) return 0;
        int min = rotateArray[0];
        for (int i = 0; i < rotateArray.size() - 1; i++) {
            if (rotateArray[i] > rotateArray[i + 1]) {
                min = rotateArray[i + 1];
                break;
            }
        }
        return min;
    }
};

二分法 5分

剑指offer JZ5

刷题 / 栈队列

JZ5

题目

用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。

核心

栈模拟队列，两个栈捯饬一下即可

思路

保持 stack2 在所有操作后为空，只在 pop 时借用

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
class Solution {
public:
    void push(int node) {
        stack1.push(node);
    }

    int pop() {
        int top=-1;
        //转移至栈2
        while (!stack1.empty()) {
            stack2.push(stack1.top());
            stack1.pop();
        }
        //栈1不空，则栈2必不空
        if (!stack2.empty()) {
            top = stack2.top();
            stack2.pop();
            while (!stack2.empty()) {
                stack1.push(stack2.top());
                stack2.pop();
            }
            return top;
            //栈1空
        } else return NULL;
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

剑指offer JZ4

刷题 / 树

JZ4

原题链接

题目

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

核心

中序+其他序造树，分随机存储（数组），顺序存储（链表）两种，找 root 两边 dfs 递归即可，PAT 送分题

思路

常规题

$T:O(n)$

$S:O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    TreeNode *reConstructBinaryTree(vector<int> pre, vector<int> vin) {
        return buildTree(pre, vin, 0, pre.size() - 1, 0, vin.size() - 1);
    }

    TreeNode *buildTree(vector<int> &pre, vector<int> &vin, int preL, int preR, int inL, int inR) {
        //返回
        if (preL > preR) return NULL;
        //新根
        TreeNode *root = new TreeNode(pre[preL]);
        //找 vin 中的根
        int i;
        for (i = inL; i <= inR; i++) {
            if (pre[preL] == vin[i]) break;
        }
        //递归子树
        int numLeft = i - inL;
        root->left = buildTree(pre, vin, preL + 1, preL + numLeft, inL, i - 1);
        root->right = buildTree(pre, vin, preL + numLeft + 1, preR, i + 1, inR);
        return root;
    }
};

剑指offer JZ3

刷题 / 链表

JZ3

原题链接

题目

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

核心

链表翻转，可提出可直接模拟

思路

提出法（包括栈模拟，数组翻转，反向迭代器）

数据提出来扔 vector 里，在输出即可，不是真正的翻转链表，仅数据反向输出

$T:O(n)$

$S:O(n)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
*  struct ListNode {
*        int val;
*        struct ListNode *next;
*        ListNode(int x) :
*              val(x), next(NULL) {
*        }
*  };
*/
class Solution {
public:
    vector<int> printListFromTailToHead(ListNode *head) {
        vector<int> list;
        while (head != nullptr) {
            list.push_back(head->val);
            head = head->next;
        }
        reverse(list.begin(), list.end());
        return list;
    }
};

模拟法

真实模拟链的变换，若题目需要输出 list 而非 vector 则此方法为好方法

剑指offer JZ2

刷题 / 字符串

JZ2

原题链接

题目

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

核心

字符串替换，STL 简单处理

思路

stl string.replace()

$T:O(n)$

$S:O(1)$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    string replaceSpace(string s) {
       for(int i=0;i<s.size();i++){
           if(s[i]==' ') s.replace(i,1,"%20");
       }
        return s;
    }
};
  • Copyrights © 2020-2023 Jack Kong
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信