Java每日一练(20230503) 外观数列、有序数组转BST、翻转字符串里的单词

简介: Java每日一练(20230503) 外观数列、有序数组转BST、翻转字符串里的单词

1. 外观数列

给定一个正整数 n ,输出外观数列的第 n 项。

「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列:

  • countAndSay(1) = "1"
  • countAndSay(n) 是对 countAndSay(n-1) 的描述,然后转换成另一个数字字符串。

前五项如下:

1.     1

2.     11

3.     21

4.     1211

5.     111221

第一项是数字 1

描述前一项,这个数是 1 即 “ 一 个 1 ”,记作 "11"

描述前一项,这个数是 11 即 “ 二 个 1 ” ,记作 "21"

描述前一项,这个数是 21 即 “ 一 个 2 + 一 个 1 ” ,记作 "1211"

描述前一项,这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ,记作 "111221"


描述 一个数字字符串,首先要将字符串分割最小 数量的组,每个组都由连续的最多 相同字符 组成。然后对于每个组,先描述字符的数量,然后描述字符,形成一个描述组。要将描述转换为数字字符串,先将每组中的字符数量用数字替换,再将所有描述组连接起来。

例如,数字字符串 "3322251" 的描述如下图:

示例 1:

输入:n = 1

输出:"1"

解释:这是一个基本样例。


示例 2:

输入:n = 4

输出:"1211"

解释:

countAndSay(1) = "1"

countAndSay(2) = 读 "1" = 一 个 1 = "11"

countAndSay(3) = 读 "11" = 二 个 1 = "21"

countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"


提示:

  • 1 <= n <= 30

出处:

https://edu.csdn.net/practice/26974821

代码:

import java.util.*;
public class countAndSay {
    public static class Solution {
        public String countAndSay(int n) {
            String pre = "1";
            for (int i = 1; i < n; i++) {
                StringBuilder temp = new StringBuilder();
                char c = pre.charAt(0);
                int cnt = 1;
                for (int j = 1; j < pre.length(); j++) {
                    char cc = pre.charAt(j);
                    if (c == cc) {
                        cnt++;
                    } else {
                        temp.append(cnt).append(c);
                        cnt = 1;
                        c = cc;
                    }
                }
                temp.append(cnt).append(c);
                pre = temp.toString();
            }
            return pre;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.countAndSay(1));
        System.out.println(s.countAndSay(4));
    }
}

输出:

1

1211


2. 将有序数组转换为二叉搜索树

给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡二叉搜索树

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1:

输入:nums = [-10,-3,0,5,9]

输出:[0,-3,9,-10,null,5]

解释:[0,-10,5,null,-3,null,9] 也将被视为正确答案:


示例 2:

输入:nums = [1,3]

输出:[3,1]

解释:[1,3] 和 [3,1] 都是高度平衡二叉搜索树。


提示:

  • 1 <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4
  • nums严格递增 顺序排列

出处:

https://edu.csdn.net/practice/26974822

代码:

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {
    }
    TreeNode(int val) {
        this.val = val;
    }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length - 1);
    }
    public TreeNode traversal(int[] nums, int left, int right) {
        if (left > right)
            return null;
        int mid = left + ((right - left) / 2);
        TreeNode node = new TreeNode(nums[mid]);
        node.left = traversal(nums, left, mid - 1);
        node.right = traversal(nums, mid + 1, right);
        return node;
    }
}

输出:


3. 翻转字符串里的单词

给你一个字符串 s ,逐个翻转字符串中的所有 单词

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

说明:

  • 输入字符串 s 可以在前面、后面或者单词间包含多余的空格。
  • 翻转后单词间应当仅用一个空格分隔。
  • 翻转后的字符串中不应包含额外的空格。

示例 1:

输入:s = "the sky is blue"

输出:"blue is sky the"


示例 2:

输入:s = "  hello world  "

输出:"world hello"

解释:输入字符串可以在前面或者后面包含多余的空格,但是翻转后的字符不能包括。


示例 3:

输入:s = "a good   example"

输出:"example good a"

解释:如果两个单词间有多余的空格,将翻转后单词间的空格减少到只含一个。


示例 4:

输入:s = "  Bob    Loves  Alice   "

输出:"Alice Loves Bob"


示例 5:

输入:s = "Alice does not even like bob"

输出:"bob like even not does Alice"


提示:

  • 1 <= s.length <= 10^4
  • s 包含英文大小写字母、数字和空格 ' '
  • s至少存在一个 单词

进阶:

  • 请尝试使用 O(1) 额外空间复杂度的原地解法。

出处:

https://edu.csdn.net/practice/26974823

代码:

import java.util.*;
import java.util.LinkedList;
public class reverseWords {
    public static class Solution {
        public StringBuilder trimSpaces(String s) {
            int left = 0, right = s.length() - 1;
            while (left <= right && s.charAt(left) == ' ')
                ++left;
            while (left <= right && s.charAt(right) == ' ')
                --right;
            StringBuilder sb = new StringBuilder();
            while (left <= right) {
                char c = s.charAt(left);
                if (c != ' ')
                    sb.append(c);
                else if (sb.charAt(sb.length() - 1) != ' ')
                    sb.append(c);
                ++left;
            }
            return sb;
        }
        public void reverse(StringBuilder sb, int left, int right) {
            while (left < right) {
                char tmp = sb.charAt(left);
                sb.setCharAt(left++, sb.charAt(right));
                sb.setCharAt(right--, tmp);
            }
        }
        public void reverseEachWord(StringBuilder sb) {
            int n = sb.length();
            int start = 0, end = 0;
            while (start < n) {
                while (end < n && sb.charAt(end) != ' ')
                    ++end;
                reverse(sb, start, end - 1);
                start = end + 1;
                ++end;
            }
        }
        public String reverseWords(String s) {
            StringBuilder sb = trimSpaces(s);
            reverse(sb, 0, sb.length() - 1);
            reverseEachWord(sb);
            return sb.toString();
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String str = "the sky is blue";
        System.out.println(s.reverseWords(str));
        str = "  hello world  ";
        System.out.println(s.reverseWords(str));
        str = "a good   example";
        System.out.println(s.reverseWords(str));
        str = "  Bob    Loves  Alice   ";
        System.out.println(s.reverseWords(str));
        str = "Alice does not even like bob";
        System.out.println(s.reverseWords(str));
    }
}

输出:

blue is sky the

world hello

example good a

Alice Loves Bob

bob like even not does Alice


🌟 每日一练刷题专栏 🌟

持续,努力奋斗做强刷题搬运工!

👍 点赞,你的认可是我坚持的动力!

🌟 收藏,你的青睐是我努力的方向!

评论,你的意见是我进步的财富!  

主页:https://hannyang.blog.csdn.net/


目录
打赏
0
0
0
0
74
分享
相关文章
|
3月前
|
java小工具util系列2:字符串工具
java小工具util系列2:字符串工具
172 83
|
3月前
|
Java零基础-字符串详解
【10月更文挑战第18天】Java零基础教学篇,手把手实践教学!
125 60
|
3月前
|
java小工具util系列1:日期和字符串转换工具
java小工具util系列1:日期和字符串转换工具
78 26
java 中操作字符串都有哪些类,它们之间有什么区别
Java中操作字符串的类主要有String、StringBuilder和StringBuffer。String是不可变的,每次操作都会生成新对象;StringBuilder和StringBuffer都是可变的,但StringBuilder是非线程安全的,而StringBuffer是线程安全的,因此性能略低。
105 8
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
71 6
Java社招面试题:一个线程运行时发生异常会怎样?
大家好,我是小米。今天分享一个经典的 Java 面试题:线程运行时发生异常,程序会怎样处理?此问题考察 Java 线程和异常处理机制的理解。线程发生异常,默认会导致线程终止,但可以通过 try-catch 捕获并处理,避免影响其他线程。未捕获的异常可通过 Thread.UncaughtExceptionHandler 处理。线程池中的异常会被自动处理,不影响任务执行。希望这篇文章能帮助你深入理解 Java 线程异常处理机制,为面试做好准备。如果你觉得有帮助,欢迎收藏、转发!
60 14
Java 面试必问!线程构造方法和静态块的执行线程到底是谁?
大家好,我是小米。今天聊聊Java多线程面试题:线程类的构造方法和静态块是由哪个线程调用的?构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节有助于掌握Java多线程机制。下期再见! 简介: 本文通过一个常见的Java多线程面试题,详细讲解了线程类的构造方法和静态块是由哪个线程调用的。构造方法由创建线程实例的主线程调用,静态块在类加载时由主线程调用。理解这些细节对掌握Java多线程编程至关重要。
43 13
【JAVA】封装多线程原理
Java 中的多线程封装旨在简化使用、提高安全性和增强可维护性。通过抽象和隐藏底层细节,提供简洁接口。常见封装方式包括基于 Runnable 和 Callable 接口的任务封装,以及线程池的封装。Runnable 适用于无返回值任务,Callable 支持有返回值任务。线程池(如 ExecutorService)则用于管理和复用线程,减少性能开销。示例代码展示了如何实现这些封装,使多线程编程更加高效和安全。
|
1月前
|
java异步判断线程池所有任务是否执行完
通过上述步骤,您可以在Java中实现异步判断线程池所有任务是否执行完毕。这种方法使用了 `CompletionService`来监控任务的完成情况,并通过一个独立线程异步检查所有任务的执行状态。这种设计不仅简洁高效,还能确保在大量任务处理时程序的稳定性和可维护性。希望本文能为您的开发工作提供实用的指导和帮助。
113 17
|
2月前
|
Java—多线程实现生产消费者
本文介绍了多线程实现生产消费者模式的三个版本。Version1包含四个类:`Producer`(生产者)、`Consumer`(消费者)、`Resource`(公共资源)和`TestMain`(测试类)。通过`synchronized`和`wait/notify`机制控制线程同步,但存在多个生产者或消费者时可能出现多次生产和消费的问题。 Version2将`if`改为`while`,解决了多次生产和消费的问题,但仍可能因`notify()`随机唤醒线程而导致死锁。因此,引入了`notifyAll()`来唤醒所有等待线程,但这会带来性能问题。
Java—多线程实现生产消费者