Build Scripts for OpenSSL and Libcurl for Android

Build Script for OpenSSL and Libcurl for Android

This script is for the compilation of OpenSSL and Libcurl.
For libcurl there is a limitation, it cannot build for version above 7.46.0

Tested in Mac OSX El Capitan

Instructions:

specify the version of OpenSSL and Libcurl. The scripts will download them automatically.

OpenSSL : run buildOpenSSL.sh to build x86 armv5 armv7 libraries

Libcurl : run buildLibCurl.sh to build x86 armv5 armv7 libraries

You can find it here

展开全文 >>

[LeetCode] Paint House

Analysis:

Typical dynamic programming issue. We define dp[i][j] represents when last i houses painted with minimum cost when i-1th house painted with jth color
The we have:

dp = [[0 for i in xrange(3)] for j in xrange(len(costs)+1)]

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    # @param {int[][]} costs n x 3 cost matrix
    # @return {int} an integer, the minimum cost to paint all houses
    def minCost(self, costs):
        dp = [[0 for i in xrange(3)] for j in xrange(len(costs)+1)]

        for i in xrange(1, len(costs)+1):
            dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + costs[i-1][0]
            dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + costs[i-1][1]
            dp[i][2] = min(dp[i-1][1], dp[i-1][0]) + costs[i-1][2]

        return min(dp[len(costs)][0], dp[len(costs)][1], dp[len(costs)][2])

展开全文 >>

[LeetCode] Paint House II

Analysis:

Complicated than the Paint House since the number of color is not certain. Therefore, we have to store the minIdx, minVal and second small value in case that the minimum value is the same in the last level

Time Complexity:

  • O(nk)

Space Complexity：

  • O(nk)

Code

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
class Solution:
    # @param {int[][]} costs n x k cost matrix
    # @return {int} an integer, the minimum cost to paint all houses
    def minCostII(self, costs):
        if len(costs) == 0 or len(costs[0]) == 0:
            return 0

        siz = len(costs)
        k = len(costs[0])

        dp = [[0 for i in xrange(k)] for j in xrange(len(costs)+1)]

        for i in xrange(1, len(costs)+1):
            minval, secminval, minIdx = dp[i-1][0], dp[i-1][0], 0
            for t in xrange(k):
                if dp[i-1][t] < minval:
                    secminval = minval
                    minval = dp[i-1][t]
                    minIdx = t
                elif dp[i-1][t] < secminval:
                    secminval = dp[i-1][t]
            for j in xrange(k):
                if minIdx == j:
                    dp[i][j] = secminval + costs[i-1][j]
                else:
                    dp[i][j] = minval + costs[i-1][j]

        retMin = dp[siz][0]
        for t in xrange(1, k):
            retMin = min(retMin, dp[siz][t])

        return retMin

展开全文 >>

[LeetCode] Sqrt(x)

Analysis:

Use binary search to solve it, pay attention to the floor of integer.

Time Complexity:

  • O(logn)

Space Complexity：

  • O(1)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution(object):
  def mySqrt(self, x):
  """
  :type x: int
  :rtype: int
  """

  l, r = 0, x
  while l <= r:
    mid = l + (r-l)/2
    if mid*mid == x or (mid*mid < x and (mid+1)*(mid+1) > x):
      return mid
    elif mid*mid < x:
      l = mid+1
    else:
      r = mid-1

  return -1

展开全文 >>

[LeetCode] Reverse Pairs

Analysis:

Use the merge sort to solve the problem, since every segment is sorted, the left part’s rest numbers are surely bigger than the pointered number in the right segment. thus we can have pair number += mid-start+1. Then we can solve it recursively.

Time Complexity:

  • O(nlogn)

Space Complexity：

  • O(n)

