一、反转字符串写出一个程序接受一个字符串然后输出该字符串反转后的字符串。字符串长度不超过1000数据范围 0≤n≤1000要求空间复杂度 O(n)时间复杂度 O(n)import java.util.*; public class Solution { public String solve(String str) { char[] arr str.toCharArray(); for (int l 0, r arr.length - 1; l r; l, r--) { char tem arr[l]; arr[l] arr[r]; arr[r] tem; } return new String(arr); } }运行结果二、最长无重复子数组给定一个长度为n的数组arr返回arr的最长无重复元素子数组的长度无重复指的是所有数字都不相同。子数组是连续的比如[1,3,5,7,9]的子数组有[1,3][3,5,7]等等但是[1,3,7]不是子数组import java.util.*; public class Solution { public int maxLength(int[] arr) { if (arr null || arr.length 0) return 0; MapInteger, Integer lastSeen new HashMap(); // 记录每个数字最后一次出现的索引 int left 0; // 窗口左边界包含 int maxLen 0; // 最长无重复子数组长度 for (int right 0; right arr.length; right) { int num arr[right]; // 如果当前数字已在窗口中出现过且位置 left if (lastSeen.containsKey(num) lastSeen.get(num) left) { // 移动左边界到重复元素的下一个位置 left lastSeen.get(num) 1; } // 更新当前数字的最新位置 lastSeen.put(num, right); // 更新最大长度窗口大小 right - left 1 maxLen Math.max(maxLen, right - left 1); } return maxLen; } }运行结果三、盛水最多的容器给定一个数组height长度为n每个数代表坐标轴中的一个点的高度height[i]是在第i点的高度请问从中选2个高度与x轴组成的容器最多能容纳多少水import java.util.*; // 盛水 类似接雨水 // 双指针i,j初始两端,每次移动小的那端,遇到更高的更新两端大小关系 面积 // 直到i,j相遇 public class Solution { public int maxArea (int[] height) { if (height.length 0) return 0; int res 0, i 0, j height.length - 1, left height[i], right height[j]; while (i j) { res Math.max(res, Math.min(left, right) * (j - i)); // 计算面积 // System.out.printf(i%d j%d %d %d res%d\n, i, j, height[i], height[j], res); // 左端更矮, 移动i if (left right) { while (i j height[i] left) { // 更低高度的,面积肯定更小,略过 i; } if (i j) left height[i]; // 遇到更高的,更新左端高 } // 右端更矮, 移动j else { while (i j height[j] right) { j--; } if (i j) right height[j]; } } return res; } }运行结果四、接雨水问题给定一个整形数组arr已知其中所有的值都是非负的将这个数组看作一个柱子高度图计算按此排列的柱子下雨之后能接多少雨水。(数组以外的区域高度视为0)import java.util.*; // 接雨水双指针i,j初始位于两端, 水柱最高取min(a[i],a[j]) // i,j总移动小的那端,向中心移动直到碰到更高的桶边更新两端大小关系 // 直至i,j相遇 public class Solution { public long maxWater (int[] arr) { if (arr.length 1) return 0; int i 0, j arr.length - 1, left arr[i], right arr[j]; long res 0; while (i j) { // 左端更矮 if (left right) { while (i j arr[i] left) { // 遇到更低的,有水 res left - arr[i]; i; } if (i j) break; left arr[i]; // 更新左端桶高 } // 右端更矮 处理同上 else { while (i j arr[j] right) { res right - arr[j]; j--; } if (i j) break; right arr[j]; } } return res; } }运行结果
