Posted on | In , |
Words count in article: 215 | Reading time ≈ 1

Given a string, your task is to count how many palindromic substrings in this string.

The substrings with different start indexes or end indexes are counted as different substrings even they consist of same characters.

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

Input: "abc"
Output: 3
Explanation: Three palindromic strings: "a", "b", "c".
 

Example 2:

Input: "aaa"
Output: 6
Explanation: Six palindromic strings: "a", "a", "a", "aa", "aa", "aaa".

DP

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
32
33
class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        boolean[][] isP = new boolean[n][n];
        
        for(int i=0; i<n; i++)
            isP[i][i] = true;
        
        for(int i=0; i<n-1; i++)
            isP[i][i+1] = s.charAt(i) == s.charAt(i+1);
        
        int len = 3;
        while(len <= n)
        {
            for(int i=0; i<=n-len; i++)
            {
                isP[i][i+len-1] = isP[i+1][i+len-2] && s.charAt(i) == s.charAt(i+len-1);
                
            }
            len++;
        }
        int count = 0;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(isP[i][j]) count++;
        
        return count;
    }
}

Posted on | In , |
Words count in article: 154 | Reading time ≈ 1

Given a collection of distinct integers, return all possible permutations.

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

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

试探回溯法

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
class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> pms = new ArrayList<>();
        rP(nums, new boolean[nums.length], new ArrayList<Integer>(), pms);
        return pms;
    }
    
    void rP(int[] nums, boolean[] set, List<Integer> pm, List<List<Integer>> pms)
    {
        if(pm.size() == nums.length)
        {
            pms.add(pm);
            return;
        }
        
        for(int i=0; i<nums.length; i++)
        {
            if(set[i]) continue;
            set[i] = true;
            List<Integer> currPm = new ArrayList<>(pm);
            currPm.add(nums[i]);
            rP(nums, set, currPm, pms);
            set[i] = false;
        }
    }
}

Posted on | In , |
Words count in article: 908 | Reading time ≈ 4

试探回溯法

八皇后

国际象棋中皇后的势力范围服盖其所在的水平线、垂直线以及两条对角线。

在n x n 的棋盘上放置n个皇后，如何使得她们彼此互不攻击。

皇后

皇后是组成期盼和最终解得基本单元。

1
2
3
4
5
6
7
8
9
10
struct Queen{
    int x, y;
    Queen (int xx = 0, int yy = 0) : x (xx), y (yy) {};
    bool operator== ( Queen const& q ) const {
        return (x == q.x) || (y == q.y) || (x + y == q.x + q.y) || (x - y == q.x - q.y);
    }
    bool operator!= ( Queen const& q ) const {
        return !(*this == q);
    }
}

既然每行能且仅能放置一个皇后，故不妨首先将各皇后分配至每一行。然后，从空棋盘开始，逐个尝试着将她们放置到无冲突的某列。每放置好一个皇后，才继续试探下一个。若当前皇后在任何列都会造成冲突，则后续皇后的试探都必将是徒劳，故此时应该回溯到上一皇后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void placeQueens(int N){
    Stack<Queen> solu;
    Queen q(0,0);
    do{
        if(N <= solu.size() || N <= q.y)
        {
            q = solu.pop(); q.y++;
        }
        else
        {
            while((q.y < N) && (0 <= solu.find(q)))
            {
                q.y++; nCheck++;
            }
            if(N > q.y)
            {
                solu.push(q);
                if(N <= solu.size())  nSolu++;
                q.x++; q.y = 0;
            }
        }
    }while((0 < q.x) || (q.y < N));
}

迷宫寻径

在任意指定的起始格点与目标格点之间，找出一条通路（如果存在）

迷宫格点：

格点是迷宫的基本组成单位，首先实现Cell类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
typedef enum {AVAILABLE, ROUTE, BACKTRACKED, WALL } Status;//迷宫单元状态
// 原始可用的，在当前路径上的，所有方向均尝试失败之后回溯过的，不可使用的（墙）