Code

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
class Solution:
  # @param {int[]} A an array
  # @return {int} total of reverse pairs
  def merge(self, start, mid, end, A):
    p, q = start, mid+1

    tmp = []

    cursum = 0
    while p <= mid and q <= end:
      if A[p] <= A[q]:
        tmp.append(A[p])
        p += 1
      else:
        tmp.append(A[q])
        q += 1
        cursum += mid-p+1

    while p <= mid:
      tmp.append(A[p])
      p += 1
    while q <= end:
      tmp.append(A[q])
      q += 1

    for i in tmp:
      A[start] = i
      start += 1

    return cursum


  def mergesort(self, start, end, A):
    if start >= end:
      return 0

    mid = (start + end)/2
    parisum = 0

    parisum += self.mergesort(start, mid, A)
    parisum += self.mergesort(mid+1, end, A)
    parisum += self.merge(start, mid, end, A)

    return parisum

  def reversePairs(self, A):
    return self.mergesort(0, len(A)-1, A)

展开全文 >>

[LeetCode] Integer Break

Analysis:

define a array dp to depict the maximum product of n, then we have
dp[i+j] = max(max(dp[i], i)*max(dp[j], j), dp[i+j])

Time Complexity:

  • O(n^2)

Space Complexity：

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
    def integerBreak(self, n):
    """
    :type n: int
    :rtype: int
    """
    dp = [1] * (n+1)

    for i in xrange(1, n+1):
        for j in xrange(1, i+1):
            if i+j <= n:
	    dp[i+j] = max(max(dp[i], i)*max(dp[j], j), dp[i+j])

    return dp[n]

展开全文 >>

Rule Yourself

当我第一次看到这个视频的时候就被深深吸引，不是因为是飞鱼。而是因为那种坚韧不拔 持之以恒的精神正是我所一直推崇，并且一直在鞭策自己在努力。

目标确实不是那么容易达成的，不然就不存在那些所谓真正的成功者了。

JUST RULE YOURSELF.

展开全文 >>

[LeetCode] Super Ugly Number

Analysis:

Using the mafia fight method, find the smallest prime and multiply with the additional list to store the ugly numbers then adding the relevant indexes of them. Finally pop the last element.

Time Complexity:

  • O(m*n)

Space Complexity：

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    # @param {int} n a positive integer
    # @param {int[]} primes the given prime list
    # @return {int} the nth super ugly number
    def nthSuperUglyNumber(self, n, primes):
        if len(primes) == 0:
            return 1

        idxlist = [0 for i in xrange(len(primes))]
        q = [1]

        minint = sys.maxint
        for i in xrange(1, n):
            minint = sys.maxint
            for j in xrange(len(primes)):
                minint = min(minint, primes[j]*q[idxlist[j]])
            q.append(minint)
            for j in xrange(len(primes)):
                if minint == primes[j]*q[idxlist[j]]:
                    idxlist[j] += 1

        return q[-1]

展开全文 >>

[LeetCode] Counting Bits

Analysis:

As the tips in the problem, the list of the incremental sequence can be divided by the pow of 2.
Then we can repeat the circle of 5 = 4(1) + 1(1) or 9 = 8(1) + 1(1)

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution(object):
    def countBits(self, num):
        """
        :type num: int
        :rtype: List[int]
        """

        retlist = [0 for i in xrange(num+1)]

        pow2, before = 1, 1

        for x in xrange(1, num+1):
            if x == pow2:
                before = 1
                retlist[x] = 1
                pow2 <<= 1
            else:
                retlist[x] = 1 + retlist[before]
                before += 1
        return retlist

展开全文 >>

[LeetCode] House Robber III

Analysis:

The depth first search can extract the maximum sum from buttom to the top, that is ret = max{root+non-left+non-right, left+right}
use the return value to switch the side.

Time Complexity:

  • O(n)

Space Complexity：

  • O(n)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
	def dfs(self, root):
		if root is None: return 0, 0

		l, nol = self.dfs(root.left)
		r, nor = self.dfs(root.right)

		return max(root.val + nol + nor, l+r), l+r
	def rob(self, root):
		"""
		:type root: TreeNode
		:rtype: int
		"""
		maxret, tmp = self.dfs(root)
		return maxret

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

Martyn's Playground