菜鸟公园
  • 编程技能
    • PHP
    • CPP
    • Golang
    • MySQL
    • 工具分享
  • 英语学习
  • 信文随笔
  • 关于本站
sign in/up

博客

2019-12-26 作者:菜鸟DJ 0
工具分享

MAC & WIN 平台效率工具清单

1. 数据库GUI工具

1.1 Sequal Pro

官方的release版本已经在2016年停更了,但是master分支仍然有人在更新。我认为这是OSX平台下最轻量,使用最舒服的DB GUI工具,没有之一。
功能特色:交互简洁,免费开源,支持查询结果集增删改。
下载:这里存放的是我编译的版本

1.2 DBeaver

DBeaver 是对目前市面流行的DB支持最全面的工具,而且社区版足够用。唯一的缺点是使用java编写的,有时候会卡。

2. Redis GUI工具

2.1 Medis

Medis是一款基于electron构建的Redis 管理工具,非常的好用。在大数量key的情况下吊打RedisDesktopManager。
官方不再提供OSX平台的安装包,在MAS上有提供下载,但是版本太老。同样下面分享我的编译版本。
下载:这里存放的是我编译的版本 提取码: pan6

3. API调试

3.1 PostMan

功能很齐全的API调试工具,界面也很优化。支持配置云同步。结果json格式化。
下载请到官网

4. 绘图工具

4.1 OpenBoard —— 一款打草稿的工具

全平台的开源软件,结合绘图板,完全可以抛弃草稿本,而且带录屏功能,可以用来制作课件视频。

5. 终端工具

5.1 Mac平台

iterm2 + ohmyzsh

5.2 Win平台

XShell

XShell 有两个功能我非常喜欢。
– 对终端显示文本可以自定义高亮,支持正则表达式,并且无需更改主机的配色。
– 支持ssh通道的代理,通过代理连接梯子服务器简直太舒服了。iterm2怎么配置摸索好久还是没找到解决方案。
附上我的正则高亮配置

