月度归档：2016年04月

LeetCode-2

发表回复

概述

Add Two Numbers 难度为Medium，这一题目简单来说即给出两个序列，代表两个整数，模拟加法运算。

分析

这一题难度个人认为依然不大，即把正常加法的算式过程用程序表示。需要特殊处理的是进位这一操作。

正常的加法竖式运算，需要将最低位对其，然后开始从低位向高位计算。

再具体一些，考虑一个加法运算，两个数相加，一个数字长度为n，一个数字为m，m>n，那么，和的字符个数至多为m+1。

对于进位值的计算，其实就是将当前位数的值以及前期的进位值相加，除以10即为进位制。

这一解法可以在O(n)的时间复杂度上解决问题。

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Map<Integer, Integer> lm1 = new HashMap<>();
        Map<Integer, Integer> lm2 = new HashMap<>();
        
        ListNode l = l1;
        int idx = 0;
        
        while (l != null) {
            lm1.put(idx, l.val);
            ++idx;
            l = l.next;
        }
        
        l = l2;
        idx = 0;
        
        while (l != null) {
            lm2.put(idx, l.val);
            ++idx;
            l = l.next;
        }
        
        Map<Integer, Integer> longer = (lm1.size() > lm2.size() ? lm1 : lm2);
        Map<Integer, Integer> shorter = (lm1.size() <= lm2.size() ? lm1 : lm2);
        int lengthGap = longer.size() - shorter.size();
        
        ListNode result = new ListNode(0);
        ListNode resultRef = result;
        int carryVal = 0;
        
        for (int i = 0; i < longer.size(); ++i) {
            int nowVal = 0;
            
            if (i >= shorter.size()) {
                nowVal = longer.get(i) + carryVal;
            } else {
                nowVal = longer.get(i) + shorter.get(i) + carryVal;
            }
            
            carryVal = (nowVal / 10);
            resultRef.val = (nowVal >= 10 ? nowVal % 10 : nowVal);
            
            if (i != longer.size() - 1) {
                resultRef.next = new ListNode(carryVal);
                resultRef = resultRef.next;
            } else {
                if (carryVal > 0) {
                    resultRef.next = new ListNode(carryVal);
                    resultRef = resultRef.next;
                }
                
                resultRef.next = null;
            }
        }
        
        return result;
    }
}

