1 NC65 斐波那契数列

 

 

public class Solution {
    public int Fibonacci(int n) {
        
        //自己首次实现
        /*
        if(n==0){
            return 0;
        }else if(n==1){
            return 1;
        }else{
            return Fibonacci(n-2) + Fibonacci(n-1);
        }
        */
        
        //参考1
        /*
        if(n<=1){
            return n;
        }else{
            return Fibonacci(n-1) + Fibonacci(n-2);
        }
        */
        
        //参考2
        /*
        int[] ans = new int[40];
        ans[0] = 0;
        ans[1] = 1;
        for(int i=2; i<=n; i++){
            ans[i] = ans[i-1] + ans[i-2];
        }
        return ans[n];
        */
        
        //参考3
        if(n <= 1){
            return n;
        }else{
            int sum = 0;
            int two = 0;
            int one = 1;
            for(int i=2; i<=n; i++){
                sum = two + one;
                two = one;
                one = sum;
            }
            return sum;
        }
           
           
    }
}

View Code

 

2 NC103 反转字符串

 

 

import java.util.*;


public class Solution {
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    public String solve (String str) {
        // write code here
        
        //解法1：SB
        //return new StringBuilder(str).reverse().toString();
         
        //解法2:双指针
        //把字符串转化为数组，使用两个指针，一个在最前面一个在最后面，两个指针指向的值相互交换，交换完之后两个指针在分别往中间走……，重复上面的过程，直到两指针相遇为止
        /*
        char[] charArr = str.toCharArray();
        int left = 0;
        int right = str.length()-1;
        while(left < right){
            char temp = charArr[left];
            charArr[left] = charArr[right];
            charArr[right] = temp;
            left++;
            right--;
        }
        return new String(charArr);
        */
        
        //解法3：单指针
        //使用一个指针，从后往前不断的把字符串的字符放到一个数组中，最后再把数组转化为字符串
        char[] chars = str.toCharArray();
        int length = str.length();
        for (int i = 0; i < length; i++)
            chars[i] = str.charAt(length - 1 - i);
        return new String(chars);
    }
}

View Code

 

3 NC38 螺旋矩阵

 

 

import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        
        //按照从左到右、从上到下、从右到左、从下到上的顺序依此遍历
        
        ArrayList<Integer> list = new ArrayList<>();

        if(matrix.length == 0) {
            return list;
        }

        int left = 0; 
        int right = matrix[0].length - 1;
        int top = 0;
        int bottom = matrix.length - 1; 


        while(true) {
            for(int i = left; i <= right; i++) {  //从左到右
               list.add(matrix[top][i]) ; 
            }

            if(++top > bottom){ //判断是否还有下一行
                break;
            } 
            for(int i = top; i <= bottom; i++){
                 list.add( matrix[i][right]);    //从上到下
            } 

            if(left > --right){ //判断是否还有前一列
                break;
            } 
            for(int i = right; i >= left; i--){
                  list.add(matrix[bottom][i]); //从右到左
            } 

            if(top > --bottom){ //判断是否还有上一行
                break;
            }
            for(int i = bottom; i >= top; i--){
                 list.add(matrix[i][left]);   //从下到上
            } 

            if(++left > right){ //判断是都还有下一列
               break;
            } 
        }
        return list;
        
    }
}

View Code

 

4 NC141 判断回文

 

 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        // write code here
        
        //自己的首次解法
        /*
        char[] charArr = str.toCharArray();
        int begin = 0;
        int end = str.length()-1;
        while(begin < end){
            if(charArr[begin] != charArr[end]){
                return false;
            }
            begin++;
            end--;
        }
        return true;
        */
        
        //参考1：双指针解法
        /*
        if(str==null || str.length()==0){
            return false;
        }
        for(int i=0, j=str.length()-1; i<j; i++, j--){
            if(str.charAt(i) != str.charAt(j)){
                return false;
            }
        }
        return true;
        */
        
        //参考2：SB解法
        //return new StringBuilder(str).reverse().toString().equals(str);
        
        //参考3
        int max_index = str.length() - 1;
        if (max_index == 0) {
            return true;
        }
        int loop = max_index / 2;
        for (int i=0; i<loop; ++i) {
            if (str.charAt(i) != str.charAt(max_index-i)) {
                return false;
            }
            if (i==(max_index-i) || (max_index-i-i)==1) {
                break;
            }
        }
        return true;
        
    }
}

View Code

 

