首页 > 代码库 > 求m行n列个方格的正方形总数
求m行n列个方格的正方形总数
一个算法题： 一个m行n列的方格，问一共有多少个长方形和正方形？
我说下我的思路：
1、长方形和正方形类似，就是判断条件不一样而已。
2、先找出正方形数
a、将m*n方格的图形每个点记录成（m+1）*（n+1）的矩阵，m行个格对应m+1行个点，n列类似。
b、先以左下角第一个点为起点开始标记，记为（x11，y11）。
c、寻找右上角的点，循环遍历除去标记点的所有点，当目标点（X，Y）满足 X-x11 = Y-y11 > 0, 数量加1.
d、上一步遍历完成后，返回b，将起点变为（x12，y12），标记此点。
e、当所有点都被标记后，结束程序。
3、长方形，就是将结束条件变为X-x11 >0 && Y-y11 > 0。
代码如下：
1 package com.smikevon.basic.interview; 2 3 import java.util.LinkedList; 4 import java.util.List; 5 6 /** 7 * Created by fengxiao on 15-1-29. 8 */ 9 public class SquareCount {10 11 public static void main(String[] args){12 System.out.println(count(5,2));13 }14 15 /**16 * m行 n 列的方格17 * @param m18 * @param n19 */20 public static int count(int m,int n){21 int total = 0;22 List<Point> points = new LinkedList<Point>();23 24 //将m行n列的方格,生成(m+1)*(n+1)个点25 for(int i=0;i<=m;i++){26 for(int j=0;j<=n;j++){27 points.add(new Point(i,j));28 }29 }30 31 for(int i=0;i<points.size();i++){32 for(int j=i+1;j<points.size();j++){33 if(points.get(i).formSquare(points.get(j))){34 total++;35 }36 }37 }38 return total;39 }40 41 42 static class Point{43 int x;44 int y;45 46 Point(int x,int y){47 this.x=x;48 this.y=y;49 }50 51 public int getY() {52 return y;53 }54 55 public int getX() {56 return x;57 }58 59 /**60 * 判断和另一个点能否组成正方形61 * @param point62 * @return63 */64 public boolean formSquare(Point point){ 65 int dx = point.getX() - this.getX();66 int dy = point.getY() - this.getY();67 return (dx==dy && dx>0)?true:false;68 }69 70 @Override71 public boolean equals(Object o) {72 if (x != this.x) return false;73 if (y != this.y) return false;74 return true;75 }76 77 @Override78 public int hashCode() {79 int result = x;80 result = 31 * result + y;81 return result;82 }83 }84 }
求m行n列个方格的正方形总数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。