剑指offer算法题(21-40)

把奇数放在偶数的前面-21

问题

输入：一个数组，乱序，有奇数和偶数

输出：把所有的奇数放在前面，所有的偶数放在后面

暴力思路

从头到尾遍历数组
遇到奇数，访问下一个
遇到偶数，把它后面的数字都向前挪动以为，该偶数放到末尾

冒泡思路

for (int i = n-1; i > 0; i--) 依次放置好后面n-1个数即可
从for (int j = 0; j < i; j++) ，遇到j-1是偶数，j是奇数，则交换

辅助数组

新数组存偶数，原数组删除偶数，最后把新数组的偶数追加到原数组
遍历原数组，遇到偶数，存到新数组，删除原数组中的偶数

双指针快排思路

类似于快速排序的思路，但不是稳定的。

指针1，在前面，向后移动，前面应是奇数
指针2，在后面，向前移动，后面应是偶数
指针1指偶数，指针2指奇数，交换两个数
直到指针相遇

关键代码

c++

/*
 * 对数组进行重新排序，把奇数放在前面，偶数在后面
 * Args:
 *      a -- 数组
 *      f -- 函数指针，什么样的条件放在后面，如是偶数、是正数，解耦
 */
void reorder_array(vector<int> & a, bool (*f)(int)) {
    int l = 0;
    int r = a.size() - 1;
    while (l < r) {
        // 从左到右找到第一个偶数
        while (l < r && !f(a[l])) {
            l++;
        }
        // 从右到左，找到第一个奇数
        while (r > l && f(a[r])) {
            r--;
        }
        // 交换
        if (l < r) {
            int t = a[l];
            a[l] = a[r];
            a[r] = t;
        }
    }
}

归并排序思路

归并排序稳定，也很快，所以使用归并排序。分成长度为1、2、4的序列，各自都排好，依次两两合并。

关键代码

c++

class Solution {
public:
  	/* 
  	 * 奇偶性
  	 */
    int get_parity(int n) {
        return (n & 1) == 1;
    }

    /*
     * a中前后有两个序列，分别有序，对其进行merge
     */
    void merge(vector<int> &a, int start, int mid, int end) {
        // 临时存储新的排序数据
        int *t = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        // 临时数组的索引
        int k = 0;
        while (i <= mid && j <= end) {
            // 奇偶性
            int pi = get_parity(a[i]);
            int pj = get_parity(a[j]);
            if (pi == 1 && pj == 0) {
                t[k++] = a[i++];
            } else if (pi == 0 && pj == 1){
                t[k++] = a[j++];
            } else if (pi == 1 && pj == 1) {
                t[k++] = a[i++];
            } else if (pi == 0 && pj == 0) {
                t[k++] = a[i++];
            }
        }
        while (i <= mid) {
            t[k++] = a[i++];
        }
        while (j <= end) {
            t[k++] = a[j++];
        }
        for (i = 0; i < end - start + 1; i++) {
            a[start + i] = t[i];
        }
        delete [] t;
        return;
    }
    
    /*
     * 对a的长度为gap的子序列，两两合并
     * Args:
     *      a -- 数组
     *      gap -- 1个子序列的长度
     * Returns:
     *      None
     */
    void merge_groups(vector<int> &a, int gap) {
        // 两组的长度
        int twolen = 2 * gap;
        int i;
        // 对相邻的两个gap进行合并
        for (i = 0; i + twolen - 1 < a.size(); i += twolen) {
            int start = i;
            int mid = start + gap - 1;
            int end = i + twolen - 1;
            merge(a, start, mid, end);
        }
        // 若最后一次不足两个gap，即1个gap和部分gap
        if (i + gap - 1 < a.size() - 1) {
            merge(a, i, i + gap - 1, a.size() - 1);
        }
    }

    void reOrderArray(vector<int> &a) {
    	// 分割为长度为i的子序列，两两进行合并
        for (int i = 1; i < a.size(); i *= 2) {
            merge_groups(a, i);
        }
    }  
};

链表中倒数第k个节点-22

不知道链表长度，要求在 $O (n)$ 内找到倒数第k个节点，注意代码的鲁棒性。

双指针思路

两个指针，l先走k-1步，r再从头节点出发，始终保持距离为k-1。 r走到末尾时，l就是倒数第k个节点。

注意头结点为空和k非法(为0、k超出等)的情况。

双指针求链表中间节点

两个指针，l走一步，r走两步。r走到末尾的时候，l正好走到中间。

双指针总结

当一个指针遍历链表不能解决问题的时候，就使用两个指针。

同时走、一个速度快
一个先走、速度一样

关键代码

c++

/*
 * 返回链表中的倒数第k个节点
 * 双指针思路，注意代码的鲁棒性
 * Args:
 *      phead -- 头指针
 *      k  -- 无符号整数
 * Returns:
 *      nullptr or 第k个节点
 */
ListNode* kth_from_end(ListNode* phead, unsigned int k) {
    // 1. phead为空或者k不合法，都返回空，k不能为0，否则k-1是一个巨大的数
    if (phead == nullptr || k == 0) {
        return nullptr;
    }

    // 2. 双指针
    ListNode* pr = phead;
    ListNode* pl = phead;
    unsigned int count = 1;

    // 3. pl先走
    while (pl && count <= k - 1) {
        pl = pl->next;
        count++;
    }
    
    // 4. 不足k个节点，返回空
    if (pl == nullptr) {
        return nullptr;
    }

    // 5. 左右指针一起走，保持k-1的距离
    while (pl->next) {
        pl = pl->next;
        pr = pr->next;
    }

    return pr;
}

链表中环的入口节点-23

如果一个链表有环，则返回这个环的入口节点

双指针法

确定有环

双指针，同时走，l一次1步，r一次2步。

r走到末尾，则无环
r与l相遇，则有环。相遇节点在环内

确定环内节点数量

相遇节点在环内，从相遇节点开始遍历一圈，计数。再次回到相遇节点，就能知道环内节点数量k。

