发表于

rdd数据倾斜解决方案

  1. 聚合源数据
  2. 过滤导致倾斜的key
  3. 提高shuffle并行度：spark.sql.shuffle.partitions
  4. 双重groupby
  5. reduce join转换为map join spark.sql.autoBroadcastJoinThreshold
  6. 采样倾斜key并单独进行join
  7. 随机key与扩容表


  1. 聚合源数据：Spark core 和Spark SQL没有区别
  2. 过滤导致倾斜的key: SQL用where过滤
  3. 提高shuffle并行度 : groupByKey(1000),spark.sql.shuffle.partitions
  4. 双重groupby: 改写SQL,两次groupby
  5. reduce join转换为map join: spark.sql.autoBroadcastJoinThreshold
  6. 采样倾斜key并单独进行join: 强Spark Core的一种方式，sample、filter等算子
  7. 随机key与扩容表

发表于 | 分类于 
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
class ListNode:
	def __init__(self,x):
		self.val = x
		self.next = None

def reverse(head):
	if head == None or head.next == None:
		return head
	pre = None
	cur = head
	h = head
	while cur:
		h = cur
		tmp = cur.next
		cur.next = pre
		pre = cur
		cur = tmp
	return h

head = None
tmp = head
for i in xrange(1,10):
	if head == None:
		head = ListNode(i)
		tmp = head
	else:
		tmp.next = ListNode(i)
		tmp = tmp.next
tmp = head
while tmp:
	print tmp.val
	tmp = tmp.next

head = reverse(head)
print '----------'
tmp = head
while tmp:
	print tmp.val
	tmp = tmp.next

发表于 | 分类于

#快速排序算法，简称快排，是最实用的排序算法，没有之一

一行代码的版本：

1
quick_sort = lambda array: array if len(array) <= 1 else quick_sort([item for item in array[1:] if item <= array[0]]) + [array[0]] + quick_sort([item for item in array[1:] if item > array[0]])

正常的快排：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort(array, left, right):
    if left >= right:
        return
    low = left
    high = right
    key = array[low]
    while left < right:
        while left < right and array[right] > key:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] <= key:
            left += 1
        array[right] = array[left]
    array[right] = key
    quick_sort(array, low, left - 1)
    quick_sort(array, left + 1, high)

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
public static int partition(int []array,int lo,int hi){
        //固定的切分方式
        int key=array[lo];
        while(lo<hi){
            while(array[hi]>=key&&hi>lo){//从后半部分向前扫描
                hi--;
            }
            array[lo]=array[hi];
            while(array[lo]<=key&&hi>lo){从前半部分向后扫描
                lo++;
            }
            array[hi]=array[lo];
        }
        array[hi]=key;
        return hi;
    }
    
    public static void sort(int[] array,int lo ,int hi){
        if(lo>=hi){
            return ;
        }
        int index=partition(array,lo,hi);
        sort(array,lo,index-1);
        sort(array,index+1,hi); 
    }

发表于

题目

牛牛拿到了一个藏宝图，顺着藏宝图的指示，牛牛发现了一个藏宝盒，藏宝盒上有一个机关，机关每次会显示两个字符串 s 和 t，根据古老的传说，牛牛需要每次都回答 t 是否是 s 的子序列。注意，子序列不要求在原字符串中是连续的，例如串 abc，它的子序列就有 {空串, a, b, c, ab, ac, bc, abc} 8 种。

解法1：

同时互相遍历

解法2：

动态规划

解法3：

正则表达式

1
2
3
4
5
6
7
8
9
10
11
import re
str1 = raw_input()
str2 = raw_input()
item = ""
for i in str2:
    item +=".*"+i
item += ".*"
if re.search(item, str1):
    print("Yes")
else:
    print("No")

发表于

字符串A与B的编辑距离,Edit Distance,是指由A转换为B所需的最少编辑操作次数。编辑操作包括字符的替换、插入与删除。
如kitten(小猫)->sitting（坐）：距离为3.
kitten–>（k→s）–>sitten–> （e→i）–>sittin–>（g）->sitting

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
 
 
 
