Java教程

剑指offer(刷题DAY1)

本文主要是介绍剑指offer(刷题DAY1),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

替换空格

class Solution {
    public String replaceSpace(String s) {
        StringBuilder res = new StringBuilder();
        for(Character c : s.toCharArray())
        {
            if(c == ' ') res.append("%20");
            else res.append(c);
        }
        return res.toString();
    }
}

从尾到头打印链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        ListNode tmp = head;
        int len=0;
        while(tmp!=null){
            len++;
            tmp=tmp.next;
        }
        int[] arr = new int[len];
        ListNode cur = head;
        for(int i=len-1;i>=0;i--){
            arr[i]=cur.val;
            cur=cur.next;
        }
        return arr;

    }
}

用两个LinkedList实现队列的功能

class CQueue {
    LinkedList<Integer> A,B;
    public CQueue() {
        A = new LinkedList<Integer>();
        B = new LinkedList<Integer>();

    }
    
    public void appendTail(int value) {
        A.addLast(value);

    }
    
    public int deleteHead() {
        if(!B.isEmpty()) return B.removeLast();
        if(A.isEmpty()) return -1;
        while(!A.isEmpty())
            B.addLast(A.removeLast());
        return B.removeLast();
        

    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

反转链表(两种方法:迭代,递归)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode cur = head,pre=null;
        while(cur!=null){
            ListNode temp = cur.next;
            cur.next = pre;
            pre=cur;
            cur = temp;
        }
        return pre;


    }
}
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
//递归

class Solution {
    public ListNode reverseList(ListNode head) {
      return rescur(head,null);
    }
    private ListNode rescur(ListNode cur,ListNode pre){
        if(cur==null) return pre;

        ListNode res = rescur(cur.next,cur);

        cur.next = pre;

        return res;
    }
}

定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min、push 及 pop 的时间复杂度都是 O(1)。

class MinStack {
    LinkedList<Integer> A, B;
    public MinStack() {
        A = new LinkedList();
        B = new LinkedList();
    }
    public void push(int x) {
        A.add(x);
        if(B.isEmpty() || B.getLast() >= x)
            B.add(x);
    }
    public void pop() {
        if(A.removeLast().equals(B.getLast()))
            B.removeLast();
    }
    public int top() {
        return A.getLast();
    }
    public int min() {
        return B.getLast();
    }
}

 

这篇关于剑指offer(刷题DAY1)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!