找到环的入口节点

双指针，r先走k步，l再走。l与r相遇时，就是环的入口节点

关键代码

c++

/*
 * 双指针判断链表是否有环时，返回两个指针相遇的节点
 * Args:
 *      phead -- 头节点
 * Returns:
 *      pmeet -- nullptr or 相遇的节点
 */
ListNode* meet_node(ListNode* phead) {
    // 空节点 or 1个节点，无法成环
    if (phead == nullptr || phead->next == nullptr) {
        return nullptr;
    }
    // 两个指针，l一次走一步，r一次走两步
    ListNode* pl = phead;
    ListNode* pr = phead->next->next;
    ListNode* pmeet = nullptr;
    while (pl && pr) {
        if (pl == pr) {
            pmeet = pl;
            break;
        }
        pl = pl->next;
        pr = pr->next;
        // pr走第二步的时候，先判断一下
        if (pr) {
            pr = pr->next;
        }
    }
    return pmeet;
}


/*
 * 获取链表中环内节点的数量，已经确保有环
 * Args:
 *      pmeet -- 链表中环内的一个节点
 * Returns:
 *      count -- 环内的节点的数量
 */
int get_circle_node_count(ListNode* pmeet) {
    if (pmeet == nullptr || pmeet->next == nullptr) {
        return 0;
    }
    ListNode* p = pmeet->next;
    int count = 1;
    while (p != pmeet) {
        p = p->next;
        count++;
    }
    return count;
}


/*
 * 双指针法获得链表中环的入口节点
 * Args:
 *      phead -- 头节点
 * Returns:
 *      pentry -- nullptr 或者 环的入口节点
 */
ListNode* circle_entry_node(ListNode* phead) {
    ListNode* pmeet = meet_node(phead);
    // 无环
    if (pmeet == nullptr) {
        return nullptr;
    }
    
    // 后面的操作已经确保有环

    // 环内节点的数量
    int k = get_circle_node_count(pmeet);
    // pl先走k步
    ListNode* pl = phead;
    ListNode* pr = phead;
    for (int i = 1; i <= k; i++) {
        pr = pr->next;
    }
    // 同时走，直到相遇在入口节点
    ListNode* pentry =  nullptr;
    while (pl && pr) {
        if (pl == pr) {
            pentry = pl;
            break;
        }
        pl = pl->next;
        pr = pr->next;
    }
    return pentry;
}

推导法和断链法

leetcode推导法

翻转链表-24

Reverse Linked List

思路

每次遍历保存三个节点：pre, pnow, pnext ，遍历到pnow

保存pnow的next
pnow指向pre
pre = pnow
把pnext赋值给pnow，下一次循环

注意当pnext为空时，已走到末尾，此时的pnow应该是新的head。

c++

ListNode* reverseList(ListNode* head) {
	ListNode* pre = nullptr;
    ListNode* pnow = head;
  	ListNode* pnext = nullptr;
  	while (pnow) {
    	// 保存pnow的next
      	pnext = pnow->next;
      	pnow->next = pre;
      	// 新的头节点
      	if (pnext == nullptr) {
          	head = pnow;
        }
      	// pnow作为新的pre
      	pre = pnow;
      	// pnext作为下一轮遍历的pnow
      	pnow = pnext;
    }
  	return head;
}

合并两个有序链表-25

见这里

树的子结构-26

Subtree of Another Tree

两棵树s和t，判断t是否是s的一个子结构

思路

层次遍历s的每个节点p
判断p是否和t完全相同

判断两颗树相同

两个都为空，相同
其中一个为空，不同
值不同，不同
则 return 左子树相同 && 右子树相同

关键代码

c++

/*
 * 判断两颗树是否相等
 */
bool is_same(TreeNode* p1, TreeNode* p2) {
    if (p1 == nullptr && p2 == nullptr) {
        return true;
    }
    if (p1 == nullptr || p2 == nullptr) {
        return false;
    }
    if (p1->val != p2->val) {
        return false;
    }
    return is_same(p1->left, p2->left) && is_same(p1->right, p2->right);
}


/*
 * 层次遍历以s的每个节点为根节点的子树是否和t相同
 */
bool isSubtree(TreeNode* s, TreeNode* t) {
    queue<TreeNode*> nodes;
    // 放根节点
    if (s != nullptr) {
        nodes.push(s);
    }
    while (!nodes.empty()) {
        // 访问根节点
        TreeNode* p = nodes.front();
        nodes.pop();
        if (is_same(p, t)) {
            return true;
        }
        // 向队列中追加左右孩子
        if (p->left) {
            nodes.push(p->left);
        }
        if (p->right) {
            nodes.push(p->right);
        }
    }
    return false;
}

二叉树的镜像-27

二叉树的镜像，就是左右孩子交换节点嘛。

思路

使用先序遍历的思想，这里是二叉树各种遍历

使用栈，根节点入栈
栈不为空，出栈一个元素p
交换其左右孩子节点
右孩子入栈，左孩子入栈

[关键代码]

c++

/*
 * 先序遍历求二叉树的镜像
 */
void mirror(TreeNode *head) {
    TreeNode* p = head;
    stack<TreeNode*> st;
    if (p != nullptr) {
        st.push(p);
    }
    // 栈不为空
    while (!st.empty()) {
        TreeNode* now = st.top();
        st.pop();
        // 交换其左右节点
        TreeNode* t = now->left;
        now->left = now->right;
        now->right = t;
        // 左右节点入栈
        if (now->right) {
            st.push(now->right);
        }
        if (now->left) {
            st.push(now->left);
        }
    }
}

对称的二叉树-28

leetcode对称的二叉树

判断一个二叉树是不是对称的

思路

普通的遍历都是先左后右，对称的话，得用先右后左。

一棵树对称，则先左后右的先序序列、先右后左的先序序列应该一样。即左右子树对称相等。

遍历的时候

根节点为空，对称
否则，看sym(root.left, root.right)
两个节点其中一个为空，则看p1 == p2
两个都不为空，则先看根节点的值
最后则交叉看左右子树，sym(p1.left, p2.right) && sym(p1.right, p2.left)

