Futu summary

Summary

算法题

二分查找变种题

Example:
[1 , 2 , 4 , 7 ]

8 返回-1
2 返回下标1
4返回下标2
0 返回-1
3返回比他小的最近的那个的下标 1

//指针移动的方法来缩小范围
function binarySearch($arr, $n, $target)
{
    $l = 0;
    $r = $n - 1; //变量实际意义 [l....r]里找target , 要明确变量的定义
    //二分查找的递归终止条件应该是没有范围可以查找 , 这里我看到的一点是递归和递归终止条件的数据的类型一般不一样
    //循环不变量是什么 , l r一直在变, 但是循环不变量不会变 , //变量实际意义 [l....r]里找target , 这个就是循环不变量
    while ($l <= $r) //区间[l..r] 依然是有效的 , 是个只有一个元素的数组
    {
        $mid = (int)(($l + $r) / 2);
        if ($arr[$mid] == $target) {
            return $mid;
        }
        //返回比他小的最近的那个的下标
        if ($target > $arr[$mid] && $target < $arr[$mid+1]) {
            return $mid;
        }
        if ($target > $arr[$mid]) {
            $l = $mid + 1;
        } else {
            $r = $mid - 1;
        }
    }
    //指针偏移出界,跳出循环,找不到
    return -1;
}

多维数组转字符串拼接

另一道类似题:一维数组转树状结构(嵌套数组)

a=1&b=2
key小写升序
如二维的 $[a][b] 则a.b=5
分号隔开 a=1&b=2;a.b=5……………

//广度优先搜索 , 使用队列 , 类似树的层序遍历
function convertToStr($arr)
{
    $str = '';
    $queue[] =$arr ;
    while (!empty($queue)) {
        $a = array_shift($queue);
        foreach ($a as $k=>$v) {
            if (is_array($v)) {
                array_push($queue, $v);
                $str .= $k;
            } else {
                $str.=$k.$v;
            }
        }
        var_dump($queue);
    }

    return $str;
}

计算用户交易费用

Example:
梯度表
1-5笔 15元
6-10笔 5元
假设用户交易笔数 6笔 , 则15 + 5 = 20元

除了遍历字典外 , 还可以用哈希表空间换时间 O(1)时间 O(n)空间

function getTradeFee(int $tradeCount):int 
{
    if ($tradeCount < 1) {
        throw new InvalidArgumentException('trade count must large than 0');
    }

    $fee = 0;
    $map = [
        ['min'=>1,'max'=>5, 'trade_fee' => 15],
        ['min'=>6,'max'=>10, 'trade_fee' => 5],
    ];

    foreach ($map as $item) {
        if ($tradeCount > $item['max']) {
            $fee += $item['trade_fee'];
            $tradeCount -= $item['max'];
        }
        if ($tradeCount >= $item['min'] && $tradeCount <= $item['max']) {
            $fee += $item['trade_fee'];
            return $fee;
        }
    }
}

实现trim函数(移除空格)

先写暴力破解 , 牺牲空间的方法
LeetCode MoveZeros的类似题目 , 使用双指针技术

//别打我,PHP的写法就是简单粗暴... 有空了再写个O(1)空间复杂度的
function trim($arr)
{
    $a = '';
    $p1 = 0;
    $len = strlen($arr);
    for ($i = 0; $i <= $len-1; $i++) {
        if ($arr[$i] != ' ') {
            $a.= $arr[$i];
            $p1++;
        }
    }

    return $a;

}

字符串翻转

LeetCode Reverse String

使用技巧: Two Pointers

function reverseStr($str)
{
    $len=strlen($str);
    $p1=0;
    $p2=$len-1;
    while ($p1 <= $p2) {
        $tmp = $str[$p1];
        $str[$p1] = $str[$p2];
        $str[$p2] =  $tmp;
        $p1++;
        $p2--;
    }
    return $str;
}

Sort Colors

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not suppose to use the library's sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

1计数排序

function sortColors($arr)
{
    $zero = 0;$one = 0;$two = 0;
    $sorted = [];
    foreach ($arr as $v) {
        if ($v == 0) {
            $zero++;
        }
        if ($v == 1) {
            $one++;
        }
        if ($v == 2) {
            $two++;
        }
    }
    for ($i = 0; $i < $zero; $i++) {
        $sorted[] = 0;
    }
    for ($i = 0; $i < $one; $i++) {
        $sorted[] = 1;
    }
    for ($i = 0; $i < $one; $i++) {
        $sorted[] = 2;
    }
    return $sorted;
}

