剑指Offer-个人题解

1
2
3
4

输入：4
返回值：3
说明：根据斐波那契数列的定义可知
fib(1)=1,fib(2)=1,fib(3)=fib(3-1)+fib(3-2)=2,fib(4)=fib(4-1)+fib(4-2)=3，所以答案为3。  

1
2

输入：1
返回值：1

1
2

输入：2
返回值：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

public class Solution {
    public int Fibonacci(int n) {
        if(n==1||n==2)return 1;
        int[] a=new int[n+1];
        a[1]=a[2]=1;
        for(int i=3;i<=n;i++){
            a[i]=a[i-1]+a[i-2];
        }
        return a[n];
    }
}

1
2
3

输入：[2,3,1,0,2,5,3]
返回值：2
说明：2或3都是对的    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型一维数组 
     * @return int整型
     */
    public int duplicate (int[] numbers) {
        // write code here
        int tep = 0;
        for(int i = 0;i < numbers.length;i++){
            tep = numbers[i];
            int count = 0;
            for(int j = 0; j< numbers.length;j++){
                if(tep==numbers[j]){
                    count++;
                    if(count>1){
                        return tep;
                    }
                }
            }
        }
        return -1;
    }
}

1
2

输入："We Are Happy"
返回值："We%20Are%20Happy"

1
2

输入：" "
返回值："%20"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param s string字符串 
     * @return string字符串
     */
    public String replaceSpace (String s) {
        // write code here
        return s.replace(" ", "%20");
    }
}

1
2

输入：{1,2,3}
返回值：[3,2,1]

1
2

输入：{67,0,24,58}
返回值：[58,24,0,67]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

/**
*    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> list = new ArrayList<>();
        ListNode tmp = listNode;
        while(tmp!=null){
            list.add(0,tmp.val);
            tmp = tmp.next;
        }
        return list;
    }
}

1
2
3
4
5
6
7

输入：["PSH1","PSH2","POP","POP"]
返回值：1,2
说明：
"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2     

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

import java.util.Stack;

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    
     public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if (stack2.size() <= 0){
            while (stack1.size() != 0){
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }
}

1
2

输入：[3,4,5,1,2]
返回值：1

1
2

输入：[3,100,200,3]
返回值：3

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int[] array) {
        if (array.length == 0) {
            return 0;
        }
        int min = array[0];
        for (int e : array) {
            if (e < min) {
                min = e;
            }
        }
        return min;
    }
}

1
2
3
4

输入：10
返回值：2
说明：
十进制中10的32位二进制表示为0000 0000 0000 0000 0000 0000 0000 1010，其中有两个1。       

1
2
3
4

输入：-1
返回值：32
说明：
负数使用补码表示 ，-1的32位二进制表示为1111 1111 1111 1111 1111 1111 1111 1111，其中32个1    

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

import java.util.*;
public class Solution {
    public int NumberOf1(int n) {
        Scanner in = new Scanner(System.in);
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & (1 << i)) != 0) {
                count++;
            }
        }
        return count;
    }
}

1
2

输入：1
返回值：[1,2,3,4,5,6,7,8,9]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型 最大位数
     * @return int整型一维数组
     */
    public int[] printNumbers (int n) {
        // write code here
        int length = (int)Math.pow(10, n);
        int []nums = new int[length-1];
        for(int i=1;i<length;i++){
            nums[i-1]=i;
        }

        return nums;
    }
}

1
2
3
4

输入：{2,5,1,9},5
返回值：{2,1,9}
说明：
给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 2 -> 1 -> 9   

1
2
3
4

输入：{2,5,1,9},1
返回值：{2,5,9}
说明：
给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 2 -> 5 -> 9   

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    public ListNode deleteNode (ListNode head, int val) {
        // write code here
        if(head.val == val) {
            return head.next;
        }
        ListNode newHead = head;
        while(newHead.next != null) {
            if(newHead.next.val == val) {
                newHead.next = newHead.next.next;
            }
            newHead = newHead.next;
        }
        return head;
    }
}

1
2
3

输入：{1,2,3,4,5},2
返回值：{4,5}
说明：返回倒数第2个节点4，系统会打印后面所有的节点来比较。 

1
2

输入：{2},8
返回值：{}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pHead ListNode类
     * @param k int整型
     * @return ListNode类
     */
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        // 快慢指针思想
        ListNode fast = pHead;
        ListNode slow = pHead;
        int step=0;
        if (pHead == null) {
            return null;
        }

        // 快指针先走k步
        while (fast != null && step != k) {
            fast = fast.next;
            step++;
        }

        if (step < k) {
            return null;
        }

        // 慢指针与快指针同步
        while (fast != null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

1
2

输入：{1,2,3}
返回值：{3,2,1}

1
2
3

输入：{}
返回值：{}
说明：空链表则输出空

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode pre = null;
        ListNode nextOne = null;
        while (head != null) {
            nextOne = head.next;
            head.next = pre;
            pre = head;
            head = nextOne;
        }
        return pre;
    }
}

1
2

输入：{1,3,5},{2,4,6}
返回值：{1,2,3,4,5,6}

1
2

输入：{},{}
返回值：{}

1
2

输入：{-1,2,4},{1,3,4}
返回值：{-1,1,2,3,4,4}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

    ListNode(int val) {
        this.val = val;
    }
}*/
public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        if (list1 == null && list2 == null) {
            return null;
        }
        ListNode head = new ListNode(-1);
        ListNode pre = head;
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                pre.next = list1;
                list1 = list1.next;
            } else if (list1.val > list2.val) {
                pre.next = list2;
                list2 = list2.next;
            } else {
                pre.next = list1;
                list1 = list1.next;
                pre=pre.next;
                pre.next = list2;
                list2 = list2.next;
            }
            pre=pre.next;
        }
        pre.next = list1 == null ? list2 : list1;
        return head.next;
    }
}