public class StringDistance {
	int dp[][];// matrix
 
	public int getStringSimilar(String s1, String s2) {
		int n, m;// respective length
		int i, j;// cursor
		n = s1.length();
		m = s2.length();
		 if (n == 0 || m == 0) {
		 return Math.abs(m - n);
		 }
		
		dp = new int[n][m];
		for (i = 0; i < n; i++)
			dp[i][0] = 1 + i;
		for (i = 0; i < m; i++)
			dp[0][i] = 1 + i;
		for (i = 0; i < n; i++) 
			for (j = 0; j < m; j++) 
				if (s1.charAt(i) == s2.charAt(j))
					dp[i][j] = getDP(i - 1, j - 1);
				else
					//注意是min(a,b,c)三个形参
					dp[i][j] = min(getDP(i - 1, j), getDP(i, j - 1), getDP(i-1, j - 1)) + 1;
		return dp[n - 1][m - 1];
	}
 
	private int min(int a, int b, int c) {
		return Math.min(Math.min(a, b),c);
	}
 
	int getDP(int i, int j) {
		if (i <0 && j <0)
			return 0;
		if(i<0)
			return j+1;
		if(j<0)
			return i+1;
		else 
			return dp[i][j];
	}
 
	public static int getStringDistance(String s1, String s2) {
		StringDistance obj = new StringDistance();
		return obj.getStringSimilar(s1, s2);
	}
	public void testGetStringSimilar(){
		assertEquals(3,getStringSimilar("kitten", "sitting"));
	}
	
}

发表于 | 分类于

题目

一闪一闪亮晶晶，满天都是小星星，牛牛晚上闲来无聊，便躺在床上数星星。
牛牛把星星图看成一个平面，左上角为原点(坐标为(1, 1))。现在有n颗星星，他给每颗星星都标上坐标(xi，yi)，表示这颗星星在第x行，第y列。
现在，牛牛想问你m个问题，给你两个点的坐标(a1, b1)(a2，b2)，表示一个矩形的左下角的点坐标和右上角的点坐标，请问在这个矩形内有多少颗星星（边界上的点也算是矩形内）。

输入

星星数

星星坐标(a1,b1)

……

问题数

问题坐标a1,b1,a2,b2

……

思路

输入完所有星星后，遍历整个空间，计算每个点的左下角有多少个星星。在计算矩形面积时，数量为右上角-左上角-右下角+左下角的左下点（减的时候多减了一个左下角）

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
snum = int(raw_input())
star = [[0 for col in range(1001)] for row in range(1001)]
for i in xrange(snum):
    line = raw_input().strip()
    x = int(line.split(' ')[0])
    y = int(line.split(' ')[1])
    star[x][y] +=1
num = [[0 for col in range(1001)] for row in range(1001)]
#用动态规划计算每个点的左下角的星星数量
for i in xrange(1,1001):
    for j in xrange(1,1001):
        num[i][j] = num[i-1][j] + num[i][j-1] + star[i][j] - num[i-1][j-1]


qnum = int(raw_input())
# juxinglist = []
for i in xrange(qnum):
    n = 0
    line = raw_input().strip()
    a1 = int(line.split(' ')[0])
    b1 = int(line.split(' ')[1])
    a2 = int(line.split(' ')[2])
    b2 = int(line.split(' ')[3])
    #计算矩形内的星星数量
    print num[a2][b2] - num[a1-1][b2] - num[a2][b1-1]  + num[a1-1][b1-1]

发表于

题目

有 n 个学生站成一排，每个学生有一个能力值，想从这 n 个学生中按照顺序选取 k 名学生，要求相邻两个学生的位置编号的差不超过 d，使得这 k 个学生的能力值的乘积最大，你能返回最大的乘积吗？

输入描述

每个输入包含 1 个测试用例。每个测试数据的第一行包含一个整数 n (1 <= n <= 50)，表示学生的个数，接下来的一行，包含 n 个整数，按顺序表示每个学生的能力值 ai（-50 <= ai <= 50）。接下来的一行包含两个整数，k 和 d (1 <= k <= 10, 1 <= d <= 50)。

