LeetCode刷题笔记——《剑指Offer》面试题（2）

算法
, , , ,

代码的完整性

数值的整数次方

思路：根据以下性质递归求解。

  1. n为正奇数时，$x^n = x^\frac{n}{2} \times x^\frac{n}{2} \times x$。
  2. n为正偶数时，$x^n = x^\frac{n}{2} \times x^\frac{n}{2}$。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public double myPow(double x, int n) {
        if (n<0) return 1/pow(x, n);
        else return pow(x,n);
    }

    public double pow(double x, int n) {
        if (n==0) return 1.;
        double y = pow(x, n/2);
        if (n%2==0) return y*y;
        else return y*y*x;
    }
}

打印从1到最大的n位数

思路：考虑到大数溢出情况，需要使用字符串代替数字类型，使用DFS全排列来解决此题。

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
class Solution {

    public ArrayList<Integer> res;
    public StringBuilder sb;

    public int[] printNumbers(int n) {
        res = new ArrayList<>();
        sb = new StringBuilder();
        dfs(0, n);
        int[] ans = new int[res.size()];
        for (int i=0; i<ans.length; i++) {
            ans[i] = res.get(i);
        }
        return ans;
    }

    public void dfs(int len, int n) {
        if (n==len) {
            while (sb.length()>0 && sb.charAt(0)=='0') {
                sb.deleteCharAt(0);
            }
            if (sb.length()!=0) res.add(Integer.parseInt(sb.toString()));
            return;
        }
        for (int i=0; i<10; i++) {
            sb.append(i+"");
            dfs(len+1, n);
            if (sb.length()!=0) sb.deleteCharAt(sb.length()-1);
        }
    }
}

在O(1)时间内删除链表的节点

思路：

  1. 如果该节点不是尾节点，将该节点的下一位节点值赋给它，它的next指针指向next.next；
  2. 如果链表中只有这一个节点，返回null；
  3. 如果该节点是尾节点，将它置为null。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        ListNode dummy = new ListNode(-1);
        dummy.next = head;
        if (head.val==val) {
            return head.next;
        }
        while (head.next!=null && head.next.val!=val) {
            head = head.next;
        }
        if (head.next==null) {
            head = null;
            return dummy.next;
        }
        head.next = head.next.next;
        return dummy.next;
    }
}

删除链表中重复的节点

思路：设置双指针，一个指针指向当前节点，另一个指针搜索与当前节点不同的第一个节点。为了防止头节点被删除而导致空指针，先设置一个辅助头节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode deleteDuplication(ListNode pHead) {
        ListNode head = new ListNode(-1);
        head.next = pHead;
        ListNode prev = head;
        ListNode next = head.next;
        while (next != null) {
            if (next.next != null && next.val == next.next.val) {
                while (next.next != null && next.next.val == next.val) next = next.next;
                prev.next = next.next;
                next = next.next;
            } else {
                prev = prev.next;
                next = next.next;
            }
        }
        return head.next;
    }
}

正则表达式匹配

思路：给定字符串s和模式字符串p，设dp[i][j]表示s[i]和p[j]的匹配情况（这里i和j分别是字符串和模式字符串的下标）。

  1. 初始状态：如果s为空，p为空，匹配成功，返回true；如果s非空，p为空，则匹配失败，返回false。其他情况需要进一步讨论。
  2. 如果p[i]不为*，那么它要么和s对应的字符相同，要么是.，此时它的匹配情况等于dp[i-1][j-1]，否则匹配失败。
  3. 如果p[i]为*，那么p[i-1]的字符可以出现0次，此时匹配情况等于dp[i][j-2]；或者p[i-1]的字符至少出现1次，此时比较dp[i-1][j]即可。
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
class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length(), n = p.length();
        //dp[0][0]保存字符串长度为0的情形
        boolean[][] dp = new boolean[m+1][n+1];
        //dp[i][j]表示s[i-1]和p[j-1]是否匹配
        for (int i=0; i<=m; i++) {
            for (int j=0; j<=n; j++) {
                if (j==0) {//判断初始情况
                    dp[i][j] = (i==0);
                } else {
                    if (p.charAt(j-1)!='*') {
                        //当p不是*时，比较两个字符是否匹配即可
                        if (i>0 && (s.charAt(i-1)==p.charAt(j-1) || p.charAt(j-1)=='.')) {
                            dp[i][j] = dp[i-1][j-1];
                        }
                    } else {
                        //当p是*时
                        //可以匹配s中的0个字符，此时dp[i][j] = dp[i][j-2]
                        if (j>1) dp[i][j] |= dp[i][j-2];
                        //可以匹配s中的多个字符，此时dp[i][j] = dp[i-1][j]
                        if (i>0 && j>1 && (s.charAt(i-1)==p.charAt(j-2) || p.charAt(j-2)=='.')) {
                            dp[i][j] |= dp[i-1][j];
                        }
                    }
                }
            }
        }
        return dp[m][n];
    }
}