5 NC101 缺失数字

 

 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 找缺失数字
     * @param a int整型一维数组 给定的数字串
     * @return int整型
     */
    public int solve (int[] a) {
        // write code here
        
        //自己首次实现
        /*
        for(int i=1; i<a.length; i++){
            if(a[i-1]+1 != a[i]){
                return a[i-1]+1;
            }
        }
        if(a[0] == 0){
            return a[a.length-1]+1;
        }else{
            return 0;
        }
        */
        
        //参考1：等差数列求和
        //如果不缺那个数字的话， 这个数组的所有数字可以组成一个等差数列， 我们只需要根据公式求和， 然后再减去数组中所有的数字即可
        /*
        int length = a.length;
        int sum = (0+length) * (length+1) / 2;
        for(int i=0; i<length; i++){
            sum -= a[i];
        }
        return sum;
        */
        
        //参考2：暴力求解
        //题中说了是递增排序数组， 所以我们只需要从前往后逐个遍历， 少了哪个就返回哪个
        /*
        int length = a.length;
        for(int i=0; i<length; i++){
            if(a[i] != i){
                return i;
            }
        }
        return length;
        */
        
        //参考3：二分查找法
        /*
        int start = 0;
        int end = a.length - 1;
        while (start <= end) {
            int mid = start + (end - start) / 2;
            if (a[mid] == mid) {
                start = mid + 1;
            } else {
                end = mid - 1;
            }
        }
        return start;
        */
        
        //参考4：位运算-异或
        int xor = 0;
        for (int i = 0; i < a.length; i++){
            xor ^= a[i] ^ (i + 1);   
        }
        return xor;
        
        
    }
}

View Code

 

 

 

 

 

 

 

 

6 NC107 寻找峰值

 

 

import java.util.*;


public class Solution {
    /**
     * 寻找最后的山峰
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int[] a) {
        // write code here
        
        //自己首次实现
        
        int length = a.length;
        int index = 0;
        for(int i=1; i<length-1; i++){
            if( (a[i]>a[i-1]) && (a[i]>a[i+1]) ){
                if(i > index){
                    index = i;
                }
            }
        }
        if(a[length-1] > a[length-2]){
            index = length - 1;
        }
        return index;

    }
}

View Code

 

7 NC110 旋转数组

 

 

import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        
        //自己首次实现（无通用性，仅适用实例1）
        /*
        if(m > n){
            m = m%n;
        }
        for(int i=m; i>0; i--){
            int temp = a[m-i];
            a[m-i] = a[n-i];
            a[n-i] = temp;
        }
        for(int i=m; i>0; i--){
            int temp = a[m-i+m];
            a[m-i+m] = a[n-i];
            a[n-i] = temp;
        }
        return a;
        */
        
        //参考：三次交换
        //将数组的元素向右移动m次后，尾部 m mod n 个元素会移动至数组头部，其余元素向后移动 m mod n 个位置
        m = m%n;
        reverse(a, 0, n-1); //可以先将所有元素翻转，这样尾部的 m mod n 个元素就被移至数组头部
        reverse(a, 0, m-1); //然后再翻转 [0,m mod n−1] 区间的元素
        reverse(a, m, n-1); //最后翻转[m mod n,n−1] 区间的元素即能得到最后的答案
        return a;
    }
    
    public void reverse(int[] nums, int start, int end){
        while(start < end){
            swap(nums, start++, end--);
        }
    }
    public void swap(int[] nums, int a, int b){
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
    
}

View Code

 

8 NC151 最大公约数

 

 

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 求出a、b的最大公约数。
     * @param a int 
     * @param b int 
     * @return int
     */
    public int gcd (int a, int b) {
        // write code here
        
        //自己首次实现
        /*
        if(a == b){
            return a;
        }
        int small = a>b?b:a;
        int max = 1;
        for(int i=1; i<=small; i++){
            if( (a%i==0) && (b%i==0) ){
                if(max < i){
                    max = i;
                }
            }
        }
        return max;
        */
        
        //参考1：辗转相除法，又称欧几里得算法
        /* 
        例子
            假如需要求 434 和 652 的最大公约数,用欧几里得算法，是这样进行的：
                434 / 652 = 0 (余 434)
                652 / 434 = 1(余218)
                434 / 218 = 216(余2)
                216 / 2 = 108 (余0)
            以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，
            所以就得出了 434 和 652 的最大公约数 2。
        */
        /*
        if(a%b == 0){
            return b;
        }else{
            return gcd(b, a%b); //递归
        }
        */
        
        //参考2：暴力
        //找出两个数a,b的最大公约数，暴力遍历，首先找出a与b中的最小值，
        //然后从最小值开始往下遍历，找到的第一个公约数即为最大公约数。1一定是a与b的公约数。
        int min = Math.min(a, b);
        while(min > 0){
            if(a%min==0 && b%min==0){
                return min;
            }
            --min;
        }
        return 1;
        
    }
}

View Code