2三路快排(对撞指针的一种) 这题能体现对指针的定义,操作,初始化

![image-20190321125552476](/Users/lin/Library/Application Support/typora-user-images/image-20190321125552476.png)

![image-20190321130629849](/Users/lin/Library/Application Support/typora-user-images/image-20190321130629849.png)

动态规划 ?

Tips: 先找到子问题,再找重叠子问题

Advanced: 找状态和状态转移函数

在数组中找凑成的这个数的最小个数

如11 [1,2,5] 11=5+5+1 3个

1如果数据量极大 , 先排序, 二分查找到<=目标值最近的那个值,往下遍历

2动态规划/递归+记忆化搜索,找重复子问题

凑硬币

1,2,5分硬币,凑100分钱

倒水

3L 4L 杯子量5L水

7L 17L 9L水

穷举下去通常从小->大开始

斐波那契数列

Climbing Stairs

House Robber

Best Time to Buy and Sell Stock

这题有点难,有点类似Climbing Stairs

~~另一到类似题:如果你已经知道了未来100天一个股票股市的每一天的价格，然后请设计一套算法求出什么时候购入什么时候卖出能达到最大收益。~~

~~如果只是一次买入一次卖出则简单许多,同样动态规划~~

思考过程: 先暴力破解再考虑优化 , 其实每次遍历只要减去前面数里最小的一个就行了 , 所以可以把子问题的解存起来 , min(1) 前1个数最小的数 , min(n-1) 前n个数最小的数 , 然后判断哪个比最大的大 , 就是答案了

function maxProfit($prices)
{
    $maxProfit=0;
    $min = $prices[0];  // 存储子问题的解  min(.....)
    foreach ($prices as $k=>$price) {
        $min = min($min, $price);
        if ($price - $min > $maxProfit) {
            $maxProfit = $price-$min;
        }
    }
    return $maxProfit;
}

手写二叉搜索树

class Node
{
    public $data;
    public $left;
    public $right;

    public function __construct($data)
    {
        $this->data = $data;
    }
}

class BST {
    public $root;

    public function __construct(Node $root)
    {
        $this->root = $root;
    }

    public function add($data)
    {
        if ($this->root == null) {
            $this->root = new Node($data);
            return true;
        }
        $node = $this->root;

        while ($node) {
            /*这里遇到了很大的问题
            if else语句 尽量写成两个分支的 , 减少在同一个if判断多个条件                                      
            小数据量(1个也行)模拟一遍循环 , 防止写错无限循环
            */
            if ($data < $node->data ) {
                if ($node->left == null) {
                    $node->left = new Node($data);
                    break;
                } else {
                    $node = $node->left;
                }
            }

            if ($data > $node->data ) {
                if ($node->right == null) {
                    $node->right = new Node($data);
                    break;
                } else {
                    $node = $node->right;
                }
            }

        }
        return true;
    }
}

反转二叉树

层序遍历法

function reverse(Node $root)
{
    $queue = [];
    if ($root == null) {
        return null;
    }
    array_push($queue, $root);
    while (!empty($queue)) {
        $node = array_shift($queue);
        swap($node->left, $node->right);
        if ($node->left) {
            array_push($queue, $node->left);
        }
        if ($node->right) {
            array_push($queue, $node->right);
        }
    }
    return $root;
}

递归法

function reverse(Node $root)
{
    if ($root == null) {
        return null;
    }

    reverse($root->left);
    reverse($root->right);
    swap($root->left, $root->right);
    return $root;
}

快速排序

操作原数组写法

![image-20190321125229483](/Users/lin/Library/Application Support/typora-user-images/image-20190321125229483.png)

//明确各变量 参数定义
//不变式
//终止条件

//对数组[l,r] 进行快速排序
function quickSort($arr, $l,$r)
{
    //当l大于等于R , 数组只有一个元素或没有元素了 , 不再需要排序
    if ($l >= $r) {
        return ;
    }
    //否则对数组进行划分操作,并返回p
    $p = partition($arr,$l,$r);
    quickSort($arr, $l, $p - 1);  //[l,p-1] 继续排
    quickSort($arr, $p+1, $r);  //[p+1,r] 继续排
}

//返回p    arr[l...p-1) < arr[p]   arr[p] > arr[p+1...r]
function partition($arr,$l,$r):int
{
    $pivot = $arr[$l]; //选取第一个元素作为pivot

    $j = $l;
    $i = $l+1;

    for (; $i <= $r; $i++) {
        if ($arr[$i] < $pivot) {
            swap($arr[$i], $arr[$j]);
        }
        $j++;
    }
    swap($arr[$l], $arr[$j]);
}