/**

* Definition for singly-linked list.

* public class ListNode {

* int val;

* ListNode next;

* ListNode(int x) { val = x; }

* }

public class Solution {

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

Map<Integer, Integer> lm1 = new HashMap<>();

Map<Integer, Integer> lm2 = new HashMap<>();

ListNode l = l1;

int idx = 0;

while (l != null) {

lm1.put(idx, l.val);

++idx;

l = l.next;

}

l = l2;

idx = 0;

while (l != null) {

lm2.put(idx, l.val);

++idx;

l = l.next;

}

Map<Integer, Integer> longer = (lm1.size() > lm2.size() ? lm1 : lm2);

Map<Integer, Integer> shorter = (lm1.size() <= lm2.size() ? lm1 : lm2);

int lengthGap = longer.size() - shorter.size();

ListNode result = new ListNode(0);

ListNode resultRef = result;

int carryVal = 0;

for (int i = 0; i < longer.size(); ++i) {

int nowVal = 0;

if (i >= shorter.size()) {

nowVal = longer.get(i) + carryVal;

} else {

nowVal = longer.get(i) + shorter.get(i) + carryVal;

}

carryVal = (nowVal / 10);

resultRef.val = (nowVal >= 10 ? nowVal % 10 : nowVal);

if (i != longer.size() - 1) {

resultRef.next = new ListNode(carryVal);

resultRef = resultRef.next;

} else {

if (carryVal > 0) {

resultRef.next = new ListNode(carryVal);

resultRef = resultRef.next;

}

resultRef.next = null;

}

return result;

}

LeetCode-1

发表回复

概述

作为简单题的第一题(Two Sum)，简答来说就是给出一个序列以及目标值，求出能加和出目标值的两个数字在数组中的下标。

分析

这个题目可以说是一目了然，直接能够想到的解法就是遍历这一个序列，然后遍历下标大于当前遍历到的数字的元素，如果有匹配的数字就直接返回结果即可。

如果单纯遍历，时间复杂度高达O(n²)，这个复杂度不太令人满意。

那么是否可以通过空间换时间呢？自然是没问题的。

后续考虑通过使用HashMap的方式记录每个值对应的元素的下标，每次检查是否有当前值相加得到目标值的的key存在，将时间复杂度降低到了O(n)，不过空间复杂度也上升到了O(n)。

解法

public class Solution {
    public int[] twoSum(int[] nums, int target) {
                Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>();

        for (int i = 0; i < nums.length; ++i) {
            numIdxMap.put(nums[i], i);
        }

        int[] idx = new int[2];

        for (int i = 0; i < nums.length; ++i) {
            if (numIdxMap.containsKey(target - nums[i])) {
                int j = numIdxMap.get(target - nums[i]);

                if (i == j) {
                    continue;
                }

                idx[0] = i;
                idx[1] = j;

                if (idx[0] > idx[1]) {
                    int tmp = idx[1];
                    idx[1] = idx[0];
                    idx[0] = tmp;
                }

                break;
            }
        }

        return idx;
    }
}

public class Solution {

public int[] twoSum(int[] nums, int target) {

Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>();

for (int i = 0; i < nums.length; ++i) {

numIdxMap.put(nums[i], i);

}

int[] idx = new int[2];

for (int i = 0; i < nums.length; ++i) {

if (numIdxMap.containsKey(target - nums[i])) {

int j = numIdxMap.get(target - nums[i]);

if (i == j) {

continue;

}

idx[0] = i;

idx[1] = j;

if (idx[0] > idx[1]) {

int tmp = idx[1];

idx[1] = idx[0];

idx[0] = tmp;

}

break;

}

return idx;

}

尝试LeetCode

发表回复

起因

OJ在学生时代应该都有所接触，作为程序设计与算法课程的实践内容也在一些OJ上做过少数的一些题目。不得不说，多年的习惯让在OJ上解题成为了一件很愉悦的事情。

工作后，原本薄弱的算法知识感觉消失殆尽，尽管在每天的工作中，组装、修改成为了工作的主题，可是总觉得自己不应如此，希望自己能保持毕业前那样积极的学习态度，希望自己能把之前的自主学习和思考的习惯保持下来。然而自己在每天的工作之后，惰性还是占了上风，阅读自然不少，可是这类基础的训练却扔下了。

本科期间由于学校身边的环境的缘故，自学了Java的基础编程。这半年对Android开发很感兴趣，再次接触Java，自己实现的过程中，感觉自己再次的丢掉了很多东西。

工作两年，经历了最开始的模仿、学习阶段之后，也尝试了各个方向，单独承担系统的开发维护工作中，更是觉得基础的知识，诸如网络、OS等基础知识在解决问题上能对思路起到打磨的作用，避免自己掉进 case by case 的坑里。积累经验当然重要，但是个人觉得更难得的是学会如何找到解决问题的方式，面向StackOverflow编程并不是一个好的选择。

近期看到 云风 大牛的关于反转单向链表微博，自己下班尝试编写了一下，也是花了一会儿时间才能顺畅的写完。这两天也是看到liaohuqiu 大牛发起的 LeetCode攻克计划，觉得是时候重新开始修行了。

目的

刷 LeetCode 的目的主要有两个：

从基础开始，重新学习Java编程
重新学习算法知识

第一个理由可能引人发笑，然而这确实是一个手段。自己在学习编写Java程序的过程中曾经过分的贪图速度，跳过了很多自认为基础的语言上的内容，在比较自己编写的代码与熟练的同事的代码中，更能有所体会。

计划

基于第一个原因，所有的LeetCode解题都会使用Java完成。

目前来看，一共有83道 Easy 题目，167道 Medium 题目，以及74道 Hard 题目。

不求过分贪心，希望半年内，我能把所有的 Easy 完成。

对于解决的题目，将会在blog里贴出自己的解题方案以及简要的解题思路，同时在解题过程中，尽量通过完备自己的思路和case解决问题，而不是通过尝试AC来解决问题。

已解决问题 [2]

two-sum Easy

add-two-numbers Medium

查看MySQL LOAD DATA进度

发表回复

概述

开发过程中经常会使用MySQL的LOAD DATA功能，用于导入文件到MySQL的指定数据库表中。

若已经将文件切分为N个小文件再进行LOAD操作（例如使用Linux下的 split 工具），那么进度还是很容易把控的，可以通过直接查找当前正在进行导入的分片，进而判断当前的分片。

可是，如果某些情况下直接对一个大型的文件进行进行LOAD操作，整个过程并不能直观的获取当前的进度的，需要通过一些相对曲折的过程才能获取当前LOAD的进度。

分析

/proc虚拟文件系统

Linux中的/proc虚拟文件系统是一个非常有趣的部分，这一个目录并不是包含了一些常规意义上的文件，而是表征了进程的部分运行时信息。部分Linux工具更是可以直接用读取目录中的部分信息来替代[1]。

在/proc下可以看到大量的名为数字的目录，这些数字正是进程的pid。而cd到其中任何一个目录下，可以看到类似的信息：

/proc/18458$ ll
总用量 0
dr-xr-xr-x 2 root root 0 3月  29 10:48 attr
-rw-r--r-- 1 root root 0 4月   3 21:34 autogroup
-r-------- 1 root root 0 4月   3 21:34 auxv
-r--r--r-- 1 root root 0 4月   3 21:34 cgroup
--w------- 1 root root 0 4月   3 21:34 clear_refs
-r--r--r-- 1 root root 0 1月  27 14:44 cmdline
-rw-r--r-- 1 root root 0 4月   3 21:34 comm
-rw-r--r-- 1 root root 0 4月   3 21:34 coredump_filter
-r--r--r-- 1 root root 0 4月   3 21:34 cpuset
lrwxrwxrwx 1 root root 0 4月   3 21:34 cwd -> /
-r-------- 1 root root 0 3月  18 10:31 environ
lrwxrwxrwx 1 root root 0 2月  23 13:24 exe -> /usr/local/nginx/sbin/nginx
dr-x------ 2 root root 0 3月  29 10:48 fd
dr-x------ 2 root root 0 4月   3 21:34 fdinfo
-r-------- 1 root root 0 4月   3 21:34 io
-rw------- 1 root root 0 4月   3 21:34 limits
-rw-r--r-- 1 root root 0 4月   3 21:34 loginuid
-r--r--r-- 1 root root 0 4月   3 21:34 maps
-rw------- 1 root root 0 4月   3 21:34 mem
-r--r--r-- 1 root root 0 4月   3 21:34 mountinfo
-r--r--r-- 1 root root 0 4月   3 21:34 mounts
-r-------- 1 root root 0 4月   3 21:34 mountstats
dr-xr-xr-x 5 root root 0 4月   3 21:34 net
dr-x--x--x 2 root root 0 4月   3 21:34 ns
-r--r--r-- 1 root root 0 4月   3 21:34 numa_maps
-rw-r--r-- 1 root root 0 4月   3 21:34 oom_adj
-r--r--r-- 1 root root 0 4月   3 21:34 oom_score
-rw-r--r-- 1 root root 0 4月   3 21:34 oom_score_adj
-r--r--r-- 1 root root 0 4月   3 21:34 pagemap
-r--r--r-- 1 root root 0 4月   3 21:34 personality
lrwxrwxrwx 1 root root 0 4月   3 21:34 root -> /
-rw-r--r-- 1 root root 0 4月   3 21:34 sched
-r--r--r-- 1 root root 0 4月   3 21:34 schedstat
-r--r--r-- 1 root root 0 4月   3 21:34 sessionid
-r--r--r-- 1 root root 0 4月   3 21:34 smaps
-r--r--r-- 1 root root 0 4月   3 21:34 stack
-r--r--r-- 1 root root 0 1月  27 14:44 stat
-r--r--r-- 1 root root 0 1月  27 15:55 statm
-r--r--r-- 1 root root 0 1月  27 14:44 status
-r--r--r-- 1 root root 0 4月   3 21:34 syscall
dr-xr-xr-x 3 root root 0 4月   3 21:34 task
-r--r--r-- 1 root root 0 4月   3 21:34 wchan

/proc/18458$ ll

总用量 0

dr-xr-xr-x 2 root root 0 3月 29 10:48 attr

-rw-r--r-- 1 root root 0 4月 3 21:34 autogroup

-r-------- 1 root root 0 4月 3 21:34 auxv

-r--r--r-- 1 root root 0 4月 3 21:34 cgroup

--w------- 1 root root 0 4月 3 21:34 clear_refs

-r--r--r-- 1 root root 0 1月 27 14:44 cmdline

-rw-r--r-- 1 root root 0 4月 3 21:34 comm

-rw-r--r-- 1 root root 0 4月 3 21:34 coredump_filter

-r--r--r-- 1 root root 0 4月 3 21:34 cpuset

lrwxrwxrwx 1 root root 0 4月 3 21:34 cwd -> /

-r-------- 1 root root 0 3月 18 10:31 environ

lrwxrwxrwx 1 root root 0 2月 23 13:24 exe -> /usr/local/nginx/sbin/nginx

dr-x------ 2 root root 0 3月 29 10:48 fd

dr-x------ 2 root root 0 4月 3 21:34 fdinfo

-r-------- 1 root root 0 4月 3 21:34 io

-rw------- 1 root root 0 4月 3 21:34 limits

-rw-r--r-- 1 root root 0 4月 3 21:34 loginuid

-r--r--r-- 1 root root 0 4月 3 21:34 maps

-rw------- 1 root root 0 4月 3 21:34 mem

-r--r--r-- 1 root root 0 4月 3 21:34 mountinfo

-r--r--r-- 1 root root 0 4月 3 21:34 mounts

-r-------- 1 root root 0 4月 3 21:34 mountstats

dr-xr-xr-x 5 root root 0 4月 3 21:34 net

dr-x--x--x 2 root root 0 4月 3 21:34 ns

-r--r--r-- 1 root root 0 4月 3 21:34 numa_maps

-rw-r--r-- 1 root root 0 4月 3 21:34 oom_adj

-r--r--r-- 1 root root 0 4月 3 21:34 oom_score

-rw-r--r-- 1 root root 0 4月 3 21:34 oom_score_adj

-r--r--r-- 1 root root 0 4月 3 21:34 pagemap

-r--r--r-- 1 root root 0 4月 3 21:34 personality

lrwxrwxrwx 1 root root 0 4月 3 21:34 root -> /

-rw-r--r-- 1 root root 0 4月 3 21:34 sched

-r--r--r-- 1 root root 0 4月 3 21:34 schedstat

-r--r--r-- 1 root root 0 4月 3 21:34 sessionid

-r--r--r-- 1 root root 0 4月 3 21:34 smaps

-r--r--r-- 1 root root 0 4月 3 21:34 stack

-r--r--r-- 1 root root 0 1月 27 14:44 stat

-r--r--r-- 1 root root 0 1月 27 15:55 statm

-r--r--r-- 1 root root 0 1月 27 14:44 status

-r--r--r-- 1 root root 0 4月 3 21:34 syscall

dr-xr-xr-x 3 root root 0 4月 3 21:34 task

-r--r--r-- 1 root root 0 4月 3 21:34 wchan

各个目录的说明可以参考此处。

/proc下的fdinfo

这里我们关注的地方是如何通过这些丰富的信息获取导入数据库的进度。

考虑到这一导入操作，实际上是利用了MySQL进行读取文件的操作，那么，只需要知道MySQL当前读取的文件位置，就可以了解到当前的进度了。

/proc/[PID]/fdinfo/这一目录正是解决这一问题的关键，这一目录包含了当前进程已打开的文件的信息，其中文件名正是文件描述符的名称，而相关信息则存储在这个只读文件之中。包含的信息形如：

/proc/18458/fd$ cat ../fdinfo/7
pos:    2293603
flags:  0102001

/proc/18458/fd$ cat ../fdinfo/7

pos: 2293603

flags: 0102001

pos

pos即文件读取游标的偏移值，也就是我们关注的已读取到的位置。

flags

flags则是一个八进制数，表征当前文件的打开状态。

以上述打开的文件为例，这是一个Nginx打开的日志文件，通过lsof +fg -p [PID]可以看到这一文件打开使用的flag：

COMMAND  PID USER   FD   TYPE  FILE-FLAG             DEVICE   SIZE/OFF     NODE NAME
...
nginx   18458 root    7w   REG    W,AP,LG                8,7    2293603  4194313 /home/www/logs/access_log

COMMAND PID USER FD TYPE FILE-FLAG DEVICE SIZE/OFF NODE NAME

...

nginx 18458 root 7w REG W,AP,LG 8,7 2293603 4194313 /home/www/logs/access_log

可以看到使用了W、AP、LG三个flag，而W对应的是O_WRONLY，AP对应的是O_APPEND，LG对应的的O_LARGEFILE，这三个常量的值一般可以在/usr/include/bits/fcntl.h中找到：

bits/fcntl.h:36:#define O_WRONLY         01
bits/fcntl.h:42:#define O_APPEND      02000
bits/fcntl.h:71:#  define O_LARGEFILE   0100000

bits/fcntl.h:36:#define O_WRONLY 01

bits/fcntl.h:42:#define O_APPEND 02000

bits/fcntl.h:71:# define O_LARGEFILE 0100000

所以flags的值为何是0102001也可以解释了。

获取进度

根据上述分析，首先我们直接找到正在进行LOAD操作的MySQL进程的PID，获取之后查看当前打开的文件（假设文件名为foo）在进程中的fd：

ls -l /proc/[PID]/fd | grep foo | grep -v grep | awk '{print $9}'

1	ls -l /proc/[PID]/fd \| grep foo \| grep -v grep \| awk '{print $9}'

获取fd之后，直接读取对应的fdinfo：

cat /proc/[PID]/fdinfo/[fd]

1	cat /proc/[PID]/fdinfo/[fd]

根据pos可以知道当前已读取了的文件位置，进而获知LOAD进度。

以上。