首页 > 学院 > 开发设计 > 正文

LeetCode -- Russian Doll Envelopes

2019-11-08 02:11:37
字体:
来源:转载
供稿:网友
题目描述:You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.What is the maximum number of envelopes can you Russian doll? (put one inside other)Example:Given envelopes = [[5,4],[6,4],[6,7],[2,3]], the maximum number of envelopes you can Russian doll is 3 ([2,3] => [5,4] => [6,7]).给定一个二维数组,对于[i,j]和[a,b]若满足i<a且j<b,则成为Russian doll。统计满足Russian doll的个数。思路:1. 使用类建模,对整个数组排序2. 两层循环,排序后从第一个往后遍历(i:0->n);内层循环从后向前查找(j:i->0):若a[i,0]>a[j,0] && a[0,i] > a[0,j]则取 Max(a[i]当前的结果,a[j]的结果+1)因此可使用DP,用result[i]来存a[i]的Russian doll的数量,初始化为1。实现代码:
public int MaxEnvelopes(int[,] envelopes)    {        if(envelopes == null || envelopes.Length == 0){    		return 0;    	}    	    	// 0. model the PRoblem    	var arr = new List<Doll>();    	var rowCount = envelopes.Length / 2;        	for (var i = 0;i < rowCount; i++){    		arr.Add(new Doll(envelopes[i,0], envelopes[i,1]));    	}    	    	// 1. sort the arrays     	arr = arr.OrderBy(x=>x).ToList();    	    	var result = new int[rowCount];    	for (var i = 0;i < rowCount; i++){    		// fetch the item from first to last    		result[i] = 1;    		for (var j = i-1;j >=0 ; j--){    			if(arr[i].Width > arr[j].Width && arr[i].Height > arr[j].Height){    				result[i] = Math.Max(result[i], result[j]+1);    			}    		}    	}    	//Console.WriteLine(result);    	var max = result.Max();    	    	return max;    	    }        public class Doll : IComparable    {    	public int Width;    	public int Height;    	public Doll(int width, int height){    		this.Width = width;    		this.Height = height;    	}    	    	public int CompareTo(object obj){    		var to = (Doll)obj;    		if(Width!=to.Width){    			return Width - to.Width;    		}else{    			return Height - to.Height;    		}    	}    }
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表