Felix021

class Solution(object):
    def mySqrt(self, x):
        """
        :type x: int
        :rtype: int
        """
        if x < 0:
            raise Exception("invalid input")
        if x < 2:
            return x
       
        left = 1
        length = x / 2
        while length > 1:
            half = length / 2
            middle = left + half
            if middle * middle > x:
                length = half
            else:
                left = middle
                length = length - half
        return left

import "math"

func mySqrt(x int) int {
    f := func (i float64) float64 {
        return i * i - float64(x)
    }
    g := func (i float64) float64 {
        return 2 * i
    }
    var i float64 = 1.0
    for math.Abs(f(i)) > 1e-6 {
        i = i - f(i) / g(i)
    }
    return int(math.Floor(i))
}

[0] -> 0 -> 1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 9 -> nil
[1] -> 0 ------> 3 ------> 5 ------> 7 ------> nil
[2]----------------------> 5-----------------> nil

class Node(object)
    def __init__(self, height, key):
        self.key = key
        self.next = [None] * height

    def height(self):
        return len(self.next)

class SkipList(object):
    def __init__(self):
        self.head = Node(0, None) #头节点高度为0，不需要key

import random

def randomHeight(self, p = 0.5):
    height = 1
    while random.uniform(0, 1) < p and self.head.height() >= height:
        height += 1
    return height

def insertFirstNode(self, key):
    node = Node(self.randomHeight(), key)
    while node.height > self.head.height():
        self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表

    for level in range(node.height()):
        node.next[level] = self.head.next[level]
        self.head.next[level] = node

def getUpdateList(self, key):
    update = [None] * self.head.height()
    for level in range(len(update)):
        x = self.head
        while x.next[level] is not None and x.next[level].key < key:
            x = x.next[level]
        update[level] = x
    return update

def insert(self, key):
    node = Node(self.randomHeight(), key)
    while node.height > self.head.height():
        self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表

    update = self.getUpdateList(key)
    next0 = update[0].next[0]
    if next0 is not None and next0.key == key:
        return # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。

    for level in range(node.height()):
        node.next[level] = update[level].next[level]
        update[level].next[level] = node

def getUpdateList(self, key):
    update = [None] * self.head.height()
    x = self.head
    for level in reversed(range(len(update))):
        while x.next[level] is not None and x.next[level].key < key:
            x = x.next[level]
        update[level] = x
    return update

def dump(self):
    for i in range(self.head.height()):
        sys.stdout.write('[H]')
        x = self.head.next[0]
        y = self.head.next[i]
        while x is not None:
            s = ' -> %s' % x.key
            if x is y:
                y = y.next[i]
            else:
                s = '-' * len(s)
            x = x.next[0]
            sys.stdout.write(s)
        print ' -> <nil>'
    print

sl = SkipList()
for i in range(10):
    sl.insert(sl)
    s1.dump()

[H] -> 0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> 9 -> <nil>
[H]----- -> 1 -> 2 -> 3---------- -> 6 -> 7---------- -> <nil>
[H]---------- -> 2-------------------- -> 7---------- -> <nil>

def find(self, key):
    update = self.getUpdateList(key)
    if len(update) == 0:
        return None

    next0 = update[0].next[0]
    if next0 is not None and next0.key == key:
        return next0 # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。
    else:
        return None

def remove(self, key):
    update = self.getUpdateList(key)
    for i, node in enumerate(update):
        if node.next[i] is not None and node.next[i].key == key:
            node.next[i] = node.next[i].next[i]

node = sl.find(3)
print node

for i in range(7, 14):
    sl.remove(i)
    sl.dump()

#coding:utf-8

import random

class Node(object):
    def __init__(self, height, key=None):
        self.key = key
        self.next = [None] * height

    def height(self):
        return len(self.next)