[关键代码]

c++

/*
 * 判断一棵树是否对称
 */
bool isSymmetric(TreeNode* root) {
    if (root == nullptr) {
        return true;
    }
    return symmetric_equal(root->left, root->right);
}


/*
 * 判断两棵树对称相等
 * Args:
 *      p1, p2 -- 一般是一棵树的左右子树
 * Returns:
 *      true or false
 */
bool symmetric_equal(TreeNode* p1, TreeNode* p2) {
    // 有空的
    if (p1 == nullptr || p2 == nullptr) {
        return p1 == p2;
    }   
    // 先看根节点的值
    if (p1->val != p2->val) {
        return false;
    }           
    // 看左右子树对称相等
    return symmetric_equal(p1->left, p2->right) && symmetric_equal(p1->right, p2->left);   
}

非递归代码

java

public boolean isSymmetric(TreeNode root) {
    if (root == null) return true;
    Stack<TreeNode> stack = new Stack<>();
    stack.push(root.left);
    stack.push(root.right);
    while (!stack.empty()) {
        TreeNode n1 = stack.pop(), n2 = stack.pop();
        if (n1 == null && n2 == null) continue;
        if (n1 == null || n2 == null || n1.val != n2.val) return false;
        stack.push(n1.left);
        stack.push(n2.right);
        stack.push(n1.right);
        stack.push(n2.left);
    }
    return true;
}

顺时针打印矩阵-29

牛客网打印矩阵

思路

用左上和右下的坐标定位出一圈要打印的数据。一圈打完以后，分别沿着对角线向中间靠拢一个单位。

关键代码

c++

vector<int> print_marix(vector<vector<int>> matrix) {
    vector<int> res;
    if (matrix.empty() || matrix[0].empty()) {
        return res;
    }

    int row = matrix.size();
    int col = matrix[0].size();

    // 通过左上、右下去锁定当前圈的元素
    int left = 0, top = 0, right = col - 1, bottom = row - 1;
    while (left <= right && top <= bottom) {
        // 左到右
        for (int i = left; i <= right; i++)
            res.push_back(matrix[top][i]);
        // 上到下
        for (int i = top + 1; i <= bottom; i++)
            res.push_back(matrix[i][right]);
        // 右到左，有多行时
        if (top != bottom)
        for (int i = right - 1; i >= left; i--)
            res.push_back(matrix[bottom][i]);
        // 下到上，有多列时
        if (left != right)
        for (int i = bottom - 1; i > top; i--)
            res.push_back(matrix[i][left]);
        // 左上角、右下角移动
        left++, top++, right--, bottom--;
    }
    return res;
}

包含min函数的栈-30

Min Stack

实现能够得到栈中最小元素的数据结构，要求入栈、出栈、获得最小元素都是O(1)

思考过程

定义一个变量，去存储最小元素，每次对其更新。可是，当最小元素出栈以后呢，怎么去得到新的最小元素呢？这样就需要把次最小元素也存储下来。就需要把每次最小的元素，按顺序存储下来，按照入栈的顺序

入栈时，入栈当前最小的元素
出栈时，把当前最小的元素也出栈，留下的是下一个状态的最小元素

思路

数据栈，正常存数据
最小栈，存放各个时刻的最小元素，栈顶一直是当前的最小元素
入栈：当前最小元素：min(min_st.top(), new) ，最小栈压入当前的最小元素
出栈：数据栈元素出栈，同时最小栈出掉当前的最小元素

[关键代码]

c++

class MinStack {
private:
    // 数据栈
    stack<int> st_data;
    // 存储每个状态最小元素的栈
    stack<int> st_min;

public:
    // 初始化数据结构
    MinStack() {

    }

    void push(int x) {
        st_data.push(x);
        // 当前的最小元素入栈
        if (st_min.empty() || x < st_min.top()) {
            st_min.push(x);
        } else {
            st_min.push(st_min.top());
        }
    }

    void pop() {
        if (st_data.empty() || st_min.empty()) {
            return;
        }
        // 当前数据栈和最小元素栈都出栈
        st_data.pop();
        st_min.pop();
    }

    int top() {
        return st_data.top();
    }

    int getMin() {
        return st_min.top();
    }
};

栈的压入和弹出序列-31

输入两个序列，第一个为栈的入栈序列，判断第二个是否为其出栈序列。入栈所有数字都不相等

思路

入栈序列，出栈序列。当前需要出栈元素为i

i在栈内，则直接出栈
i不在栈内，则把如栈序列 前面到i 的元素全部入栈，再重复1
入栈序列全都入栈了，依然没有i，则不是弹出序列

示例

入栈：1 2 3 4 5，出栈 4 5 3 2 1

4不在栈顶，前面元素入栈

操作	栈内元素	剩余出栈元素	剩余入栈元素
4不在栈顶，4入栈	1 2 3 4	4 , 5 3 2 1	5
4出栈	1 2 3	5 3 2 1	5
5不在栈顶，5入栈	1 2 3 5	5, 3 2 1	-
5出栈	1 2 3	3 2 1	-
3出栈	1 2	2 1	-
2出栈	1	1	-
1出栈	-	-	-

入栈：1 2 3 4 5，出栈 4 3 5 1 2

操作	栈内元素	剩余出栈元素	剩余入栈元素
4不在栈顶，4入栈	1 2 3 4	4 , 3 5 1 2	5
4出栈	1 2 3	3 5 1 2	5
3出栈	1 2	5 1 2	5
5出栈，不在栈顶，入栈	1 2 5	5, 1 2
5出栈	1 2	1 2
1出栈，不在栈顶，已经无可入元素，终止

[关键代码]

遍历每个出栈元素now
使其在栈顶，对如栈序列进行入栈，直到now
如果now依然不在栈顶，则不是
如果now在栈顶，则出栈
继续遍历下一个出栈now

c++

