算法练习LeetCode初级算法之数学

  • Fizz Buzz

    class Solution {

    public List<String> fizzBuzz(int n) {

    List<String> list=new LinkedList<>();

    for (int i = 1; i <=n; i++) {

    if (i%3==0&&i%5==0) {

    list.add("FizzBuzz");

    continue;

    }else if (i%3==0) {

    list.add("Fizz");

    continue;

    }else if (i%5==0) {

    list.add("Buzz");

    continue;

    }

    list.add(String.valueOf(i));

    }

    return list;

    }

    }

  • 计数质数

  • 很快的方法

    class Solution {

    public int countPrimes(int n) {

    if (n<3) {

    return 0;

    }

    int res=0;

    boolean[] notPrime=new boolean[n];//默认都为false

    for (int i = 2; i < n; i++) {

    if (!notPrime[i]) {

    res++;

    for (int j = 2; i*j < n; j++) {

    notPrime[i*j]=true;

    }

    }

    }

    return res;

    }

    }

  • 我的解法:耗时间

    class Solution {

    public int countPrimes(int n) {

    if (n==0||n==1||n==2) {

    return 0;

    }

    int res=0;

    for (int i = 2; i < n; i++) {

    boolean isPrimes=true;

    for (int j = 2; j <=Math.sqrt(i); j++) {

    if (i%j==0) {

    isPrimes=false;

    break;

    }

    }

    if (isPrimes) {

    res++;

    }

    }

    return res;

    }

    }

  • 3的幂

在解这道题的时候。首先要明确地将整数划分为两大部分,即小于等于零(此时没有幂,log x 其中x>0)

和大于零的部分;

在大于零的部分又可以划分为1和不能被3整除(则不是3的幂次方)和能被3整除的!

  • 递归法

    class Solution {

    public boolean isPowerOfThree(int n) {

    if (n==0) {

    return false;

    }else if (n==1) {

    return true;

    }else if (n%3==0) {

    return isPowerOfThree(n/3);

    }else {

    return false;

    }

    }

    }

  • 循环法

    class Solution {

    public boolean isPowerOfThree(int n) {

    if (n<1) {

    return false;

    }

    while (n!=1) {

    if (n%3!=0) {

    return false;

    }else {

    n/=3;

    }

    }

    return true;

    }

    }

  • 数学方法log10

    class Solution {

    public boolean isPowerOfThree(int n) {

    if (n<1) {

    return false;

    }

    double d=Math.log10(n)/Math.log10(3);

    return (d-(int)d)==0?true:false;

    }

    }

  • 罗马数字转整数

  • 我的解法:

    有点暴力,虽然代码很多,但很好理解,写出这么长的代码我确实好菜!!!

    因为没看清题目,人家都说了这六种特殊情况是因为小的在大的左边 蠢到家!!

    class Solution {

    public int romanToInt(String s) {

    int res=0;

    char[] cs=s.toCharArray();

    int len=cs.length;

    int i=len-1;

    int f=len-2;

    StringBuffer st=new StringBuffer();

    StringBuffer sp=new StringBuffer();

    //现将特殊和单个分为两个数组

    while (i>=0||f>=0) {

    try {

    if (cs[i]=='V'&&cs[f]=='I') {//1

    st.append(cs[f]);

    st.append(cs[i]);

    i-=2;

    f-=2;

    }else if (cs[i]=='X'&&cs[f]=='I') {//2

    st.append(cs[f]);

    st.append(cs[i]);

    i-=2;

    f-=2;

    }else if (cs[i]=='L'&&cs[f]=='X') {//3

    st.append(cs[f]);

    st.append(cs[i]);

    i-=2;

    f-=2;

    }else if (cs[i]=='C'&&cs[f]=='X') {//4

    st.append(cs[f]);

    st.append(cs[i]);

    i-=2;

    f-=2;

    }else if (cs[i]=='D'&&cs[f]=='C') {//5

    st.append(cs[f]);

    st.append(cs[i]);

    i-=2;

    f-=2;

    }else if (cs[i]=='M'&&cs[f]=='C') {//6

    st.append(cs[f]);

    st.append(cs[i]);

    i-=2;

    f-=2;

    }

    else if (cs[i]=='I') {

    sp.append(cs[i]);

    i--;

    f--;

    }else if (cs[i]=='V') {

    sp.append(cs[i]);

    i--;

    f--;

    }else if (cs[i]=='X') {

    sp.append(cs[i]);

    i--;

    f--;

    }else if (cs[i]=='L') {

    sp.append(cs[i]);

    i--;

    f--;

    }else if (cs[i]=='C') {

    sp.append(cs[i]);

    i--;

    f--;

    }else if (cs[i]=='D') {

    sp.append(cs[i]);

    i--;

    f--;

    }else if (cs[i]=='M') {

    sp.append(cs[i]);

    i--;

    f--;

    }

    } catch (Exception e) {//这里还越界,通过抛出异常处理

    // TODO: handle exception

    sp.append(cs[i]);

    i--;

    }

    }

    char[] st1=st.toString().toCharArray();

    char[] sp1=sp.toString().toCharArray();

    int lenst=st1.length;

    int i1=lenst-1;

    int f1=lenst-2;

    //对特殊数组取值

    while (i1>=0||f1>=0) {

    if (st1[i1]=='V'&&st1[f1]=='I') {//1

    res+=4;

    i1-=2;

    f1-=2;

    }else if (st1[i1]=='X'&&st1[f1]=='I') {//2

    res+=9;

    i1-=2;

    f1-=2;

    }else if (st1[i1]=='L'&&st1[f1]=='X') {//3

    res+=40;

    i1-=2;

    f1-=2;

    }else if (st1[i1]=='C'&&st1[f1]=='X') {//4

    res+=90;

    i1-=2;

    f1-=2;

    }else if (st1[i1]=='D'&&st1[f1]=='C') {//5

    res+=400;

    i1-=2;

    f1-=2;

    }else if (st1[i1]=='M'&&st1[f1]=='C') {//6

    res+=900;

    i1-=2;

    f1-=2;

    }

    }

    int lensp=sp1.length;

    int i2=lensp-1;

    //对单个数组取值

    while (i2>=0) {

    if (sp1[i2]=='I') {

    res+=1;

    i2--;

    }else if (sp1[i2]=='V') {

    res+=5;

    i2--;

    }else if (sp1[i2]=='X') {

    res+=10;

    i2--;

    }else if (sp1[i2]=='L') {

    res+=50;

    i2--;

    }else if (sp1[i2]=='C') {

    res+=100;

    i2--;

    }else if (sp1[i2]=='D') {

    res+=500;

    i2--;

    }else if (sp1[i2]=='M') {

    res+=1000;

    i2--;

    }

    }

    return res;

    }

    }

  • 大神解法:利用map,挺好!

    class Solution {

    public int romanToInt(String s) {

    Map<Character, Integer> hashMap = new HashMap<>();

    // I 1

    // V 5

    // X 10

    // L 50

    // C 100

    // D 500

    // M 1000

    hashMap.put('I', 1);

    hashMap.put('V', 5);

    hashMap.put('X', 10);

    hashMap.put('L', 50);

    hashMap.put('C', 100);

    hashMap.put('D', 500);

    hashMap.put('M', 1000);

    int sum=0;

    char[] cs=s.toCharArray();

    for (int i = cs.length-1; i>=0; i--) {

    //处理六种特殊情况,即大的在右,小的在左

    if ((i-1)>=0&&hashMap.get(cs[i])>hashMap.get(cs[i-1])) {

    sum+=hashMap.get(cs[i])-hashMap.get(cs[i-1]);

    i--;

    }else {

    //处理单个的情况

    sum+=hashMap.get(cs[i]);

    }

    }

    return sum;

    }

    }

上一篇:WARN util.NativeCodeLoader: Unable to load native-hadoop library for your platform... using builtin-java classes where applicable Exception in thread "main" java.io.IOException: No FileSystem for sc F


下一篇:javascript如何判断是手机还是电脑访问本网页