Ruixiang's blog

OPPO

什么是快慢指针？

快慢指针是遍历操作时的一种技巧，通常是由一个快指针和一个慢指针组成，一般应用在链表操作上。以下示例是快指针走两步，慢指针走一步：

1
2
3
4
5

fast, slow = head # head是链表的头节点（单链表且无环）
while fast and fast.next:
    fast = fast.next.next
    slow = slow.next
#循环终止时slow指针指向链表的中间节点

Introduction

Quick select is a transformation of quicksort, we can use it to find the $k-th$ element in a list if it exists. The average time complexity of this algorithm is $O(n)$. We all know that the average time complexity of quick sort is $O(nlogn)$.

This kind of problem can also be solved by using Max_heap or Min_heap, the time complexity is $O(nlogk)$.

Docker 简介

Docker 是一个开源，轻量级的应用容器引擎，基于GO语言开发，用于创建、管理和编排容器。Docker 可以让开发者打包他们的应用以及依赖包到一个轻量级、可移植的容器中，然后发布到任何流行的 Linux 机器上，也可以实现虚拟化。Docker 属于 Linux 容器的一种封装，提供简单易用的容器使用接口。它是目前最流行的 Linux 容器解决方案。Docker 将应用程序与该程序的依赖，打包在一个文件里面。运行这个文件，就会生成一个虚拟容器。程序在这个虚拟容器里运行，就好像在真实的物理机上运行一样。有了 Docker，就不用担心环境问题。Docker 的接口相当简单，用户可以方便地创建和使用容器，把自己的应用放入容器。容器还可以进行版本管理、复制、分享、修改，就像管理普通的代码一样。

资料链接：leetcode 文章讲解

视频链接：huahua 视频讲解

主串（在主串中寻找匹配串），匹配串（需要被匹配的串）

KMP 算法主要目的是将字符串匹配控制在线性时间复杂度 $O(m+n)$ 内， 如果采用暴力算法的话时间复杂度为$O((m-n)*n)$ , 其中 $m$ 为主串的长度，$n$ 为匹配串的长度。

主要思想：善于利用匹配串中的信息，避免重复判断和主串上匹配指针回退。

比如匹配串为 ABCABE, 当我们再匹配的过程中在 E 这个位置上出现不匹配，而之前的 ABCAB 都已经匹配成功。如果是暴力算法的我们需要先回退主串中的匹配指针到开始位置（即第一个 A 出现的位置），并且在其下一个位置处再从头对 ABCABE 进行匹配。但是很显然我们并不需要回退匹配指针和从 ABCABE 的头部开始匹配，我们只需要在主串的当前位置处对 CABE 再进行匹配即可，这样就利用了匹配串里面的信息，避免了重复操作。KMP 算法就是利用匹配串的这一特性，而且 KMP 最大的一个特点就是主串上的匹配指针从来不走回头路。

赛题地址：

零基础入门数据挖掘 - 贷款违约预测

Pipeline:

对于这种csv表格式数据有一套固定的流程， 多用传统机器学习方法搭建模型。

Problem:

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

1
2
3
4
5
6

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

问题：

实现函数double Power(double base, int exponent)，求base的exponent次方。不得使用库函数，同时不需要考虑大数问题。

示例 1:

输入: 2.00000, 10
输出: 1024.00000
示例 2:

输入: 2.10000, 3
输出: 9.26100
示例 3:

输入: 2.00000, -2
输出: 0.25000
解释: 2-2= 1/22 = 1/4 = 0.25

解决方法：

这道题需要使用快速幂求解，时间复杂度为 O($\log_2(n)$) 。

如果我们按照常规思路，令$x = x * x$，重复 $n$ 次， 时间复杂度为 O($n$)， 会超时。

Problem:

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once.

Find all the elements that appear twice in this array.

Could you do it without extra space and in O(n) runtime?

Example:

1
2
3
4
5

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Solutions:

This is a very confusing question, since we must solve it in O(n) runtime without extra space. Obviously, the easiest way is to use hash set, which needs extra space. Here we will construct two different tricky hash functions within the original array, which will simulate the process of hash set.

Problem:

Implement a trie with insert, search, and startsWith methods.

Example:

1
2
3
4
5
6
7
8

Trie trie = new Trie();

trie.insert("apple");
trie.search("apple");   // returns true
trie.search("app");     // returns false
trie.startsWith("app"); // returns true
trie.insert("app");   
trie.search("app");     // returns true

Methods & Solutions: