牛客-算法(题解)

[toc]

0. 斐波那契数列

public class Solution {
    public int Fibonacci(int n) {
        
        if(n==0) return 0; 
        
        if(n<=2) return 1;     
        
        return Fibonacci(n-1)+Fibonacci(n-2);
      
    }
}

1. 反转链表

/*
public class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

import java.util.Stack;

public class Solution {
    public ListNode ReverseList(ListNode head) {
        
        if(head ==null || head.next ==null)return head;
        
        
        Stack<ListNode> s = new Stack<>();
     
      
        ListNode cur = head;
        
        
        // 遍历原来的单链表，入栈【从左边进去】
        while(cur.next !=null){
            
          s.push(cur);
            
          cur = cur.next;
        }
        s.push(cur);
        
        
        
        // 建立反转后的单链表
        ListNode newHead = new ListNode(0);
        newHead.next = null;
        
        
        int maxIndex = s.size();
        
        for(int i=0;i<maxIndex;i++){
            
            ListNode tmp = s.firstElement();
           
            tmp.next = newHead.next ;      
            
            newHead.next = tmp;
            
            s.remove(tmp);
        
        }
        
        
      return  newHead.next;

    }
}

2. 找出最小的 K 个数

import java.util.ArrayList;
import java.util.Comparator;

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        
        // arr  用于存放input数组
        // arr2 用于存放最终结果
            ArrayList<Integer> arr = new ArrayList<>();
            ArrayList<Integer> arr2 = new ArrayList<>();
        
        // 如果数组为空，或 指定长度k 大于数组的实际长度时，返回空数组[]
            if(input.length == 0 || input == null || input.length<k) 
            {
                return arr2;
            }
        
        
        // input将数组中的元素放入arr中【目的是：便于排序】
            for( int i = 0; i < input.length; i++ ){
                 arr.add(input[i]);
            }

        // 使用ArrayList的sort方法，并传入Java Comparator接口的naturalOrder()方法，指定元素以自然顺序（升序）排序
            arr.sort(Comparator.naturalOrder());

        // 获取指定个数的值，并存入arr2中
            for(int j=0;j<k;j++){
                arr2.add(arr.get(j));
            }

            return arr2;
    }
}

3. 两数之和

import java.util.*;

public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        
        int[] result = new int[2];
        
        Map<Integer, Integer> map = new HashMap();
        
        for(int i = 0; i < numbers.length; i++) {
            if(map.get(target - numbers[i]) != null) {
                result[0] = map.get(target - numbers[i]) + 1;
                result[1] = i + 1;
                return result;
            }
            map.put(numbers[i], i);
            
        }
        return result;
      
    }
}

4. 用2个栈来实现队列

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
    
     // 思路：
        //    入队：进:s1,
        //    出队：出:先将s1中除栈底元素外的所有元素依次进s2，s1栈底元素再出来,s2中的元素重新进入s1
    
    public void push(int node) {       
        
        stack1.push(node);     
                
    }
    
    public int pop() {
        
        if(stack1.size()>0){
            while(stack1.size()>1){
                 stack2.push(stack1.pop());      
            }
            int tmp = stack1.pop();
            
            while(stack2.size()>0){
                stack1.push(stack2.pop()); 
                
            }
            return tmp;
        }      
        return 0;
    }
}

5. 从尾到头打印链表

/**
*    public class ListNode {
*        int val;
*        ListNode next = null;
*
*        ListNode(int val) {
*            this.val = val;
*        }
*    }
*
*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {     
     
        
        ArrayList<Integer> arr = new ArrayList<>();        
       
        if(listNode == null) {          
           return arr;
        }
              
       
// 遍历链表，将元素的数据域 添加到 arr        
        ListNode p = listNode;
        
        while(p.next != null){
            arr.add(p.val);    
            p = p.next;
        }
        arr.add(p.val);

// 反转arr        
        int i = 0,j=arr.size()-1;
        
        while(i<=j){
            int t=arr.get(i);
            arr.set(i,arr.get(j));
            arr.set(j,t);
            i++;
            j--;
        }
        
        
        return arr;
        
        
    }
}

6. 二维数组的查找

public class Solution {
    public boolean Find(int target, int [][] array) {
        
        if(array==null)return false;
              
        for(int i=0;i<array.length;i++){
            for(int j=0;j<array[0].length;j++){
                if(target == array[i][j]) return true;
            }
        }
        return false;
      
    }
    
}

7. 旋转数组的最小数字