class SkipList(object):
    def __init__(self):
        self.head = Node(0, None) #头节点高度为0，不需要key

    def randomHeight(self, p = 0.5):
        height = 1
        while random.uniform(0, 1) < p and self.head.height() >= height:
            height += 1
        return height

    def insert(self, key):
        node = Node(self.randomHeight(), key)
        print node.height(), node.key
        while node.height() > self.head.height():
            self.head.next.append(None) #保证头节点的next数组覆盖所有层次的链表

        update = self.getUpdateList(key)
        if update[0].next[0] is not None and update[0].next[0].key == key:
            return # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。

        for level in range(node.height()):
            node.next[level] = update[level].next[level]
            update[level].next[level] = node


    def getUpdateList(self, key):
        update = [None] * self.head.height()
        x = self.head
        for level in reversed(range(len(update))):
            while x.next[level] is not None and x.next[level].key < key:
                x = x.next[level]
            update[level] = x
        return update

    def dump(self):
        for i in range(self.head.height()):
            sys.stdout.write('[H]')
            x = self.head.next[0]
            y = self.head.next[i]
            while x is not None:
                s = ' -> %s' % x.key
                if x is y:
                    y = y.next[i]
                else:
                    s = '-' * len(s)
                x = x.next[0]
                sys.stdout.write(s)
            print ' -> <nil>'
        print

    def find(self, key):
        update = self.getUpdateList(key)
        if len(update) == 0:
            return None

        next0 = update[0].next[0]
        if next0 is not None and next0.key == key:
            return next0 # 0层总是包含所有元素；如果 update[0] 的下一个节点与key相等，则无需插入。
        else:
            return None

    def remove(self, key):
        update = self.getUpdateList(key)
        for i, node in enumerate(update):
            if node.next[i] is not None and node.next[i].key == key:
                node.next[i] = node.next[i].next[i]

$dbTrans = $db->beginTransaction();
try {
    $order = PayRequest::model()->newPayRequest(...); #在数据库中插入一条支付请求记录，状态为待支付
    //其他业务改动
    $result = PaySvr::pay($order->id, $order->amount); #请求PaySvr（或第三方支付通道）扣款
    if ($result['code'] == PaySvr::E_SUCCESS) {
        $order->setAsSucceeded();
    } else {
        $order->setAsPending();
    }
    $dbTrans->commit();
} catch (Exception $e) {
    $dbTrans->rollback();
}

$dbTrans = $db->beginTransaction();
try {
    $order = PayRequest::model()->newPayRequest(...);
    //其他业务改动
    $dbTrans->commit(); #先将支付请求落地
} catch (Exception $e) {
    $dbTrans->rollback();
}

#再请求PaySvr
$result = PaySvr::pay($order->id, $order->amount);

#根据PaySvr结果修改支付请求和其他业务记录的状态
$dbTrans = $db->beginTransaction();
try {
    if ($result['code'] == PaySvr::E_SUCCESS) {
        $order->setAsSucceeded();
        //其他业务改动
    } else {
        $order->setAsPending();
        //其他业务改动
    }
} catch (Exception $e) {
    $dbTrans->rollback();
}

#匹配系统
function matcher() {
    $dbTrans = $db->beginTransaction();
    try {
        foreach (matchCapitalAndProject() as $match_result) {
            list($capital_id, $project_id, $amount) = $match_result;
            $relation = Relation::model()->create($capital_id, $project_id, $amount);
            $redis->lPush($relation->id);
        }
        $dbTrans->commit();
    } catch (Exception $e) {
        $dbTrans->rollback();
    }
}

#Worker
function Worker() {
    while (true) {
        $id = $redis->brPop();
        $relation = Relation::model()->findByPk($id);
        if ($relation) {
            BankApi::invest($relation->capital_id, $relation->project_id, $amount);
        }
    }
}

#匹配系统
function matcher() {
    $arr_relation = [];
    $dbTrans = $db->beginTransaction();
    try {
        foreach (matchCapitalAndProject() as $match_result) {
            list($capital_id, $project_id, $amount) = $match_result;
            $relation = Relation::model()->create($capital_id, $project_id, $amount);
            $arr_relation[] = $relation;
        }
        $dbTrans->commit();
    } catch (Exception $e) {
        $dbTrans->rollback();
    }
    foreach ($arr_relation as $relation) {
        $redis->lPush($relation->id);
    }
}

