y*****e
发帖数: 712 | 1 1. 给你一些平面的点（坐标是整数），求能够成正方形的数目。
我想了想这题大概可以这么做：把每两个点之间的距离用hashmap存下来，key是
distance, values是arraylist of point pairs， 比如（p1, p2), (p3,p4)之间距离
都是6, 把他们都放到map.get(6)的list里面。这样一共要查（n,2)pairs, time也就是
(n^2). 下一步对于每一个distance, 查看对应的list size是不是大于4（至少有4个
pairs之间距离相同）。然后对于每一个list再进一步确定有没有正方形，比如
(p1,p2), (p1,p3), (p1,p4), (p2, p3), (p2, p4), (p3, p4) 都在list里，就可以确
认这四个点可以组成正方形。。。。确认的时候可以再建一个hashmap, map p1 to (p2
, p3, p4), p2 to (p3, p4), 然后找需要的pair是不是都在map里。。。就是好麻烦这
个solution, 不知有没有简单点的解法？
2. 设计json的data structure实现json encoding 要求one line version先不考虑
indent，follow up考虑indent和括号
来自这里
http://www.mitbbs.com/article_t/JobHunting/32883371.html
没有思路，不知怎么start， 还请大家帮忙。。。 | n*********u
发帖数: 1030 | 2 第一题感觉可以先以一个坐标轴扫描一遍所有垂直于那个坐标轴的可能的直线，放到一
个list里存起来。
把所有点放到一个hash map里存起来。
扫描完一遍后，对于每条直线，找需要构成正方形的另外两个点存不存在就行了。
第二题可以参考java的jsonObject class，或者类似的。
也就是把json的几个类别弄出来，(int,long,float), string, jsonObject, jsonList
，每个都有自己的__str__().
像画tree一样让__str__()自己recursive print出来就行了。 | c*******e
发帖数: 373 | 3 题目没有说正方形的边一定是水平或者垂直的
可以是任意方向
jsonList
【在 n*********u 的大作中提到】
: 第一题感觉可以先以一个坐标轴扫描一遍所有垂直于那个坐标轴的可能的直线，放到一
: 个list里存起来。
: 把所有点放到一个hash map里存起来。
: 扫描完一遍后，对于每条直线，找需要构成正方形的另外两个点存不存在就行了。
: 第二题可以参考java的jsonObject class，或者类似的。
: 也就是把json的几个类别弄出来，(int,long,float), string, jsonObject, jsonList
: ，每个都有自己的__str__().
: 像画tree一样让__str__()自己recursive print出来就行了。
| n*********u
发帖数: 1030 | 4
哦，那好像只能每个情况的试了。
http://www.codechef.com/problems/D6
【在 c*******e 的大作中提到】
: 题目没有说正方形的边一定是水平或者垂直的
: 可以是任意方向
:
: jsonList
| c*******e
发帖数: 373 | 5 第一题，我觉得大的思路和2sum / 3sum是类似的
- 所有的点进hashset，方便o(1)的查找 同时进一个array，方便遍历所有点对的组合
- for (每两个点的组合)
计算组成正方形的第三和第四个点的可能坐标，有两组 （镜像的两个正方形），从
hash里找，无法同时找到第三点或者第四点，则失败
时间 o(n2)，空间o(n)
进一步分析 - 由于正方形有4个边，我们是先定一边，再判断能否找到另外两点(或者4
点)出一个(或一对镜像)正方形，计算成功次数，会多算。为了去重复：
a方法: 可以引入一个hashset来存储已经算出来的正方形
b方法：在每次发现正方形时，如果是独立的，singleSquareSide ++;
如果是镜像相连的两个的，就 mirrorSquareSide ++;
最后的postProcess:
每个独立正方形，4条非公用边，会引起4次 single++
每对镜像正方形，6条非公用边，会引起6次 single++，加上一条公用边引起的1次
mirror++
所以最终结果 squareCount = mirror * 2 + (single - mirror * 6) / 4;
b看起来复杂，其实只是分析过程复杂，实际代码可能会更简单、更快、而且比a省一个
hashset的空间 | y*****e
发帖数: 712 | 6 第二题需要这么多class吗？我觉得用一个hashmap， 再traverse map行不行呢？
jsonList
【在 n*********u 的大作中提到】
: 第一题感觉可以先以一个坐标轴扫描一遍所有垂直于那个坐标轴的可能的直线，放到一
: 个list里存起来。
: 把所有点放到一个hash map里存起来。
: 扫描完一遍后，对于每条直线，找需要构成正方形的另外两个点存不存在就行了。
: 第二题可以参考java的jsonObject class，或者类似的。
: 也就是把json的几个类别弄出来，(int,long,float), string, jsonObject, jsonList
: ，每个都有自己的__str__().
: 像画tree一样让__str__()自己recursive print出来就行了。
| n*********u
发帖数: 1030 | 7
直接用map的话，python, php什么的应该没问题。
但是java这种strong typing好像不是很方便（Object有点hacky）。
比如
{
"A":1
"B":"C"
}
或者写interface？
而且如果他问题里说要用data structure的话。。。
【在 y*****e 的大作中提到】
: 第二题需要这么多class吗？我觉得用一个hashmap， 再traverse map行不行呢？
:
: jsonList
| y*****e
发帖数: 712 | 8 我好像突然明白了，这题和L家的print nested map level order traversal 是一个思
路啊应该。
【在 n*********u 的大作中提到】
:
: 直接用map的话，python, php什么的应该没问题。
: 但是java这种strong typing好像不是很方便（Object有点hacky）。
: 比如
: {
: "A":1
: "B":"C"
: }
: 或者写interface？
: 而且如果他问题里说要用data structure的话。。。
| T*****u
发帖数: 7103 | 9 我觉着你说的有戏。坐标是int，说明应该用hash或者点的范围不大的话用matrix存点
，然后根据square rule dsf从matrix的一个稀疏的边开始搜索。应为点的分布和
matrix的形状，每次搜索的范围不一定是全部的点，只是其中一个subset。
者4
【在 c*******e 的大作中提到】
: 第一题，我觉得大的思路和2sum / 3sum是类似的
: - 所有的点进hashset，方便o(1)的查找 同时进一个array，方便遍历所有点对的组合
: - for (每两个点的组合)
: 计算组成正方形的第三和第四个点的可能坐标，有两组 （镜像的两个正方形），从
: hash里找，无法同时找到第三点或者第四点，则失败
: 时间 o(n2)，空间o(n)
: 进一步分析 - 由于正方形有4个边，我们是先定一边，再判断能否找到另外两点(或者4
: 点)出一个(或一对镜像)正方形，计算成功次数，会多算。为了去重复：
: a方法: 可以引入一个hashset来存储已经算出来的正方形
: b方法：在每次发现正方形时，如果是独立的，singleSquareSide ++;
| b***e
发帖数: 1419 | 10 第一题看任意两点为对角线的正方形存在否. O(n^2) with Hash.
p2
【在 y*****e 的大作中提到】
: 1. 给你一些平面的点（坐标是整数），求能够成正方形的数目。
: 我想了想这题大概可以这么做：把每两个点之间的距离用hashmap存下来，key是
: distance, values是arraylist of point pairs， 比如（p1, p2), (p3,p4)之间距离
: 都是6, 把他们都放到map.get(6)的list里面。这样一共要查（n,2)pairs, time也就是
: (n^2). 下一步对于每一个distance, 查看对应的list size是不是大于4（至少有4个
: pairs之间距离相同）。然后对于每一个list再进一步确定有没有正方形，比如
: (p1,p2), (p1,p3), (p1,p4), (p2, p3), (p2, p4), (p3, p4) 都在list里，就可以确
: 认这四个点可以组成正方形。。。。确认的时候可以再建一个hashmap, map p1 to (p2
: , p3, p4), p2 to (p3, p4), 然后找需要的pair是不是都在map里。。。就是好麻烦这
: 个solution, 不知有没有简单点的解法？
| | | c*******e
发帖数: 373 | 11 对角线好
我提的想法里，从一边开始，有镜像正方形的特殊情况，增加了一点复杂性
【在 b***e 的大作中提到】
: 第一题看任意两点为对角线的正方形存在否. O(n^2) with Hash.
:
: p2
| y*****e
发帖数: 712 | 12 我觉得这个办法好。。。想问一下具体怎么找另外两个点。
比如(x1,y1), (x2,y2)组成对角线，找另外两点，可以链接这两点，顺时针旋转45度找
一个点，逆时针转45度找另一个点。这是要解方程吗？如果对角线是a, 正方形边就是a
/sqrt(2), 我怎么觉得写程序实现这个还很麻烦啊
【在 b***e 的大作中提到】
: 第一题看任意两点为对角线的正方形存在否. O(n^2) with Hash.
:
: p2
| C****t
发帖数: 53 | 13 可以用中点的法线方向来做。
p1 = [x1, y1]
p2 =[x2, y2]
mid =[ (x1+x2)/2, (y1+y2)/2 ]
normal = [y2-y1, x1-x2]
standardNormal = normal / sqrt( y2-y1)^2 + (x1-x2)^2 )
distance = |p1-p2|/2
p3 or p4 = mid +- standardNormal*distance
check p3 和 p4 是不是都在 hashset里面。 | x*****0
发帖数: 452 | | y*****e
发帖数: 712 | 15 太赞了谢谢！忘了互相垂直的两线段乘积是-1这个条件了，都还给数学老师了。。。
【在 C****t 的大作中提到】
: 可以用中点的法线方向来做。
: p1 = [x1, y1]
: p2 =[x2, y2]
: mid =[ (x1+x2)/2, (y1+y2)/2 ]
: normal = [y2-y1, x1-x2]
: standardNormal = normal / sqrt( y2-y1)^2 + (x1-x2)^2 )
: distance = |p1-p2|/2
: p3 or p4 = mid +- standardNormal*distance
: check p3 和 p4 是不是都在 hashset里面。
| c*******e
发帖数: 373 | 16 简单的加减就可以了哦
以(x1,y1), (x2, y2)为对角线上两点的正方形的另外两点，坐标用newX1,newY1,
newX2,newY2表示
dx=(x2-x1)/2;
dy=(y2-y1)/2;
cx = x1+dx;
cy = y1+dy;
newX1 = cx - dy;
newY1 = cy - dx;
newX2 = cx + dy;
newY2 = cy - dx;
【在 C****t 的大作中提到】
: 可以用中点的法线方向来做。
: p1 = [x1, y1]
: p2 =[x2, y2]
: mid =[ (x1+x2)/2, (y1+y2)/2 ]
: normal = [y2-y1, x1-x2]
: standardNormal = normal / sqrt( y2-y1)^2 + (x1-x2)^2 )
: distance = |p1-p2|/2
: p3 or p4 = mid +- standardNormal*distance
: check p3 和 p4 是不是都在 hashset里面。
| y*****e
发帖数: 712 | 17 好像不可以吧。。。两点连的线段可以是任何角度的，不一定是平行x,y轴的。
【在 c*******e 的大作中提到】
: 简单的加减就可以了哦
: 以(x1,y1), (x2, y2)为对角线上两点的正方形的另外两点，坐标用newX1,newY1,
: newX2,newY2表示
: dx=(x2-x1)/2;
: dy=(y2-y1)/2;
: cx = x1+dx;
: cy = y1+dy;
: newX1 = cx - dy;
: newY1 = cy - dx;
: newX2 = cx + dy;
| f******4
发帖数: 51 | 18 同问第二题，尤其是indent和括号的情况怎么处理？ | c*******e
发帖数: 373 | 19 你画一个正方形 再把两个对角线画上 看看四个点和中心那个点的关系
然后可能就明白
想通了很简单
【在 y*****e 的大作中提到】
: 好像不可以吧。。。两点连的线段可以是任何角度的，不一定是平行x,y轴的。
| h******k
发帖数: 810 | 20 反证一下：按照你的算法，如果正方形对角线两点坐标都是有理数，则另一条对角线两
点坐标也一定是有理数。因为你公式里只有加减乘除。这个显然不成立。
【在 c*******e 的大作中提到】
: 你画一个正方形 再把两个对角线画上 看看四个点和中心那个点的关系
: 然后可能就明白
: 想通了很简单
| c*******e
发帖数: 373 | 21 大哥 画个图就知道了
道理很简单 如果以正方形对角线的中点为坐标原点 那么正方形的四个点 都是旋转90
度 就相互重合了
一个点 绕原点旋转90度 坐标会怎么样变化？有理数会变无理吗？当然不会，因为是90
度啊
你的反证法 搞混了顶点坐标和边长了
如果顶点坐标是整数 那么边长很可能无理 因为勾股定理里面有开方造成的嘛
反之亦然
现在的题目 顶点都是整数或者有理数 没有矛盾的
给个例子吧 正方形的4个点坐标:
-1,-3
1,3
-3,1
3,-1
【在 h******k 的大作中提到】
: 反证一下：按照你的算法，如果正方形对角线两点坐标都是有理数，则另一条对角线两
: 点坐标也一定是有理数。因为你公式里只有加减乘除。这个显然不成立。
| l*******c
发帖数: 316 | |
|