/*
 * 判断vpop是否是入栈序列vpush的出栈序列
 * Args:
 *      vpush -- 入栈序列
 *      vpop -- 要判断的出栈序列
 * Returns:
 *      true or false
 */
bool is_poporder(const vector<int>& vpush, const vector<int>& vpop) {
    bool res = false;
    stack<int> st;
    // 入栈的元素
    int k = 0;
    for (int i = 0; i < vpop.size(); i++) {
        // 当前要出栈的元素
        int now = vpop[i];

        // now不在栈顶，则从入栈序列中入栈
        if (st.empty() || st.top() != now) {
            while (k < vpush.size()) {
                st.push(vpush[k]);
                if (vpush[k] == now) {
                    k++;
                    break;
                }
                k++;
            }
        }

        // now依然不在栈顶
        if (st.empty() || now != st.top()) {
            res =false;
            break;
        }

        // now 在栈顶，出栈
        st.pop();
        if (i == vpop.size() - 1) {
            res = true;
        }
    }
    return res;
}

从上到下打印二叉树-32

leetcode层次遍历

有3个题

层次遍历序列

每次遍历一层

分行层次遍历打印

每次打印一层

z型遍历二叉树

见leetcode的z型遍历二叉树

二叉搜索树的后序遍历-33

给一个数组，判断是否是二叉搜索树的后序遍历

后序遍历：最后一个是根节点

BST：左 < 根 < 右

python

     8
  6    10
5  7  9  11

给一个数组：5 7 6 9 11 10 8

根节点是8，
5 7 6前面小于8的，是左子树，全部小于8
9 11 10中间大于8的，是右子树，全部大于8
再依次取判断左右子树是否是BST

思路

判断nums[start, end] 是否是BST的后序遍历序列
空返回false，一个元素返回true。
找到根节点root = nums[end]
从start开始，找左子树的最后一个元素i-1，直到end-1，每个元素都小于根节点
从i开始， 找右子树，直到end-1，每个元素都要大于根节点。
右子树时，前面左子树已经ok（有或者没有），所以后面的元素都是右子树的，都要大于根节点。
如果后面有小于根节点的，则不满足右子树，返回false
递归判断左右子树是否是BST，返回结果。

cpp

/*
 * 是否是BST的后序遍历序列
 * Args:
 *      nums: 要判断的目标序列，没有重复的数字
 *      start: 序列的起始值
 *      end: 序列的结束位置
 * Returns:
 *      true or false
 */
bool is_bst_postorder(const vector<int> &nums, int start, int end) {
    // 不合法
    if (nums.empty() || start < 0 || end > nums.size() - 1 || start > end) {
        return false;
    }
    // 只有一个元素
    if (start == end) {
        return true;
    }
    int root = nums[end];

    // 1. 找到左子树
    int i = start;
    for (; i <= end - 1; i++) {
        if (nums[i] > root) 
            break;
    }
    // 2. 找到右子树，全部都大于root
    int j = i;
    for (; j <= end - 1; j++) {
        // 右子树中有小于root的值，不合法
        if (nums[i] < root) {
            return false;
        }
    }
    // 3. 判断左右子树
    bool left = true;
    if (i > start) {
        // 判断右子树
        left = is_bst_postorder(nums, start, i - 1);
    }
    bool right = true;
    if (j > i) {
        // 判断左子树
        right = is_bst_postorder(nums, i, j - 1);
    }
    return left && right;
}

二叉树中的路径求和-34

参考leetcode中各种pathsum汇总

复杂链表的复制-35

链表：值，下一个节点，任意一个节点。复制这样的一个链表。

思路1 暴力解法

先把链表连接起来，不管任意指针
遍历链表，为每个新节点找到任意指针的节点，连接起来
同时知道旧节点N、新节点N1、旧节点的任意指针节点S
遍历新链表，找到任意指针S1
把N1和S1连接起来

时间复杂度 $O (n^{2})$ ，遍历新链表，找到任意指针S1的节点。

思路2 Hash解法

上面耗时间：找任意指针S1。用HashMap建立(N, N1)的配对，就能够 $O (1)$ 查找到S1。从而总时间为 $O (n)$

思路3 最优-新旧链表先连再断

连接新节点。把N1连接到N后面，a-a1-b-b1-c-c1
设置随机节点。设置N1的S1，实际上，a-s, a-a1，s-s1 ，所以能够找到a1-s1
新旧节点断开。把N和N1断开，得到a1-b1-c1

注意：设置随机节点时，随机节点可能为空。断链时，下一个节点可能为空。

[关键代码]

c++

RandomListNode* clone(RandomListNode* head) {
    if (head == nullptr) {
        return nullptr;
    }

    // 1. 新建节点，连接到原节点的后面
    RandomListNode* p = head;
    while (p) {
        RandomListNode* p1 = new RandomListNode(p->label);
        // 连接
        p1->next = p->next;
        p->next = p1;
        p = p1->next;
    }

    // 2. 为新节点设置随机节点
    p = head;
    while (p) {
        RandomListNode* p1 = p->next;
        RandomListNode* s = p->random;
        // 注意random可能为空
        if (s != nullptr) {
            p1->random = s->next;
        }
        p = p1->next;
    }

    // 3. 新旧节点断开
    p = head;
    RandomListNode* head1 = p->next;
    while (p) {
        // 新节点
        RandomListNode* p1 = p->next;
        // 原节点，连接到原下一个节点
        p->next = p1->next;
        // 新节点的下一个节点，可能下一个节点为空
        if (p->next) {
            p1->next = p->next->next;
        } else {
            p1->next = nullptr;
        }
        p = p->next;
    }
    return head1;
}

二叉搜索树转双向链表-36

给一个二叉搜索树，转化为一个排好序的双向链表。左孩子-前一个节点，右孩子-后一个节点。

牛客网二叉搜索树与双向链表，类似题型：有序链表转平衡BST

BST的中序遍历就是自动有序的。

递归思路

中序遍历，使用pre来记录链表中的最后一个元素。

遍历到根节点时，递归转换左子树
pre与root连接，pre.right=root, root.left=pre, pre=root 。注意pre为空时，pre=root
递归创建右子树

再从pre找到第一个节点。

[关键代码]

c++

/*
 * 把树转化为链表，递归版本
 * Args:
 *      root -- 树
 * Returns:
 *      转换后的链表的头结点
 */
TreeNode* convert(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }
    TreeNode* pre = nullptr;
    // 转换为链表，pre为最后一个节点
    convert_inorder(root, pre);
    // 从末尾找到第一个节点
    while (pre && pre->left) {
        pre = pre->left;
    }
    return pre;
}

/*
 * 递归转换
 * Args:
 *      root -- 当前节点
 *      pre -- 上一个节点，引用类型，改变值。
 * Returns:
 *      None
 */
void convert_inorder(TreeNode* root, TreeNode* &pre) {
    if (root == nullptr) {
        return;
    }
    // 左子树
    convert_inorder(root->left, pre);
    // 当前节点
    if (pre != nullptr) {
        root->left = pre;
        pre->right = root;
        pre = root;
    } else {
        pre = root;
    }
    // 右子树
    convert_inorder(root->right, pre);
}

非递归思路

中序遍历时，记录pre节点，每次进行修改即可，访问到p时，则连接到pre即可。

p不为空，p入栈，p=p.left， 扫描左孩子
p为空，p从栈顶获得，p=st.top()，显然p没有左孩子或者左孩子已经出栈遍历过，p访问出栈。此时，把p与pre连接即可，注意pre为空
扫描右孩子，p = p.right

最后从末尾，找到头结点

c++

TreeNode* convert_stack(TreeNode* root) {
    if (root == nullptr) {
        return nullptr;
    }

    stack<TreeNode*> st;
    TreeNode* p = root;
    // 上一个节点
    TreeNode* pre = nullptr;
    while (p || !st.empty()) {
        if (p) {
            // p入栈
            st.push(p);
            // 扫描左孩子
            p = p->left;
        } else {
            // p为空，出栈元素，p为根节点，左孩子已经访问结束或者没有左孩子
            p = st.top();
            st.pop();
            if (pre == nullptr) {
                pre = p;
            } else {
                pre->right = p;
                p->left = pre;
                pre = p;
            }
            // 扫描右孩子
            p = p->right;
        }
    }

    // 找到头结点
    while (pre && pre->left) {
        pre = pre->left;
    }
    return pre;
}

序列化和反序列化二叉树-37

leetcode序列化和反序列化二叉树笔记

数字全排列-38

leetcode数字全排列笔记

数组中出现次数超过一半的数-39

Leetcode笔记

最小的k个数-40

牛客最小的k个数

给一个数组，找到最小的k个数

思路1 快排思路

修改原数组。partition左边即可。O(n) 。快速排序。关键代码如下：

c++

/*
 * 通过快速排序来找到最小的k个数，改变原数组
 * Args:
 *      a -- 数组
 *      k -- 最小的k个数
 * Returns:
 *      res -- 最小的k个数
 */
vector<int> get_leastnums_by_partition(vector<int>& a, int k) {
    // 条件合法性判断
    if (a.empty() || k < 1 || k > a.size()) {
        return vector<int>();
    } 
    int l = 0, r = a.size() - 1;
    int i = partition(a, l, r);
    // 直到左边是最小的k个数，包含a[i]
    while (i + 1 != k) {
        if (i + 1 > k) {
            // 左边有超过k个数，左边继续划分
            r = i - 1;
        } else if (i + 1 < k) {
            // 左边不足k个，划分右边，加一些给左边
            l = i + 1;
        }
        i = partition(a, l, r);
    }
    // 把左边给到res中
    vector<int> res(k);
    std::copy(a.begin(), a.begin() + k, res.begin());
    return res;
}

/*
 * 快排的partition，左边小于，中间x，右边大于
 * Args:
 *      a -- 数组
 *      l -- 左边起始值
 *      r -- 右边结束值
 * Returns:
 *      a[l]的最终位置
 */
int partition(vector<int>& a, int l, int r) {
    int x = a[l];
    while (l < r) {
        // 从右向左，找到小于x的值，放到a[l]上
        while (l < r && a[r] >= x) {
            r--;
        }
        if (l < r) {
            a[l++] = a[r];
        }
        
        // 从左向右，找到大于x的值，放到a[r]上
        while (l < r && a[l] <= x) {
            l++;
        } 
        if (l < r) {
            a[r--] = a[l];
        }
    }
    a[l] = x;
    return l;
}

思路2 最大堆

不修改原数组，用最大堆找到最小的k个数。O(nlogk) 。自己的堆操作和stl堆操作。关键代码如下：

c++

/*
 * 通过最大堆来获得数组中最小的k个数
 */
vector<int> get_leastknums_by_heap(vector<int>& a, int k) {
    if (a.empty() || k <= 0 || k > a.size()) {
        return vector<int>();
    }

    // 选择前k个元素，初始化堆
    vector<int> res(k);
    std::copy(a.begin(), a.begin() + k, res.begin());
    std::make_heap(res.begin(), res.end());
    
    // 剩余元素入堆
    for (auto it = a.begin() + k; it != a.end(); it++) {
        auto n = *it;
        printf("n=%d, max=%d\n", n, res[0]);
        // 大于最大值，无需入堆
        if (n >= res[0]) {
            continue;
        }
        // n小于最大堆的最大值，入堆
        // 最大元素出堆，默认放到末尾
        std::pop_heap(res.begin(), res.end());
        // 新元素入堆
        res[k - 1] = n;
        std::push_heap(res.begin(), res.end());
    }
    return res;
}

数据流中的中位数-41

给一个数据流，找到数组排序之后的中间的数值。奇数，中间；偶数，中间两个数的平均值。

牛客网数据流中的中位数

