小猴爬台阶问题

深碍√TFBOYSˉ_ 2022-03-11 14:36 195阅读 0赞

小猴爬台阶问题：

有一只小猴很顽皮，喜欢爬台阶，但由于小猴太小，所以它只能一步爬1个或2个台阶。请计算该小猴所有可能的爬行路径。

package shuai.study.steps;
    
    import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.Iterator;
    import java.util.List;
    import java.util.Set;
    
    /**
     * @author shengshu
     * 
     */
    public class MonkeyCrawl {
    
    	// Get paths, which will be permutated
    	public static Set<String> getPathsSet(int steps) {
    		Set<String> pathsSet = new HashSet<String>();
    
    		for (int i = 0; i <= steps / 2; i++) {
    			int twoStepSum = i * 2;
    			int oneStepTimes = steps - twoStepSum;
    
    			StringBuffer pathStringBuffer = new StringBuffer();
    
    			for (int x = 0; x < oneStepTimes; x++) {
    				// "-" represent one step
    				pathStringBuffer.append("-");
    			}
    
    			for (int y = 0; y < i; y++) {
    				// "=" represent two steps
    				pathStringBuffer.append("=");
    			}
    
    			pathsSet.add(pathStringBuffer.toString());
    		}
    
    		return pathsSet;
    	}
    
    	// Permutate all possible paths
    	public static void permutatePaths(String path, List<String> list) {
    		if (path.length() == 1) {
    			for (int i = 0; i < list.size(); i++) {
    				System.out.print(list.get(i));
    			}
    
    			System.out.println(path);
    		} else {
    			int index[] = new int[path.length()];
    
    			for (int i = 0; i < index.length; i++) {
    				index[i] = path.indexOf(path.charAt(i));
    			}
    
    			for (int i = 0; i < path.length(); i++) {
    				String subPath = path.substring(1, path.length());
    
    				if (i == index[i]) {
    					list.add("" + path.charAt(0));
    
    					permutatePaths(subPath, list);
    
    					list.remove(list.size() - 1);
    				}
    
    				path = subPath + path.charAt(0);
    			}
    		}
    	}
    
    	public static void main(String[] args) {
    		// Set steps as 15, or others
    		Set<String> pathsSet = MonkeyCrawl.getPathsSet(15);
    
    		Iterator<String> iterator = pathsSet.iterator();
    		while (iterator.hasNext()) {
    			String path = iterator.next();
    			MonkeyCrawl.permutatePaths(path, new ArrayList<String>());
    		}
    	}
    
    }