1
2
3

输入：{8,6,10,5,7,9,11}
返回值：{8,10,6,11,9,7,5}
说明：如题面所示    

1
2

输入：{}
返回值：{}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return TreeNode类
     */
    public TreeNode Mirror (TreeNode pRoot) {
        // write code here
        if (pRoot == null) {
            return null;
        }

        TreeNode tmp = pRoot.left;
        pRoot.left = pRoot.right ;
        pRoot.right = tmp;
        Mirror(pRoot.left);
        Mirror(pRoot.right);
        return pRoot;
    }
}

1
2

输入：{1,2,2,3,4,4,3}
返回值：true

1
2

输入：{8,6,9,5,7,7,5}
返回值：false

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/

import java.util.*;
public class Solution {

    boolean isSymmetrical(TreeNode pRoot) {
        if (pRoot == null) {
            return true;
        }

        Queue<TreeNode> left = new LinkedList();
        Queue<TreeNode> right = new LinkedList();

        left.offer(pRoot.left);
        right.offer(pRoot.right);

        while (!left.isEmpty() && !right.isEmpty()) {
            TreeNode tn_left = left.poll();
            TreeNode tn_right = right.poll();

            if (tn_left == null && tn_right == null) {
                continue;
            }
            if (tn_left == null || tn_right == null || tn_left.val != tn_right.val) {
                return false;
            }

            left.offer(tn_left.left);
            left.offer(tn_left.right);

            right.offer(tn_right.right);
            right.offer(tn_right.left);

        }

        return  true ;
    }
}

1
2

输入：[[1,2,3,4],[5,6,7,8],[9,10,11,12],[13,14,15,16]]
返回值：[1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10]

1
2

输入：[[1,2,3,1],[4,5,6,1],[4,5,6,1]]
返回值：[1,2,3,1,1,1,6,5,4,4,5,6]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

import java.util.*;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> nums = new ArrayList();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return nums;
        }

        int up = 0, down = matrix.length - 1, left = 0, right = matrix[0].length - 1;

        while (true) {
            // 往右走
            for (int index = left; index <= right; index++) {
                nums.add(matrix[up][index]);
            }
            up++;
            if (up > down) {
                break;
            }

            // 往下走
            for (int index = up; index <= down; index++) {
                nums.add(matrix[index][right]);
            }
            right--;
            if (left > right) {
                break;
            }

            // 往左走
            for (int index = right; index >= left; index--) {
                nums.add(matrix[down][index]);
            }
            down--;
            if (up > down) {
                break;
            }

            // 往上走
            for (int index = down; index >= up; index--) {
                nums.add(matrix[index][left]);
            }
            left++;
            if (left > right) {
                break;
            }
        }
        return nums;
    }
}

1
2

输入：["PSH-1","PSH2","MIN","TOP","POP","PSH1","TOP","MIN"]
返回值：-1,2,1,-1

1
2

输入：" "
返回值："%20"

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.Stack;

public class Solution {

    Stack<Integer>num = new Stack<>();
    Stack<Integer>min = new Stack<>();

    public void push(int node) {
        num.push(node);
        if (min.isEmpty() || min.peek() > node) {
            min.push(node);
        } else {
            min.push(min.peek());
        }

    }

    public void pop() {
        num.pop();
        min.pop();
    }

    public int top() {
        int top_val = num.peek();
        return top_val;
    }

    public int min() {
        return min.peek();
    }
}

1
2

输入：{8,6,10,#,#,2,1}
返回值：[8,6,10,2,1]

1
2

输入：{5,4,#,3,#,2,#,1}
返回值：[5,4,3,2,1]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

import java.util.*;
/**
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/
public class Solution {
    ArrayList<Integer> num = new ArrayList();
    Queue<TreeNode>node = new LinkedList();
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        node.add(root);
        while (!node.isEmpty()) {
            TreeNode tmp = node.poll();
            if (tmp != null) {
                num.add(tmp.val);
                node.add(tmp.left);
                node.add(tmp.right);
            }

        }
        return num;
    }
}

1
2
3

输入：
[1,2,3,2,2,2,5,4,2]
返回值：2

1
2

输入：[3,3,3,3,2,2,2]
返回值：3

1
2

输入：[1]
返回值：1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int []count = new int[10000];
        if(array.length==1){
            return array[0];
        }
        for (int i = 0; i < array.length; i++) {
            count[array[i]]++;
        }
        int mid = array.length >> 1;
        int target = 0;
        for (int i = 0; i < count.length; i++) {
            if (count[i] > mid) {
                target = i;
                break;
            }
        }
        return target;
    }
}

1
2
3

输入：[1,-2,3,10,-4,7,2,-5]
返回值：18
说明：经分析可知，输入数组的子数组[3,10,-4,7,2]可以求得最大和为18

1
2

输入：[2]
返回值：2

1
2

输入：[-10]
返回值：-10

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        // 未优化
        // int []dp = new int[array.length];
        // int max = array[0];
        // dp[0] = array[0];
        // for (int i = 1; i < array.length; i++) {
        //     dp[i] = Math.max(array[i], dp[i - 1] + array[i]);
        //     max = Math.max(max, dp[i]);
        // }
        // return max;


        // 优化空间复杂度
        int sum=array[0];
        int max=array[0];
        for(int i=1;i<array.length;i++){
            sum=Math.max(sum+array[i],array[i]);
            max=Math.max(max,sum);
        }
        return max;
    }
}