剑指 Offer 原版

题目

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

给定单向链表的头指针和一个节点指针，定义一个函数在 O(1) 时间内删除该节点。

解答

解答1[Java]

LeetCode 版本

解答

解答1[Java]

public class Problem18Solution1 {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return head;
        }

        if (head.val == val) {
            return head.next;
        }

        ListNode pre = head;
        ListNode current = head.next;
        while (current != null) {
            if (current.val == val) {
                pre.next = current.next;
                return head;
            } else {
                current = current.next;
                pre = pre.next;
            }
        }

        return head;
    }
}

class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
    }
}

对应 LeetCode 题目

剑指 Offer 18. 删除链表的节点 - 力扣（LeetCode）

题目

参考资料

剑指Offer 题解索引

发表于 2021-05-14 更新于 2022-09-13

Index	Problem ID	Title and Link
1	2	剑指Offer 2. 实现单例模式
2	3	剑指Offer 3. 数组中重复的数字
3	4	剑指Offer 4. 二维数组中的查找
4	5	剑指Offer 5. 替换空格
5	6	剑指Offer 6. 从尾到头打印链表
6	7	剑指Offer 7. 重建二叉树
7	8	剑指Offer 8. 二叉树的下一个节点
8	9	剑指Offer 9. 用两个栈实现队列
9	10	剑指Offer 10. 斐波那契数列
10	11	剑指Offer 11. 旋转数组的最小数字
11	13	剑指Offer 13. 机器人的运动范围
12	39	剑指Offer 39. 二叉树的深度
13	67	剑指Offer 67. 把字符串转换成整数

题目

输入数字 n，按照顺序打印出从 1 到最大的 n 位十进制数。

解答

解法1[Java]

public class Problem17Solution1 {
    public void print1ToMaxOfNDigits(int n) {
        if (n <= 0) {
            return;
        }

        char[] number = new char[n];
        Arrays.fill(number, '0');

        while (!increment(number)) {
            printNumber(number);
        }
    }

    /**
     * 进行加 1 操作，
     *
     * @param number 对 number 加 1
     * @return 达到最大值后返回 true,否则返回 false
     */
    private boolean increment(char[] number) {
        int currentDigitValue;
        // 表示进位
        int carry = 0;
        // number.length - 1 是数字最后一位的索引，即从最后一位开始处理
        for (int index = number.length - 1; index >= 0; index--) {
            // 通过字符串计算获得当前位的值
            currentDigitValue = (number[index] - '0') + carry;
            if (index == number.length - 1) {
                // 当且仅当是个位时，值加 1
                currentDigitValue++;
            }

            if (currentDigitValue >= 10) {
                // 满 10 进位
                if (index == 0) {
                    // index 为 0 表示已经到了最高位
                    // 最高位满 10 了，说明已经达到最大值了
                    return true;
                } else {
                    currentDigitValue -= 10;
                    carry = 1;
                    number[index] = (char) ('0' + currentDigitValue);
                }
            } else {
                // 不满 10，更新当前位上的数字
                number[index] = (char) ('0' + currentDigitValue);
                break;
            }
        }

        return false;
    }

    /**
     * 从第一个非零的数字开始，后边的所有数字都打印（包括零）
     */
    private void printNumber(char[] number) {
        boolean isLeadingZero = true;
        for (char c : number) {
            if (isLeadingZero && (c - '0') != 0) {
                isLeadingZero = false;
            }

            if (!isLeadingZero) {
                System.out.print(c);
            }
        }

        System.out.println();
    }
}

思路

使用字符串表示数字，同时模拟加法运算，处理进位等操作。

解法2[Java]

public class Problem17Solution2 {
    public void print1ToMaxOfNDigits(int n) {
        if (n <= 0) {
            return;
        }

        char[] number = new char[n];
        Arrays.fill(number, '0');

        for (int i = 0; i < 10; ++i) {
            number[0] = (char) (i + '0');
            print1ToMaxOfNDigitsRecursively(number, n, 0);
        }
    }

    private void print1ToMaxOfNDigitsRecursively(char[] number, int length, int index) {
        if (index == length - 1) {
            // 每次递归到个位的时候打印数字
            printNumber(number);
        } else {
            ++index;
            for (int i = 0; i < 10; ++i) {
                number[index] = (char) (i + '0');
                print1ToMaxOfNDigitsRecursively(number, length, index);
            }
        }
    }

    /**
     * 从第一个非零的数字开始打印
     */
    private void printNumber(char[] number) {
        boolean isLeadingZero = true;
        for (char c : number) {
            if (isLeadingZero && (c - '0') != 0) {
                isLeadingZero = false;
            }

            if (!isLeadingZero) {
                System.out.print(c);
            }
        }

        System.out.println();
    }
}

思路

全排列的方式，通过递归实现。

测试用例设计

正常值：1、2、3…

边界值：0、-1

LeetCode 122. Best Time to Buy and Sell Stock II[Easy].md

发表于 2021-05-12 更新于 2024-08-05

题目

You are given an array prices where prices[i] is the price of a given stock on the ith day.

Find the maximum profit you can achieve. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

Example 1:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.

Example 2:

Input: prices = [1,2,3,4,5]
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.
Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.

Example 3:

1
2
3

Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e., max profit = 0.

Constraints:

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

题解

解答1[Java]

public class Problem122Solution1 {
    public int maxProfit(int[] prices) {
        int totalProfit = 0;

        for (int i = 1; i < prices.length; i++) {
            totalProfit += Math.max(0, prices[i] - prices[i - 1]);
        }

        return totalProfit;
    }
}

思路

假设股价是连续上涨的，比如 [1, 2, 3, 4, 5]，那么我们第一天买，然后第 5 天卖，其实等价于，第 1 天买，第 2 天卖，第 2 天再买，第 3 天再卖。只要后一天比前一天价格高，我们就做操作。反之，如果后一天比前一天估计低，我们就不操作。

这种思路其实就是贪心算法的思路。

参考资料

题目

将类似于”二十五万五百亿三千零八万一千零三十五”的中文数字转换成对应的阿拉伯数字

分析

一些基本假设：

中文数字中，字符可以分为数字和单位（或者叫数量级），比如一、二、三这种是数字，十、百、千、万这种是单位。
必须以数字开头，单位不能作为开头，但是有个例外情况，十 虽然是个单位，但是 十 可以作为开头，比如十六万。
零 的时候可以略过

corner case:

中文表示习惯中，二放在开头的时候，会用 两
十 既是单位又是数字。

解法1

解法2

思路

按照单位，把字符串从左到右切分。

参考资料

LeetCode 300. Longest Increasing Subsequence[Medium]

发表于 2020-05-21 更新于 2024-08-05

题目链接：https://leetcode.com/problems/longest-increasing-subsequence/

题解链接：https://leetcode.com/articles/longest-increasing-subsequence/

题目

Given an unsorted array of integers, find the length of longest increasing subsequence.

Example:

1
2
3

Input: [10,9,2,5,3,7,101,18]
Output: 4 
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Note:

There may be more than one LIS combination, it is only necessary for you to return the length.
Your algorithm should run in O(n^2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

解法1：蛮力法

思路

递归的方式，从第一个数字开始遍历，遍历每一个数字的时候，都存在两种情况，当前数字比最大递增字串中的最后一个数字大或者比最后一个数字小。如果当前数字比最长递增子串的最后一个数字小，那么当前数字肯定不能加入到最长递增子串中。但是如果当前数字比最长的最后一个数字大，那么可以把当前数字加入到最长递增字串中，也可以不加入。因为存在这么一种情况，当前位置的数字特别大，如果把当前位置的数字加入到最长递增字串中，后边就再也无法增加数字了。但是如果不把当前数字加入到最长递增子串中，那么后边还能继续添加其他的数字。

判断当前数字和当前最长递增子串的最后一个数字的关系，如果比前一个数字更大，那么下一步就算一下包含当前数字和不包含当前数字的情况。如果比前一个数字小，那么下一步就计算一下不包含当前数字的情况。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        return lengthOfLIS(nums, Integer.MIN_VALUE, 0);
    }

    public int lengthOfLIS(int[] nums, int prev, int curpos) {
        if (curpos == nums.length) {
            return 0;
        }

        int includeCurrentElement = 0;
        if (nums[curpos] > prev) {
            includeCurrentElement = 1 + lengthOfLIS(nums, nums[curpos], curpos + 1);
        }

        int notIncludeCurrentElement = lengthOfLIS(nums, prev, curpos + 1);
        return Math.max(includeCurrentElement, notIncludeCurrentElement);
    }
}

复杂度分析

时间复杂度：$O(2^n)$

空间复杂度：$O(n^2)$

解法2：递归方法优化

感觉这个方法不太容易理解，现在也没有很好的理解缓存所代表的意义。

但是如果没有彻底理解的话，就简单的把缓存当作是某些参数的结算结果，或许可以达到初步理解。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        int[][] cache = new int[nums.length + 1][nums.length];
        for (int[] l : cache) {
            Arrays.fill(l, -1);
        }
        return lengthOfLIS(nums, -1, 0, cache);
    }

    /**
     *
     * @param nums
     * @param prevIndex
     * @param curIndex 表示当前的元素
     * @param cache
     * @return
     */
    public int lengthOfLIS(int[] nums, int prevIndex, int curIndex, int[][] cache) {
        if (curIndex == nums.length) {
            // curIndex 已经越界了，返回
            return 0;
        }

        if (cache[prevIndex + 1][curIndex] >= 0) {
            return cache[prevIndex + 1][curIndex];
        }

        int taken = 0;
        if (prevIndex < 0 || nums[curIndex] > nums[prevIndex]) {
            // prevIndex 小于 0 表示是第一个数字
            // 把当前元素算入到最长子串中，所以要加 1
            taken = 1 + lengthOfLIS(nums, curIndex, curIndex + 1, cache);
        }

        int notTaken = lengthOfLIS(nums, prevIndex, curIndex + 1, cache);
        cache[prevIndex + 1][curIndex] = Math.max(taken, notTaken);
        return cache[prevIndex + 1][curIndex];
    }
}

参考：https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/

解法3：动态规划

思路：利用一个临时数组 dp[]，dp[i] 表示截止到当前位置的最大递增子串的长度。这样，假如向原数组后边继续追加新的数字，只需要把新数字和数组中前边位置的数字作比较，只要比前边的数字大，就表示当前位置的最大递增字串的长度至少是 dp[i] + 1 ，把所有数字遍历下来就可以知道当前位置的最大递增字串的长度。

public class Problem300Solution3 {
    public int lengthOfLIS(int[] nums) {
        if (nums.length == 0) {
            return 0;
        }

        int[] dp = new int[nums.length];
        dp[0] = 1;
        int globalMaxLength = 1;
        for (int i = 1; i < dp.length; i++) {
            int currentMaxLength = 0;
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    currentMaxLength = Math.max(currentMaxLength, dp[j]);
                }
            }
            dp[i] = currentMaxLength + 1;
            globalMaxLength = Math.max(globalMaxLength, dp[i]);
        }

        return globalMaxLength;
    }
}

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/

复杂度分析

解法4：贪心算法（二分查找）

思路：既然要求的是最大递增子串的长度，那么就找到其中一个最长递增子串。从第一个数字开始遍历，只要能形成递增数列就加到末尾，如果比当前的最长递增子串的最大值要小，就替换掉最长递增子串中的一个刚好比这个数字小的数字。

public class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        ArrayList<Integer> currentLIS = new ArrayList<Integer>();
        currentLIS.add(nums[0]);
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] > currentLIS.get(currentLIS.size() - 1)) {
                currentLIS.add(nums[i]);
                continue;
            }

            int begin = 0;
            int end = currentLIS.size() - 1;
            while (begin <= end) {
                int mid = begin + (end - begin) / 2;
                if (nums[i] < currentLIS.get(mid)) {
                    end = mid - 1;
                } else if (nums[i] > currentLIS.get(mid)) {
                    begin = mid + 1;
                } else {
                    begin = mid;
                    break;
                }
            }
            currentLIS.set(begin, nums[i]);
        }
        return currentLIS.size();
    }
}

https://leetcode-cn.com/problems/longest-increasing-subsequence/solution/chao-xiang-xi-tu-jie-di-gui-dong-tai-gui-hua-er-fe/

复杂度分析

时间复杂度：$O(nlog n)$

空间复杂度：$O(n)$

参考资料

LeetCode 300. Longest Increasing Subsequence 最长递增子序列 - Grandyang - 博客园

LeetCode 151. Reverse Words in a String[Medium]

发表于 2020-05-21 更新于 2024-08-05

题目地址：https://leetcode.com/problems/reverse-words-in-a-string/

题目

Given an input string, reverse the string word by word.

Example 1:

1 2	Input: "the sky is blue" Output: "blue is sky the"

Example 2:

1
2
3

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

1
2
3

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

A word is defined as a sequence of non-space characters.
Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.

解法1

思路

实现

参考资料

LeetCode Reverse Words in a String 翻转字符串中的单词 - Grandyang - 博客园

LeetCode 189. Rotate Array[Easy]

发表于 2020-05-20 更新于 2022-09-13

题目地址：https://leetcode.com/problems/rotate-array/

题解地址：https://leetcode.com/articles/rotate-array/

题目

Given an array, rotate the array to the right by k steps, where k is non-negative.

Follow up:

Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
Could you do it in-place with O(1) extra space?

Example 1:

Input: nums = [1,2,3,4,5,6,7], k = 3
Output: [5,6,7,1,2,3,4]
Explanation:
rotate 1 steps to the right: [7,1,2,3,4,5,6]
rotate 2 steps to the right: [6,7,1,2,3,4,5]
rotate 3 steps to the right: [5,6,7,1,2,3,4]

Example 2:

Input: nums = [-1,-100,3,99], k = 2
Output: [3,99,-1,-100]
Explanation: 
rotate 1 steps to the right: [99,-1,-100,3]
rotate 2 steps to the right: [3,99,-1,-100]

Constraints:

1 <= nums.length <= 2 * 10^4
It’s guaranteed that nums[i] fits in a 32 bit-signed integer.
k >= 0

解法1：蛮力法

思路

一次向右移动 1 位，移动 k 次。

代码

略

解法2：使用额外数组

思路

使用和原数组大小相同的额外数组，直接把原数组元素放置到新数组对应位置上。

代码

略

解法3：循环赋值

思路

从第一个元素开始依次向后移动，每次都先把下一个元素缓存起来，这样最终会循环到最初的位置。

代码

解法4：三次翻转

思路

整体翻转一次。

把前 k 个翻转一下。

把后 n-k 个翻转一下。

代码

LeetCode 509. Fibonacci Number [Easy]

发表于 2020-04-16 更新于 2024-08-05

Fibonacci Number - LeetCode

题目

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

1 2	F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

Example 1:

1
2
3

Input: 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

1
2
3

Input: 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

1
2
3

Input: 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Note:

0 ≤ N ≤ 30.

解法1[Java]：递归

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        } else {
            return fib(N - 1) + fib(N - 2);
        }
    }
}

时空复杂度

时间复杂度：

空间复杂度：

解法2[Java]：

class Solution {
    public int fib(int N) {
        if (N == 0) {
            return 0;
        } else if (N == 1) {
            return 1;
        } else {
            int last = 1;
            int secondToLast = 0;
            int result = 0;
            for (int i = 2; i <= N; ++i) {
                result = last + secondToLast;
                secondToLast = last;
                last = result;
            }
            return result;
        }
    }
}

时空复杂度

时间复杂度：$O(n)$

空间复杂度：$O(1)$

剑指 Offer 原版

题目

解答

解答1[Java]

LeetCode 版本

解答

解答1[Java]

对应 LeetCode 题目

题目

参考资料

题目

解答

解法1[Java]

思路

解法2[Java]

思路

测试用例设计

题目

题解

解答1[Java]

思路

参考资料

题目

分析

解法1

解法2

思路

参考资料

题目

解法1：蛮力法

思路

复杂度分析

解法2：递归方法优化

解法3：动态规划

复杂度分析

解法4：贪心算法（二分查找）

复杂度分析

参考资料

题目

解法1

思路

实现

参考资料

题目

解法1：蛮力法

思路

代码

解法2：使用额外数组

思路

代码

解法3：循环赋值

思路

代码

解法4：三次翻转

思路

代码

题目

解法1[Java]：递归

时空复杂度

解法2[Java]：

时空复杂度

解法3[Java]：

参考资料