输出描述

输出一行表示最大的乘积。

例子

3

7 4 7

2 50

输出

49

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
n = int(raw_input().strip())

line = raw_input().strip().split(' ')

line2 = raw_input().strip()
arr = []
for l in line:
    arr.append(int(l))

getnum = int(line2.split(' ')[0])
maxspace = int(line2.split(' ')[1])


maxresult = 0

fmax = [[0 for col in xrange(n+1)] for row in xrange(getnum + 1)]
fmin = [[0 for col in xrange(n+1)] for row in xrange(getnum + 1)]
# print getnum
# print n
# print fmax
res = 0
for i in xrange(1, n+1):
    fmax[1][i] = arr[i-1]
    fmin[1][i] = arr[i-1]

    for k in xrange(2,getnum+1):
        j = i-1
        while True:
            if j > 0 and i-j <= maxspace:
                print fmax[k][i]
                print fmax[k - 1][j] * arr[i - 1]
                print fmin[k - 1][j] * arr[i - 1]

                fmax[k][i] = max(fmax[k][i], max(fmax[k - 1][j] * arr[i - 1], fmin[k - 1][j] * arr[i - 1]))
                fmin[k][i] = min(fmax[k][i], min(fmax[k - 1][j] * arr[i - 1], fmin[k - 1][j] * arr[i - 1]))
                j -= 1
            else:
                break
    res = max(res, fmax[getnum][i])

print res
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
import java.util.Scanner;

public class PuductMax {
        public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);
        while (cin.hasNextInt()) {
            int n = cin.nextInt();          // n 个学生
            int[] arr = new int [n+1];
            for (int i = 1; i <=n ; i++) {
                arr[i] = cin.nextInt();
            }
            int K = cin.nextInt();            // 选出K个
            int d = cin.nextInt();            // 两个学生的位置编号的差不超过 d
            long[][] fmax = new long[K+1][n+1]; // 记录最大乘积
            long[][] fmin = new long[K+1][n+1]; // 记录最小乘积
            // fmax[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最大乘积；
            // fmin[k][i]表示 : 当选中了k个学生，并且以第i个学生为结尾，所产生的最小乘积；
            //初始化第一行
            long  res = Integer.MIN_VALUE; // 记得用Long类型，考虑数值范围
            for (int i = 1; i <=n; i++) {
                fmax[1][i] = arr[i];
                fmin[1][i] = arr[i];
                for (int k = 2; k <=K; k++) {
                    for (int j = i-1 ; j > 0 &&  i-j<=d ; j--) {
                        fmax[k][i] = Math.max(fmax[k][i], Math.max(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i]));
                        fmin[k][i] = Math.min(fmin[k][i], Math.min(fmax[k-1][j] * arr[i], fmin[k-1][j] * arr[i]));
                    }
                }
                res = Math.max(res ,fmax[K][i]);
            }
            System.out.println(res);
            break;
        }
    }
}

发表于

今年的世界杯要开始啦，牛牛作为一个球迷，当然不会放过去开幕式现场的机会。但是牛牛一个人去又觉得太过寂寞，
便想叫上了他的n个小伙伴陪他一起去莫斯科(一共n+1人)。当牛牛开始订开幕式的门票时，发现门票有m种套餐，每种套餐需要花费x元，
包含y张门票，每张门票也可以单独购买，此时这张门票的价格为k元。请问牛牛要怎样选择购买门票，使得他花费的钱最少。
(每种套餐可以购买次数没有限制)。

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
def start():
    line = raw_input().strip()
    if line == '':
        return
    line = line.split(' ')
    num = int(line[0])+1
    mnum = int(line[1])
    k = int(line[2])
    dp = []
    for i in xrange(num):
        dp.append((i+1)*k)


    for i in xrange(mnum):
        line = raw_input().strip()
        if line == '':
            return
        x = int(line.split(' ')[0])
        y = int(line.split(' ')[1])
        for i in xrange(1,num+1):
            if i - y >0:
                dp[i-1] = min(dp[i-1],dp[i-1-y]+x)
            else:
                dp[i-1] = min(dp[i-1],x)
    print dp[num-1]