数据结构	插入时间	获取中位数时间	方法备注
未排序数组	O(1)	O(n)	快排partition方法
排序数组	O(n)	O(1)
排序链表	O(n)	O(1)	两个指针指向中间节点
二叉搜索树	平均O(logn)，最差O(n)	平均O(logn)，最差O(n)
AVL树	O(logn)	O(1)
最大堆和最小堆	O(logn)	O(1)

堆思路

两个容器（最大堆和最小堆），数据量平均分配，左边全部小于右边，左右两边无需排好序，根据左边最大的，右边最小的 来找到中位数。

总体思路

左边小，右边大。左边最大堆max，右边最小堆min。
先放右边，后方左边。
奇数：右边min[0]；偶数：求平均(max[0] + min[0]) / 2

插入右边

索引为偶数时，放右边。从0开始
num较大，直接插入右边min堆
num较小，插入左边max堆，再把max插入右边min堆。num < 左边max[0]

插入左边

索引为奇数时，放左边min堆。
num较小，直接插入左边min堆
num较大，插入右边min堆，再把min插入右边max堆。num > 右边min[0]

Githubd代码

c++

class Solution {
private:
    // 位于左边的最大堆
    vector<int> max;
    // 位于右边的最小堆
    vector<int> min;

public:
    /*
     * 序号是偶数时，写入右边的最小堆
     */
    void insert2min(int num) {
        // num较小，写到左边的最大堆
        if (max.size() > 0 && num < max[0]) {
            max.push_back(num);
            // num入堆
            std::push_heap(max.begin(), max.end(), less<int>());
            // max出堆
            std::pop_heap(max.begin(), max.end(), less<int>());
            num = max.back();
            max.pop_back();
        }

        // num写入最小堆
        min.push_back(num);
        std::push_heap(min.begin(), min.end(), greater<int>());
    }

    /*
     * 序号是奇数时，写入左边的最大堆
     */
    void insert2max(int num) {
        // num较大，先写到右边的最小堆
        if (min.size() > 0 && num > min[0]) {
            min.push_back(num);
            // num 入最小堆
            std::push_heap(min.begin(), min.end(), greater<int>());
            // min 出堆
            std::pop_heap(min.begin(), min.end(), greater<int>());
            num = min.back();
            min.pop_back();
        }
        // num写入最大堆
        max.push_back(num);
        std::push_heap(max.begin(), max.end(), less<int>());
    }
    
    /*
     * 写入一个元素，先右后左，右边比左边多一个或相等
     */
    void Insert(int num) {
        int idx = max.size() + min.size();
        // 奇数，写入左边的最大堆
        if ((idx & 1) == 1) {
            insert2max(num);
        } else {
            insert2min(num);
        } 
    }
	
  	/*
  	 * 获取中间元素，奇数在右边min[0]，偶数求平均
  	 */
    double GetMedian() { 
        int size = min.size() + max.size();
        if (size == 0) {
            return -1;
        } else if (size & 1) {
            return min[0];
        } else {
            return (min[0] + max[0]) / 2.0;
        }
    }
};

连续子数组的最大和-42

给一个数组，有正数有负数。求所有连续子数组和的最大值。O(n)

牛客网连续子数组的最大和，github代码

思路1 累加切换思路

当前累加和，最大累加和。遍历遇到数n

如果cursum <= 0，则cursum = n，否则 cursum += n
如果cursum > bestsum，则bestsum = cursum

c++

int maxsum_subarray(const vector<int>& a) {
    if (a.empty()) {
        return 0;
    }
    
    int cursum = a[0];
    int bestsum = a[0];

    for (int i = 1; i < a.size(); i++) {
        if (cursum <= 0) {
            cursum = a[i];
        } else {
            cursum += a[i];
        }

        if (cursum > bestsum) {
            bestsum = cursum;
        }
    }
    return bestsum;
}

思路2 动态规划

设f[i]表示以 $a_{i}$ 结尾的子数组的最大和，我们要求max[fi]

