Pygame

理解Pygame

• • Python最经典的2D游戏开发第三方库，也支持3D游戏开发
• • Pygame适合用于游戏逻辑验证、游戏入门及系统演示验证
• • Pygame是一种游戏开发引擎，基本逻辑具有参考价值
• • Pygame有些”过时”，但永远”不过时”
• • 使用Pygame可以开发出优秀的游戏！

Given a string containing just the characters ‘(‘ and ‘)’, find the length of the longest valid (well-formed) parentheses substring.

1
2
3
4
5
6
7
8
9
10

Example 1:

Input: "(()"
Output: 2
Explanation: The longest valid parentheses substring is "()"
Example 2:

Input: ")()())"
Output: 4
Explanation: The longest valid parentheses substring is "()()"

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

The cache is initialized with a positive capacity.

Follow up:

Could you do both operations in O(1) time complexity?

1
2
3
4
5
6
7
8
9
10
11
12
13

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

Example 1:

Input: [1,2,3]

       1
      / \
     2   3

Output: 6
Example 2:

Input: [-10,9,20,null,null,15,7]

   -10
   / \
  9  20
    /  \
   15   7

Output: 42

Pandas数据特征分析

Pandas库的数据排序

Pandas库入门

• Pandas是Python第三方库，提供高性能易用数据类型和分析工具
• import pandas as pd

• Pandas基于NumPy实现，常与NumPy和Matplotlib一同使用

• 两个数据类型：Series, DataFrame

• 基于上述数据类型的各类操作
• 基本操作、运算操作、特征类操作、关联类操作
  Read more »

Windows下C语言多线程函数_beginthread简单入门

_ beginthread、_beginthreadex 两个函数是Windows下C语言推荐使用的创建多线程的函数，简单的说，_beginthread函数很简单，就是创建一个后台线程并即刻执行，直到运行结束或者调用_endthread函数终止线程。缺点就是你没法很好的控制由_beginthread函数创建的线程，因为它没有任何返回值给你用来后续的控制，它创建完成后立马就执行了，由不得你控制。

_beginthreadex则是_beginthread的升级版，形参更多，可控性更好，可以实现线程的同步，适用范围更加广。因此也更加复杂。

_beginthread函数有三个形参，函数原型如下：

1
2
3
4
5

uintptr_t _beginthread( 
   void( __cdecl *start_address )( void * ),  
   unsigned stack_size,  
   void *arglist   
);

• 第一个参数：start_address为启动开始执行新线程的例程的地址，一般我们执行一个函数，这个参数就是你定义的函数名。

• 第二个参数：stack_size，新线程的堆栈大小或 0。一般我们使用0，代表跟主线程使用一样的堆栈。

• 第三个参数：arglist，要传递到新线程的参数列表或 NULL。如果你要传递参数给新的线程，可以在这里写上参数的地址指针，如果不需要传递数据，就使用NULL。

实例：

注意：需要包含头文件process.h，否则编译出错。使用Sleep函数延时的还需加入windows.h头文件

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

例子一：不需要传递参数的情形

#include <stdio.h>
#include <windows.h>
#include <process.h>

int a = 0; //全局变量

//自定义的函数，在新的线程中执行
void fun1(void *){//形参void * 不可省略，否则编译出错
        while(1){
        a++;
        if(a>=10) break;
        Sleep(200);
        printf("a = %d, 线程运行中...\n", a);
    } 
    printf("新建的后台线程结束\n\n");
    _endthread();
}
int main(){
    _beginthread(fun1,0,NULL);
    while(1){
        if(a >= 10){
            printf("主线程执行完毕\n");
            break;
        }
    }
    return 0;
}

我们实现在main主程序当中创建一个新的线程，然后在新的线程当中计数，计数一次延时200毫秒，如果全局变量a达到10就结束新的线程并输出一句话提醒。在新的线程运行过程中，主线程在创建新的线程之后，就不停地检查全局变量a的值，如果等于10就退出循环，结束主线程。特别提醒的，这里我们可以使用全局变量的方式来进行线程间的通信，非常简单，只需要注意全局变量a定义的位置就好。

要在主线程当中传递参数给新线程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

#include <stdio.h>
#include <windows.h>
#include <process.h>

int a = 0; //全局变量

void fun2(void *pArg){
    printf("主线程传递进来的值是：%d\n\n", *(int *)pArg);
    a = *(int *)pArg;
    while(1){
        a++;
        if(a>=10) break;
        Sleep(200);
        printf("a = %d, 线程运行中...\n", a);
    } 
    printf("新建的后台线程结束\n\n");
    _endthread();
}

int main(){
    int b = 5;
    int* arg = &b;
    _beginthread(fun2, 0, (void *)arg);
    while(1){
        if(a >= 10){
            printf("主线程执行完毕\n");
            break;
        }
    }
    return 0;
}

在这个例子当中，我们在主线程当中传入一个参数给新建的线程，然后在新的线程中将传入的数值赋给全局变量a再进行计数。特别需要注意的是，使用_beginthread创建线程时候，传递的参数必须是void 型的指针值，实际使用的时候，我们就需要用到强制类型转换了，否则会无法编译通过。传入参数的时候强制转换为void 型，在新线程中取出来使用的时候就再次强制类型转换，变成原来的函数类型。总之，传入的就是主函数定义的参数的地址指针，使用过程中需要注意转换。

中国剩余定理

分治算法

分而治之

分治法所能解决的问题一般具有以下几个特征：

1) 该问题的规模缩小到一定的程度就可以容易地解决

2) 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。

3) 利用该问题分解出的子问题的解可以合并为该问题的解；

4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。

分治法在每一层递归上都有三个步骤：

step1 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题；

step2 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题

step3 合并：将各个子问题的解合并为原问题的解。

实际上就是类似于数学归纳法，找到解决本问题的求解方程公式，然后根据方程公式设计递归程序。

1、一定是先找到最小问题规模时的求解方法
2、然后考虑随着问题规模增大时的求解方法
3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。

应用：

大整数相乘: