LintCode二叉树中的最大路径和

给出一棵二叉树，寻找一条路径使其路径和最大，路径可以在任一节点中开始和结束（路径和为两个节点之间所在路径上的节点权值之和）

样例
给出一棵二叉树：

  1
 / \
2   3

返回 6

代码:

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
/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */
public class Solution {
    /**
     * @param root: The root of binary tree.
     * @return: An integer.
     */
   int max = Integer.MIN_VALUE;
	public int maxPathSum(TreeNode root) {
		if(null == root)
		{
			return 0;
		}
		subMaxPathSum(root);
		return max;
        }
	
	public int subMaxPathSum(TreeNode node)
	{
		if(null == node)
		{
			return 0;
		}
		int leftMax = subMaxPathSum(node.left);
		int rightMax = subMaxPathSum(node.right);
		int subMax = Math.max(Math.max(Math.max(leftMax + node.val, rightMax + node.val), node.val),leftMax + rightMax + node.val);
		if(max < subMax)
		{
			max = subMax;
		}
		return Math.max(Math.max(leftMax + node.val, rightMax + node.val), node.val);
	}
}

LintCode背包问题

一：
在n个物品中挑选若干物品装入背包，最多能装多满？假设背包的大小为m，每个物品的大小为A[i]

样例
如果有4个物品[2, 3, 5, 7]

如果背包的大小为11，可以选择[2, 3, 5]装入背包，最多可以装满10的空间。

如果背包的大小为12，可以选择[2, 3, 7]装入背包，最多可以装满12的空间。

函数需要返回最多能装满的空间大小。

注意
你不可以将物品进行切割。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A: Given n items with size A[i]
     * @return: The maximum size
     */
 public int backPack(int m, int[] capacitys) {
		if(capacitys == null || capacitys.length <= 0)
			return 0;
		int[] maxCapacity = new int[m + 1];
		for(int i = 0;i < capacitys.length;i++)
		{
			for(int j = m;j >= 1;j--)
			{
				if(j >= capacitys[i])
				{
					maxCapacity[j] = Math.max(maxCapacity[j - capacitys[i]] + capacitys[i], maxCapacity[j]);
				}
			}
		}
		return maxCapacity[m];
	}
}

二：
给出n个物品的体积A[i]和其价值V[i]，将他们装入一个大小为m的背包，最多能装入的总价值有多大？

样例
对于物品体积[2, 3, 5, 7]和对应的价值[1, 5, 2, 4], 假设背包大小为10的话，最大能够装入的价值为9。

注意
A[i], V[i], n, m均为整数。你不能将物品进行切分。你所挑选的物品总体积需要小于等于给定的m。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
   public int backPackII(int m, int[] capacitys, int values[]) {
		if(null == capacitys || capacitys.length <= 0 || null == values || values.length <= 0)
			return 0;
		int[] maxValues = new int[m + 1];
		for(int i = 0;i < capacitys.length;i++)
		{
			for(int j = m;j >= 1;j--)
			{
				if(j >= capacitys[i])
				{
					maxValues[j] = Math.max(maxValues[j - capacitys[i]] + values[i], maxValues[j]);
				}
			}
		}
		return maxValues[m];
	}
}

LintCode Maximal Square

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

样例
For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 4.

解题思路
初始思路是判断对角方向以及相邻的两个数,运行结果错误，然后查看错误发现需要判断整个邻边，因此想到遍历邻边判断（i，j）位置的最大面积。但是会发现（i，j）之前的点的结果已经得出，为什么会重复用到之前的点，整个过程应该可以优化。思考后想到了同时三个方向判断，因此得出转移方程：maxArea[i][j] = Math.min(maxArea[i][j - 1],Math.min(maxArea[i - 1][j - 1], maxArea[i - 1][j])) + 1；

错误代码

1
2
3
4
5
6
7
8
if(matrix[i - 1][j] == 1 && matrix[i][j - 1] == 1 && matrix[i - 1][j - 1] == 1)
{
          maxArea[i][j] = maxArea[i - 1][j - 1] + 1;
   if(maxArea[i][j] > maxResultArea)
   {
             maxResultArea = maxArea[i][j];
   }
}

正确代码

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 Solution {
    /**
     * @param matrix: a matrix of 0 and 1
     * @return: an integer
     */
  public int maxSquare(int[][] matrix) {
		if(null == matrix)
		{
			return 0;
		}
		int row = matrix.length;
		if(row <= 0)
		{
			return 0;
		}
		int col = matrix[0].length;
		int[][] maxArea = new int[row][col];
		int maxResultArea = Integer.MIN_VALUE;
		
		for(int i = 0;i < row;i++)
		{
			maxArea[i][0] = matrix[i][0];
			if(maxArea[i][0] > maxResultArea)
			{
				maxResultArea = maxArea[i][0];
			}
		}
		
		for(int i = 0;i < col;i++)
		{
			maxArea[0][i] = matrix[0][i];
			if(maxArea[0][i] > maxResultArea)
			{
				maxResultArea = maxArea[0][i];
			}
		}
		
		for(int i = 1;i < row;i++)
		{
			for(int j = 1;j < col;j++)
			{
				if(matrix[i][j] == 1)
				{
					maxArea[i][j] = Math.min(maxArea[i][j - 1],Math.min(maxArea[i - 1][j - 1], maxArea[i - 1][j])) + 1;
				}
				if(maxArea[i][j] > maxResultArea)
				{
					maxResultArea = maxArea[i][j];
				}
			}
		}
		return maxResultArea > 0 ?  maxResultArea * maxResultArea : 0;
	}
}

LintCode数字三角形

给定一个数字三角形，找到从顶部到底部的最小路径和。每一步可以移动到下面一行的相邻数字上。

样例
比如，给出下列数字三角形：

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

从顶到底部的最小路径和为11 ( 2 + 3 + 5 + 1 = 11)。

注意
如果你只用额外空间复杂度O(n)的条件下完成可以获得加分，其中n是数字三角形的总行数。

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
public class Solution {
    /**
     * @param triangle: a list of lists of integers.
     * @return: An integer, minimum path sum.
     */
   public int minimumTotal(int[][] triangle) {
		if(null == triangle)
			return 0;
		int row = triangle.length;
		if(row <= 0)
			return 0;
		int[][] steps = new int[row][row];
		int min = Integer.MAX_VALUE;
		steps[0][0] = triangle[0][0];
		if(row == 1)
			return steps[0][0];
		for(int i = 1;i < row;i++)
		{
			for(int j = 0;j <= i;j++)
			{
				if(j == 0)
				{
					steps[i][j] = steps[i - 1][j] + triangle[i][j];
				}
				else if(j == i)
				{
					steps[i][j] = steps[i - 1][j - 1] + triangle[i][j];
				}
				else
				{
					steps[i][j] = Math.min(steps[i - 1][j], steps[i - 1][j - 1]) + triangle[i][j];
				}
				
				if(i == row - 1)
				{
					if(steps[i][j] < min)
					{
						min = steps[i][j];
					}
				}
			}
		}
		return min;
	}
}

LintCode最小路径和

给定一个只含非负整数的m*n网格，找到一条从左上角到右下角的可以使数字和最小的路径。
样例
注意
你在同一时间只能向下或者向右移动一步

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
public class Solution {
    /**
     * @param grid: a list of lists of integers.
     * @return: An integer, minimizes the sum of all numbers along its path
     */
   public int minPathSum(int[][] grid) {
		if(null == grid)
			return 0;
		int row = grid.length;
		int col = grid[0].length;
		if(row <= 0 || col <= 0)
			return 0;
		int[][] steps = new int[row][col];
		steps[0][0] = grid[0][0];
		for(int i = 1;i < row;i++)
		{
			steps[i][0] += steps[i - 1][0] + grid[i][0];
		}
		
		for(int i = 1;i < col;i++)
		{
			steps[0][i] += steps[0][i - 1] + grid[0][i];
		}
	
		for(int i = 1;i < row;i++)
		{
			for(int j = 1;j < col;j++)
			{
				steps[i][j] = Math.min(steps[i - 1][j], steps[i][j - 1]) + grid[i][j];
			}
		}
	
		return steps[row - 1][col - 1];
	}
}

LintCode交叉字符串

给出三个字符串:s1、s2、s3，判断s3是否由s1和s2交叉构成。

样例
比如 s1 = “aabcc” s2 = “dbbca”

- 当 s3 = "aadbbcbcac"，返回  true.

- 当 s3 = "aadbbbaccc"， 返回 false.

