劍指offer算法題刷題日常2020年3月21日10:29:27

LeetCode刷題記錄

• 面試題03. 數組中重複的數字
• • 思路
  • 代碼實作
• 面試題04. 二維數組中的查找
• • 思路
  • 代碼實作
• 面試題05. 替換空格
• • 思路
  • 方法代碼實作
• 面試題06. 從尾到頭列印連結清單
• • 思路
  • 代碼實作

面試題03. 數組中重複的數字

在一個長度為 n 的數組 nums 裡的所有數字都在 0～n-1的範圍内。數組中某些數字是重複的，但不知道有幾個數字重複了，也不知道每個數字重複了幾次。請找出數組中任意一個重複的數字。

思路

因為題目要求找出任意一個重複的數字，是以以數組第一個元素取出，周遊比較數組剩下的元素，一旦找到結束周遊。

代碼實作

public class findRepeatNumber {
    public static void main(String[] args) {
        findRepeatNumber question03 = new findRepeatNumber();
        int[] nums ={3, 1, 2, 3};
        question03.findRepeatNumber(nums);
    }


    public int findRepeatNumber(int[] nums) {
        int repeat=-1;
        for (int i=0;i<nums.length;i++){
            for (int j = 0; j <nums.length; j++) {
                if (i!=j&&nums[i] == nums[j]) {
                    repeat=nums[i];
                    break;
                }
            }
            if (repeat!=-1) {
                break;
            }
        }
        return repeat;
    }
}
           

面試題04. 二維數組中的查找

在一個 n * m 的二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

思路

1. 定義temp次元為11，對于一個nm的matrix矩陣，先從矩陣最小值matrix[i][j]開始判斷，
2. 如果target等于matrix[i][j]，break，return true
3. 如果target大于matrix[i][j]，i++，j++，
4. 如果target小于matrix[i][j]，周遊最後一行和列
5. 如果存在，return true 如果不存在，return false

代碼實作

public boolean findNumberIn2DArray(int[][] matrix, int target) {
    for (int i = 0; i <matrix.length ; i++) {
        for (int j = 0; j <matrix[i].length ; j++) {
            if (target==matrix[i][j]){
                return true;
            } else if (target>matrix[i][j]) {
                System.out.println("需要下一步擴容");
            }else{
                for (int k = 0; k <j; k++) {
                    if (target==matrix[i][k]){
                        return true;
                    }
                }
                for (int k = 0; k <i; k++) {
                    if (target==matrix[k][j]){
                        return true;
                    }
                }
            }
        }
    }
    return false;
}
           

面試題05. 替換空格

請實作一個函數，把字元串 s 中的每個空格替換成"%20"。

示例 ：

輸入：s = “We are happy.”

輸出：“We%20are%20happy.”

思路

1. 由于每次替換從 1 個字元變成 3 個字元，使用字元數組可友善地進行替換。建立字元數組地長度為 s 的長度的 3

   倍，這樣可保證字元數組可以容納所有替換後的字元。

2. 獲得 s 的長度 length
3. 建立字元數組 array，其長度為 length * 3
4. 初始化 size 為 0，size 表示替換後的字元串的長度
5. 從左到右周遊字元串 s獲得 s 的目前字元 c
6. 如果字元 c 是空格，則令 array[size] = ‘%’，array[size + 1] = ‘2’，array[size +2] = ‘0’，并将 size 的值加 3
7. 如果字元 c 不是空格，則令 array[size] = c，并将 size 的值加 1 周遊結束之後，size 的值等于替換後的字元串的長度，從 array 的前 size 個字元建立新字元串，并傳回新字元串

方法代碼實作

public String replaceSpace(String s) {
        int length = s.length();
        char[] array = new char[length * 3];
        int size = 0;
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            if (c == ' ') {
                array[size++] = '%';
                array[size++] = '2';
                array[size++] = '0';
            } else {
                array[size++] = c;
            }
        }
        String newStr = new String(array, 0, size);
        return newStr;
    }
           

面試題06. 從尾到頭列印連結清單

輸入一個連結清單的頭節點，從尾到頭反過來傳回每個節點的值（用數組傳回）。 示例 ：

輸入：head = [1,3,2] 輸出：[2,3,1]

思路

棧的特點是後進先出，即最後壓入棧的元素最先彈出。考慮到棧的這一特點，使用棧将連結清單元素順序倒置。從連結清單的頭節點開始，依次将每個節點壓入棧内，然後依次彈出棧内的元素并存儲到數組中。

建立一個棧，用于存儲連結清單的節點

建立一個指針，初始時指向連結清單的頭節點

當指針指向的元素非空時，重複下列操作：

将指針指向的節點壓入棧内

将指針移到目前節點的下一個節點

獲得棧的大小 size，建立一個數組 print，其大小為 size

建立下标并初始化 index = 0

重複 size 次下列操作：

從棧内彈出一個節點，将該節點的值存到 print[index]

将 index 的值加 1

傳回 print

代碼實作

public int[] reversePrint(ListNode head) {
        Stack<ListNode> stack = new Stack<ListNode>();
        ListNode temp = head;
        while (temp != null) {
            stack.push(temp);
            temp = temp.next;
        }
        int size = stack.size();
        int[] print = new int[size];
        for (int i = 0; i < size; i++) {
            print[i] = stack.pop().val;
        }
        return print;
    }