牺牲空间复杂度但思路清晰的写法 (未写待续)

合并排序

function mergeSort($arr)
{
    $count = count($arr);

    $midIndex = (int)(($count-1 / 2) ) ;
    if ($count==1) {
        return $arr;
    }
    $l = mergeSort(array_slice($arr,0,$midIndex));
    $r = mergeSort(array_slice($arr, $midIndex));
    return merge2($l,$r);
}

function merge($l,$r)
{
    $arr = [];
    $lp = 0;
    $rp = 0;

    $lpMax = count($l)-1;
    $rpMax = count($r)-1;

    while ($lp<=$lpMax && $rp<=$rpMax) {
        if ($l[$lp] < $r[$rp]) {
            $arr[] = $l[$lp];
            $lp++;
        }
        if ($r[$rp] < $l[$lp]) {
            $arr[] = $r[$rp];
            $rp++;
        }
    }

    if ($lp <= $lpMax) {
        $arr = array_merge($arr,array_slice($l,$lp));
    }
    if ($rp <= $rpMax) {
        $arr = array_merge($arr,array_slice($r,$rp));
    }
    return $arr;
}

Move Zeros

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

Input: [0,1,0,3,12]
Output: [1,3,12,0,0]

1可以用类似trim的解法,后面填充

function moveZeros($arr)
{
    $a = [];
    $p1 = 0;
    for ($i = 0; $i <= count($arr)-1; $i++) {
        if ($arr[$i] != 0) {
            $a[] = $arr[$i];
            $p1++;
        }
    }
    for (; $p1 <= count($arr) - 1; $p1++) {
        $a[$p1]=0;
    }
    return $a;
}

2双指针(未写待续)

[0,k) 是非0 [k,n-1]是0

一个指针用于遍历数组 , 遇到非0元素放到k处遍历完毕停止

另一个用于准备下一个非0元素的存放位置 , 然后从k遍历到数组末尾填充0

![image-20190321201343415](/Users/lin/Library/Application Support/typora-user-images/image-20190321201343415.png)

给定一个数据量极大的乱序整数数组，找出里面的最大值

请想出一个高效算法

最少都要扫描一遍,暴力破解感觉就是最优了

除非可以容忍一定的错误率 , 按数据分布取部分样本(比如每隔1个取1个)

function max($arr)
{
    $gap = 2;
    $max = $arr[0];
    for ($i = 0; $i < count($arr); $i += $gap) {
        if ($arr[$i] > $max) {
            $max = $arr[$i];
        }
    }
    return $max;
}

两个有序数组 , 判断其中一个是否为另一个的子数组

二分查找变种

Kth Largest Element in an Array ?

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

快排partition + 类似二分

or 遍历 n*k遍

Longest Palindromic Subsequence ?

Given a string s, find the longest palindromic subsequence's length in s. You may assume that the maximum length of s is 1000.

Example 1:
Input:

"bbbab"

Output:

One possible longest palindromic subsequence is "bbbb".

Example 2:
Input:

"cbbd"

Output:

One possible longest palindromic subsequence is "bb".

使用滑动窗口

Multiply Strings ?

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2, also represented as a string.

Example 1:

Input: num1 = "2", num2 = "3"
Output: "6"

Example 2:

Input: num1 = "123", num2 = "456"
Output: "56088"

Note:

The length of both num1 and num2 is < 110.
Both num1 and num2 contain only digits 0-9.
Both num1 and num2 do not contain any leading zero, except the number 0 itself.
You must not use any built-in BigInteger library or convert the inputs to integer directly.

乱序数组中找比左边都小比右边都大的数用Go写的

//小于前面最小的 , 大于后面最大的      t 满足 arr[0...t-1]>arr[t]  arr[t+1...l]<arr[t]
// O(n^2)
//优化,存储 前n个数字最小的 , 后n个数字最大的 , 则第二次扫描只要一遍n+n=2n
func findPos(arr []int) int {
    l := len(arr) - 1
    for i := 0; i <= l; i++ {
        minLeft := arr[0]
        maxRight := arr[l]
        for j := 0; j <= l; j++ {
            if j < i {
                if arr[j] < minLeft {
                    minLeft = arr[j]
                }

            }
            if j == i {
                continue
            }
            if j > i {
                if arr[j] > maxRight {
                    maxRight = arr[j]
                }
            }

        }
        if arr[i] < minLeft && arr[i] > maxRight {
            return i
        }

    }
    return -1
}

func main() {
    arr := []int{3, 4, 2, 0, 1}
    fmt.Println(findPos(arr))
}

数组实现循环队列

算法题总结

1.总结各种算法用到的解题工具

1.1对撞指针/多指针/滑动窗口

1.2分解为子问题/树状结构/动态规划/递归+记忆化搜索

1.3利用partition每一步的性质获得第k大的数

2.需要始终贯彻的

2.1明确变量的定义

2.2明确函数的定义

2.3循环不变量/不变式 -> 确认边界条件

2.4小数据量调试

3.其他

3.1当实在没有好的思路的时候,先解决问题, 之后再考虑优化一定要尝试暴力解法虽然没有使用到特殊条件 , 但是解决了比没解决强 , 不断问自己是否能更优

3.2很多问题都是经典问题和经典问题的延伸

3.3字符串的问题可以看做就是数组问题

3.4一些实际问题可以转化成算法模型来解决 , 比如那道老鼠毒药题 , 转化为状态0和1

非算法题

SQL题

用户表帖子表前10发帖量用户名和发帖量,是最优解吗,如何加索引,为何这样加

select a.username b.thread_count from users as a
join
(select uid,count(*) as thread_count from thread groupby thread_count limit 10 order by thread desc ) as b
on a.uid=b.uid

可能的优化:
仔细看看JOIN,GROUPBY,ORDERBY,LIMIT 这几个的内部执行过程 , 内部对索引的使用

ORDERBY 内部过程索引使用 https://www.cnblogs.com/gulingjingguai/p/9...

ORDERBY

MySQL

问了隔离级别 mysql默认级别 , 可重复读是啥 , 还说了MVCC

ASCII , UTF8编码 , 字节序

概率论题

Tips: 排列组合问题解不出来就做笛卡尔积 , 爆破

1.30个人每个人生日都不同的概率

简单排列题…不能再简单

2.从100只重量不同羊里面先选出十只，然后从这十只中选出一只最重的记为A，然后再从剩余的90只选出十只，再从十只里面选重量最重的为B 问 P（A>B）=？

贝叶斯公式 , P(A|B) , 再P(A>B)= P(A|B)*0.5

3.n个人有多大概率至少两个人是同一天生日

假设n=30

至少两个人同一天生日= 1-没有一个人是同一天生日,同第一题

4.一个村有一条河一边70W人另一边30W,每天有100W,跨河的有多少(题意模糊,最好先问清题意)

逻辑题

1.1000 个瓶子中有一瓶毒药，一只老鼠吃到毒药一周之内会死，如果要在一周之内检测出有毒药的一瓶，问至少需要几只老鼠？

只有一瓶毒药,所以有1000种组合 , 一只老鼠有死/活两种状态 , 10只老鼠有2^10种死活组合

状态映射 2^10=1024 > 1000个状态

类似的二进制映射: ASCII 二进制映射到字符

QQ使用的udp是如何保证可靠的

FPM/NGINX/MYSQL 许多都是使用TCP进行通信的,体现了TCP的重要性

参考:告知你不为人知的 UDP：连接性和负载均衡

排查连接问题的方法 ?

如:排查php-fpm连接数过多问题
查看TCP连接命令: lsof -i tcp

排查FPM进程问题

排查NGINX进程问题

排查MYSQL线程问题,事务问题,锁问题

死锁的本质,如何排查死锁 ?

mysql官方文档

如何用一条表达式求出ABC三个数中间的那个数

暴力解法:

if（a>=b&&a<=c||a<=b&&a>=c）则a 
if（b>=a&&b<=c||b<=a&&b>=c）则c 
if(c>=a&&c<=b||c<=a&&c>=b)则b

数学解法:

private static int f(int a, int b, int c) {
        if ((b - a) * (a - c) >= 0) {
            return a;
        } else if ((a - b) * (b - c) >= 0) {
            return b;
        } else {
            return c;
        }
    }

考察素质问题

有没有坚持(学)过什么？

本作品采用《CC 协议》，转载必须注明作者和本文链接

twisted-fate

L5.5 译者 169 声望

暂无个人描述~

0 人点赞

我们将带你从零开发一个项目并部署到线上，本课程教授 Web 开发中专业、实用的技能，如 Git 工作流、Laravel Mix 前端工作流等。

从零开始带你一步步开发一个 Go 博客项目，让你在最短的时间内学会使用 Go 进行编码。项目结构很大程度上参考了 Laravel。

讨论数量: 0

(=￣ω￣=)··· 暂无内容！

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容，与人为善，比聪明更重要！

帮助