用途 表达式
时间 \d{4}[\-\/]\d{2}[\-\/]\d{2}\ \d{2}\:\d{2}\:\d{2}
API (?<=\[)\/(\S)*(?=(\]\[))
IPv4 ((2(5[0-5]|[0-4]\d))|[0-1]?\d{1,2})(\.((2(5[0-5]|[0-4]\d))|[0-1]?\d{1,2})){3}

6. 开发环境搭建工具

6.1 oneinstack

php,db,nosql db,nginx,还有各种组件。懒人开发必备。

2019-09-05 作者:菜鸟DJ 0
MySQL

你真的会用MySQL里的max函数吗?

在MySQL我们经常会用到count,max,min这些函数,但是在使用这些函数的时候你确定你写的sql一定正确吗?话不多说,我们来个需求。

假设现在有一张消费表如下:

CREATE TABLE `tb_user_consume` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `user_id` int(11) unsigned DEFAULT NULL,
  `goods_id` int(11) unsigned DEFAULT NULL,
  `goods_name` varchar(50) CHARACTER SET utf8mb4 DEFAULT NULL,
  `price` decimal(10,2) unsigned DEFAULT NULL,
  `num` int(10) unsigned DEFAULT NULL,
  `total` decimal(10,2) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `uq_user_good` (`user_id`,`goods_id`),
  KEY `ind_total` (`total`),
  KEY `idx_user` (`user_id`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8;

现在我们需要取出每个用户购买最多的商品名。看似一个很简单的需求,基本上都能在脑海里想出来下面的SQL。

SELECT max(num),user_id,goods_name FROM tb_user_consume GROUP BY user_id LIMIT 10;

从语句上面看,好像没有什么问题都满足需求,我们执行下来验证下。
返回的结果如下:

max(num)    user_id     goods_name
982         1000000     1号商品
898         1000001     1号商品
982         1000002     1号商品
883         1000003     1号商品
706         1000004     1号商品
940         1000005     1号商品
761         1000006     1号商品
958         1000007     1号商品
739         1000008     1号商品
967         1000009     1号商品

感觉有点不对劲,难道1号商品这么畅销吗?大家都是买1号商品,我们来看下原始数据。

id  user_id goods_id    goods_name  price   num total
1   1000000 1   1号商品    1.30    982 1276.60
2   1000000 2   2号商品    1.15    212 243.80
3   1000000 3   3号商品    3.40    356 1210.40
4   1000000 4   4号商品    18.99   974 18496.26
5   1000000 5   5号商品    7.40    760 5624.00
6   1000001 1   1号商品    1.30    25  32.50
7   1000001 2   2号商品    1.15    898 1032.70
8   1000001 3   3号商品    3.40    743 2526.20
9   1000001 4   4号商品    18.99   311 5905.89
10  1000001 5   5号商品    7.40    732 5416.80
11  1000002 1   1号商品    1.30    982 1276.60
12  1000002 2   2号商品    1.15    674 775.10
13  1000002 3   3号商品    3.40    378 1285.20
14  1000002 4   4号商品    18.99   285 5412.15
15  1000002 5   5号商品    7.40    519 3840.60

我们很清楚的看出来了,1000001 购买的商品是2号商品居多,结合上面的查询结果来看,max(num)似乎没有问题,那么出问题似乎的是在goods_name的显示上。
查下网上的教程查询的结果集都只会包含group的那一列,和max的结果值。
那么我们还得自己来想解决办法,做一个子查询先按照user_id分组取出最大的num值,创建临时表和源表用user_id和num查询,于是就有了下面的SQL。

SELECT a.user_id,a.`goods_name`,a.num FROM tb_user_consume a JOIN (SELECT user_id , max(num) AS num FROM tb_user_consume  where user_id &lt; 1000010 GROUP BY user_id) b ON a.user_id = b.user_id AND a.num = b.num;

查询结果为

user_id goods_name  num
1000000 1号商品    982
1000001 2号商品    898
1000002 1号商品    982
1000003 3号商品    883
1000004 5号商品    706
1000005 1号商品    940
1000006 3号商品    761
1000007 3号商品    958
1000008 4号商品    739
1000009 5号商品    967

对比数据发现查询结果准确无误。所以千万不能偷懒使用简单的使用max查询其他列。

2019-08-23 作者:菜鸟DJ 0
PHP

MySQL 分组之后如何取Top(N)?

最近碰到一个有意思的问题,因为MySQL里没有top n的用法,所以如果要实现取数据的前几操作只能通过排序之后加limit限制数量,但是这种用法又跟group 冲突。这篇文章就是来分析下分组取topN的解题思路。

现在创建一个测试表。用户的商品消费数据(测试表就不建立索引了)

CREATE TABLE `tb_user_consume` (
  `id` int(11) unsigned NOT NULL AUTO_INCREMENT,
  `user_id` int(11) unsigned DEFAULT NULL,
  `goods_id` int(11) unsigned DEFAULT NULL,
  `goods_name` varchar(50) CHARACTER SET utf8mb4 DEFAULT NULL,
  `price` decimal(10,2) unsigned DEFAULT NULL,
  `num` int(10) unsigned DEFAULT NULL,
  `total` decimal(10,2) unsigned DEFAULT NULL,
  PRIMARY KEY (`id`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

INSERT INTO `tb_user_consume`(`user_id`,`goods_id`,`goods_name`,`price`,`num`,`total`)
VALUES
(100,1,"1号商品",1.3,10, price*num),
(100,2,"2号商品",1.15,12, price*num),
(100,3,"3号商品",3.4,5, price*num),
(100,4,"4号商品",18.99,2, price*num),
(100,5,"5号商品",7.4,9, price*num),'
(101,1,"1号商品",1.3,13, price*num),
(101,2,"2号商品",1.15,12, price*num),
(101,3,"3号商品",3.4,20, price*num),
(101,4,"4号商品",18.99,8, price*num),
(101,5,"5号商品",7.4,7, price*num),'
(102,1,"1号商品",1.3,21, price*num),
(102,2,"2号商品",1.15,3, price*num),
(102,3,"3号商品",3.4,51, price*num),
(102,4,"4号商品",18.99,23, price*num),
(102,5,"5号商品",7.4,22, price*num),'
(103,1,"1号商品",1.3,2, price*num),
(103,2,"2号商品",1.15,7, price*num),
(103,3,"3号商品",3.4,9, price*num),
(103,4,"4号商品",18.99,22, price*num),
(103,5,"5号商品",7.4,99, price*num),'
(104,1,"1号商品",1.3,77, price*num),
(104,2,"2号商品",1.15,54, price*num),
(104,3,"3号商品",3.4,23, price*num),
(104,4,"4号商品",18.99,23, price*num),
(104,5,"5号商品",7.4,44, price*num)
;

假如现在有一个需求是,筛选出用户消费商品总价最高的前三个商品。

粗一看,这个需求也没有什么实现上的难度,就是根据用户分组,取出表里total最高的三行记录就可以了。
对没有错,需求就是这么简单,解题思路也不难,那么我们开始着手编码了。

第一步,做一个子查询,

取出表里total最高的三行记录

sql写起来也很简单,如下所示

SELECT * FROM `tb_user_consume` WHERE user_id = 100 ORDER BY total DESC LIMIT 3;

第二步,按照用户分组
取出所有用户

SELECT * FROM `tb_user_consume` ORDER BY total DESC LIMIT 3 GROUP BY user_id;

看这个好像是满足了需求,别急,我们运行一下。

You have an error in your SQL syntax; check the manual that corresponds to your MySQL server version for the right syntax to use near ‘GROUP BY user_id’ at line 1

报错了,很明显上面的sql有语法错误。limit 只能用在查询语句的最后面。
那么我们要怎么去实现这个需求呢?用单一的子查询好像都没法直接的按照用户分组来取数据。
一般到这种时候,我们很可能就直接用代码来解决了。

先取出所有用户列表。 SELECT DISTINCT(user_id) AS uid FROM tb_user_consume;

然后遍历用户列表,按照上面的查询语句查出所有的用户前三total信息 SELECT * FROM tb_user_consume WHERE user_id = 100 ORDER BY total DESC LIMIT 3;

这种方法不是不可取,在表里的数据不多的时候,用这个也能完成需求,抛去执行效率不说,我们就说开发效率,又是写代码,又是写sql。还要去联调,是不是很费时费力?
那么到底能不能通过sql语句直接查询出来呢?

首先我们要想,上面不能实现的痛点在哪里?没有办法先limit 3,对不对?那我们能不能通过排序筛选的方式来实现,排序后达到三个的数量我们就停止。
按照机器的思维应该是,先order by user_id, 然后 order by total desc。

SELECT * FROM tb_user_consume ORDER BY user_id ,total DESC;

在这个结果集里当user_id 输出3个记录行就停止。 本文的重点来了 怎么实现这个呢?
通过谷歌(其实是百度)发现mysql里有一个 case when的条件判断。正好满足我们的需求。【 在这个结果集里当user_id 输出3个记录行就停止 】 美哉!开撸。

SELECT @rnd :=
    CASE
    WHEN @userid = `user_id` THEN
    @rnd := @rnd+1
    ELSE 1
    END rnd, @userid := `user_id`, user_id,total,goods_id,goods_name,price
FROM `tb_user_consume`,
    (SELECT @rnd := 1,
         @userid:=0) b
    ORDER BY  `user_id` ,`total` DESC

像这样我们就可以以rnd变量来标记我们的结果集排序结果了。这样我们把它作为一个子查询在外面加上限制条件就拿到指定的行数。
最终的sql如下:

SELECT *
FROM 
    (SELECT @rnd :=
        CASE
        WHEN @userid = `user_id` THEN
        @rnd := @rnd+1
        ELSE 1
        END rnd, @userid := `user_id`, user_id,total,goods_id,goods_name,price
    FROM `tb_user_consume`,
        (SELECT @rnd := 1,
         @userid:=0) b
        ORDER BY  `user_id` ,`total` DESC) aa
    WHERE rnd <=3;

最终的查询展示结果:

+------+----------------------+---------+--------+----------+------------+-------+
| rnd  | @userid := `user_id` | user_id | total  | goods_id | goods_name | price |
+------+----------------------+---------+--------+----------+------------+-------+
|    1 |                  100 |     100 |  66.60 |        5 | 5号商品    |  7.40 |
|    2 |                  100 |     100 |  37.98 |        4 | 4号商品    | 18.99 |
|    3 |                  100 |     100 |  17.00 |        3 | 3号商品    |  3.40 |
|    1 |                  101 |     101 | 151.92 |        4 | 4号商品    | 18.99 |
|    2 |                  101 |     101 |  68.00 |        3 | 3号商品    |  3.40 |
|    3 |                  101 |     101 |  51.80 |        5 | 5号商品    |  7.40 |
|    1 |                  102 |     102 | 436.77 |        4 | 4号商品    | 18.99 |
|    2 |                  102 |     102 | 173.40 |        3 | 3号商品    |  3.40 |
|    3 |                  102 |     102 | 162.80 |        5 | 5号商品    |  7.40 |
|    1 |                  103 |     103 | 732.60 |        5 | 5号商品    |  7.40 |
|    2 |                  103 |     103 | 417.78 |        4 | 4号商品    | 18.99 |
|    3 |                  103 |     103 |  30.60 |        3 | 3号商品    |  3.40 |
|    1 |                  104 |     104 | 436.77 |        4 | 4号商品    | 18.99 |
|    2 |                  104 |     104 | 325.60 |        5 | 5号商品    |  7.40 |
|    3 |                  104 |     104 | 100.10 |        1 | 1号商品    |  1.30 |
+------+----------------------+---------+--------+----------+------------+-------+

参考文章: 我的mysql如何分组取top10?

<?php
$host = '127.0.0.1';
$dbname = 'yang';
$port = 3306;

$db = new PDO("mysql:host=$host;dbname=$dbname;port=$port", 'root', '12345');

$goods_info = [
    ['id' => 1, 'name' => '1号商品', 'price' => 1.30],
    ['id' => 2, 'name' => '2号商品', 'price' => 1.15],
    ['id' => 3, 'name' => '3号商品', 'price' => 3.40],
    ['id' => 4, 'name' => '4号商品', 'price' => 18.99],
    ['id' => 5, 'name' => '5号商品', 'price' => 7.40],
];

function insert($goods_info, PDO &$db, $start)
{
    $sql = 'insert into tb_user_consume(user_id,goods_id,goods_name,price,num,total) values';
    for ($i = $start; $i < $start + 50000; $i++) {
        foreach ($goods_info as $info) {
            $num = mt_rand(0, 1000);
            $total = $num * $info['price'];
            $sql .= sprintf("(%d,%d,\"%s\",%f,%d,%f),", $i, $info['id'], $info['name'], $info['price'], $num, $total);
        }
    }
    $sql = substr($sql, 0, -1);
    //echo $sql;

    $db->prepare($sql)->execute();
}

// 批量添加测试数据
//for ($j = 1000000; $j < 2000000; $j += 50000) {
//    insert($goods_info,$db,$j);
//}

// 执行时间
$start = time();
select($db);
echo "cost:".(time()-$start)."\n";

function select(PDO &$db){
    for ($i = 1000000; $i < 2000000; $i++) {
        $sql = 'SELECT * FROM `tb_user_consume` WHERE user_id = '.$i.' ORDER BY total DESC LIMIT 3; ';
        $ret = $db->query($sql)->fetchAll();
        //var_dump($ret);
    }
}

MySQL php

2019-05-05 作者:菜鸟DJ 0
Golang

B站代码解读 — LRUCache

0x01. 说明

  • 本文源码来源于互联网,本人保证公开部分不涉及任何公司的敏感信息,本人保证不传播任何敏感信息。
  • 本文仅用于学术交流,请勿在商业用途中使用此源码,此源码并未执行任何开源授权。

0x02. 介绍

LRU全称为Least Recently Used,为内存管理算法的一种。通过淘汰最近最少使用的KEY来实现内存置换。

LRU的规则是最近调用的key排在列表的最前面。例如:set 3,set 4,set 5, 内存中key的排列应该是 543。然后get 4,内存刷新为453,再set 1,内存刷新为145。【注,排列顺序为阅读顺序,最左边为顶部】
从描述中可以看出,最近读取,最近更新的key,会排到队列的最顶部,该key之前的首尾会连接起来保持顺序。那么实现这种数据结构成为双向链表。

对于双向链表,了解数据结构的同学肯定不陌生,本着解读的目的,我们来介绍下什么是双向链表。

链表是一种物理存储单元上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点(链表中每一个元素称为结点)组成,结点可以在运行时动态生成。
每个结点包括两个部分:一个是存储数据元素的数据域,另一个是存储下一个结点地址的指针域。

双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结点和后继结点。

有一点需要注意的是,队列的顶部和底部并不是相连的(LRU不是循环双向链表),所以我们需要有一个head指针,和tail指针来保存头尾信息。

LRU结构示意 alt

对于双向链表的实现不是本文讨论的重点,在这里略过。我们重点是解读LRU的实现。

0x03. LRU Cache实现

从上面的示意图中,我们需要定义一个结构体,包含四个元素,next指针,prev指针,key和value字段。在golang中可以使用interface{}作为泛型支持。
实现如下:

type Element struct {
    prev, next *Element
    Key        interface{}
    Value      interface{}
}

整个LRUCache的结构如下,head为头指针,tail为尾指针,capacity为队列长度,【为什么要指定长度,因为是内存置换,属于虚拟内存,所以肯定是要限制长度来使用的】。
cache 为字典结构存储Element元素(以我的理解其中Element.key 为冗余设计,应该是可以省略Element.key字段)。

type LRUCache struct {
    cache    map[interface{}]*Element
    head     *Element
    tail     *Element
    capacity int
}

那么剩下的就是实现几个方法,『内存开辟』,『设置值』,『更新队列』,『删除元素』。具体实现可以看下面的源代码

package lrucache

// Element - node to store cache item
type Element struct {
    prev, next *Element
    Key        interface{}
    Value      interface{}
}

// Next - fetch older element
func (e *Element) Next() *Element {
    return e.next
}

// Prev - fetch newer element
func (e *Element) Prev() *Element {
    return e.prev
}

// LRUCache - a data structure that is efficient to insert/fetch/delete cache items [both O(1) time complexity]
type LRUCache struct {
    cache    map[interface{}]*Element
    head     *Element
    tail     *Element
    capacity int
}

// New - create a new lru cache object
func New(capacity int) *LRUCache {
    return &LRUCache{make(map[interface{}]*Element), nil, nil, capacity}
}

// Put - put a cache item into lru cache
func (lc *LRUCache) Put(key interface{}, value interface{}) {
    if e, ok := lc.cache[key]; ok {
        e.Value = value
        lc.refresh(e)
        return
    }

    if lc.capacity == 0 {
        return
    } else if len(lc.cache) >= lc.capacity {
        // evict the oldest item
        delete(lc.cache, lc.tail.Key)
        lc.remove(lc.tail)
    }

    e := &Element{nil, lc.head, key, value}
    lc.cache[key] = e
    if len(lc.cache) != 1 {
        lc.head.prev = e
    } else {
        lc.tail = e
    }
    lc.head = e
}

// Get - get value of key from lru cache with result
func (lc *LRUCache) Get(key interface{}) (interface{}, bool) {
    if e, ok := lc.cache[key]; ok {
        lc.refresh(e)
        return e.Value, ok
    }
    return nil, false
}

// Delete - delete item by key from lru cache
func (lc *LRUCache) Delete(key interface{}) {
    if e, ok := lc.cache[key]; ok {
        delete(lc.cache, key)
        lc.remove(e)
    }
}

// Range - calls f sequentially for each key and value present in the lru cache
func (lc *LRUCache) Range(f func(key, value interface{}) bool) {
    for i := lc.head; i != nil; i = i.Next() {
        if !f(i.Key, i.Value) {
            break
        }
    }
}

// Update - inplace update
func (lc *LRUCache) Update(key interface{}, f func(value *interface{})) {
    if e, ok := lc.cache[key]; ok {
        f(&e.Value)
        lc.refresh(e)
    }
}

// Front - get front element of lru cache
func (lc *LRUCache) Front() *Element {
    return lc.head
}

// Back - get back element of lru cache
func (lc *LRUCache) Back() *Element {
    return lc.tail
}

// Len - length of lru cache
func (lc *LRUCache) Len() int {
    return len(lc.cache)
}

// Capacity - capacity of lru cache
func (lc *LRUCache) Capacity() int {
    return lc.capacity
}

func (lc *LRUCache) refresh(e *Element) {
    if e.prev != nil {
        e.prev.next = e.next
        if e.next == nil {
            lc.tail = e.prev
        } else {
            e.next.prev = e.prev
        }
        e.prev = nil
        e.next = lc.head
        lc.head.prev = e
        lc.head = e
    }
}

func (lc *LRUCache) remove(e *Element) {
    if e.prev == nil {
        lc.head = e.next
    } else {
        e.prev.next = e.next
    }
    if e.next == nil {
        lc.tail = e.prev
    } else {
        e.next.prev = e.prev
    }
}

bilibili B站 Golang 算法

2019-04-07 作者:菜鸟DJ 0
CPP, 编程技能

解搜索二维矩阵题

今天我来讲下我做这道题的思路吧。原题点击此处跳转 。

下面是具体的题目:

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性:

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:

现有矩阵 matrix 如下:

 [
 [1,   4,  7, 11, 15],
 [2,   5,  8, 12, 19],
 [3,   6,  9, 16, 22],
 [10, 13, 14, 17, 24],
 [18, 21, 23, 26, 30]
]

给定 target = 5,返回 true。

给定 target = 20,返回 false。

看似很平常的题,逐行搜索也可以解决,但是题目中要求使用高效的算法,所以本题的解题思路肯定是不是两层for循环那么简单。

结合题目描述二维矩阵有『从左往右,上往下是递增』的规律,可以摸索出,我们只要横着扫一行,竖着扫一列,便可以大致确定范围,例如题目中的target = 5,在第一行中小于等于5的只有1,4两个数,在第一列中小于五的数只有1,2,3三个数,那么搜索的范围就可以确定为 一个2*3的矩阵。相比5*5是不是范围小了很多。

但是!

这就是最高效的算法吗?接下来我们算示例中给的第二个target=20, 我们发现第一行全都小于20,第一列全都小于20,看来还是要遍历整个矩阵了。所以上面那种思路并不能算是高效的(因此便不放代码)。那么对于target=20这种输入,该如何优化呢?

我们再来抠题目中的『从左往右,上往下是递增』的规律,那么我们一开始搜索每行最右边的数字,判定他与目标值的关系,假如最右边的值小于目标值,根据题目中的规律,这一行都不用搜索了,肯定比目标值小。假如最右边的值大于目标值,我们便向右边搜索,因为往下搜索已经是永远大于目标值了。根据这个条件我们对于target=20的搜索路径为15->19->22->24->30->26->23->21->18,只需要搜索9次,便可以给出答案。是不是比搜索25个值快多了。同样对于target=5的输入,我们的搜索路径为15->11->7->4->5,也不用像前面提到的搜索行与列确定范围那么麻烦。

下面是我写的代码


bool Solution::searchMatrix(std::vector<std::vector<int>> &matrix, int target) { if (matrix.size() == 0 || matrix[0].size() == 0 || matrix[0][0] > target || matrix[matrix.size() - 1][matrix[0].size() - 1] < target) { return false; } int h = matrix.size();// i int w = matrix[0].size(); // j int i = 0, j = 0; // int l = 0; for (i = 0; i < h; i++) { if (matrix[i][w - 1] < target) { // std::cout << w-1 << ",-" << i <<"," <<l<<std::endl; // ++l; continue; } for (j = w - 1; j >= 0; j--) { // std::cout << j << ",-" << i << "," << l << std::endl; // ++l; if (matrix[i][j] == target) { return true; } else if (matrix[i][j] < target) { break; } else { w = j; } } } return false; } }

注释的l变量是用来打印搜索路径的。
我们看下搜索路径图(原点是第一个元素,矩阵向右,和向下延伸)

搜索路径图

测试无误之后,提交。然后再去看大神的代码。然后发现我和大神代码之间差了好几个卧槽。

bool Solution::searchMatrix(std::vector<std::vector<int>> &matrix, int target) {
    // int l = 0;
    int n = matrix.size();
    if (n == 0)
        return false;
    int m = matrix[0].size();

    for (int c = 0, r = m - 1; c < n && r >= 0;) {
        // std::cout << "" << r << ",-" << c << "," << l << std::endl;
        // ++l;
        if (matrix[c][r] > target) {
            --r;
        } else if (matrix[c][r] < target) {
            ++c;
        } else
            return true;
    }
    return false;
}

因为思路是一样,所以搜索路径是一样的,这里就不放图了。但是代码要精简很多,值得学习。

cpp leetcode 算法

2019-03-21 作者:菜鸟DJ 0
编程技能

解一道字符串变化题

0x01. 做一道字符串变换的题目

给定一组字符串例按照设定一个行数,以从上到下,从左到右进行Z字形排列。
比如输入的字符串为『ABCEDFGHIJKLMN』,行数设为3的时候,排列如下

[A] [ ] [E] [ ] [I] [ ] [M]
[B] [D] [F] [H] [J] [L] [N]
[C] [ ] [G] [ ] [K] [ ] [ ]

之后,你的输出需要从左往右逐行读取,产生一个新的字符串,比例如『AEIMBDFHJLNCGK』
请设计一个这样的字符串变换函数

0x02. 分析解题思路

拿到这个题目,从最直观的方向入手就是,按照题目示例中的排序方式给逐个字符串扫描,排列到对应规则的位置上。
通俗来说,按照坐标系走(x轴从左到右,y轴从上到下)我们可以分析出下面的坐标点。
A(0,0)
B(0,1)
C(0,2)
D(1,1)
E(2,0)
F(2,1)
G(2,2)
H(3,1)
…
仔细观察排列关系之后,我们不难发现题中说的排列方式按照Z字形其实是一个误导,对程序而言A->G,E->K实际上不是一个可以重复循环处理的方案,我们需要把这种排列切割为A->D,E->H,这样的处理方式可以使程序能够重复循环处理。
可以得到如下伪代码

*p = str[0]
while *p != '\0'{
    if (i<row){
        ... set value
    }else{
        ... set value
    }
    loop++
}

具体代码实现可以拉到文末。

程序解题到这里,其实本题基本上已经解决了,但是如果我们更深层的思考下,这种解题过程是否可以值得更优化下,一定要使用二维数据来填值吗?从题目的立意来看,无非是将字符串重组,既然说到重组无非就是一个权重变化的过程,那么我们可否设计一个方程来计算这种权重呢? 其实上面的解题里对应的二维数组也是一个权重的表现。二维坐标对应到一维的权重里。

按照x+y*10的思路去做。
A(0,0)->0
B(0,1)->10
C(0,2)->20
D(1,1)->11
E(2,0)->2
F(2,1)->12
G(2,2)->22
H(3,1)->13

按照解题思路一的分块重复的思路,我们惊奇的发现,后面的循环只是对前面的对应位置加2,这就很棒棒哒,只要算出第一块排列的位置,后面的权重就很好计算了。
转换公式x+y*10 中的系数10肯定不是一个好的系数,对于row 大于10的情况就非常容易两个位置出现转换的权重一致的情况,所以在设计公式的时候我们需要把10替换为字符串长度len,这样就可以保证唯一权重。

0x03. 解题代码

php版本,包含2种思路的解题

<?php

$para = getopt("s:n:");

$row = $para["n"] ?? 0;
if ($row < 2) {
    exit("请输入大于2的行数");
}
$str = $para['s'] ?? '';
if (strlen($str) <= 0) {
    exit("请输入要排序的字符串");
}

$output = null;
$len = strlen($str);
$pos = 0;
$i = 0;
$j = 0;
$loop = 1;
while ($pos < $len) {
    for ($i; $i < $row; $i++) {
        if ($pos == $len) {
            break;
        }
//        echo "$i,$j," . $str[$pos] . "\n";

        $output[$i][$j] = $str[$pos];
        $pos++;

    }
//    echo "| \n";
    $i -= 2;
    $j++;
    for ($j; $j < $row * $loop - 1; $j++) {
        if ($pos == $len) {
            break;
        }
//        echo "$i,$j," . $str[$pos] . "\n";
        $output[$i][$j] = $str[$pos];
        $pos++;
        $i--;
        if ($i < 0) {
            $i = 0;
            $pos--;
            break;
        }
    }
    $loop++;
//    echo "- \n";

}

$output2 = '';
for ($n = 0; $n < $row; $n++) {
    for ($m = 0; $m < $j; $m++) {
        echo isset($output[$n][$m]) ? "[" . $output[$n][$m] . "] " : "[ ] ";
        if (isset($output[$n][$m])) {
            $output2 .= $output[$n][$m];
        }
    }
    echo "\n";
}
echo "$output2.\n";

$output3 = [];
$n = 2 * ($row - 1);
$cnt = ceil((float)$len/$n);
$pos = 0;
for ($k = 0; $k < $cnt; $k++) {
    for ($l = 0; $l < $n; $l++) {
        if ($l < $row) {
            $output3[$l * $len + $k * ($row - 1)] = $str[$pos];
            $pos++;
        } else {
            $output3[($n - $l) * $len + $l - $row + 1 + $k * ($row - 1)] = $str[$pos];
            $pos++;
        }
        if ($pos >= $len) {
            break;
        }
    }
}
ksort($output3);

$output3 = array_values($output3);
$len = count($output3);
for ($i = 0; $i < $len; $i++) {
    echo $output3[$i];
}
echo "\n";

C++版本(限于能力问题,C++版本是练手的,写的不好还望大家指出改进)

#include <iostream>
#include <cmath>

int main(int argc, const char *argv[])
{
    int row, len;
    char str[100];
    std::cout << "请输入行数" << std::endl;
    std::cin >> row;
    if (row < 2) {
        std::cout << "请输入大于2的行数";
        exit(1);
    }

    std::cout << "请输入需要排序字符串" << std::endl;
    std::cin >> str;
    len = (int)strlen(str);
    if (len <= 0) {
        std::cout << "请输入需要排序字符串" << std::endl;
    }

    int b = 2 * (row - 1);
    int cnt = ceil((float)len / b);
//    printf("len=%d,b=%d,cnt=%d\n",len,b,cnt);
//    printf("%f\n",ceil(10.0/3));

    int pos = 0;
    char output3[100 * 100] = {};
    for (int k = 0; k < cnt; k++) {
        for (int l = 0; l < b; l++) {
            if (l < row) {
                output3[l * len + k * (row - 1)] = str[pos];
//                printf("竖排:%d,%d,%d,%c\n", k, l, l * len + k * (row - 1), str[pos]);
                pos++;
            } else {
                output3[(b - l) * len + l - row + 1 + k * (row - 1)] = str[pos];
//                printf("斜排:%d,%d,%d,%c\n", k, l, (b - l) * len + l - row + 1 + k * (row - 1), str[pos]);
                pos++;
            }
//            printf("len=%d,pos=%d,k=%d,l=%d\n",len,pos,k,l);
            if (pos >= len) {
                break;
            }
        }
    }
//    len = (int)strlen(output3);
    for (int i = 0; i < 100 * 100; i++) {
        if (output3[i] != '\0') {
            printf("%c", output3[i]);
        }
    }
    printf("\n");
    return 0;
}

C++ php 字符串 编程

2018-12-31 作者:菜鸟DJ 0
信文随笔

致即将逝去的2018

选择在这最后一天发表开站,发布文章的目的很简单,明天我就可以说,我们是2018年创建的站点。 其实是因为太懒了,来谈一谈为什么要创建这样一个站点吧。其实出于几个目的,想了很久,一直没有付诸行动。
  • 1 人总想实现点自己的价值,在赚钱的领域里找不到存在感。所以总要在其他方面找点存在感。既然不能做一个暴发户,那就一个文化者,做一个知识的传播者。何以解忧,唯有暴富啊!
  • 2 和当当一样,平时看的东西杂七杂八,碎片化太严重。然而做笔记的习惯又不好,经常是当时记得,过段时间就忘了。本来之前都写在微信公众号里,但是微信公众号的编辑器是众所周知的不好用。而且对程序猿而言,放代码上去不利于阅读。
  • 3 给当当建立一个文章汇聚平台,对文科生而言,整理资料就是她们最大的痛苦,在她们的观点里,电脑就应该是我说一句话,能把所有事情都能做完的。(是不是很像你的老板,给你撂一句话,你去揣摩吧)。

我主要写的内容是一些编程方面的,对于一些读者而言,可能过于专业,但这不要紧。我们当当同学写初高中英语的辅导教材,这就很接地气了。不用到辅导班就能获得辅导老师的教材,是不是很nice?

2018还剩几个小时,就要过去了。别管你在2018学得到什么,错过什么。我们展望2019,一起好好的学习!

文章分页

上一页 1 2
17/17

天气

分类目录

热门文章

记一次和流氓软件战斗的过程0 comments
手机app https抓包步骤一揽0 comments
记一下RabblitMQ的安装和RPC的工作模式0 comments
聊一聊快排算法0 comments
MAC & WIN 平台效率工具清单0 comments
你真的会用MySQL里的max函数吗?0 comments
MySQL 分组之后如何取Top(N)?0 comments
B站代码解读 — LRUCache0 comments
解搜索二维矩阵题0 comments
解一道字符串变化题0 comments

微信公众号:菜鸟公园

微信公众号
微信公众号:菜鸟公园
隐私政策