挑战
要求时间复杂度为O(n^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
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
public class Solution {
    /**
     * Determine whether s3 is formed by interleaving of s1 and s2.
     * @param s1, s2, s3: As description.
     * @return: true or false.
     */
    public boolean isInterleave(String s1, String s2, String s3) {
		if(null == s1 || null == s2 || null == s3 || s1.length() + s2.length() != s3.length())
			return false;
		if(s1.length() <= 0 && s2.length() <= 0 && s3.length() <= 0)
			return true;
		
		boolean[][] common = new boolean[s1.length() + 1][s2.length() + 1];
		for(int i = 1;i <= s1.length();i++)
		{
			if(s1.charAt(i - 1) == s3.charAt(i - 1))
			{
				common[i][0] = true;
			}
		}
		
		for(int i = 1;i <= s2.length();i++)
		{
			if(s2.charAt(i - 1) == s3.charAt(i - 1))
			{
				common[0][i] = true;
			}
		}
		
		for(int i = 1;i <= s1.length();i++)
		{
			for(int j = 1;j <= s2.length();j++)
			{
				if(s1.charAt(i - 1) == s3.charAt(i + j - 1))
				{
					common[i][j] = common[i - 1][j];
				}
				
				if(common[i][j])
				{
					continue;
				}
				
				if(s2.charAt(j - 1) == s3.charAt(i + j - 1))
				{
					common[i][j] = common[i][j - 1];
				}
			}
		}
		return common[s1.length()][s2.length()];
	}
}

LintCode不同的路径

一：
有一个机器人的位于一个M×N个网格左上角（下图中标记为’Start’）。
机器人每一时刻只能向下或者向右移动一步。机器人试图达到网格的右下角（下图中标记为’Finish’）。
问有多少条不同的路径？

1,1 1,2 1,3 1,4 1,5 1,6 1,7
2,1
3,1 3,7 
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 class Solution {
    /**
     * @param n, m: positive integer (1 <= n ,m <= 100)
     * @return an integer
     */
   public int uniquePaths(int m, int n) {
		if(m == 0 || n == 0)
			return 0;
		int[][] paths = new int[m][n];
		for (int i = 0; i < m; i++) {
			paths[i][0] = 1;
		}

		for (int i = 0; i < n; i++) {
			paths[0][i] = 1;
		}

		for (int i = 1; i < m; i++) {
			for (int j = 1; j < n; j++) {
				paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
			}
		}
		return paths[m - 1][n - 1];
	}
}

二：
“不同的路径” 的跟进问题：

现在考虑网格中有障碍物，那样将会有多少条不同的路径？

网格中的障碍和空位置分别用 1 和 0 来表示。
样例
如下所示在3x3的网格中有一个障碍物：

[
[0,0,0],
[0,1,0],
[0,0,0]
]
一共有2条不同的路径从左上角到右下角。

注意
m 和 n 均不超过100

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
public class Solution {
    /**
     * @param obstacleGrid: A list of lists of integers
     * @return: An integer
     */
  public int uniquePathsWithObstacles(int[][] obstacleGrid) {
		if (null == obstacleGrid)
			return 0;
		int[] columns = obstacleGrid[0];
		int[][] paths = new int[obstacleGrid.length][columns.length];
		boolean havePath = true;
		for (int i = 0; i < obstacleGrid.length; i++) {
			if (!havePath) {
				paths[i][0] = 0;
				continue;
			}
			if (obstacleGrid[i][0] == 1) {
				paths[i][0] = 0;
				havePath = false;
			} else {
				paths[i][0] = 1;
			}
		}

		havePath = true;
		for (int i = 0; i < columns.length; i++) {
			if (!havePath) {
				paths[0][i] = 0;
				continue;
			}
			if (obstacleGrid[0][i] == 1) {
				paths[0][i] = 0;
				havePath = false;
			} else {
				paths[0][i] = 1;
			}
		}

		for (int i = 1; i < obstacleGrid.length; i++) {
			for(int j = 1;j < columns.length;j++)
			{
				if(obstacleGrid[i][j] == 1)
				{
					paths[i][j] = 0;
					continue;
				}
				else	
				{
					paths[i][j] = paths[i - 1][j] + paths[i][j - 1];
				}
			}
		}
		return paths[obstacleGrid.length - 1][columns.length - 1];
	}
}

LintCode最长上升连续子序列

给定一个整数数组（下标从 0 到 n-1， n 表示整个数组的规模），请找出该数组中的最长上升连续子序列。（最长上升连续子序列可以定义为从右到左或从左到右的序列。）

代码如下：

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
public class Solution {
    /**
     * @param A an array of Integer
     * @return  an integer
     */
   public int longestIncreasingContinuousSubsequence(int[] nums) {
		if(null == nums || nums.length <= 0)
			return 0;
		int ascendCount = 1;
		int maxAscendCount = -1;
		for(int i = 1;i < nums.length;i++)
		{
			if(nums[i] > nums[i - 1])
			{
				ascendCount++;
				if(ascendCount > maxAscendCount)
				{
					maxAscendCount = ascendCount;
				}
			}
			else
			{
				ascendCount = 1;
			}
		}
		
		if(ascendCount > maxAscendCount)
		{
			maxAscendCount = ascendCount;
		}
		ascendCount = 1;
		for(int i = nums.length - 1;i >= 1;i--)
		{
			if(nums[i] < nums[i - 1])
			{
				ascendCount++;
				if(ascendCount > maxAscendCount)
				{
					maxAscendCount = ascendCount;
				}
			}
			else
			{
				ascendCount = 1;
			}
		}
		return maxAscendCount;
	}
}

MSWeakTimer机制解析

MSWeakTimer地址：https://github.com/mindsnacks/MSWeakTimer

基本介绍

线程安全的MSWeakTimer是NSTimer的替代品，最基本的特点是它不会 retain target 以及支持GCD queues。

问题的提出

关于 NSTimer 中 target 的生命周期问题，当 repeat 为 YES 时NSTimer 会 retains 它的 target，那么target的生命周期就成了问题，完全的交给了这个timer，只有当timer 调用invalidate后 dealloc 才有机会发生。

另一个问题是GCD，在苹果的官方文档中说的很清楚:

Special Considerations

You must send this message from the thread on which the timer was installed. If you send this message from another thread, the input source associated with the timer may not be removed from its run loop, which could prevent the thread from exiting properly.

invalidate必须由安装这个timer的线程发起，否则这个timer有可能不会从run loop中移除。这种情况会发生的一个情况就是：当这个线程是由 GCD 管理的。这是因为 NSTimer 依赖于当前线程的run loop, 而GCD完全是另外一回事，它不能确保timer的阻塞和invalidate是由同一个线程发起的，run loop和queue将会交织在一起，世界就乱了…

而MSWeakTimer完全就不是用run loop实现的，所以就不用考虑那么多了，它可以与GCD和谐共存，被任意线程 install 和 invalidate。

源码分析
（1）初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
if ((self = [super init]))
    {
        self.timeInterval = timeInterval;
        self.target = target;
        self.selector = selector;
        self.userInfo = userInfo;
        self.repeats = repeats;

        NSString *privateQueueName = [NSString stringWithFormat:@"com.mindsnacks.msweaktimer.%p", self];
 // 1.创建串行队列
 // Dispatch queues created with the DISPATCH_QUEUE_SERIAL or a NULLattribute
 // invoke blocks serially in FIFO order.
        self.privateSerialQueue = dispatch_queue_create([privateQueueName cStringUsingEncoding:NSASCIIStringEncoding], DISPATCH_QUEUE_SERIAL);
        dispatch_set_target_queue(self.privateSerialQueue, dispatchQueue);
 // 2.dispatch_source 定时器
        self.timer = dispatch_source_create(DISPATCH_SOURCE_TYPE_TIMER,
                                            0,
                                            0,
                                            self.privateSerialQueue);
    }

（2）设置定时器的触发时间

1
2
3
4
5
dispatch_source_set_timer(self.timer,
                              dispatch_time(DISPATCH_TIME_NOW, intervalInNanoseconds),
                              (uint64_t)intervalInNanoseconds,
                              toleranceInNanoseconds
                              );

（3）设置定时器触发的事件

1
2
3
4
5
6
7
__weak MSWeakTimer *weakSelf = self;

   dispatch_source_set_event_handler(self.timer, ^{
       [weakSelf timerFired];
   });

   dispatch_resume(self.timer);

（4）具体event

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if (OSAtomicAnd32OrigBarrier(1, &_timerFlags.timerIsInvalidated)) // 原子操作
   {
       return;
   }

   // We're not worried about this warning because the selector we're calling doesn't return a +1 object.
   #pragma clang diagnostic push
   #pragma clang diagnostic ignored "-Warc-performSelector-leaks"
       [self.target performSelector:self.selector withObject:self];
   #pragma clang diagnostic pop

   if (!self.repeats)
   {
       [self invalidate];
   }

（5）释放

1
2
3
4
5
6
7
8
9
10
11
12
13
- (void)invalidate
{
    // We check with an atomic operation if it has already been invalidated. Ideally we would synchronize this on the private queue,
    // but since we can't know the context from which this method will be called, dispatch_sync might cause a deadlock.
    if (!OSAtomicTestAndSetBarrier(7, &_timerFlags.timerIsInvalidated))
    {
        dispatch_source_t timer = self.timer;
        dispatch_async(self.privateSerialQueue, ^{
            dispatch_source_cancel(timer);
            ms_release_gcd_object(timer);
        });
    }
}

附：
OSAtomicAnd32OrigBarrier ： 用于原子操作的判断，出于线程安全考虑
OSAtomic原子操作：http://southpeak.github.io/blog/2014/10/17/osatomicyuan-zi-cao-zuo/
GCD dispatch_source：http://www.cnblogs.com/sunfrog/p/3308766.html