剑指offer刷题积累(Java)

思路：依次遍历String中的每一个字符string.charAt(i)，用StringBuilder来存储最终结果，判断是否为空格，是则往stringbuilder添加要替换成的字符，否则直接添加。

思路：用HashSet来存储数据，遍历数组将数字添加到set里，用set.contains(i)方法判断是否有重复，有则直接返回。

思路1：递归，遍历到链表尾部，在将尾部数据添加到数组或集合里

思路2：栈

public class Solution {
    Stack stack1 = new Stack();
    Stack stack2 = new Stack();
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        if(stack1.empty()&&stack2.empty()){
            throw new RuntimeException("Queue is empty!");
        }
        if(stack2.empty()){
            while(!stack1.empty()){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

思路：最大的n位数就是10的n次方减一，如1对应9，2对应99

    public int[] printNumbers (int n) {
        // write code here
        int max =(int) Math.pow(10,n)-1;
        
        int[] res = new int[max];
        for(int i = 1;i<=max;i++){
            res[i-1] = i;
        }
        return res;
    }

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。返回删除后的链表的头节点

思路：迭代遍历

public class Solution {
    public ListNode deleteNode (ListNode head, int val) {
        //加入一个头节点
        ListNode res = new ListNode(0);
        res.next = head;
        //前序节点
        ListNode pre = res;
        //当前节点
        ListNode cur = head;
        //遍历链表
        while(cur != null){
            //找到目标节点
            if(cur.val == val){
                //断开连接
                pre.next = cur.next;
                break;
            }
            pre = cur;
            cur = cur.next;
        }
        //返回去掉头节点
        return res.next;
    }
}

思路：

• step 1：准备一个快指针，从链表头开始，在链表上先走kkk步。
• step 2：准备慢指针指向原始链表头，代表当前元素，则慢指针与快指针之间的距离一直都是kkk。
• step 3：快慢指针同步移动，当快指针到达链表尾部的时候，慢指针正好到了倒数kkk个元素的位置。

public class Solution {
    public ListNode FindKthToTail (ListNode pHead, int k) {
        int n = 0;
        ListNode fast = pHead;
        ListNode slow = pHead;
        //快指针先行k步
        for(int i = 0; i < k; i++){ 
            if(fast != null)
                fast = fast.next;
            //达不到k步说明链表过短，没有倒数k
            else
                return slow = null;
        }
        //快慢指针同步，快指针先到底，慢指针指向倒数第k个
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

思路1：使用栈解决

import java.util.Stack;
public class Solution {
public ListNode ReverseList(ListNode head) {
    Stack stack= new Stack<>();
    //把链表节点全部摘掉放到栈中
    while (head != null) {
        stack.push(head);
        head = head.next;
    }
    if (stack.isEmpty())
        return null;
    ListNode node = stack.pop();
    ListNode dummy = node;
    //栈中的结点全部出栈，然后重新连成一个新的链表
    while (!stack.isEmpty()) {
        ListNode tempNode = stack.pop();
        node.next = tempNode;
        node = node.next;
    }
    //最后一个结点就是反转前的头结点，一定要让他的next
    //等于空，否则会构成环
    node.next = null;
    return dummy;
}
}

思路1：递归

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        if(list1==null){
            return list2;
        }
        else if(list2==null){
            return list1;
        }
        if(list2.val>list1.val){
            list1.next = Merge(list1.next,list2);
            return list1;
        }
        else{
            list2.next = Merge(list1,list2.next);
            return list2;
        }
    }
}

思路2：双指针