| Steven's profile永远的第一天PhotosBlogLists |  Tools  Help |
|
|
July 05 request,session属性一览
December 15 GOOGLE编程题目 今天看了下题目，呵呵好象比预计的要简单很多，1小时也许是可以完成的，特别是后面750分那道，好象异常的简单，花了不到20多分钟，一次测试成功：），不知道是不是有其他的限制。
当然，我的编码几乎是不讲算法的，按照题目意思+ＯＯ一步步下去就ＯＫ了。我想也许这也是一个不错的方法，偶尔理不清，拿张纸涂一下就差不多了。
基本原则：代码就是你思想的全过程，也就是说80％以上的时间都是花在写代码上的
以下是我的基本编码
public class BusStops {
private Location Xloc = null; public int countStops(String[] cityMap, int walkingDistance) { int result = 0; char[][] formatedMap = _formatMap(cityMap); for (int i = 0; i < formatedMap.length; i++) { for (int j = 0; j < formatedMap[i].length; j++) { if (formatedMap[i][j] == 'B') { if (new Location(i, j).minus(Xloc) <= walkingDistance) { result++; } } } } return result; } // 把cityMap由1维数组变为2维数组 private char[][] _formatMap(String[] cityMap) { char[][] formatedMap = new char[cityMap.length][]; boolean locationed = false; for (int i = 0; i < cityMap.length; i++) { if (!false) { int j = cityMap[i].indexOf("X"); if (j != -1) { // 得到X的位置，写在这里为了省去再一边的扫描去定位X，但是也一定程度的降低了代码的可读性 this.Xloc = new Location(i, j); //找到了就不需要再找X了，这样只是为了加快一定的速度 locationed = true; } } formatedMap[i] = cityMap[i].toCharArray(); } return formatedMap; } //这个方法没有用，只是习惯性的写上去而已 private Location getXloc() { return Xloc; } public static void main(String[] args) { String[] cityMap = { "BBBBB", "BB.BB", "B.X.B", "BB.BB", "BBBBB" }; int walkingDistance = 1; BusStops test = new BusStops(); System.out.println("Result : " + test.countStops(cityMap, walkingDistance)); } } //位置的对象话，如果用c编程，可能就没有这样的习惯了 class Location { private int x, y; public int getX() { return x; } public void setX(int x) { this.x = x; } public int getY() { return y; } public void setY(int y) { this.y = y; } Location(int x, int y) { this.x = x; this.y = y; } public int minus(Location loc) { return Math.abs(loc.getX() - x) + Math.abs(loc.getY() - y); } public String toString() { return "[X=" + x + ",Y=" + y + "]"; } } public class Balls { public int countWays(int baskets, int capacity, int balls) { if (baskets < 1 || baskets > 5 || capacity < 1 || capacity > 20 || balls < 1 || balls > 100) { System.out.println("Illegal Arguments ..........."); return -1; } if (balls > baskets * capacity) { return 0; } _countWaysImp(baskets, capacity, balls); return result; } private static int result = 0; private void _countWaysImp(int baskets, int capacity, int balls) { // 获取当前篮子可以放的最大球的数量 int max = getMaxBallsInCurrentBasket(baskets, capacity, balls); // 获取当前篮子可以放的最少球的数量 int min = getMinBallsInCurrentBasket(baskets, capacity, balls); // 在最大和最小间取一定的球 for (int curr = min; curr <= max; curr = curr + 1) { // 如果basket的第2个个数已定那么他最后一个个数其实也已经定了所以 // 换句话说就是该树是不可能再分叉了，避免再扫下面的叶节点了（测试证明可以省下不少的时间哦） // 当然也降低了一定的可读性 if (baskets > 2) { // 剩下的篮子和球递归再继续取 _countWaysImp(baskets - 1, capacity, balls - curr); } else { // 全部取好了，方法数量就加一 result = result + 1; } } } private int maxTotalCapacity(int baskets, int capacity) { return baskets * capacity; } private int getMinBallsInCurrentBasket(int baskets, int capacity, int balls) { int result = 0; if (baskets > 1) { result = balls - maxTotalCapacity(baskets - 1, capacity); } else { result = balls; } return result > 0 ? result : 0; } private int getMaxBallsInCurrentBasket(int baskets, int capacity, int balls) { return balls > capacity ? capacity : balls; } public static void main(String[] args) { Balls test = new Balls(); int baskets = 5; int capacity = 20; int balls = 50; long begTime = System.currentTimeMillis(); System.out.println("Results : " + test.countWays(baskets, capacity, balls)); System.out.println("Total costs : " + (System.currentTimeMillis() - begTime)); } } December 14 GOOGLE挑战赛Question:（250）
Problem Statement You have several identical balls that you wish to place in several baskets. Each basket has the same maximum capacity. You are given an int baskets, the number of baskets you have. You are given an int capacity, the maximum capacity of each basket. Finally you are given an int balls, the number of balls to sort into baskets. Return the number of ways you can divide the balls into baskets. If this cannot be done without exceeding the capacity of the baskets, return 0.
Each basket is distinct, but all balls are identical. Thus, if you have two balls to place into two baskets, you could have (0, 2), (1, 1), or (2, 0), so there would be three ways to do this. Definition Class:
FillBaskets Method: countWays Parameters: int, int, int Returns: int Method signature: int countWays(int baskets, int capacity, int balls) (be sure your method is public) Constraints - baskets will be between 1 and 5, inclusive. - capacity will be between 1 and 20, inclusive. - balls will be between 1 and 100, inclusive. Examples：
0)
2
20 2 Returns: 3 The example from the problem statement. 1)
3
20 1 Returns: 3 We have only 1 ball, so we must choose which of the three baskets to place it in. 2)
3
20 2 Returns: 6 We can place both balls in the same basket (3 ways to do this), or one ball in each of two baskets (3 ways to do this). 3)
1
5 10 Returns: 0 We have more balls than our basket can hold. 4)
4
5 10 Returns: 146 This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2003, TopCoder, Inc. All rights reserved. Problem Statement（750） ???? You are given a String[] cityMap representing the layout of a city. The city consists of blocks. The first element of cityMap represents the first row of blocks, etc. A 'B' character indicates a location where there is a bus stop. There will be exactly one 'X' character, indicating your location. All other characters will be '.'. You are also given an int walkingDistance, which is the maximum distance you are willing to walk to a bus stop. The distance should be calculated as the number of blocks vertically plus the number of blocks horizontally. Return the number of bus stops that are within walking distance of your current location. Definition ???? Class: BusStops Method: countStops Parameters: String[], int Returns: int Method signature: int countStops(String[] cityMap, int walkingDistance) (be sure your method is public) ???? Constraints ???? ???? ???? ???? This problem statement is the exclusive and proprietary property of TopCoder, 自己测试过，1h完成对我而言目前是impossible mission,主要是老毛病思维混乱+乱想，但我相信以后我一定会出色的完成的。几天后我将提出自己的完全思想解决过程 |
|
|
