- 浏览: 71761 次
- 性别:
- 来自: 北京
最新评论
-
xiayh04:
楼主好人!
Django书籍分享 -
winchun323:
感觉楼主,资料下载了!!!
ANDROID资料共享 -
tonyseek:
sydra 写道不是很懂python,鄙人是做java的,很奇 ...
Python单例模式 -
tterry:
没看出来怎么个劣法,莫非你说劣就劣?
避免劣化的python代码 -
edison0951:
Kabie 写道Singleton模式一般是用metaclas ...
Python单例模式
1.平衡点问题
平衡点:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24,25后面的总和也是24,25这个点就是平衡点;假如一个数组中的元素,其前面的部分等于后面的部分,那么这个点的位序就是平衡点
要求:返回任何一个平衡点
下面是代码:
2.支配点问题:
支配数:数组中某个元素出现的次数大于数组总数的一半时就成为支配数,其所在位序成为支配点;比如int[] a = {3,3,1,2,3};3为支配数,0,1,4分别为支配点;
要求:返回任何一个支配点
本问题可归结为众数问题(统计学范畴),即一组数据中出现次数最多的那个数值,它可以没有也可以为多个。
下面是代码,如果你又更号的实现,不吝赐教。
最后,还有个一个中位数的问题,在很多笔试中也会遇到。
中位数:即数据从小到大排列,将数据分为两部分,一部分大于该数值,一部分小与该数值。中位数的位置是这样计算的:如果数据长度为奇数,中位数的位置为(N+1)/2,如果为偶数则为第N/2个数与第(N/2)+1的平均数。
强!算法好牛啊! 大哥什么学历几年经验平常都看些什么书啊 ?
想您学习啊! 我只想到个最SB的是 for 循环。。。 效率太低了!
不敢当,小弟小本,09年7月份毕业。看过thinking in java(部分),practical java(市场上很难找到了),js,
感觉JavaScript的灵活性可以提高java水瓶,个人意见。
这句恐怕得改改,如果leftSum = 1, (sum - numbers[i]) = 3,结果会怎样?
强!算法好牛啊! 大哥什么学历几年经验平常都看些什么书啊 ?
想您学习啊! 我只想到个最SB的是 for 循环。。。 效率太低了!
运行你的代码 无法得出正确结果 !
平衡点一定是最大值,找出最大值和所在的点的时候的和,遍历能够求和。相减进行比较
平衡点不一定是最大值,例如[1,1,1,1,2,1], 其中第四个1为平衡点且不是数组中最大值
明白了```重新修改一下代码
右值的总和可以用 数组总和-左值总-平衡点,不需要再把右边加一遍。
平衡点:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24,25后面的总和也是24,25这个点就是平衡点;假如一个数组中的元素,其前面的部分等于后面的部分,那么这个点的位序就是平衡点
要求:返回任何一个平衡点
下面是代码:
1 li = [1,3,5,7,8,25,4,20] 2 def main(): 3 i = 0 4 length = len(li) 5 before = 0 6 after = 0 7 mark = 0 8 balance = 0 9 total = sum(li) 10 while True: 11 balance = i + 1 12 if balance + 1 > length -1: 13 return -1 14 if li[i] == li[balance+1]: 15 mark = balance 16 return (mark,li[mark]) 17 else: 18 before = before + li[i] 19 other = total - before - li[balance] 20 if before == other: 21 mark = balance 22 return (mark,li[mark]) 23 i += 1 24 if __name__ == "__main__": 25 print main()
2.支配点问题:
支配数:数组中某个元素出现的次数大于数组总数的一半时就成为支配数,其所在位序成为支配点;比如int[] a = {3,3,1,2,3};3为支配数,0,1,4分别为支配点;
要求:返回任何一个支配点
本问题可归结为众数问题(统计学范畴),即一组数据中出现次数最多的那个数值,它可以没有也可以为多个。
下面是代码,如果你又更号的实现,不吝赐教。
1 li = [1,3,4,3,3] 2 def main(): 3 mid = len(li)/2 4 for l in li: 5 count = 0 6 i = 0 7 mark = 0 8 while True: 9 if l == li[i]: 10 count += 1 11 temp = i 12 i += 1 13 if count > mid: 14 mark = temp 15 return (mark,li[mark]) 16 if i > len(li) - 1: 17 break 18 else: 19 return -1 20 if __name__ == "__main__": 21 print main()
最后,还有个一个中位数的问题,在很多笔试中也会遇到。
中位数:即数据从小到大排列,将数据分为两部分,一部分大于该数值,一部分小与该数值。中位数的位置是这样计算的:如果数据长度为奇数,中位数的位置为(N+1)/2,如果为偶数则为第N/2个数与第(N/2)+1的平均数。
评论
26 楼
mwei
2010-02-25
showr 写道
强!算法好牛啊! 大哥什么学历几年经验平常都看些什么书啊 ?
想您学习啊! 我只想到个最SB的是 for 循环。。。 效率太低了!
不敢当,小弟小本,09年7月份毕业。看过thinking in java(部分),practical java(市场上很难找到了),js,
感觉JavaScript的灵活性可以提高java水瓶,个人意见。
25 楼
279471315
2010-02-24
int[] numbers = {1,3,5,7,8,25,1,5,7,8,3};
int count = 0;
int nowcount = 0;
int zhi = 0;
for(int i=0;i<numbers.length;i++){
count += numbers[i];
}
for(int j=0;j<numbers.length;j++){
int now = numbers[j];
int x = (count-now)/2;
if(nowcount==x){
zhi = now;
break;
}
nowcount += now;
}
System.out.println(zhi);
int count = 0;
int nowcount = 0;
int zhi = 0;
for(int i=0;i<numbers.length;i++){
count += numbers[i];
}
for(int j=0;j<numbers.length;j++){
int now = numbers[j];
int x = (count-now)/2;
if(nowcount==x){
zhi = now;
break;
}
nowcount += now;
}
System.out.println(zhi);
24 楼
xingqiliudehuanghun
2010-02-24
不懂python,javascript写的,用java还要开编辑器太麻烦。
var a=[1,3,5,7,8,25,1,5,7,8,3]; var totalSum=(function(){ var ret=0; for(var i=0,len=a.length;i<len;i++){ ret+=a[i]; } return ret; })(); var sum=a[0],points=[]; for(var i=1,len=a.length;i<len;i++){ if(sum*2+a[i]==totalSum){ points.push(a[i]); } sum+=a[i]; } alert(points); //支配点问题,用Map解决-------------------------------------- var a = [3,3,1,2,3]; var mid=parseInt(a.length/2); var map={}; var points=[]; var record; for(var i=0,len=a.length;i<len;i++){ record=map[a[i]]?map[a[i]]:map[a[i]]={value:a[i],count:0,points:[]}; record.count++; record.points.push(i); } for(var key in map){ record=map[key]; if(record.count>mid){ points.push(record); } } for(var i=0;i<points.length;i++){ alert("支配数:"+points[i].value+"\n支配点:"+points[i].points); }
23 楼
leason
2010-02-24
erotica 写道
public int balance(int[] numbers) {
int sum = sum(numbers);
int leftSum = 0;
for (int i = 1; i < numbers.length - 1; i++) {
leftSum += numbers[i - 1];
if ((sum - numbers[i]) / 2 == leftSum) {
return numbers[i];
}
}
throw new RuntimeException("数组:" + numbers.toString() + "没有平衡点");
}
int sum = sum(numbers);
int leftSum = 0;
for (int i = 1; i < numbers.length - 1; i++) {
leftSum += numbers[i - 1];
if ((sum - numbers[i]) / 2 == leftSum) {
return numbers[i];
}
}
throw new RuntimeException("数组:" + numbers.toString() + "没有平衡点");
}
if ((sum - numbers[i]) / 2 == leftSum) { return numbers[i]; }
这句恐怕得改改,如果leftSum = 1, (sum - numbers[i]) = 3,结果会怎样?
22 楼
darkbaby123
2010-02-24
<p>问一下LZ平衡点的问题,像这样的数组:[1, 0, 0],第一个数 1 算平衡点吗?</p>
<p>而且我试过LZ的代码,似乎数组必须是5位或以上,才算做可以计算平衡点的数组?</p>
<p>因为下面两个数组都无法通过测试:</p>
<p>[1, 2, 1] # 按LZ的说法,数字 2 的位序应该是平衡点</p>
<p>[1, 1, 3, 2] # 数字 3 的位序应该是平衡点</p>
<p>还是这个平衡点算法对数组有其他要求,比如数组元素不能重复?</p>
<p> </p>
<p>平衡点算法:</p>
<p>需要两次循环,sum一次,循环比较一次(len不知道算不算,要算就有三次了……)。另外,每次算after时都要从数组中按下标取(不过这不算什么吧)元素。下面的思路可以不计算after,但个人觉得性能节省可以忽略不计……</p>
<pre name="code" class="python"># 懒得想名字,大家包涵
def ping_heng(li):
# before,after分别为的前后的总和
before, after = 0, sum(li[1:])
idx, li_len = 0, len(li)
for num in li:
if before == after:
return (idx, num)
if idx == li_len - 1:
return (None, None)
idx += 1
# 随着循环,before不断增加,after不断减少
before += num
after -= li[idx]
if __name__ == '__main__':
test_lists = (
[1, 0, 0, 0],
[1, 3, 5, 7, 8, 25, 4, 20],
[1, 3, 5, 7, 8, 25, 7, 20],
)
for li in test_lists:
print "list: %s" % li
print "index: %s number: %s\n" % ping_heng(li)</pre>
<p>测试结果:</p>
<pre name="code" class="console">list: [1, 0, 0, 0]
index: 0 number: 1
list: [1, 3, 5, 7, 8, 25, 4, 20]
index: 5 number: 25
list: [1, 3, 5, 7, 8, 25, 7, 20]
index: None number: None</pre>
<p> </p>
<p>其实还有个思路,就是判断 <strong>before * 2 + current_num == total</strong>,这样就不需要计算after了。但最开始的求和还是省不了。问下有没有不求和,就一次循环搞定的?</p>
<p> </p>
<p>支配点算法:</p>
<p>基本实现功能。一次循环,利用了Python的dictionary简化代码,这在纯算法题中该算是取巧了吧?不过我觉得利用语言特性也算是编程的一个方面</p>
<pre name="code" class="python"># 支配点算法:
def zhi_pei(li):
dic = {} # 用dictionary来存储每个数出现的次数
mid = len(li) / 2
for num in li:
# 如果一个数重复出现,则把计数加1,否则当做第一次出现
if num in dic.keys():
dic[num] += 1
else:
dic[num] = 1
if dic[num] > mid:
return (num, dic[num])
return (None, None)
if __name__ == '__main__':
test_zp = (
[1],
[1, 2],
[1, 2, 2],
[3, 3, 1, 2, 3],
[2, 2, 3, 3, 2, 2],
)
for li in test_zp:
print "list: %s" % li
print "number: %s count: %s\n" % zhi_pei(li)</pre>
<p>测试结果:</p>
<pre name="code" class="console">list: [1] # 嗯,我觉得对于一个元素的数组,应该是这个结果……
number: 1 count: 1
list: [1, 2]
number: None count: None
list: [1, 2, 2]
number: 2 count: 2
list: [3, 3, 1, 2, 3]
number: 3 count: 3
list: [2, 2, 3, 3, 2, 2]
number: 2 count: 4</pre>
<p>而且我试过LZ的代码,似乎数组必须是5位或以上,才算做可以计算平衡点的数组?</p>
<p>因为下面两个数组都无法通过测试:</p>
<p>[1, 2, 1] # 按LZ的说法,数字 2 的位序应该是平衡点</p>
<p>[1, 1, 3, 2] # 数字 3 的位序应该是平衡点</p>
<p>还是这个平衡点算法对数组有其他要求,比如数组元素不能重复?</p>
<p> </p>
<p>平衡点算法:</p>
<p>需要两次循环,sum一次,循环比较一次(len不知道算不算,要算就有三次了……)。另外,每次算after时都要从数组中按下标取(不过这不算什么吧)元素。下面的思路可以不计算after,但个人觉得性能节省可以忽略不计……</p>
<pre name="code" class="python"># 懒得想名字,大家包涵
def ping_heng(li):
# before,after分别为的前后的总和
before, after = 0, sum(li[1:])
idx, li_len = 0, len(li)
for num in li:
if before == after:
return (idx, num)
if idx == li_len - 1:
return (None, None)
idx += 1
# 随着循环,before不断增加,after不断减少
before += num
after -= li[idx]
if __name__ == '__main__':
test_lists = (
[1, 0, 0, 0],
[1, 3, 5, 7, 8, 25, 4, 20],
[1, 3, 5, 7, 8, 25, 7, 20],
)
for li in test_lists:
print "list: %s" % li
print "index: %s number: %s\n" % ping_heng(li)</pre>
<p>测试结果:</p>
<pre name="code" class="console">list: [1, 0, 0, 0]
index: 0 number: 1
list: [1, 3, 5, 7, 8, 25, 4, 20]
index: 5 number: 25
list: [1, 3, 5, 7, 8, 25, 7, 20]
index: None number: None</pre>
<p> </p>
<p>其实还有个思路,就是判断 <strong>before * 2 + current_num == total</strong>,这样就不需要计算after了。但最开始的求和还是省不了。问下有没有不求和,就一次循环搞定的?</p>
<p> </p>
<p>支配点算法:</p>
<p>基本实现功能。一次循环,利用了Python的dictionary简化代码,这在纯算法题中该算是取巧了吧?不过我觉得利用语言特性也算是编程的一个方面</p>
<pre name="code" class="python"># 支配点算法:
def zhi_pei(li):
dic = {} # 用dictionary来存储每个数出现的次数
mid = len(li) / 2
for num in li:
# 如果一个数重复出现,则把计数加1,否则当做第一次出现
if num in dic.keys():
dic[num] += 1
else:
dic[num] = 1
if dic[num] > mid:
return (num, dic[num])
return (None, None)
if __name__ == '__main__':
test_zp = (
[1],
[1, 2],
[1, 2, 2],
[3, 3, 1, 2, 3],
[2, 2, 3, 3, 2, 2],
)
for li in test_zp:
print "list: %s" % li
print "number: %s count: %s\n" % zhi_pei(li)</pre>
<p>测试结果:</p>
<pre name="code" class="console">list: [1] # 嗯,我觉得对于一个元素的数组,应该是这个结果……
number: 1 count: 1
list: [1, 2]
number: None count: None
list: [1, 2, 2]
number: 2 count: 2
list: [3, 3, 1, 2, 3]
number: 3 count: 3
list: [2, 2, 3, 3, 2, 2]
number: 2 count: 4</pre>
21 楼
laitaogood
2010-02-24
平衡点问题
支配者问题
轩辕互动机试不会还是这几道题吧
/** * 寻找平衡点 * * @author 陌上霜寒 * Jun 26, 2009 */ public class Equity { /** * 返回一个数组的平衡点 * @param numbers * @return 平衡点 */ public static int equity(int[] numbers){ //初始下标 int initPoint = numbers.length/2; //平衡点下标 int eqPoint = -1; for(int i = 0;i<numbers.length;i++){ int frontSum = 0; int endSum = 0; //前部分元素之和 for(int j = 0;j<initPoint;j++){ frontSum +=numbers[j]; } //后部分元素之和 for(int k = initPoint+1;k<numbers.length;k++){ endSum +=numbers[k]; } if(frontSum == endSum){ eqPoint = initPoint; break; }else if(frontSum < endSum){ initPoint ++; }else{ initPoint --; } } //另一个思路是:先求出所有的和,然后取得前一部分的和,然后就可以得到后半部分的和了,避免了再次循环 return eqPoint; } public static void main(String[]args){ int[] numbers = new int[]{1,8,7,8,25,4,49,30,23}; System.out.println("The equity number index is === "+Equity.equity(numbers)); } }
支配者问题
import java.util.HashMap; import java.util.Map; /** * 寻找支配者 * * @author 陌上霜寒 * Jun 26, 2009 */ public class Dominator { /** * 寻找支配者的下标 * @param a * @return 支配者的下标 */ public static int dominator(int a[]){ Map<String,String> map = new HashMap<String,String>(); String key = null; String value = null; for(int j:a){ key = String.valueOf(j); value = map.get(key); if(map.get(key) != null){ value = String.valueOf(Integer.parseInt(value)+1); map.put(key, value); }else{ map.put(key, "1"); } } int dominator = 0; for(String k:map.keySet()){ float intValue = Float.parseFloat(map.get(k)); if(intValue/a.length >0.5){ dominator = Integer.parseInt(k); break; } } for (Map.Entry<String, String> entry : map.entrySet()) { String eachCount = entry.getValue(); } int index = -1; for(int i:a){ if(a[i] == dominator){ index = i; break; } } return index; } /** * 主方法 * @param args */ public static void main(String[]args){ int[]a = new int[]{2,4,4,2,4,5,4,3,4,4}; System.out.println("The random index is === "+Dominator.dominator(a)); } }
轩辕互动机试不会还是这几道题吧
20 楼
erotica
2010-02-24
public int balance(int[] numbers) {
int sum = sum(numbers);
int leftSum = 0;
for (int i = 1; i < numbers.length - 1; i++) {
leftSum += numbers[i - 1];
if ((sum - numbers[i]) / 2 == leftSum) {
return numbers[i];
}
}
throw new RuntimeException("数组:" + numbers.toString() + "没有平衡点");
}
int sum = sum(numbers);
int leftSum = 0;
for (int i = 1; i < numbers.length - 1; i++) {
leftSum += numbers[i - 1];
if ((sum - numbers[i]) / 2 == leftSum) {
return numbers[i];
}
}
throw new RuntimeException("数组:" + numbers.toString() + "没有平衡点");
}
19 楼
showr
2010-02-24
mwei 写道
给个一目了然版的,前后同时求和
public static void getBalancePoint(int[] arg){ if(arg==null){ System.out.println("array is null..."); return; } if(arg.length<3){ System.out.println("array's length is smaller than 3...no balance..."); return; } if(arg.length==3){ if(arg[0]==arg[2]){ System.out.println("array's balance is : "+arg[1]); }else{ System.out.println("array has no balance..."); } return; } int totalHead=0; //前部分总和(假设数组下标小的部分表示前) int totalEnd=0; //后部分总和 int head=0; //前部分的数组下标 int end=arg.length-1; //后部分的数组下标 boolean addHead=true; //是否累加前部分 boolean addEnd=true; //是否累加后部分 int addCount=0; //总共累加次数 while(head<end){ if(addHead){ //前部分依次累加 totalHead+=arg[head]; addCount++; } if(addEnd){ //后部分依次累加 totalEnd+=arg[end]; addCount++; } if(totalHead<totalEnd){ //只允许前部分累加 head++; addHead=true; addEnd=false; }else if(totalHead>totalEnd){ //只允许后部分累加 end--; addHead=false; addEnd=true; }else{ //前后同时累加 head++; end--; addHead=true; addEnd=true; } } //end while if(addCount==(arg.length-1)){ System.out.println("array's balance is : "+arg[head]); }else{ System.out.println("array has no balance..."); } }
强!算法好牛啊! 大哥什么学历几年经验平常都看些什么书啊 ?
想您学习啊! 我只想到个最SB的是 for 循环。。。 效率太低了!
18 楼
showr
2010-02-24
koth 写道
平衡点Java代码, 时间复杂度O(N)
二楼贴的平衡点还是25,可找出
public int calcBalance(int arr[]) { int left[]=new int[arr.length]; int right[]=new int[arr.length]; int b=arr.length-1; for(int i=0;i<left.length;i++) { if(i==0) { left[i]=0; } else { left[i]=left[i-1]+arr[i-1]; } } for(;b>=0;b--) { if(b==arr.length-1) { right[b]=0; } else { right[b]=right[b+1]+arr[b+1]; } if(left[b]==right[b])return b; } return b; }
二楼贴的平衡点还是25,可找出
运行你的代码 无法得出正确结果 !
17 楼
mwei
2010-02-23
给个一目了然版的,前后同时求和
public static void getBalancePoint(int[] arg){ if(arg==null){ System.out.println("array is null..."); return; } if(arg.length<3){ System.out.println("array's length is smaller than 3...no balance..."); return; } if(arg.length==3){ if(arg[0]==arg[2]){ System.out.println("array's balance is : "+arg[1]); }else{ System.out.println("array has no balance..."); } return; } int totalHead=0; //前部分总和(假设数组下标小的部分表示前) int totalEnd=0; //后部分总和 int head=0; //前部分的数组下标 int end=arg.length-1; //后部分的数组下标 boolean addHead=true; //是否累加前部分 boolean addEnd=true; //是否累加后部分 int addCount=0; //总共累加次数 while(head<end){ if(addHead){ //前部分依次累加 totalHead+=arg[head]; addCount++; } if(addEnd){ //后部分依次累加 totalEnd+=arg[end]; addCount++; } if(totalHead<totalEnd){ //只允许前部分累加 head++; addHead=true; addEnd=false; }else if(totalHead>totalEnd){ //只允许后部分累加 end--; addHead=false; addEnd=true; }else{ //前后同时累加 head++; end--; addHead=true; addEnd=true; } } //end while if(addCount==(arg.length-1)){ System.out.println("array's balance is : "+arg[head]); }else{ System.out.println("array has no balance..."); } }
16 楼
马背{eric.liu}
2010-02-23
换一种思路写看看:)
BTW:又改了下,修改前后累加值相等时候的判断。
BTW:又改了下,修改前后累加值相等时候的判断。
public class BalanceElement { public static void main(String[] argc) { //测试数据:{1,1,1,1,2,1}; int[] elements = new int[]{1, 3, 5, 7, 8, 25, 4, 20}; findBalance(elements); } public static void findBalance(int[] elements) { //判断不合理情况 if (elements == null || elements.length < 3) { System.out.println("==bad elements =="); return; } int pos = 0; //最终找到的平衡点的位置 int element = 0; //平衡点的值 int n = elements.length; //当前判断剩余的元素,初始值为元素总长度 int headPos = -1; //循环判断中头部元素位置 int tailPos = elements.length; //循环判断中尾部元素位置 int head = 0; //头部值的累加和 int tail = 0; //尾部值的累加和 boolean headStep = true; //头部累加在循环判断中下一步是否前进 boolean tailStep = true; //尾部累加在循环判断中下一步是否前进 //循环判断 do { if (headStep) { head += elements[++headPos]; n--; } if (tailStep) { tail += elements[--tailPos]; n--; } if (head < tail) { headStep = true; tailStep = false; } else if (head > tail) { headStep = false; tailStep = true; } else if(n==1){ //注意此处n==1的判断 pos = headPos + 1; element = elements[pos]; } } while (n > 1); //输出结果 if (pos != 0) { System.out.println("==find balance element pos is:" + pos + ",and value is:" + element); } else { System.out.println("==can't find balance element =="); } } }
15 楼
马背{eric.liu}
2010-02-23
seele 写道
public int blanPoint(int[] intArray) { int max = 0; int sum_point = 0; int sum = 0; for (int i = 0; i < intArray.length; i++) { sum += intArray[i]; if (intArray[i] > max) { sum_point = sum; max = intArray[i]; } } if ((sum - sum_point) == (sum_point - max)) { System.out.println("max:" + max); return max; } else { System.out.println("NO POINT"); return 0; } }
平衡点一定是最大值,找出最大值和所在的点的时候的和,遍历能够求和。相减进行比较
平衡点不一定是最大值,例如[1,1,1,1,2,1], 其中第四个1为平衡点且不是数组中最大值
14 楼
seele
2010-02-23
明白了```重新修改一下代码
13 楼
fanzy618
2010-02-23
平衡点:
加上求和操作要遍历两遍,不知道有什么方法可以只遍历一边?
def calcBalance(array): left = 0 right = sum(array) for i,offset in range(len(array)): if left + i == right: return offset,i left += i right -= i else: return None
加上求和操作要遍历两遍,不知道有什么方法可以只遍历一边?
12 楼
clchun
2010-02-23
<pre name="code" class="Perl">#!/usr/bin/perl
@num=(1,1,1,1,2,2,2,2,3,3,3,3,4,5,6,7,8,9,10);
sub getCount
{
my @temp=@_;
# print @temp."\n";
my %count;
my %result=();
for $i (0..@temp-1)
{
# print $temp[$i]."\n";
$count{$temp[$i]}.=$i.',';
}
my $templength=0;
foreach $key (keys(%count))
{
# print $key."\n";
$count{$key} =~s/,$//;
my @position=split(',',$count{$key});
if ( @position>$templength){
undef %result=();
$templength= @position;
$result{$key}=$count{$key};
}
elsif(@position==$templength)
{
$result{$key}=$count{$key};
}
}
return %result;
}
%temp1 = getCount(@num);
foreach $key (keys(%temp1))
{
print $key."---".$temp1{$key}."\n";
}
exit;
</pre>
@num=(1,1,1,1,2,2,2,2,3,3,3,3,4,5,6,7,8,9,10);
sub getCount
{
my @temp=@_;
# print @temp."\n";
my %count;
my %result=();
for $i (0..@temp-1)
{
# print $temp[$i]."\n";
$count{$temp[$i]}.=$i.',';
}
my $templength=0;
foreach $key (keys(%count))
{
# print $key."\n";
$count{$key} =~s/,$//;
my @position=split(',',$count{$key});
if ( @position>$templength){
undef %result=();
$templength= @position;
$result{$key}=$count{$key};
}
elsif(@position==$templength)
{
$result{$key}=$count{$key};
}
}
return %result;
}
%temp1 = getCount(@num);
foreach $key (keys(%temp1))
{
print $key."---".$temp1{$key}."\n";
}
exit;
</pre>
11 楼
clchun
2010-02-23
<pre name="code" class="Perl">#!/usr/bin/perl
my @num=(1,2,3,8,9,10,4);
sub getBalance
{
my($balance,@temp)=@_;
my($templeft,$tempright)=(0,0);
for $i (0..$balance-1)
{
$templeft+=$temp[$i];
}
for $i($balance+1..@temp-1)
{
$tempright+=$temp[$i];
}
print $balance,"\t", $templeft,"\t", $tempright,"\n";
if($templeft==$tempright)
{
return $temp[$balance];
}
elsif($templeft<$tempright)
{
getBalance($balance+1,@temp) ;
}
else
{
getBalance($balance-1,@temp) ;
}
}
print getBalance(6,@num);
exit;</pre>
my @num=(1,2,3,8,9,10,4);
sub getBalance
{
my($balance,@temp)=@_;
my($templeft,$tempright)=(0,0);
for $i (0..$balance-1)
{
$templeft+=$temp[$i];
}
for $i($balance+1..@temp-1)
{
$tempright+=$temp[$i];
}
print $balance,"\t", $templeft,"\t", $tempright,"\n";
if($templeft==$tempright)
{
return $temp[$balance];
}
elsif($templeft<$tempright)
{
getBalance($balance+1,@temp) ;
}
else
{
getBalance($balance-1,@temp) ;
}
}
print getBalance(6,@num);
exit;</pre>
10 楼
edisonlz
2010-02-23
## #2.支配点问题: #支配数:数组中某个元素出现的次数大于数组总数的一半时就成为支配数,其所在位序成为支配点;比如int[] a = {3,3,1,2,3};3为支配数,0,1,4分别为支配点; puts "支配点问题" + "* " * 20 h_count = {} #用于存储数量 h_index = {} #用于存储位置 Hash a = [3,3,1,2,3] a.each_index do |i| h_count[a[i]]=0 if h_count[a[i]].nil? h_count[a[i]] += 1 h_index[a[i]] = [] if h_index[a[i]].nil? h_index[a[i]] << i end list = h_count.sort {|a,b| b[1]<=> a[1]} puts "支配数是:#{list[0][0]} 数量:#{list[0][1]}" puts "支配点数:#{h_index[list[0][0]].join(",")}"
9 楼
edisonlz
2010-02-23
##
#1.平衡点问题
# 平衡点:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24,25后面的总和也是24,25这个点就是平衡点;假如一个数组中的元素,其前面的部分等于后面的部分,那么这个点的位序就是平衡点
#要求:返回任何一个平衡点
#初始化常量
numbers = [1, 3, 5, 7, 8, 25, 4, 20]
len = numbers.size - 1
head_sum = 0;tail_sum = 0
head= 0;tail =len
#开始计算
for i in 0..len
(puts "mid is :#{numbers[i]} sum is:#{head_sum}";break) if head_sum.eql?(tail_sum) and head_sum > 0
(head_sum += numbers[head];head += 1) if head_sum <=tail_sum
(tail_sum += numbers[tail]; tail -= 1) if tail_sum <= head_sum
end
#1.平衡点问题
# 平衡点:比如int[] numbers = {1,3,5,7,8,25,4,20}; 25前面的总和为24,25后面的总和也是24,25这个点就是平衡点;假如一个数组中的元素,其前面的部分等于后面的部分,那么这个点的位序就是平衡点
#要求:返回任何一个平衡点
#初始化常量
numbers = [1, 3, 5, 7, 8, 25, 4, 20]
len = numbers.size - 1
head_sum = 0;tail_sum = 0
head= 0;tail =len
#开始计算
for i in 0..len
(puts "mid is :#{numbers[i]} sum is:#{head_sum}";break) if head_sum.eql?(tail_sum) and head_sum > 0
(head_sum += numbers[head];head += 1) if head_sum <=tail_sum
(tail_sum += numbers[tail]; tail -= 1) if tail_sum <= head_sum
end
8 楼
edison0951
2010-02-23
回复7楼,我就是用的和去减的,之前右边加确实有点麻烦。
7 楼
lzyzizi
2010-02-23
koth 写道
平衡点Java代码, 时间复杂度O(N)
二楼贴的平衡点还是25,可找出
public int calcBalance(int arr[]) { int left[]=new int[arr.length]; int right[]=new int[arr.length]; int b=arr.length-1; for(int i=0;i<left.length;i++) { if(i==0) { left[i]=0; } else { left[i]=left[i-1]+arr[i-1]; } } for(;b>=0;b--) { if(b==arr.length-1) { right[b]=0; } else { right[b]=right[b+1]+arr[b+1]; } if(left[b]==right[b])return b; } return b; }
二楼贴的平衡点还是25,可找出
右值的总和可以用 数组总和-左值总-平衡点,不需要再把右边加一遍。
发表评论
-
Python单例模式
2011-01-19 15:37 5102网上曾经看到过PYTHON的面试题中有一个是PYTHON的单例 ... -
How To Use Linux epoll with Python
2011-01-15 21:56 1648Benefits of Asynchronous Socket ... -
避免劣化的python代码
2010-12-02 16:16 2427劣化代码: s = [] for i in seq: ... -
三行代码的快速排序
2010-08-05 14:58 0def qsort(L): if len(L) &l ... -
memcache
2010-03-25 10:17 0import cmemcached import MySQLd ... -
读写XML文件
2010-03-11 15:05 01 from xml.dom.minidom impo ... -
守护进程(Python)
2010-03-08 20:19 2242守护进程:通常被定义为一个后台进程,而且它不属于任何一个终 ... -
备份代码
2010-03-04 11:19 0class Outter: name = None ... -
memcache,多线程
2010-02-26 17:11 0import threading import urll ... -
轩辕互动面试题目-----最大递增子序列(Python实现)
2010-02-12 10:46 2212数组A中存放很多数据,比如A={1,2,3,4,3,2,1,4 ... -
PYGAME初探
2010-01-29 16:09 1702这几天闲着无聊,想着自己编个小游戏来玩玩,看网上的大牛可是 ... -
Logging 模块的使用
2010-01-04 11:02 1070def initlog(): import lo ... -
(转)ASCII 到UNICODE再到UTF8
2009-12-23 13:54 2449从 ASCII 到 UTF-8 : 大话编码 话说当年,老美搞 ... -
(进阶)判断字符串中是否有汉字
2009-12-14 16:02 2361方式一:Regular Expressions a =u&qu ... -
wxPython + BOA
2009-09-05 19:12 4304最近公司要写个WINDOWS ...
相关推荐
Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python面试题及答案共70道Python...
Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 Python经典面试题 python面试题 python 面试题 Python经典面试题 ...
在面试准备过程中,了解和掌握一些常见的Python面试题对于求职者来说至关重要。以下将详细解释上述文件中提到的Python知识点。 1. 利用Python的内置函数sum()可以非常简便地计算序列的总和。例如一行代码`sum(range...
本文件内含10个文档,文档格式为md,需要用...包含:2019 Python最新面试题及答案16道题、110道Python面试题(上)、最常见的 35 个 Python 面试题及答案(2018 版)、整理的最全 python常见面试题(基本必考)等!
"128道Python面试题.pdf" Python基础知识点: 1. 文件操作:文件读写、文件类型、文件权限等。 2. 模块与包:Python中的模块和包、模块的导入、模块的使用等。 3. 日期处理:Python中的日期处理、日期格式化、日期...
Python面试题大全 Python是一种广泛应用于数据科学、人工智能、Web开发等领域的高级编程语言。以下是 Python 面试题大全,涵盖了 Python 的基础知识、语法、标准库、面向对象编程、多线程编程等方面。 1. Python ...
Python是目前编程领域最受欢迎的语言。...每道题都提供参考答案,希望能够帮助你在2019年求职面试中脱颖而出,找到一份高薪工作。这些面试题涉及Python基础知识、Python编程、数据分析以及Python函数库等多个方面。
python基础面试题 python程序员面试题
Python面试题汇总 Python 是如何进行内存管理的? Python 内部使用引用计数机制来保持追踪内存中的对象,所有对象都有引用计数。引用计数增加的情况有:1、一个对象分配一个新名称;2、将其放入一个容器中(如...
《剑指Offer面试题Python实现》是一份针对Python程序员在面试过程中可能会遇到的常见问题的解答集锦。这个资源主要涵盖了数据结构、算法、编程基础等多个方面,旨在帮助求职者提升技能,顺利通过面试。其中,...
【Python面试知识点详解】 1. **Python标准库**:Python提供了丰富的标准库,例如os、sys、re、math和datetime。os库包含了与操作系统交互的函数,如文件操作和路径处理;sys库常用于处理命令行参数;re库支持正则...
Python面试经验技巧面试题面试宝典python面试常见问题面试资料: 110道Python面试题.pdf Python面试宝典.pdf python面试常见的25个问题.pdf Python面试必须要看的16个问题.pdf 你不清楚的18个非技术面试题.pdf
大数据架构 python基础 数据库 等应有尽有 可免费下载 面经 面试题 python面试题 300多道题 ,可以参考一下 适用人群:大一到大四,正在找工作的各位老哥 ,我相信这份面试题会给你们带来满意的效果 但是切记 不要...
针对“110道Python面试题汇总”的主题,我们可以深入探讨其中可能涵盖的多个知识点,这些知识点是Python开发者在面试中可能会遇到的常见问题。 1. **基础语法**:面试中经常考察Python的基础知识,如变量定义、数据...
Python是一种广泛使用的高级编程语言,以其简洁明了的语法和强大的功能深受程序员喜爱。...这份"110道Python面试题汇总.pdf"将是你准备面试的重要参考资料,它覆盖了各个层面的问题,帮助你全面复习和巩固Python知识。
Python 面试题集锦 Python 是目前编程领域最受欢迎的语言,本文总结了 Python 面试中最常见的问题,涉及 Python 基础知识、Python 编程、数据分析以及 Python 函数库等多个方面。下面是对这些问题的详细解释: Q1 ...
### Python面试题详解 #### Python语言特性 **1. Python的函数参数传递** 在Python中,函数参数的传递实质上是引用的传递。这与C语言中的指针类似,但又有本质的区别。Python中所有变量都是对内存中某个对象的...
python面试题100道答案全部 一般的只写了30个答案题目大概有 1、一行代码实现1--100之和 2、如何在一个函数内部修改全局变量 利用global 修改全局变量 3、列出5个python标准库 os:提供了不少与操作系统相关联的函数...