typedef enum {UNKNOWN, EAST, SOUTH, WEST, NORTH, NO_WAY} ESWN; //单元的相对邻接方向
// 未定、东、南、西、北、无路可通

inline ESWN nextESWN( ESWN eswn ) { return ESWN ( eswn + 1 ); } //依次转到下一邻接方向

struct Cell {
    int x, y; // x, y 坐标
    Status status; // 类型
    ESWN incoming, outgoing; //进入、走出方向
}

#define LABY_MAX 24 //最大迷宫尺寸
Cell laby[LABY_MAX][LABY_MAX]; // 迷宫

邻格查询：

1
2
3
4
5
6
7
8
9
inline Cell* neighbor ( Cell* cell ) {
    switch (Cell->outgoing){
        case EAST : return cell + LABY_MAX;
        case SOUTH: return cell + 1;
        case WEST: return cell - LABY_MAX;
        case NORTH: return cell - 1;
        default : exit (-1);
    }
}

邻格转入：

1
2
3
4
5
6
7
8
9
10
11
inline Cell* advance ( Cell* cell ) { //从当前位置转入相邻格点
    Cell* next;
    switch ( cell->outgoing ) {
       case EAST:  next = cell + LABY_MAX; next->incoming = WEST;  break; //向东
       case SOUTH: next = cell + 1;        next->incoming = NORTH; break; //向南
       case WEST:  next = cell - LABY_MAX; next->incoming = EAST;  break; //向西
       case NORTH: next = cell - 1;        next->incoming = SOUTH; break; //向北
       default : exit ( -1 );
    }
    return next;
}

算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 迷宫寻径算法：在格单元s至t之间规划一条通路（如果的确存在）
bool labyrinth ( Cell Laby[LABY_MAX][LABY_MAX], Cell* s, Cell* t ) {
   if ( ( AVAILABLE != s->status ) || ( AVAILABLE != t->status ) ) return false; //退化情况
   Stack<Cell*> path; //用栈记录通路（Theseus的线绳）
   s->incoming = UNKNOWN; s->status = ROUTE; path.push ( s ); //起点
   do { //从起点出发不断试探、回溯，直到抵达终点，或者穷尽所有可能
      Cell* c = path.top(); //检查当前位置（栈顶）
      if ( c == t ) return true; //若已抵达终点，则找到了一条通路；否则，沿尚未试探的方向继续试探
      while ( NO_WAY > ( c->outgoing = nextESWN ( c->outgoing ) ) ) //逐一检查所有方向
         if ( AVAILABLE == neighbor ( c )->status ) break; //试图找到尚未试探的方向
      if ( NO_WAY <= c->outgoing ) //若所有方向都已尝试过
         { c->status = BACKTRACKED; c = path.pop(); }//则向后回溯一步
      else //否则，向前试探一步
         { path.push ( c = advance ( c ) ); c->outgoing = UNKNOWN; c->status = ROUTE; }
   } while ( !path.empty() );
   return false;
}

Posted on | In |
Words count in article: 152 | Reading time ≈ 1

递归算法求斐波那契数列的第n项

