求最大公约数--欧几里德算法

最后修改于: 2016-03-19 15:38:25.0

之前在算法和数据结构书上看过来着,时间一久又忘记了。

用GCD来表示最大公约数,GCD=Greatest Commen Divisor

欧几里德定理

  • 若 a=b×r+q 则gcd(a, b) = gcd(b, q).

欧几里德定理的证明:

a = b × r + q
设c = gcd(a, b), a = m×c, b= n×c

数组中出现次数超过一半的数字

最后修改于: 2016-03-15 22:22:41.0

题目描述

数组中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。

很容易想到一个解法就是用一个Map,key是数,value是这个数出现的次数,找到出现次数大于数组长度一般的就返回这个数,遍历完也没找到则返回0;

import java.util.*;
public class Solution {
    public int moreThanHalfNum(int [] array) {
        Map<Integer, Integer>

字符串的可能排列

最后修改于: 2016-03-14 21:22:53.0

题目描述

输入一个字符串(最长9个字母,可能有重复),按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。 结果请按字母顺序输出。 

自己写了一个解法:对于输入字符串str,把从第二个字母到结束的子串所排序的结果解出,然后把第一个字母分别插入这些结果的每一个位置,用Set排除重复。

这个解法不是很高效,存在很多重复的情况,还有一种办法是通过交换遍历每个位置上可能出现的每一个字母。下面是网上看到实现。

import java.util.*;
public class Solution {
    public ArrayList<String>

压栈与出栈序列

最后修改于: 2016-03-09 00:00:57.0

输入两个整数序列,第一个序列表示栈的压入顺序,请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序,序列4,5,3,2,1是该压栈序列对应的一个弹出序列,但4,3,5,1,2就不可能是该压栈序列的弹出序列。

 

代码其实很简单,一眼就能想清楚这个过程,先压栈直到找到第一个出栈的数,然后出栈,出到不能出又入栈。但是写代码的时候费了好大功夫才写清楚循环的组合和判断边界条件,大概是今天晚上脑子出毛病了。

import java.util.*;

public class Solution {
    public boolean IsPopOrder(int [] pus

求整数次幂

最后修改于: 2016-03-01 10:18:17.0

刚刚遇到一个题问

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

说实话以前对于求幂这个问题还真是一无所知,其实求整数次幂的方法很简单,利用整数的二进制表示就可以很快地完成。

比如求5的13次幂,13的二进制表示为1101,那么5^13=5^1*5^4*5^8=5^0001*5^0100*5^1000,最后的幂为二进制表示。

将exponent取绝对值,再向右移位,遇到1则乘到结果里,遇到0则自乘,这么说也不是很明确,直接看代码,很直观

public class Solution {  &n

矩形覆盖问题

最后修改于: 2016-02-29 23:02:42.0

题目如下:

我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形,总共有多少种方法?

最开始的思路是先横着一个一个填满,然后用竖着的两个小矩形去取代横着的两个。

这样其实很不好解,因为替换多少个?在哪里替换?都是问题,很容易造成情况漏掉或者重复。

说白了这个问题只是跳台阶问题穿了一个马甲,设覆盖2*n有f(n)种方法,那么覆盖2*n可以由以下两种方式完成

1、先覆盖2*(n-1),然后加一块横的

由二叉树的前序遍历和中序遍历数组重新构造树

最后修改于: 2016-02-28 23:02:38.0

这个题目也很常见,笔记里面遇到后序+中序的时候记过一下,今天又遇到前序+中序,就在网站上记一笔吧。

思路很简单:对任意一颗树或者子树。前序遍历的第一个元素val肯定是根,以val构造根,然后在中序遍历数组中找到val所在的位置index,

然后看中序数组中index左边还有没有元素,如果有的话,在前序数组中,val的后一个元素一定是左子树的根。

构造左子树时,前序数组中的“根”元素要依次向后推,因为根据前序遍历的定义,左子树遍历完才会轮到右子树,所以需要维护一个rootIndex记录前序数组中的“根”元素的位置。

关于我

男,1991年末出生,这个人很懒,其他的不想写了。
More about me

文章分类

其他玩意儿