function transpose($array) {
    array_unshift($array, null);
    return call_user_func_array('array_map', $array);
}

function utf8_str2arr($str)
{
    preg_match_all("/./u", $str, $arr);
    return $arr[0];
}

function substr_width($str, $start, $width)
{
    $arr = utf8_str2arr($str);
    $arr_ret = [];
    $i = 0;
    while ($width > 0 and $i < count($arr))
    {
        $arr_ret[] = $arr[$start + $i];
        if (strlen($arr_ret[$i]) == 1) //ascii,width=1
            $width -= 1;
        else
            $width -= 2;
        $i++;
    }
    if ($width < 0)
        array_pop($arr_ret);
    return join('', $arr_ret);
}

pclose(popen("nohup $cmd &", 'r'));

#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[])
{
    MPI_Init(&argc, &argv); //初始化MPI环境

    printf("Hello world!\n");

    MPI_Finalize(); //结束MPI环境
    return 0;
}

#include <stdio.h>
#include <mpi.h>

int main(int argc, char *argv[])
{
    int myid, numprocs, source, msg_tag = 0;
    char msg[100];

    MPI_Status status;

    MPI_Init(&argc, &argv);

    MPI_Comm_size(MPI_COMM_WORLD, &numprocs); //共启动几个进程
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);  //当前进程的编号（0～n-1）

    printf("I'm %d of %d\n", myid, numprocs);
    if (myid != 0)
    {
        int len = sprintf(msg, "hello from %d", myid);
        MPI_Send(msg, len, MPI_CHAR, 0, msg_tag, MPI_COMM_WORLD); //向id=0的进程发送信息
    }
    else
    {
        for (source = 1; source < numprocs; source++)
        {
            //从id=source的进程接受消息
            MPI_Recv(msg, 100, MPI_CHAR, source, msg_tag, MPI_COMM_WORLD, &status);
            printf("from %d: %s\n", source, msg);
        }
    }

    MPI_Finalize();
    return 0;
}

#include <stdio.h>
#include <mpi.h>

int is_lp(long long x)
{
    long long t = x * x, i = 10;
    while (i < t)
    {
        long long l = t / i, r = t % i;
        if (l + r == x)
            return 1;
        i *= 10;
    }
    return 0;
}

int main(int argc, char *argv[])
{
    int myid, numprocs, source;
    const int N = 100000000;

    MPI_Status status;

    MPI_Init(&argc, &argv);
    MPI_Comm_rank(MPI_COMM_WORLD, &myid);
    MPI_Comm_size(MPI_COMM_WORLD, &numprocs);

    printf("I'm %d of %d\n", myid, numprocs);
    int start = myid * (N / numprocs), stop = (myid + 1) * (N / numprocs);
    if (myid == numprocs - 1)
        stop = N;
    printf("start from %d to %d\n", start, stop);
    int ans = 0, i;
    for (i = start; i < stop; i++)
        if (is_lp(i))
            ans += 1;
    printf("%d finished calculation with %d numbers\n", myid, ans);

    if (myid != 0)
    {
        MPI_Send(&ans, 1, MPI_INT, 0, 0, MPI_COMM_WORLD);
    }
    else
    {
        int tmp;
        for (source = 1; source < numprocs; source++)
        {
            MPI_Recv(&tmp, 1, MPI_INT, source, 0, MPI_COMM_WORLD, &status);
            printf("from %d: %d\n", source, tmp);
            ans += tmp;
        }
        printf("final ans: %d\n", ans);
    }

    MPI_Finalize();
    return 0;
}

void rand_factor()
{
    //randomization
    const int factor = 100;
    int r, t, i;
    for (i = n / factor; i > 0; i--)
    {
        r = rand() % n;
        t = a[0], a[0] = a[r], a[r] = t;
    }
}