Java每日一练(20230422) 拼接最大数、Z字形变换、跳跃游戏

简介: Java每日一练(20230422) 拼接最大数、Z字形变换、跳跃游戏

1. 拼接最大数

给定长度分别为 mn 的两个数组,其元素由 0-9 构成,表示两个自然数各位上的数字。现在从这两个数组中选出 k (k <= m + n) 个数字拼接成一个新的数,要求从同一个数组中取出的数字保持其在原数组中的相对顺序。

求满足该条件的最大数。结果返回一个表示该最大数的长度为 k 的数组。

说明: 请尽可能地优化你算法的时间和空间复杂度

示例 1:

输入:

nums1 = [3, 4, 6, 5]

nums2 = [9, 1, 2, 5, 8, 3]

k = 5

输出:[9, 8, 6, 5, 3]

示例 2:

输入:

nums1 = [6, 7]

nums2 = [6, 0, 4]

k = 5


输出:[6, 7, 6, 0, 4]

示例 3:

输入:

nums1 = [3, 9]

nums2 = [8, 9]

k = 3


输出:[9, 8, 9]

出处:

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

代码:

import java.util.*;
class maxNumber {
    public static class Solution {
        private int[] maxInNums(int[] nums, int k) {
          int[] max = new int[k];
          int len = nums.length;
          for (int i = 0, j = 0; i < len; ++i) {
             while (j > 0 && k - j < len - i && max[j - 1] < nums[i])
                 --j;
             if (j < k)
                 max[j++] = nums[i];
          }
          return max;
        }
        private boolean greater(int[] nums1Max, int i, int[] nums2Max, int j) {
          int lenNums1Max = nums1Max.length;
          int lenNums2Max = nums2Max.length;
          while (i < lenNums1Max && j < lenNums2Max && nums1Max[i] == nums2Max[j]) {
             ++i;
             ++j;
          }
          return j == lenNums2Max || (i < lenNums1Max && nums1Max[i] > nums2Max[j]);
        }
        private int[] merge(int[] nums1Max, int[] nums2Max) {
          int lenCurRes = nums1Max.length + nums2Max.length;
          int[] curRes = new int[lenCurRes];
          for (int i = 0, j = 0, m = 0; m < lenCurRes; ++m) {
             curRes[m] = greater(nums1Max, i, nums2Max, j) ? nums1Max[i++] : nums2Max[j++];
          }
          return curRes;
        }
        public int[] maxNumber(int[] nums1, int[] nums2, int k) {
          int[] res = null;
          for (int i = Math.max(k - nums2.length, 0); i <= Math.min(nums1.length, k); ++i) {
             int[] merge = merge(maxInNums(nums1, i), maxInNums(nums2, k - i));
             res = (res == null || greater(merge, 0, res, 0)) ? merge : res;
          }
          return res;
        }
    }
    public static void printArray(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; ++i) {
            System.out.print(arr[i]);
            if (i+1 < arr.length) {
                System.out.print(",");
            }
        }
        System.out.println("]");
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums1 = {3, 4, 6, 5};
        int[] nums2 = {9, 1, 2, 5, 8, 3};
        printArray(s.maxNumber(nums1, nums2, 5));
        int[] nums3 = {6, 7};
        int[] nums4 = {6, 0, 4};
        printArray(s.maxNumber(nums3, nums4, 5));
        int[] nums5 = {3, 9};
        int[] nums6 = {8, 9};
        printArray(s.maxNumber(nums5, nums6, 3));
    }
}

输出:

[9,8,6,5,3]

[6,7,6,0,4]

[9,8,9]


2. Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ,以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时,排列如下:

P   A   H   N

A P L S I I G

Y   I   R

之后,你的输出需要从左往右逐行读取,产生出一个新的字符串,比如:"PAHNAPLSIIGYIR"

请你实现这个将字符串进行指定行数变换的函数:

string convert(string s, int numRows);


示例 1:

输入:s = "PAYPALISHIRING", numRows = 3

输出:"PAHNAPLSIIGYIR"


示例 2:

输入:s = "PAYPALISHIRING", numRows = 4

输出:"PINALSIGYAHRPI"

解释:

P     I    N

A   L S  I G

Y A   H R

P     I


示例 3:

输入:s = "A", numRows = 1

输出:"A"


提示:

  • 1 <= s.length <= 1000
  • s 由英文字母(小写和大写)、',''.' 组成
  • 1 <= numRows <= 1000

出处:

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

代码:

import java.util.*;
class convert {
    public static class Solution {
        public String convert(String s, int numRows) {
            if (numRows == 1)
                return s;
            int len = s.length();
            if (len <= numRows)
                return s;
            int cycle_len = 2 * numRows - 2;
            int full_cycles = len / cycle_len;
            int left = len % cycle_len;
            StringBuilder r = new StringBuilder();
            int i;
            for (i = 0; i < full_cycles; ++i) {
                r.append(s.charAt(i * cycle_len));
            }
            if (left > 0) {
                r.append(s.charAt(i * cycle_len));
            }
            for (i = 0; i < numRows - 2; ++i) {
                int j;
                for (j = 0; j < full_cycles; ++j) {
                    r.append(s.charAt(j * cycle_len + i + 1));
                    r.append(s.charAt(j * cycle_len + i + 1 + cycle_len - 2 * (i + 1)));
                }
                if (left > 0) {
                    if (j * cycle_len + i + 1 < len)
                        r.append(s.charAt(j * cycle_len + i + 1));
                    if (j * cycle_len + i + 1 + cycle_len - 2 * (i + 1) < len)
                        r.append(s.charAt(j * cycle_len + i + 1 + cycle_len - 2 * (i + 1)));
                }
            }
            for (i = 0; i < full_cycles; ++i)
                r.append(s.charAt(i * cycle_len + numRows - 1));
            if (left >= numRows)
                r.append(s.charAt(i * cycle_len + numRows - 1));
            return r.toString();
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        String str = "PAYPALISHIRING";
        System.out.println(s.convert(str, 3));
        System.out.println(s.convert(str, 4));
    }
}

输出:

PAHNAPLSIIGYIR

PINALSIGYAHRPI


3. 跳跃游戏

给定一个非负整数数组 nums ,你最初位于数组的 第一个下标

数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标。

示例 1:

输入:nums = [2,3,1,1,4]

输出:true

解释:可以先跳 1 步,从下标 0 到达下标 1, 然后再从下标 1 跳 3 步到达最后一个下标。

示例 2:

输入:nums = [3,2,1,0,4]

输出:false

解释:无论怎样,总会到达下标为 3 的位置。但该下标的最大跳跃长度是 0 , 所以永远不可能到达最后一个下标。


提示:

  • 1 <= nums.length <= 3 * 10^4
  • 0 <= nums[i] <= 10^5

出处:

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

代码:

import java.util.*;
class canJump {
    public static class Solution {
        public boolean canJump(int[] nums) {
            boolean can = true;
            if (nums.length < 2) {
                return can;
            }
            int n = nums.length;
            int stride = 1;
            for (int i = n - 2; i >= 0; i--) {
                if (nums[i] < stride) {
                    stride++;
                    can = false;
                } else {
                    can = true;
                    stride = 1;
                }
            }
            return can;
        }
    }
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] nums = {2,3,1,1,4};
        System.out.println(s.canJump(nums));
        int[] nums2 = {3,2,1,0,4};
        System.out.println(s.canJump(nums2));
    }
}

输出:

true

fasle


🌟 每日一练刷题专栏 🌟

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

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

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

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

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


目录
相关文章
|
1月前
|
缓存 算法 Java
本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制
在现代软件开发中,性能优化至关重要。本文聚焦于Java内存管理与调优,介绍Java内存模型、内存泄漏检测与预防、高效字符串拼接、数据结构优化及垃圾回收机制。通过调整垃圾回收器参数、优化堆大小与布局、使用对象池和缓存技术,开发者可显著提升应用性能和稳定性。
49 6
|
5月前
|
Java 索引
Java实现扑克牌游戏 | 随机发牌 ( 过程拆分详解+完整代码 )
Java实现扑克牌游戏 | 随机发牌 ( 过程拆分详解+完整代码 )
128 3
|
2月前
|
开发框架 IDE Java
java制作游戏,如何使用libgdx,入门级别教学
本文是一篇入门级教程,介绍了如何使用libgdx游戏开发框架创建一个简单的游戏项目,包括访问libgdx官网、设置项目、下载项目生成工具,并在IDE中运行生成的项目。
60 1
java制作游戏,如何使用libgdx,入门级别教学
|
3月前
|
算法 Oracle Java
Java字符串拼接技术演进及阿里巴巴的贡献
本文主要讲述了Java字符串拼接技术的演进历程,以及阿里巴巴贡献的最新实现 PR 20273。
140 11
|
3月前
|
算法 Oracle Java
Java字符串拼接技术演进及阿里巴巴的贡献
本文主要讲述了Java字符串拼接技术的演进历程,以及阿里巴巴贡献的最新实现 PR 20273。
|
4月前
|
安全 Java 编译器
【Java基础面试二十九】、说一说你对字符串拼接的理解
这篇文章讨论了Java中字符串拼接的四种常用方式(使用`+`运算符、`StringBuilder`、`StringBuffer`和`String`类的`concat`方法),每种方式适用的场景,以及在不同情况下的性能考量。
|
4月前
|
人工智能 算法 Java
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
LeetCode经典算法题:井字游戏+优势洗牌+Dota2参议院java解法
54 1
|
5月前
|
Java 程序员 语音技术
怎么用Java 把多个音频拼接成一个?
**Java音频拼接指南** 在Java中,利用音频处理库`cn.juwatech.*`可合并音频文件。步骤包括导入库,创建`AudioFile`对象,将它们添加到列表,然后用`AudioConcatenator.concat()`拼接成一个文件。注意确保音频格式一致,处理异常,并考虑性能优化。此技术提升用户体验,适用于音频编辑和合成场景。[来源:稀土掘金](https://juejin.cn/post/7387701265797840932)
169 0
|
5月前
|
安全 Java
Java8 拼接字符串 StringJoiner
Java8 拼接字符串 StringJoiner
|
6月前
|
Java
使用java编写猜数字游戏
使用java编写猜数字游戏