f (i) = {\begin{cases} a_{i}, & f (i - 1) \leq 0 o r i = 0 \\ f (i - 1) + a_{i}, & f (i - 1) > 0 a n d i \neq 0 \end{cases}

c++

int maxsum_subarray_dp(const vector<int>& a) {
    if (a.empty()) {
        return 0;
    }
    // p[i]=k，以i结尾的所有连续子数组中的最大值为k
    vector<int> p(a.size(), 0);
    for (int i = 0; i < a.size(); i++) {
        if (i == 0 || p[i-1] <= 0) {
            p[i] = a[i];
        } else if (p[i-1] > 0) {
            p[i] = p[i-1] + a[i];
        }
    }
    return *std::max_element(p.begin(), p.end());
}

1-n整数中1出现的次数-43

输入一个n，求问1-n数字中，1出现的总个数。

牛客网1-n整数中1出现的次数，github源码

思路1 暴力无offer思路

用个count计数，遍历所有的数字，求每一个数字的1的个数，再求和。O(nlogn)

c++

/*
 * 求余计算数字n中1的个数
 */
int numberof1(unsigned int n) {
    int count = 0;
    while (n) {
        if (n % 10 == 1) {
            count++;
        }
        n = n / 10;
    }
    return count;
}

思路2 分治递归思路

例子，找到1-21345中1的个数。分为两段：1346-21345（当前解），1-1345 （递归解）

思路总结

21345，先求位数5和最高位2，
1346-21345，计算最高位为1的数量h1。 h >= 2时， $10^{4}$ 。 h==1时，做减法。
1346-21345，计算其余位为1的数量o1。选1位为1，剩余位0-9任选，排列组合。 $4 \cdot 10^{3} \cdot 2$
递归计算1-1345中1的个数r1
返回h1+o1+r1

c++

/*
 * 递归计算从1-n中1的个数
 */
int numberof1_between1andn(int n) {
    if (n <= 9) {
        return n >= 1 ? 1 : 0;
    }
    // 以21345为例，分为1346-21345(本次求解)和1-1345(递归求解)两段

    // 1. 计算位数和最高位
    string ns = std::to_string(n);
    int len = ns.size();
    int h = ns[0] - '0';

    // 2. 计算最高位为1的数量
    int h1 = 0;
    if (h >= 2) {
        h1 = std::pow(10, len-1);
    } else {
        h1 = n - pow(10, len-1) + 1;
    }

    // 3. 计算其他位为1的个数，选1位为1，其余位0-9任选
    int o1 = h * (len-1) * pow(10, len-2);

    // 4. 递归求1-1346中1的位数
    int p = h * pow(10, len-1);
    int r = n - h * pow(10, len-1);
    int r1 = numberof1_between1andn(r);
    return h1 + o1 + r1;
}

数字序列中某一位的数字-44

数字序列：01234567891011121314.... 给位数，返回该位置上的数字。

例子，第1001位

1位数，10个，不在此，找后面的1001-10=991位
2位数，180个，不在此，找后面的991-180=881位
3位数，2700个，在此。881/3=270，881%3=1。即，从100开始的第270个数中的第2位。即370中的第2位7

github代码

注意每次递减index时，减的是位数*总数量，即index -= numcount * digits

在某个d位数中时，先算出d位数，再算出在d位数字内的res_index，反正是除法求余。

c++

/*
 * 数字流012345...某一位的数字
 * Args:
 *      index -- 数字序列中索引，从0开始
 * Returns:
 *      res -- 某一位的数字 
 */
int digit_in_sequence(int index) {
    if (index < 0) {
        return -1;
    }
    int res = 0;
    // 位数
    int digits = 1;

    while (true) {
        // d位数的总数量
        int numcount = count_num(digits);
        if (index <= numcount * digits - 1) {
            // index在某个d位数中
            // d位数的某个数的index
            int num_index = index / digits;
            // 数字内的某位数
            int res_index = index % digits;
            // 目标d位数
            int num = num_in_digits(num_index, digits);
            res = to_string(num)[res_index] - '0';
            break;
        } else {
            // index在某个d+1位数中
            index -= digits * numcount;
            digits++;
        }
    }
    return res;
}

/*
 * 获得几位数的所有数字数量
 * Args:
 *      digits -- 位数
 * Returns:
 *      count -- 该位数所有数字的数量
 */
int count_num(int digits) {
    if (digits <= 0) {
        return -1;
    }
    if (digits == 1) {
        return 10;
    }
    // 加0.5是这个版本的编译器pow的问题
    int count = (int) (std::pow(10, digits - 1) + 0.5);
    return 9 * count;
}

/*
 * 第1个d位数 
 */
int first_d_num(int digits) {
    if (digits == 1) {
        return 0;
    }
    return (int) (pow(10, digits - 1) + 0.5);
}

/**
 * d位数中的第index个数
 * Args:
 *      index -- 从0开始
 * Returns:
 *      num -- d位数中的第index个数字 
 */
int num_in_digits(int index, int digits) {
    int first = first_d_num(digits);
    return first + index;
}

把数组排成最小的数-45

给一个正整数数组，把它们拼接起来，求得一个最小的数字。

牛客网排成最小的数

1 全排列思路

实际上可以获得所有的排列方法，然后选择最小的。但是这样会比较慢。一共n!个排列组合。参考全排列。

2 排序思路

因为实际上最终是，按照一个规则把所有数字排列起来。

把所有数字转换成字符串
定义一个compare方法，判断哪个数字应该排列在前面。字符串本身的比较即可。
对所有数字排序，使用sort(nums.begin(), nums.end(), cmp)
按照排好序的数字来拼接到一个字符串

注意：隐藏的大数问题。用字符串来保存。

github源代码

c++

/*
 * 把数组排列成最小的数
 */
string array2minnum(const vector<int> &a) {
    vector<string> nums;
    for (auto n: a) {
        nums.push_back(to_string(n));
    }
    sort(nums.begin(), nums.end(), cmp);
    ostringstream res;
    for (auto s:nums) {
        res << s;
    }
    return res.str(); 
}

/*
 * 用于从小到大排序的比较函数。n1<n2，返回true
 * 小于的意义：谁小谁在前。
 * Args:
 *      n1, n2 -- 两个数字，由字符串表示
 * Returns:
 *      true or false
 */
bool cmp(const string& n1, const string& n2) {
    string n1n2 = n1 + n2;
    string n2n1 = n2 + n1;
    if (n1n2 < n2n1) {
        // n1 < n2，n1应该在前面
        return true;
    } else {
        return false;
    }
}

把数字翻译成字符串-46

基本规则：0-a, 1-b, 2-c, ... , 25-z。一个数字(可能是多位数)有多种翻译的可能。给一个数字字符串，求出有多少种翻译方法。比如12258有5种翻译方法。bccfi,bwfi,bczi,mcfi,mzi

1 递归计算

1 - 2258, 12 - 258 。第一个数字有2种翻译方法，再递归地去翻译剩下的部分。

由于存在重复的子问题，所以递归不好。从上到下计算也不好。我们要用从最小的子问题自下而上解决问题

从上到下思考，自下而上循环计算。

设c[i] 是a[i]开始到末尾的所有翻译种类的数量。

每个a[i]都能单独翻译，c[i] = c[i+1]
如果a[i]a[i+1]可以一起翻译，则c[i] += c[i+2]

f (i) = {\begin{cases} f (i + 1) + f (i + 2), & a_{i} a_{i + 1} 可以一起翻译 \\ f (i + 1), & a_{i} 只能单独翻译 \end{cases}

github代码

c++

/*
 * 把数字翻译成字母，找到有多少种翻译方法
 */
int get_trans_count(int number) {
    string num = to_string(number);
    if (number < 0 || num.empty()) {
        return 0;
    }
    if (num.length() == 1) {
        return 1;
    }
    // c[i]=k，i~n的翻译法有k种
    vector<int> c(num.size());

    for (int i = c.size() - 1; i >= 0; i--) {
        // 0. 计算a[i]能否和a[i+1]一起翻译
        bool flag = false;
        if (i+1 < c.size()) {
            int now = num[i] - '0';
            int back = num[i+1] - '0';
            int sum = now * 10 + back;
            if (sum >= 10 && sum <= 25) {
                // a[i]与a[i+1]一起翻译
                flag = true;
            }
        }

        // 1. 每个a[i]都可以单独翻译
        if (i == c.size() - 1) {
            c[i] = 1;
        } else {
            c[i] = c[i+1];
        }

        // 2. a[i]a[i+1]一起翻译，则与c[i+2]有关
        if (flag == true) {
           if (i+2 < c.size()) {
               c[i] += c[i+2];
           } else {
               c[i] += 1;
           }
        }

    }

    // 返回0-n的翻译数量
    return c[0];
}

礼物的最大价值-47

m*n的棋盘，每个格子上有一个礼物，每个礼物都有一个价值。从左上角开始走到右下角。每次只能向下-向右走。走一个格子，拿一个礼物。问，最大能拿多大的价值。

设v[i,j]是格子ij上的价值，设m[i,j] 是到达ij后的总路线最大价值。只能从上面或左边到达。

m [i, j] = max (m [i - 1, j], m [i, j - 1]) + v [i, j]

一行一行、一列一列的计算。初始化left和up为0，如果有，则赋值。计算m[i,j] = max(left, up)+v[i,j]

github源码

c++

/*
 * 给一个礼物价值矩阵，找到最大价值 
 * Args:
 *      v -- 各个位置上的礼物矩阵
 * Returns:
 *      res -- (0,0)-(m,n)的最大礼物价值
 */
int max_gifts_value(const vector<vector<int>> &v) {
    if (v.empty() || v[0].empty()) {
        return 0;
    }
    vector<vector<int>> m;
    int row = v.size();
    int col = v[0].size();

    // 初始化为0
    for (int i = 0; i < row; i++) {
        vector<int> cur_row(col, 0);
        m.push_back(cur_row);
    }

    // 一行一行地计算
    for (int i = 0; i < row; i++) {
        // 一列一列地算
        for (int j = 0; j < col; j++) {
            // 从上边和左边来的
            int up = 0;
            int left = 0;
            if (i > 0) {
                up = m[i-1][j];
            }
            if (j > 0) {
                left = m[i][j-1];
            }
            // 选大的+v
            m[i][j] = std::max(up, left) + v[i][j];
        }
    }
    return m[row-1][col-1];
}

最长不重复的子字符串-48

给一个字符串，找到里面最长子字符串的长度。

leetcode最长子字符串笔记

第n个丑数-49

leetcode丑数笔记

第一个只出现一次的字符-50

找到字符串中，第一个只出现一次的字符

用空间换时间，HashMap，统计出现次数；再遍历字符串，找出现次数为1的字符。

c++

/*
 * 字符串中出现次数为1的字符
 */
char first_char(const string& s) {
    if (s.empty()) {
        return '\0';
    }
    // 每个字符的出现次数
    map<char, int> c;
    // 计算
    for (auto ch:s) {
        if (c.count(ch) == 0) {
            c[ch] = 1;
        } else {
            c[ch] += 1;
        }
    }

    // 遍历找
    for (auto ch : s) {
        if (c[ch] == 1) {
            return ch;
        }
    }
    return '\0';
}

字符流中出现的第一个不重复字符

c++

class Solution{
private:
    // char出现次数
    map<char, int>m;
    // 保留字符串
    string s;
public:
    /*
     * 写入一个字符
     */
    void insert(char ch) {
        s += ch;
        if (m.count(ch) == 0) {
            m[ch] = 1;
        } else {
            m[ch] += 1;
        }
    }
    /*
     * 找到第一个出现一次的字符
     */
    char first_char() {
        char ch = '#';
        for (auto c:s) {
            if (m[c] == 1) {
                ch = c;
                break;
            }
        }
        return ch;
    }
};

剑指offer3(21-40)

把奇数放在偶数的前面-21 ​

链表中倒数第k个节点-22 ​

链表中环的入口节点-23 ​

双指针法 ​

推导法和断链法 ​

翻转链表-24 ​

合并两个有序链表-25 ​

树的子结构-26 ​

二叉树的镜像-27 ​

对称的二叉树-28 ​

顺时针打印矩阵-29 ​

包含min函数的栈-30 ​

栈的压入和弹出序列-31 ​

从上到下打印二叉树-32 ​

二叉搜索树的后序遍历-33 ​

二叉树中的路径求和-34 ​

复杂链表的复制-35 ​

二叉搜索树转双向链表-36 ​

序列化和反序列化二叉树-37 ​

数字全排列-38 ​

数组中出现次数超过一半的数-39 ​

最小的k个数-40 ​

数据流中的中位数-41 ​

连续子数组的最大和-42 ​

1-n整数中1出现的次数-43 ​

数字序列中某一位的数字-44 ​

把数组排成最小的数-45 ​

把数字翻译成字符串-46 ​

礼物的最大价值-47 ​

最长不重复的子字符串-48 ​

第n个丑数-49 ​

第一个只出现一次的字符-50 ​

把奇数放在偶数的前面-21

链表中倒数第k个节点-22

链表中环的入口节点-23

双指针法

推导法和断链法

翻转链表-24

合并两个有序链表-25

树的子结构-26

二叉树的镜像-27

对称的二叉树-28

顺时针打印矩阵-29

包含min函数的栈-30

栈的压入和弹出序列-31

从上到下打印二叉树-32

二叉搜索树的后序遍历-33

二叉树中的路径求和-34

复杂链表的复制-35

二叉搜索树转双向链表-36

序列化和反序列化二叉树-37

数字全排列-38

数组中出现次数超过一半的数-39

最小的k个数-40

数据流中的中位数-41

连续子数组的最大和-42

1-n整数中1出现的次数-43

数字序列中某一位的数字-44

把数组排成最小的数-45

把数字翻译成字符串-46

礼物的最大价值-47

最长不重复的子字符串-48

第n个丑数-49

第一个只出现一次的字符-50