表示数值的字符串

思路：需要判断.、e/E和+/-。

  1. 小数点最多出现一次，且不能出现在e或E之后。
  2. e或E最多出现一次，且其前后要有一个合法的数。
  3. 正负号只能出现在整个数字的第一位或者e/E后的第一位。
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
class Solution {
    public boolean isNumber(String s) {
        char[] ch = s.trim().toCharArray();
        if (ch.length==0) return false;
        boolean isNum = false, hasE = false, hasP = false;
        for (int i=0; i<ch.length; i++) {
            //判断是否是数字
            if (ch[i]>='0' && ch[i]<='9') isNum = true;
            //判断正负号，要么出现在第一位，要么出现在e之后第一位
            else if (ch[i]=='+' || ch[i]=='-') {
                if (i!=0 && ch[i-1]!='e' && ch[i-1]!='E') return false;
            }
            //判断E或者e，前面需要有合法数字，只能出现一次，并且重置isNum，保证e之后是合法数字
            else if (ch[i]=='E' || ch[i]=='e') {
                if (!isNum || hasE) return false;
                hasE = true;
                isNum = false;
            }
            //判断小数点，不能重复出现，不能出现在e之后
            else if (ch[i]=='.') {
                if (hasP || hasE) return false;
                hasP = true;
            } else return false;//其他非法字符
        }
        return isNum;
    }
}

调整数组顺序使奇数位于偶数前面

思路：使用前后双指针判断并交换奇偶数。

如果题目要求奇偶数的相对位置不变，则需要先遍历一遍数组，找到偶数的开始位置，然后两个指针分别记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] exchange(int[] nums) {
        int i=0, j=nums.length-1;
        while (i<j) {
            while (i<j && isOdd(nums[i])) i++;
            while (i<j && !isOdd(nums[j])) j--;
            swap(nums, i, j);
        }
        return nums;
    }

    public boolean isOdd(int num) {
        return num%2==1;
    }

    public void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

代码的鲁棒性

链表中倒数第k个结点

思路：使用快慢双指针，快指针先走k步，然后两个指针一起走，当快指针走到链表尾部时，慢指针所指向的就是倒数第k个节点。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        ListNode fast = head;
        ListNode slow = head;
        while (k>0) {
            fast = fast.next;
            k--;
        }
        while (fast!=null) {
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }
}

链表中环的入口结点

思路：使用快慢双指针，快指针一次走2步，慢指针一次走1步。若链表存在环，则两指针必定相遇，此时慢指针到达环入口的距离等于从头节点到环入口的距离。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead) {
        if (pHead == null || pHead.next == null) return null;
        ListNode pFast = pHead;
        ListNode pSlow = pHead;
        do {
            pFast = pFast.next.next;
            pSlow = pSlow.next;
        } while (pFast != pSlow);
        pFast = pHead;
        while (pFast != pSlow) {
            pFast = pFast.next;
            pSlow = pSlow.next;
        }
        return pSlow;
    }
}

反转链表

思路1：递归。

1
2
3
4
5
6
7
8
9
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head==null || head.next==null) return head;
        ListNode next = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return next;
    }
}

思路2：迭代。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        while (head!=null) {
            ListNode next = head.next;
            head.next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }
}

合并两个排序的链表

思路：顺序遍历两个链表，将值较小的节点放入新的链表。当遍历完一个链表后将剩余的链表节点直接接入结果链表后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        ListNode newList = new ListNode(0);
        ListNode head = newList;
        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                head.next = list2;
                list2 = list2.next;
            } else {
                head.next = list1;
                list1 = list1.next;
            }
            head = head.next;
        }
        if (list1 == null) head.next = list2;
        if (list2 == null) head.next = list1;
        return newList.next;
    }
}

树的子结构

思路：递归判断。

  1. 判断B是否是A为根节点构成的树的子结构；
  2. 判断B是否是A的左子节点为根节点构成的树的子结构；
  3. 判断B是否是A的右子节点为根节点构成的树的子结构。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A==null || B==null) return false;
        return isSameTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean isSameTree(TreeNode A, TreeNode B) {
        if (B==null) return true;
        if (A==null) return false;
        if (A.val!=B.val) return false;
        return isSameTree(A.left, B.left) && isSameTree(A.right, B.right);
    }
}