if __name__ == '__main__':
    start()

发表于 | 分类于

给定两个字符串str1和str2，返回两个字符串的最长公共子串

解法一：动态规划

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
public int[][] getdp(char[] str1, char[] str2){
	int[][] dp = nex int[str1.length][str2.length];
	for (int i =0; i < str1.length; i++){
		if (str1[i] == str2[0]){
			dp[i][0] = 1;
		}
	}
	for (int j =0; j < str2.length; j++){
		if (str1[0] == str2[j]){
			dp[0][j] = 1;
		}
	}
	for (int i = 1; i < str1.length; i++){
		for (int j = 1; j < str2.length; j++){
			if(str1[i] == str2[j]){
				dp[i][j] = dp[i-1][j-1] +1;
			}
		}
	}
	return dp;
}

public String lcst1(String str1, String str2){
	if (str1 == null || str2 == null || str1 == "" || str2 == ""){
		return "";
	}
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.tocharArray();
	
	int[][] dp = getdp(chs1, chs2);
	
	int end = 0;
	int max = 0;
	
	for (int i = 0; i< chs1.length; i++){
		for (int j =0; j < chs2.length; j++){
			if (dp[i][j] > max){
				end = i;
				max = dp[i][j];
			}
			
		}
	}
	return str1.substring(end-max+1, end+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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42

public String lcat2(String str1, String str2){
	if (str1 == null || str2 == null || str1 == "" || str2 == ""){
		return "";
	}
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.toCharArray();
	
	int row = 0;
	int col = chs2.length -1;
	int max = 0;
	int end = 0;
	
	while(row < chs1.length){
		int i = row;
		int j = col;
		int len = 0;
		while (i < chs1.length && j < chs2.length){
			if (chs1[i] != chs2[j]){
				len = 0;
			}else{
				len++;
			}
			
			//记录最大值，以及结束字符的位置
			if (len > max) {
				end = i;
				max = len;
			}
			
			i++;
			j++;
		}
		if (col > 0){
			col--;
		}
		else{
			row++;
		}
	}
	return str1.substring(end -max +1,end +1);
}

发表于 | 分类于

给定两个字符串str1和str2，返回两个字符串的最长公共子序列。
str1 = 1A2B3D4B56 str2 = B1D23CA45B6A
公共子序列123456 ,12C4B6都可以

解法：

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
//计算出最长公共子序列长度
public int[][] getdp(char[] str1, char[] str2){
	int[][] dp = new int[str1.length][str2.length];
	dp[0][0] = str[0] == str[1] ? 1 : 0;
	for (int i = 1; i < str1.length; i++){
		dp[i][0] = Math.max(dp[i-1][0], str1[i] == str2[0] ? 1 : 0);
	}
	for (int j = 1; i < str2.length; j++){
		dp[0][j] = Math.max(dp[0][j-1], str1[0] == str2[j] ? 1 : 0);
	}
	
	for (int i = 1; i < str1.length; i++){
		for (int j = 1; j < str2.length; j++){
			dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
			if (str1[i] == str2[j]){
				dp[i][j] == Math.max(dp[i][j], dp[i-1][j-1]+1);
			}
		}
	}
	return dp
}
//取出最长公共子序列
public String lcse(String str1, String str2){
	if(str1 == null || str2 == null || str1 == "" || str2 == ""){
		return "";
	}
	
	char[] chs1 = str1.toCharArray();
	char[] chs2 = str2.toCharArray();
	int[][] dp = getdp(chs1, chs2);
	int m = chs1.length -1;
	int n = chs2.length -1;
	char[] res = new char[dp[m][n]];
	int index = res.length -1;
	while(index >= 0){
		if (n > 0 && dp[m][n] == dp[m][n-1]){
			n--;
		}else if(m >0 && dp[m][n] == dp[m-1][n]){
			m--;
		}else{
			res[index--] = chs1[m]
			n--;
			m--;
		}
	}
}