国产探花免费观看_亚洲丰满少妇自慰呻吟_97日韩有码在线_资源在线日韩欧美_一区二区精品毛片,辰东完美世界有声小说,欢乐颂第一季,yy玄幻小说排行榜完本

首頁 > 學院 > 開發設計 > 正文

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;    		}    	}    }
發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 克什克腾旗| 监利县| 左贡县| 宜丰县| 云阳县| 陆川县| 阿鲁科尔沁旗| 尼玛县| 宜兰县| 赤峰市| 东海县| 美姑县| 德州市| 舟山市| 齐齐哈尔市| 惠来县| 二连浩特市| 蓬溪县| 神农架林区| 乐昌市| 乌苏市| 南平市| 留坝县| 巨野县| 永川市| 盐池县| 宁都县| 四会市| 噶尔县| 道孚县| 北海市| 兴安县| 正定县| 金阳县| 怀来县| 民权县| 临湘市| 东方市| 平阳县| 金华市| 共和县|