1
2
3
4
5
6
7
8
9
int Fibonacci(int n)
{
    if(n <= 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return Fibonacci(n-1) + Fibonacci(n-2);
}

有没有更好的算法？

递推关系式的优化：

用一个数组存储所有已经计算过的项

求解通项公式：

公式引入无理数，不能保证结果的精度

分治

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Matrix; 

Matrix MatrixPow( const Matrix& m, int n)
{
    Matrix result = Matrix::Identity;
    Matrix tmp = m;
    for(; n; n >>= 1)
    {
        if(n & 1)
            result  *= tmp;
            tmp *= tmp;
    }
}

int Fibonacci (int n){
    Matrix an = MatrixPow(A, n-1);
    return F1 * an(0,0) + F0 * an(1,0);
}

Posted on | In |
Words count in article: 1.5k | Reading time ≈ 9

1
1

index.css

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
* {
    box-sizing: border-box;
    -moz-box-sizing:border-box; 
}

h1{
    transition: 2s;
}

h1:hover{
    transform: scale(1.1);
}

.head {
    padding: 20px;
    text-align: center;
    font-size: 22pt;
    background: #EE9A00;
    color: white;
    font-family: sans-serif;
}

.menu {
    overflow: hidden;
    background-color: #333;
}

.menu a {
    float: left;
    display: block;
    color: white;
    text-align: center;
    padding: 8px 20px;
    text-decoration: none;
}

.menu a:hover {
    background-color: #ddd;
    color: black;
}

.content {  
    display: -ms-flexbox; 
    display: flex;
    -ms-flex-wrap: wrap; 
    flex-wrap: wrap;
}

.leftt {
    -ms-flex: 25%; 
    flex: 25%;
    background-color: #BBBBBB;
    padding: 20px;
}

.leftt p{
	font-size: 22pt;
    color: white;
    font-family: sans-serif;
}

.leftt p:hover {
    color: #FF9F0F;
}

.leftt img{
    transition: 2s;
}

.leftt img:hover{
    transform: scale(1.1);
}

.rightt {   
    -ms-flex: 75%; 
    flex: 75%;
    background-color: #f1f1f1;
    padding: 20px;
}

.rightt a{
	font-size: 15pt;
    font-family: sans-serif;
    color: black;
}

.rightt a:hover {
    color: #FF7F00;
}

.week2 ul{
	list-style-image: url('http://courses.cs.washington.edu/courses/cse190m/09sp/homework/1/pie_icon.gif');
	list-style-type: none;
}

index.html

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
<!DOCTYPE html>
<html lang="en">
	<head>
		<title>Index of Homework</title>
		<meta name="description" content="index of homework" />
		<meta http-equiv="content-type" content="text/html; charset=UTF-8">
		<link rel="stylesheet" type="text/css" href="index.css">
		<link href="https://timgsa.baidu.com/timg?image&quality=80&size=b9999_10000&sec=1567590043834&di=eb8b284c4cf45cadbd526bfe14d54772&imgtype=0&src=http%3A%2F%2Fku.90sjimg.com%2Felement_origin_min_pic%2F18%2F02%2F18%2F597a908f980e964090d3eb910f39acf3.jpg%2521%2Ffwfh%2F804x804%2Fquality%2F90%2Funsharp%2Ftrue%2Fcompress%2Ftrue" type="image/gif" rel="shortcut icon" />
		
	</head>

	<body>
		<div class="head">
		  <h1>Homework Of Web2.0</h1>
		</div>

		<div class="menu">
		  <a href="https://www.google.com">Google</a>
		  <a href="https://www.baidu.com/">Baidu</a>
		  <a href="http://validator.w3.org/">HTML</a>
		  <a href="http://jigsaw.w3.org/css-validator/">CSS</a>
		</div>

		<div class="content">
		  <div class="leftt">
		      <div align="center">
		      	<img src="https://wx4.sinaimg.cn/mw690/c79a1380gy1g6npxzglzzj20j70j8wft.jpg" width="280px" height="280px" />
		      	<p> Homework Index Of <br /> Zhuomin Zheng</p>
		      </div>
		  </div>
		  <div class="rightt">
		  		<div class="week2">
			      <h2>Week2:</h2>
			      	<ul>
			      		<li> <a href="pie.html"> A Recipe Of Grandma's Lemon Meringue Pie </a> </li>
			      	</ul>
			    </div>
		      	<div class="week3">
			      <h2>Week3:</h2>
			    </div>
			    <div class="week4">
			      <h2>Week4:</h2>
			    </div>
			    <div class="week5">
			      <h2>Week5:</h2>
			    </div>
			    <div class="week6">
			      <h2>Week6:</h2>
			    </div>
		  </div>
		</div>

	</body>
</html>

pie.css

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
body{
	background-image: url('http://courses.cs.washington.edu/courses/cse190m/09sp/homework/1/silverware.jpg');

}

h1, h2{
	letter-spacing: 0.2em;
	background-color: #F0F0F0;
	color: #A4A400;
	font-family: "Century Gothic", "Futura", "Verdana", "sans-serif";
	text-decoration: underline;
}

h1{
	font-size: 22pt;
	font-weight: bold;
	text-align: center;
}

h2{
	text-align: left;
	font-size: 18pt;
	font-weight: normal;
}

p, li, blockquote, a{
	color:  #404040;
	font-size: 11pt;
	font-family: "Georgia", "Garamond", "sans-serif";
}


ul{
	list-style-image: url('http://courses.cs.washington.edu/courses/cse190m/09sp/homework/1/pie_icon.gif');
	list-style-type: none;
}

a{
	color: #A4A400;

}

blockquote{
	background-color: #FFFFC8;
}

hr{
	border: none;
	border-top:2pt solid #D3D3D3;
}

pie.html

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
<!DOCTYPE html>
<html lang="en">
	<head>
		<title>Grandma's Lemon Meringue Pie</title>
		<meta name="description" content="homework of web2.0" />
		<meta http-equiv="content-type" content="text/html; charset=UTF-8">
		<link rel="stylesheet" type="text/css" href="recipe.css">
		<link href="http://courses.cs.washington.edu/courses/cse190m/09sp/homework/1/pie_icon.gif" type="image/gif" rel="shortcut icon" />
	</head>

	<body>
		<h1> Grandma's Lemon Meringue Pie </h1>

		<hr />
		<div>
			<img src="http://courses.cs.washington.edu/courses/cse190m/09sp/homework/1/pie.jpg" alt="Grandma's Pie" />
			<p> One 9-inch pie <br />
			 30 Min - Prep time <br />
			 10 Min - Cook time <br />
			 40 Min - Total <br />
			 8 Servings </p>
		</div>

		<hr />

		<h2> INGREDIENTS </h2>

		<div>
			<ul>
				<li> 1 cup white sugar </li>
				<li> 2 tablespoons all-purpose flour </li>
				<li> 3 tablespoons cornstarch </li>
				<li> 1/4 teaspoon salt </li>
				<li> 1 1/2 cups water </li>
				<li> 2 lemons, juiced and zested </li>
				<li> 2 tablespoons butter </li>
				<li> 4 egg yolks, beaten </li>
				<li> 1 (9 inch) pie crust, bakes </li>
				<li> 4 egg whites</li>
				<li> 6 tablespoons white sugar </li>
			</ul>
		</div>

		<hr />

		<h2> DIRECTIONS </h2>

		<div>
			<ol>
				<li> <strong>Preheat Oven</strong>: Preheat oven to 350 degrees F(175 degrees C). </li>
				<li> <strong> Make Lemon Filling:</strong> In a medium saucepan ...
					<ul>
						<li> Whisk together 1 cup sugar, flour, cornstarch, and salt. </li>
						<li> Stir in water, lemon juice and lemon zest. </li>
						<li> Cook over medium-high heat, stirring frequently, until mixture comes to a boil. </li>
						<li> Stir in butter. </li>
						<li> Place egg yolks in a small bowl and gradually whisk in 1/2 cup of hot sugar mixture. </li>
						<li> Whisk egg yolk mixture back into remaining sugar mixture. </li>
						<li> Bring to a boil and continue to cook while stirring constantly until thick. </li>
					</ul>
				</li>
				<li> <strong>  Make Meringue:</strong> In a large glass or metal bowl...
					<ul>
						<li> Whip egg whites until foamy. </li>
						<li> Add sugar gradually, and continue to whip until stiff peaks form. </li>
						<li> Spread meringue over pie, sealing the edges at the crust. </li>
					</ul>
				</li>
				<li> <strong>Bake ：</strong>Bake in preheated oven for 10 minutes, or until meringue is golden brown. </li>
			</ol>
		</div>

		<hr />

		<h2> USER COMMENTS</h2>

		<div>
			<blockquote >
				<em>
					This is a very fun recipe to follow, because Grandma makes it sweet and simple. This pie is thickened with cornstarch and flour in addition to egg yolks, and contains no milk.
					<br /><br />
					- Emilie S.
				</em>
			</blockquote>
			<blockquote >
				<em>
					Q: What do you call an ape who loves pie?
					<br />
					A: A meringue-utan.
					<br /><br />
					- Vickie K.
				</em>
			</blockquote>
		</div>

		<hr />
		<h2> LINKS </h2>

		<div>
			<a href=" https://www.google.com.hk/search?q=lemon+meringue+pie+recipe"> Search for other lemon meringue pie recipes </a><br />
			<a href="index.html"> Home </a><br /><br />
			<a href="http://validator.w3.org/check/referer">
				<img src="http://www.w3.org/Icons/valid-xhtml11" alt="html"/> 
			</a>
			<a href="http://jigsaw.w3.org/css-validator/check/referer">
				<img src="http://jigsaw.w3.org/css-validator/images/vcss" alt="css"/>
			</a>
		</div>
	</body>
</html>

Posted on | In |
Words count in article: 77 | Reading time ≈ 1

任给定一个正整数N， 求一个最小的正整数M(M > 1) ， 使得N * M 的十进制表示形式里只含有1 和0

题意转换：

求一个最小的正整数X， 使得X的十进制表示形式里只含有1和0， 并且X被N整除

Posted on | In |
Words count in article: 722 | Reading time ≈ 3

求两个正整数的最大公约数Greatest Common Divisor,GCD。

如果两个正整数都很大，有什么简单的算法？

例如求1 100 100 210 001 和 120 200 021 的最大公约数

解法一：

辗转相除法

假设用f(x,y)表示x,y的最大公约数，取k = x/y, b = x%y, 则x = ky + b， 如果一个数能够同时整除x和y，则必能同时整除b和y，而能同时整除b和y的数也必能同时整除x和y，即x和y的公约数与b和y的公约数是相同的，其最大公约数也是相同的。

则有f(x,y) = f(y, x%y) (x >= y > 0)

1
2
3
4
int gcd(int x, int y)
{
    return (!y)? x:gcd(y, x%y);
}

解法二：

对于大整数而言，取模运算（其中用到除法）是非常昂贵的开销，有没有办法能不用取模运算？

采用类似前面辗转相除法的分析，如果一个数能够同时整除x和y，则必能同时整除x-y和y；而能够同时整除x-y和y的数也必能同时整除x和y，即x和y的公约数与x-y和y的公约数是相同的，其最大公约数也是相同的，即f(x,y) = f(x-y, y), 那么就可以不再需要进行大整数的取模运算，而转换成简单得多的大整数的减法。

在实际操作中，如果x < y, 可以先交换(x, y)，从而避免求一个正数和一个负数的最大公约数，一直迭代下去，知道其中一个数为0

1
2
3
4
5
6
7
8
9
BigInt gcd(BigInt x, BigInt y)
{
    if(x < y)
        return gcd(y, x);
    if(y == 0)
        return x;
    else
        return gcd(x-y, y);
}

代码中BigInt是自己实现的一个大整数类。

这个算法免去了大整数触发的繁琐，但是同样有不足之处，最大的瓶颈就是迭代的次数比之前多了很多。

解法三：

能否结合解法一和解法二，得到一个更佳的算法

对于y 和x 来说， 如果y = k*y1, x = k*x1。 那么有f(y, x) = k*f(y1, x1)。

另外，如果x = p x1, 假设p是素数，并且y%p！=0（即y不能被p整除），那么f(x, y) = f(px1, y) = f(x1, y)

因此：最简单的方法是，2是一个素数，同时对于二进制表示的大整数而言，可以很容易地将除以2和乘以2地运算转化为移位运算，从而避免大整数触发，由此就可以利用2来进行分析。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
BigInt gcd(BigInt x, BigInt y)
{
    if(x < y)
        return gcd(y, x);
    if(y == 0)
        return x;
    else
    {
        if(IsEven(x))
        {
            if(IsEven(y))
                return (gcd(x >> 1, y >> 1) << 1);
            else
                return gcd(x >> 1, y);
        }
        else
        {
            if(IsEven(y))
                return gcd(x, y >> 1);
            else
                return gcd(y, x-y);
        }
    }
}

Posted on | In |
Words count in article: 305 | Reading time ≈ 1

给定一个有限小数或无限循环小数，你能否以分母最小的分数形式来返回这个小数呢？如果输入为循环小数，循环节用括号标记出来。下面是一些可能的输入数据，如0.3、0.30、0.3（000）、0.3333（3333）、。。。

解法：

从最简单的情况入手，因为所有的小数都可以分解成一个整数和一个纯小数之和，不妨只考虑大于0、小于1的纯小数，且暂时不考虑分子和分母的约分。

对于有限小数X = 0.a1a2a3….an，X就等于(a1a2a3…an)/10^n

对于无限循环小数X = 0.a1a2a3…an(b1b2…bm)来说，做如下转换

X = 0.a1a2…an(b1b2…bm)

-> 10^n* X = a1a2…an.(b1b2…bm)

-> X = (a1a2..an + 0.(b1b2..bm))/10^n

令Y = 0.(b1b2…bm)

10^m * Y = b1b2…bm.(b1b2..bm)

-> 10^m * Y - Y = b1b2…bm

-> Y = b1b2…bm/(10^m - 1)

代入Y进X

X = (a1a2…an + Y) / 10^n

= ((a1a2…an)(10^m-1) + (b1b2…bm))/((10^m-1)\10^n)

至此便得到任意一个小数的分数表示，但是此时分母未必是最简的，应对分子分母约分，就是求分子分母的最大公约数。再约分

Posted on | In |
Words count in article: 665 | Reading time ≈ 2

有很多个无序的数，姑且假定它们个不相等，怎么选出其中最大的若干个数呢？

解法一：

我们先假设元素的数量不大，例如在几千个左右，在这种情况下，我们就排序吧。快速排序和堆排序都是不错的选择，他们的平均时间复杂度都是O(N*log_2N)，然后取出前K个，O(K)。总时间复杂度就是前两者相加得O(N*log_2N)

题目只要求最大的K个数，并不需要前K个数有序，也不需要后N-K个数有序。

如何避免做后N-K个数的排序呢？ 我们需要部分排序算法，选择排序和交换排序（冒泡排序）都是不错的选择，把N个数中的前K个数排序出来，复杂度是O(N*K)

哪一个更好呢？O(N*log_2N)还是O(N*K)？这取决于K的大小。在K（K<=log2N）较小的情况下，可以选择部分排序。

解法二：

在快速排序中，每一步都是将待排数据分成两组，其中一组数据的任何一个数都比另一组中的任何数大，再对两组分别做类似的操作。。。

假设N个数存储在数组S中，我们从数组S中随机找出一个元素X，把数组分为两部分Sa和Sb。Sa中的元素大于等于X，Sb中的元素小于X

这时有两种情况：

  1. Sa中元素的个数小于K，Sa中的所有数和Sb中最带的K-|Sa|个元素就是数组S中最大的K个数

  2. Sa中元素的个数大于或等于K，则返回Sa中最大的K个元素。

递归，平均复杂度为O(N*log2K)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//伪代码
Kbig(S, K):
    if(k <= 0):
        return []
    if(length S <= K):
        return S
    (Sa, Sb) = Partition(S)
    return Kbig(Sa, k).Append(Kbig(Sb, k - Sa.length))

Partition(S):
    Sa = []
    Sb = []
    Swap(S[1], S[Random() % S.length])

    p = S[1]
    for i in [2:S.length]:
        S[i] > p ? Sa.Append(S[i]) : Sb.Append(S[i])

    Sa.length < Sb.length ? Sa.Append(p) : Sb.Append(p)
    return (Sa, Sb)

解法三：

寻找N个数中最大的K个数，本质上就是寻找最大的K个数中最小的那个，也就是第K大的数，可以使用二分搜索的策略。

对于一个给定的数p，可以在O（N）时间复杂度内找出所有不小于p的数，假如N个数中最大的数为Vmax，最小的数为Vmin，那么这N个数中的第K大数一定在区间Vmin~Vmax之间，那么可以在这个却见内二分搜索N个数中的第K大数p

Posted on | In |
Words count in article: 1.1k | Reading time ≈ 4

https://baike.baidu.com/item/%E6%9C%89%E6%95%88%E6%95%B0%E5%AD%97/406066?fr=aladdin

舍入规则

1．当保留n位有效数字，若第n+1位数字≤4就舍掉。

2．当保留n位有效数字，若第n+1位数字≥6时，则第n位数字进1。

3．当保留n位有效数字，若第n+1位数字=5且后面数字为0时 ，则第n位数字若为偶数时就舍掉后面的数字，若第n位数字为奇数时加1；若第n+1位数字=5且后面还有不为0的任何数字时，无论第n位数字是奇或是偶都加1。

以上称为“四舍六入五留双”

如将下组数据保留一位小数：

45.77≈45.8；43.03≈43.0；0.26647≈0.3；10.3500≈10.4；

38.25≈38.2；47.15≈47.2；25.6500≈25.6；20.6512≈20.7

有效数字

从一个数的左边第一个非0数字起，到末位数字止，所有的数字都是这个数的有效数字。

就是一个数从左边第一个不为0的数字数起到末尾数字为止，所有的数字（包括0，科学计数法不计10的N次方），称为有效数字。简单的说，把一个数字前面的0都去掉，从第一个正整数到精确的数位止所有的都是有效数字了。

如：0.0109，前面两个0不是有效数字，后面的109均为有效数字（注意，中间的0也算）。

3.109*10^5（3.109乘以10的5次方）中，3 1 0 9均为有效数字，后面的10的5次方不是有效数字。

5.2*10^6，只有5和2是有效数字。

0.0230，前面的两个0不是有效数字，后面的230均为有效数字（后面的0也算）。

1.20 有3个有效数字。

1100.120 有7位有效数字。

2.998*10^4（2.998乘以10的4次方）中，保留3个有效数字为3.00*10^4。

对数的有效数字为小数点后的全部数字，如log x=1.23有效数字为2.3，log a=2.045有效数字为0、4.5，pH=2.35有效数字为3.5。

整体遵循“四舍五入”的方法

计算规则

加减法

以小数点后位数最少的数据为基准，其他数据修约至与其相同，再进行加减计算，最终计算结果保留最少的位数。

例：计算50.1+1.45+0.5812=

修约为：50.1+1.5+0.6=52.1

乘除法

以有效数字最少的数据为基准，其他有效数修约至相同，再进行乘除运算，计算结果仍保留最少的有效数字。

例：计算0.0121×25.64×1.05728=

修约为：0.0121×25.6×1.06=

计算后结果为：0.3283456，结果仍保留为三位有效数字。

记录为：0.0121×25.6×1.06=0.328

例：计算2.5046×2.005×1.52=

修约为：2.50×2.00×1.52=

当把1.13532×10⒑保留3个有效数字时，结果为1.14×10⒑

运算中若有π、e等常数，以及√2.1/2等系数，其有效数字可视为无限，不影响结果有效数字的确定。

一般来讲，有效数字的运算过程中，有很多规则.为了应用方便，本着实用的原则，加以选择后，将其归纳整理为如下两类。

一般性入手规则

⑴可靠数字之间运算的结果为可靠数字。

⑵可靠数字与存疑数字，存疑数字与存疑数字之间运算的结果为存疑数字。

⑶测量数据一般只保留一位存疑数字。

⑷运算结果的有效数字位数不由数学或物理常数来确定，数学与物理常数的有效数字位数可任意选取，一般选取的位数应比测量数据中位数最少者多取一位.例如：π可取=3.14或3.142或3.1416……；在公式中计算结果不能由于”2”的存在而只取一位存疑数字，而要根据其他数据来决定。

⑸运算结果将多余的存疑数字舍去时应按照”四舍五入”的法则进行处理.即小于等于四则舍；大于五则入；等于五时，根据其前一位按奇入偶舍处理（等几率原则）。例如，3.625化为3.62，4.235则化为4.24。