首页 / JAVA / 《Java练习题》进阶练习题（二）
《Java练习题》进阶练习题（二）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《Java练习题》进阶练习题（二），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含14870字，纯文字阅读大概需要22分钟。
内容图文
前言：不仅仅要实现，更要提升性能，精益求精，用尽量少的时间复杂度和空间复杂度解决问题。
【程序58】
给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点?(i,?ai) 。在坐标内画 n 条垂直线，垂直线 i?的两个端点分别为?(i,?ai) 和 (i, 0)。找出其中的两条线，使得它们与?x?轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且?n?的值至少为 2。
图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
/**
* 给定 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点?(i,?ai) 。在坐标内画 n 条垂直线，垂直线 i?的两个端点分别为?(i,?ai) 和 (i, 0)。找出其中的两条线，使得它们与?x?轴共同构成的容器可以容纳最多的水。
* 说明：你不能倾斜容器，且?n?的值至少为 2。
* 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
*/
public class Subject58 {
public static void main(String[] args) {
int[] arr = new int[]{1,8,6,2,5,4,8,3,7};
System.out.println(maxArea2(arr));
}
/**
* 求最大面积
* @param height
* @return
*/
public static int maxArea2(int[] height) {
int maxArea = 0; //最大面积
int left = 0;
int right = height.length-1;
int leftvalue = 0;
int rightvalue = 0;
while (left < right){
if(height[left] < height[right]){
if(height[left] > leftvalue && height[left]*(right-left) > maxArea){
maxArea = height[left]*(right-left);
}
leftvalue = height[left];
left++;
}else{
if( height[right] > rightvalue && height[right] * (right - left) > maxArea) {
maxArea = height[right] * (right - left);
}
rightvalue = height[right];
right--;
}
}
return maxArea;
}
/**
* 计算最大面积
* @param height
* @return
*/
public static int maxArea(int[] height) {
int maxArea = 0;
int tmp0 = 0;
for (int i = 0; i < height.length; i++) {
if(height[i] > tmp0){
tmp0 = height[i];
}else{
continue;
}
for (int j = height.length-1; j >= 0 && j>i ; j--) {
if(height[j] >= height[i]){
if(height[i]*(j-i) > maxArea){
maxArea = height[i]*(j-i);
break;
}
}
}
}
tmp0 = 0;
for (int i = height.length-1; i >=0 ; i--) {
if(height[i] > tmp0){
tmp0 = height[i];
}else{
continue;
}
for (int j = 0; j < height.length && i>j; j++) {
if(height[j] >= height[i]){
if(height[i]*(i-j) > maxArea){
maxArea = height[i]*(i-j);
break;
}
}
}
}
return maxArea;
}
}
时间复杂度：O(n)
运行结果：
【程序59】
阿拉伯数字转罗马数字，罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
import java.util.ArrayList;
import java.util.List;
/**
* 【程序59】
* 阿拉伯数字转罗马数字，罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
*/
public class Subject59 {
public static void main(String[] args) {
System.out.println(intToRoman(1994));
}
/**
* 阿拉伯数字转罗马数字
* @param num
* @return
*/
public static String intToRoman(int num) {
List<String> list = new ArrayList<>();
StringBuilder result = new StringBuilder();
int i = num;
int num0 = 1;
while(i > 0){
int tmp = i%10;
if(num0 == 1){
if(tmp == 4){
list.add("IV");
}else if(tmp == 9) {
list.add("IX");
}else{
list.add(AssembleNumber(tmp,"I","V"));
}
}else if(num0 == 10){
if(tmp == 4){
list.add("XL");
}else if(tmp == 9) {
list.add("XC");
}else{
list.add(AssembleNumber(tmp,"X","L"));
}
}else if(num0 == 100){
if(tmp == 4){
list.add("CD");
}else if(tmp == 9) {
list.add("CM");
}else{
list.add(AssembleNumber(tmp,"C","D"));
}
}else{
list.add(AssembleNumber(tmp,"M",""));
}
num0 = num0*10;
i = i/10;
}
for(int index=list.size()-1 ;index >= 0;index--){
result.append(list.get(index));
}
return result.toString();
}
/**
* 转化
* @param tmp
* @param str0
* @param str1
* @return
*/
public static String AssembleNumber(int tmp,String str0,String str1){
String result = "";
if(tmp < 4){
for (int i=1;i <= tmp;i++){
result = result+str0;
}
}else{
result = result+str1;
for (int i=1;i <= tmp-5;i++){
result = result+str0;
}
}
return result;
}
}
时间复杂度：O(n)
运行结果：
【程序60】
罗马数字转阿拉伯数字，罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
import java.util.HashMap;
import java.util.Map;
/**
* 【程序60】
* 罗马数字转阿拉伯数字，罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。
*/
public class Subject60 {
public static void main(String[] args) {
System.out.println(new Subject60().romanToInt("MCMXCIV"));
}
static Map<String,Integer> map = new HashMap<>();
/**
* 静态代码块加载数据
*/
static {
map.put("I",1);
map.put("II",2);
map.put("III",3);
map.put("IV",4);
map.put("V",5);
map.put("VI",6);
map.put("VII",7);
map.put("VIII",8);
map.put("IX",9);
map.put("X",10);
map.put("XX",20);
map.put("XXX",30);
map.put("XL",40);
map.put("L",50);
map.put("LX",60);
map.put("LXX",70);
map.put("LXXX",80);
map.put("XC",90);
map.put("C",100);
map.put("CC",200);
map.put("CCC",300);
map.put("CD",400);
map.put("D",500);
map.put("DC",600);
map.put("DCC",700);
map.put("DCCC",800);
map.put("CM",900);
map.put("M",1000);
map.put("MM",2000);
map.put("MMM",3000);
}
/**
* 罗马数字转阿拉伯数字
* @param s
* @return
*/
public int romanToInt(String s) {
// I X C M 分别代表1，10，100，1000
int result = 0;
char[] arr = s.toCharArray();
int lenth = arr.length;
String tmp = "";
int index0 = 0;
for (int i = 0; i < lenth ;) {
tmp = tmp + arr[i];
if(map.containsKey(tmp)){
index0 = map.get(tmp);
i++;
}else{
result = result +index0;
tmp = "";
index0 = 0;
}
}
return result+index0;
}
}
时间复杂度：O(n)
运行结果：
【程序61】
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ""。
/**
* 编写一个函数来查找字符串数组中的最长公共前缀。
* 如果不存在公共前缀，返回空字符串 ""。
*/
public class Subject61 {
public static void main(String[] args) {
String[] strs = new String[]{"f","fl","flight"};
System.out.println(longestCommonPrefix(strs));
}
/**
* 最长公共前缀
* @param strs
* @return
*/
public static String longestCommonPrefix(String[] strs) {
String result = "";
if(strs.length <= 0){
return result;
}
boolean flag;
char tmp ;
int index = 0;
while(true){
flag = true;
if(index >= strs[0].length()){
break;
}else{
tmp = strs[0].charAt(index);
}
for (int i = 1 ;i < strs.length; i++) {
if(index >= strs[i].length() || strs[i].charAt(index) != tmp){
flag = false;
break;
}
}
if(flag){
result = result+tmp;
}else{
break;
}
index++;
}
return result;
}
}
时间复杂度：O(S?log(n))
运行结果：
【程序62】
给定一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，
使得?a + b + c = 0 ？找出所有满足条件且不重复的三元组。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 给定一个包含 n 个整数的数组?nums，判断?nums?中是否存在三个元素 a，b，c ，
* 使得?a + b + c = 0 ？找出所有满足条件且不重复的三元组。
*/
public class Subject62 {
public static void main(String[] args) {
int[] nums = new int[]{2,-1,-1,0,2,1,1};
System.out.println(threeSum(nums));
}
/**
* 获取满足条件的组合
* @param nums
* @return
*/
public static List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> tuples = new ArrayList<>();
for(int i = 0; i < nums.length-2; i++){
if(i > 0 && nums[i-1] == nums[i]) continue; //去重
int l = i+1, r = nums.length-1;
if(nums[l] < 0 && Integer.MIN_VALUE-nums[l] > nums[i]) continue; //如果溢出最小值则跳过
if(nums[i] > 0 && Integer.MAX_VALUE-nums[l] < nums[i]) break; //溢出最大值直接结束，不可能会有新的三元组出现了
while(l < r){
if(nums[r] > -nums[i]-nums[l]){
while(l < r && nums[r-1] == nums[r]) r--; //右指针去重
r--;
}
else if(nums[r] < -nums[i]-nums[l]){
while(l < r && nums[l+1] == nums[l]) l++; //左指针去重
l++;
}
else{
tuples.add(Arrays.asList(nums[i],nums[l],nums[r]));
while(l < r && nums[r-1] == nums[r]) r--; //左指针去重
while(l < r && nums[l+1] == nums[l]) l++; //右指针去重
r--;
l++;
}
}
}
return tuples;
}
}
时间复杂度：O(nlogn)
运行结果：
【程序63】
给定一个包括n 个整数的数组nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。
假定每组输入只存在唯一答案。
/**
* 给定一个包括n 个整数的数组nums和 一个目标值target。找出nums中的三个整数，使得它们的和与target最接近。返回这三个数的和。
* 假定每组输入只存在唯一答案。
*/
public class Subject63 {
public static void main(String[] args) {
int[] arr = new int[]{1,1,1,1};
int target = 0;
System.out.println(threeSumClosest(arr,target));
}
/**
* 获取最接近的三个数之和
* @param nums
* @param target
* @return
*/
public static int threeSumClosest(int[] nums, int target) {
int sum = 0;
if(nums.length<=3){
for (int i = 0; i < nums.length; i++) {
sum = sum + nums[i];
}
return sum;
}
int max = Integer.MAX_VALUE;
int min = Integer.MIN_VALUE;
for (int i = 0; i < nums.length-2; i++) {
for (int j = i+1; j < nums.length-1; j++) {
for (int k = j+1; k < nums.length; k++) {
int tmp = nums[i] + nums[j] + nums[k];
if(tmp == target ){
return target;
}else if(tmp > target){
if(tmp < max){
max = tmp;
}
}else{
if(tmp > min){
min = tmp;
}
}
}
}
}
if(max == Integer.MAX_VALUE){
return min;
}
if(min == Integer.MIN_VALUE){
return max;
}
if(Math.abs(max-target) <= Math.abs(target-min)){
sum = max;
}else{
sum = min;
}
return sum;
}
}
时间复杂度：O(n^2)
运行结果：
【程序64】
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
备注，每个数字对应的字母为9宫格输入法。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
* 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
* 备注，每个数字对应的字母为9宫格输入法。
*/
public class Subject64 {
public static void main(String[] args) {
System.out.println(letterCombinations("23"));
}
public static Map<Character,List<Character>> map = new HashMap<>();
//初始化数据
static {
List<Character> list = new ArrayList<>();
list.add('a');
list.add('b');
list.add('c');
map.put('2',list);
list = new ArrayList<>();
list.add('d');
list.add('e');
list.add('f');
map.put('3',list);
list = new ArrayList<>();
list.add('g');
list.add('h');
list.add('i');
map.put('4',list);
list = new ArrayList<>();
list.add('j');
list.add('k');
list.add('l');
map.put('5',list);
list = new ArrayList<>();
list.add('m');
list.add('n');
list.add('o');
map.put('6',list);
list = new ArrayList<>();
list.add('p');
list.add('q');
list.add('r');
list.add('s');
map.put('7',list);
list = new ArrayList<>();
list.add('t');
list.add('u');
list.add('v');
map.put('8',list);
list = new ArrayList<>();
list.add('w');
list.add('x');
list.add('y');
list.add('z');
map.put('9',list);
}
public static List<String> list;
/**
* 处理组合情况
* @param digits
* @return
*/
public static List<String> letterCombinations(String digits) {
if("".equals(digits)){
return list;
}
list = new ArrayList<>();
list.add("");
char[] arr = digits.toCharArray();
for (int i = 0; i < arr.length ; i++) {
letterCombinations0(arr[i]);
}
return list;
}
/**
* 配合letterCombinations使用
* @param c
*/
public static void letterCombinations0(char c){
List<Character> list0 = map.get(c);
List<String> listTmp = new ArrayList<>();
for (int i = 0; i < list.size(); i++) {
for (int j = 0; j < list0.size(); j++) {
listTmp.add(list.get(i)+list0.get(j));
}
}
list = listTmp;
}
}
时间复杂度：O(3N×4M)
运行结果：
【程序65】
给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？
找出所有满足条件且不重复的四元组。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* 给定一个包含n 个整数的数组nums和一个目标值target，判断nums中是否存在四个元素 a，b，c和 d，使得a + b + c + d的值与target相等？
* 找出所有满足条件且不重复的四元组。
*/
public class Subject65 {
public static void main(String[] args) {
int[] arr = new int[]{1, 0, -1, 0, -2, 2};
System.out.println(fourSum(arr,0));
}
/**
* 4个数之和
* @param nums
* @param target
* @return
*/
public static List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> lists = new ArrayList<>();
Arrays.sort(nums);
int lenths = nums.length;
if(lenths <= 3){
return lists;
}
int min = nums[0];
int max = nums[lenths-1];
int min0 = nums[0] + nums[1];
int max0 = nums[lenths-1]+nums[lenths-2];
for (int i = 0; i < lenths; i++) {
for (int j = i+1; j < lenths; j++) {
int tmp1 = target - nums[i] - nums[j];
if(tmp1 > max0){
continue;
}
if(tmp1 < min0){
break;
}
for (int k = j+1; k < lenths; k++) {
int tmp = target - nums[i] - nums[j] - nums[k];
if(tmp > max){
continue;
}
if(tmp < min){
break;
}
for (int l = k+1; l < lenths; l++) {
int tmp0 = nums[i] + nums[j] + nums[k] + nums[l];
if(target == tmp0){
List<Integer> list = new ArrayList<>();
list.add( nums[i]);
list.add(nums[j]);
list.add(nums[k]);
list.add(nums[l]);
if(!lists.contains(list)){
lists.add(list);
}
}
}
}
}
}
return lists;
}
}
时间复杂度：O(n3)
运行结果：
【程序66】
给定一个链表(单项链表)，删除链表的倒数第 n 个节点，并且返回链表的头结点。
public class ListNode {
int val;
ListNode next;
ListNode(){
}
ListNode(int x) { val = x; }
}
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*
* 给定一个链表(单项链表)，删除链表的倒数第 n 个节点，并且返回链表的头结点。
*/
public class Subject66 {
public static void main(String[] args) {
ListNode listNode0 = new ListNode(1);
ListNode listNode1 = new ListNode(2);
ListNode listNode2 = new ListNode(3);
ListNode listNode3 = new ListNode(4);
ListNode listNode4 = new ListNode(5);
listNode0.next = listNode1;
listNode1.next = listNode2;
listNode2.next = listNode3;
listNode3.next = listNode4;
ListNode listNode = new Subject66().removeNthFromEnd(listNode0,1);
StringBuilder stringBuilder = null;
while(listNode !=null){ //指向位置是否为空
if(stringBuilder == null){
stringBuilder = new StringBuilder();
stringBuilder.append(listNode.val);
}else{
stringBuilder.append(" -> "+ listNode.val);
}
listNode = listNode.next; // 指向下一个节点
}
System.out.println(stringBuilder.toString());
}
//公共变量
public static ListNode listNodeTmp;
/**
* 删除倒数N的节点
* @param head
* @param n
* @return
*/
public ListNode removeNthFromEnd(ListNode head, int n) {
listNodeTmp = null;
if(head == null){
return head;
}
int num = nodeNum(head,n);
if(num == n){
return head.next;
}
return head;
}
/**
* 递归获取节点位置
* @param head
* @param n
* @return
*/
public int nodeNum(ListNode head,int n){
int tmp = 0;
if(head != null){
tmp = 1+ nodeNum(head.next,n);
if(tmp == n +1){
head.next = listNodeTmp;
}
if(tmp == n-1){
listNodeTmp = head;
}
}
return tmp;
}
}
时间复杂度：O(n)
运行结果：
【程序67】
给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
/**
* 【程序67】
* 给定一个只包括 '('，')'，'{'，'}'，'['，']'的字符串，判断字符串是否有效。
* 有效字符串需满足：
* 左括号必须用相同类型的右括号闭合。
* 左括号必须以正确的顺序闭合。
* 注意空字符串可被认为是有效字符串。
*/
public class Subject67 {
public static void main(String[] args) {
String s= "[]";
System.out.println( new Subject67().isValid(s));
}
static Map<Character,Character> map = new HashMap<>();
static {
map.put('(',')');
map.put('{','}');
map.put('[',']');
}
/**
* 后进先匹配原理
* @param s
* @return
*/
public boolean isValid(String s) {
char[] arr = s.toCharArray();
if(arr.length <= 0){
return true;
}
List<Character> list = new ArrayList<>();
for (int i = 0; i < arr.length; i++) {
if(map.containsKey(arr[i])){
list.add(arr[i]);
}else{
if(list.size() <= 0) {
return false;
}
if(map.get(list.get(list.size()-1)) == arr[i]){
list.remove(list.size()-1);
}else{
return false;
}
}
}
if(list.size() == 0){
return true;
}else {
return false;
}
}
}
时间复杂度：O(n)
运行结果：
以上题目均来自：https://leetcode-cn.com/ ，如果你热爱编码，热爱算法，该网站一定适合你。
内容总结
以上是互联网集市为您收集整理的《Java练习题》进阶练习题（二）全部内容，希望文章能够帮你解决《Java练习题》进阶练习题（二）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。
来源：【匿名】