1. 拼接最大数
给定长度分别为 m 和 n 的两个数组，其元素由 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
