程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> LeetCode -- Perfect Squares

LeetCode -- Perfect Squares

編輯:C++入門知識

LeetCode -- Perfect Squares


題目描述
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.


For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.


Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.


思路:
本題還是BFS, 遞歸的對象是完全平方數集合,以及要尋找的數集list[0...i](=n-table[0...i])






1. 找出小於目標數:n的完全平方數,如果找到直接返回
2. 進行BFS(完全平方數集合:table,要尋找的數集:list,層數:depth):
循環table,針對每個小於當前n的完全平方數,求出它要尋找的數集:x={n-table[i]} , i∈[0,table.Count] => 得到list


實現代碼



public class Solution {
    public int NumSquares(int n) 
    {
       if(n == 1){
		return 1;
	}
	
	var len = n/2;
	var depth = 1;
	var table = new List();
	for(var i = 1;i <= len; i++){
		var x = i * i;
		if(x == n){
			return 1;
		}
		if(x < n){
			table.Add(x);
		}
	}
	
	
	var list = new List();
	for(var i = 0 ;i < table.Count; i++){
		list.Add(n-table[i]);
	}
	
	Bfs(table, list, depth + 1);
	
	return Depth;
}


private int Depth;
private bool Found = false;


public void Bfs(IList table , IList target , int depth)
{
	if(Found){
		return;
	}
	
	for(var i =0 ;i < table.Count; i++){
		for(var j = 0;j < target.Count; j++){
			if(table[i] == target[j]){
				Depth = depth;
				Found = true;
				return;
			}
		}
	}
	
	var list = new List();
	for(var i = 0;i < target.Count; i++){
		var t = table.Where(x=>x

 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved