打印从1到最大的n位数

剑指 Offer 17. 打印从1到最大的n位数 - 力扣（Leetcode）

题目要求

输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。

例子：

1
2
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]

说明：

  • 用返回一个整数列表来代替打印
  • n 为正整数

思路分析

该题不需要考虑大数问题，因此并不难，直接求出10的n次方，就是能确定最大的数，然后遍历即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int[] printNumbers(int n) {
        // 求10的n次方确定最大数
        int sum =(int)Math.pow(10,n);
        // 定义数组存放返回结果，大小为sum-1
        int[] arr = new int[sum-1];
        for(int i=0;i<sum-1;i++){
            arr[i] = i+1; 
        }
        return arr;
    }
}

删除链表的节点

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

题目要求

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

返回删除后的链表的头节点。

例子：

1
2
3
输入: head = [4,5,1,9], val = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.

说明：

  • 题目保证链表中节点的值互不相同
  • 若使用 C 或 C++ 语言，你不需要 free 或 delete 被删除的节点

思路分析

链表删除节点，需要定义两个指针变量temp和pre，必须保证pre一直指向链表temp的前一个节点，当找到要删除的节点，就pre.next=temp.next，然后返回head完成节点删除；

代码实现

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        // 链表是否为空
        if(head==null){
            return null;
        }
        // 删除的是否为头节点
        if(head.val == val){
            return head.next;
        }
        // 定义辅助变量
        ListNode temp = head.next;
        // pre永远指向temp的前一个节点
        ListNode pre = head;
        while(temp!=null){
            if(temp.val==val){
                // 找到了要删除的节点
                pre.next = temp.next;
                return head;
            }
            // temp后移
            temp = temp.next;
            // pre后移
            pre = pre.next;
        }
        return head;
    }
}

正则表达式匹配

剑指 Offer 19. 正则表达式匹配 - 力扣（Leetcode）

题目要求

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。

例子：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
    
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
    
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

提示：

  • s 可能为空，且只包含从 a-z 的小写字母。
  • p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 *，无连续的 '*'。

思路分析

使用动态规划求解

image-20221215154506106

dp[i][j]：表示当字符串长度为i,j时，S与P是否匹配

  1. p[j]->普通字符或者.时：
    • s[i] = p[j]或p[j]->.时： dp[i][j] = dp[i-1][j-1];
    • s[i] != p[j] dp[i][j] = false;
  2. p[j]->*时：
    • 当p[j-1] != s[i]时： dp[i][j] = dp[i][j-2];（*在这里代表匹配0个字符）
    • 当p[j-1] == s[i]时：
      • 当*匹配0个字符：dp[i][j] = dp[i][j-2];
      • 当*匹配1个字符：dp[i][j] = dp[i][j-1];
      • 当*匹配多个字符：dp[i][j] = dp[i-1][j];

寻找初始值：

不让dp[i][j]越界)

  • dp[0][0] = true

  • dp[0][1] = false

  • dp[0][2及以上] =：(j>=2)

    当dp[i][j]中p[j]=*时：

    • dp[0][j] = dp[0][j-2]

    当p[j]!=*时：

    • dp[0][j] = 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
class Solution {
    public boolean isMatch(String s, String p) {
        // s和p是否为空
        if(s == null || p == null){
            return true;
        }
        // 获取s和p的长度
        int m = p.length();
        int n = s.length();
        // 定义数组dp
        boolean[][] dp = new boolean[n+1][m+1];
        // java中定义boolean数组初始值默认都为false
        dp[0][0] = true;
        for(int j=2;j<=m;j++){
            // 如果p[j-1] = *
            if(p.charAt(j-1) == '*'){
                dp[0][j] = dp[0][j-2];
            }
        }
        for(int i =1;i<=n;i++){
            for(int j=1;j<=m;j++){
                // 当j不为*
                if(p.charAt(j-1)!='*'){
                    if(p.charAt(j-1)=='.' || p.charAt(j-1) == s.charAt(i-1)){
                        dp[i][j] = dp[i-1][j-1];
                    }
                }else{ 
                    // 当j为*时：
                    // 当*与j-1个字符不匹配
                    if(p.charAt(j-2)!=s.charAt(i-1) && p.charAt(j-2)!='.'){
                        dp[i][j] = dp[i][j-2];
                    }else{
                        // 匹配0个或者匹配1个或者匹配多个
                        dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
                    }
                }
            }
        }
        return dp[n][m];
    }
}

表示数值的字符串

剑指 Offer 20. 表示数值的字符串 - 力扣（Leetcode）

题目要求

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

数值（按顺序）可以分成以下几个部分：

  1. 若干空格
  2. 一个 小数 或者 整数
  3. （可选）一个 'e' 或 'E' ，后面跟着一个 整数
  4. 若干空格

小数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 下述格式之一：
    1. 至少一位数字，后面跟着一个点 '.'
    2. 至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
    3. 一个点 '.' ，后面跟着至少一位数字

整数（按顺序）可以分成以下几个部分：

  1. （可选）一个符号字符（'+' 或 '-'）
  2. 至少一位数字

部分数值列举如下：

  • ["+100", "5e2", "-123", "3.1416", "-1E-16", "0123"]

部分非数值列举如下：

  • ["12e", "1a3.14", "1.2.3", "+-5", "12e+5.4"]

例子：

1
2
3
4
5
输入：s = "0"
输出：true
    
输入：s = "e"
输出：false

提示：

  • 1 <= s.length <= 20
  • s 仅含英文字母（大写和小写），数字（0-9），加号 '+' ，减号 '-' ，空格 ' ' 或者点 '.'

思路分析

有限状态机：根据题目所给的要求进行排除，把符合条件的返回true，其他情况返回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
51
52
class Solution {
    public boolean isNumber(String s) {
        // 有限随机态 小数点 数字 e/E +-
        // 判断字符串是否为空
        if(s == null || s.length()<=0){
            return false;
        }
        // 取出空格，并存放到char[] 中
        char[] res = s.trim().toCharArray();
        // 判断res是否为空
        if(res.length <=0) return false;

        // 获取char数组长度
        int n = res.length;

        // 定义三个布尔值，默认为false 存放是否为数字，小数点和E/e
        boolean is_num = false;
        boolean is_dot = false;
        boolean is_e_or_E = false;
        
        for(int i=0;i<n;i++){
            if(res[i]>='0' && res[i]<='9'){
                // 如果是数字，就将is_num变为true
                is_num = true;
            }else if(res[i] == '.'){
                //  +- 9.  .9   9.9
                // 如果是小数点，那么它前面不能再有小数点，
                // 也不能有重复的e/E
                if(is_dot || is_e_or_E){
                    return false;
                }
                is_dot = true;
            }else if(res[i] == 'e' || res[i] == 'E'){
                // 如果是e/E，前面必须要有数字，
                // 且前面不能出现重复的e/E
                if(is_e_or_E || !is_num){
                    return false;
                }
                is_e_or_E = true;
                is_num = false; // 10E+ 10E
            }else if(res[i] == '+' || res[i] == '-'){
                // +- 它的前面要有e/E
                if(i!=0 && res[i-1] != 'e' && res[i-1] != 'E'){
                    return false;
                }
            }else{
                return false;
            }
        }
        return is_num;
    }
}

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

剑指 Offer 21. 调整数组顺序使奇数位于偶数前面 - 力扣（Leetcode）

题目要求

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数在数组的前半部分，所有偶数在数组的后半部分。

例子：

1
2
3
输入：nums = [1,2,3,4]
输出：[1,3,2,4] 
注：[3,1,2,4] 也是正确的答案之一

提示：

  1. 0 <= nums.length <= 50000
  2. 0 <= nums[i] <= 10000

思路分析

定义left和right两个指针，分别指向数组最左和最右，让left向右扫描，同时right向左扫描，当left遇到偶数就停止，right遇到奇数就停止，然后left和right的值进行交换即可。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] exchange(int[] nums) {
        // 判断数组不为空
        if(nums==null || nums.length==0){
            return nums;
        }
        // 定义left和right两个指针
        int left = 0;
        int right = nums.length-1;
        while(left<right){
            // left是否扫描到偶数
            while(left<right && nums[left]%2!=0) left++;
            // right是否扫描到奇数
            while(left<right && nums[right]%2!=1) right--;
            // 进行交换
            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
        }
        return nums;
    }
}