编程合集： https://www.cnblogs.com/jssj/p/12002760.html
前言：不仅仅要实现，更要提升性能，精益求精，用尽量少的时间复杂度和空间复杂度解决问题。
【程序88】
给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
/**
* 给定一个未排序的整数数组，找出其中没有出现的最小的正整数。
*/
public class Subject88 {
public static void main(String[] args) {
int[] arrInt = new int[]{-1,-9,1,2,4,6,9,8};
int number = new Subject88().firstMissingPositive(arrInt);
System.out.println(number);
} public int firstMissingPositive(int[] nums) {
int n = nums.length; // 基本情况
int contains = 0;
for (int i = 0; i < n; i++) {
if (nums[i] == 1) {
contains++;
break;
}
}
if (contains == 0)
return 1; // nums = [1]
if (n == 1)
return 2; // 用 1 替换负数，0，
// 和大于 n 的数
// 在转换以后，nums 只会包含
// 正数
for (int i = 0; i < n; i++)
if ((nums[i] <= 0) || (nums[i] > n))
nums[i] = 1; // 使用索引和数字符号作为检查器
// 例如，如果 nums[1] 是负数表示在数组中出现了数字 `1`
// 如果 nums[2] 是正数 表示数字 2 没有出现
for (int i = 0; i < n; i++) {
int a = Math.abs(nums[i]);
// 如果发现了一个数字 a - 改变第 a 个元素的符号
// 注意重复元素只需操作一次
if (a == n)
nums[0] = - Math.abs(nums[0]);
else
nums[a] = - Math.abs(nums[a]);
} // 现在第一个正数的下标
// 就是第一个缺失的数
for (int i = 1; i < n; i++) {
if (nums[i] > 0)
return i;
} if (nums[0] > 0)
return n; return n + 1;
}
}
时间复杂度为 O(n)。
运行结果：
【程序89】
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。
/**
* 【程序89】
* 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
* 上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。感谢 Marcos 贡献此图。
*/
public class Subject89 { public static void main(String[] args) {
int[] arrInt = new int[]{0,1,4,2,1,0,1,7,2,1,2,6};
int side = new Subject89().trap(arrInt);
System.out.println(side);
} public int trap(int[] height) {
int max = 0;
int side =0;
for (int i = 0; i < height.length ; i++) {
if(height[i] > max){
max = height[i];
side = i;
}
} int unit = 0;
//右边接收雨水量
unit = unit + trapRight(height,side);
//左边接受雨水量
unit = unit + trapLeft(height,side);
return unit;
} public int trapRight(int[] height,int side) {
int unit = 0;
int maxTmp = 0;
int sideTmp =0;
for (int i = height.length-1 ; i > side; i--) {
if(height[i] > maxTmp){
maxTmp = height[i];
sideTmp = i;
}
} //计算中间存在多少单位
unit = trapUnit(height,side,sideTmp);
if(maxTmp > 0 && sideTmp != height.length-1){
unit += trapRight(height,sideTmp);
}
return unit;
} public int trapLeft(int[] height,int side) {
int unit = 0;
int maxTmp = 0;
int sideTmp =0;
for (int i = 0 ; i < side; i++) {
if(height[i] > maxTmp){
maxTmp = height[i];
sideTmp = i;
}
}
//计算中间存在多少单位
unit = trapUnit(height, sideTmp,side);
if(maxTmp > 0 && sideTmp != 0) {
unit += trapLeft(height, sideTmp);
}
return unit;
} /**
* 计算中间可以存在多少单位雨水
* @param height
* @return
*/
public int trapUnit(int[] height,int left,int right){
int unit = 0;
if(right-left <= 1){
return unit;
} int low =0;
if(height[left] > height[right]){
low = height[right];
}else{
low = height[left];
} for (int i = left+1; i <= right-1; i++) {
unit = unit + (low - height[i]);
}
return unit;
}
}
时间复杂度为 O(n)。
运行结果：
【程序90】
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
/**
* 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
*/
public class Subject90 {
public static void main(String[] args) {
String num1 = "123";
String num2 = "456";
String nultiply = new Subject90().multiply(num1,num2);
System.out.println(nultiply);
}
public String multiply(String num1, String num2) {
if (num1.equals("0") || num2.equals("0")) {
return "0";
}
int[] res = new int[num1.length() + num2.length()];
for (int i = num1.length() - 1; i >= 0; i--) {
int n1 = num1.charAt(i) - '0';
for (int j = num2.length() - 1; j >= 0; j--) {
int n2 = num2.charAt(j) - '0';
int sum = (res[i + j + 1] + n1 * n2);
res[i + j + 1] = sum % 10;
res[i + j] += sum / 10;
}
} StringBuilder result = new StringBuilder();
for (int i = 0; i < res.length; i++) {
if (i == 0 && res[i] == 0) continue;
result.append(res[i]);
}
return result.toString();
}
}
时间复杂度为 O(MN)。
运行结果：
【程序91】
给定一个字符串(s) 和一个字符模式(p) ，实现一个支持'?'和'*'的通配符匹配。
'?' 可以匹配任何单个字符。
'*' 可以匹配任意字符串（包括空字符串）。
两个字符串完全匹配才算匹配成功。
/**
* 给定一个字符串(s) 和一个字符模式(p) ，实现一个支持'?'和'*'的通配符匹配。
* '?' 可以匹配任何单个字符。
* '*' 可以匹配任意字符串（包括空字符串）。
* 两个字符串完全匹配才算匹配成功。
*/
public class Subject91 {
public static void main(String[] args) {
String str1 = "abbabaaabababbaababbabbbbbabbbabb";
String str2 = "**aa*abb***";
System.out.println(new Subject91().isMatch(str1,str2));
} boolean isMatch(String str, String pattern) { int s = 0, p = 0, match = 0, starIdx = -1;
//遍历整个字符串
while (s < str.length()){
// 一对一匹配，两指针同时后移。
if (p < pattern.length() && (pattern.charAt(p) == '?' || str.charAt(s) == pattern.charAt(p))){
s++;
p++;
}
// 碰到 *，假设它匹配空串，并且用 startIdx 记录 * 的位置，记录当前字符串的位置，p 后移
else if (p < pattern.length() && pattern.charAt(p) == '*'){
starIdx = p;
match = s;
p++;
}
// 当前字符不匹配，并且也没有 *，回退
// p 回到 * 的下一个位置
// match 更新到下一个位置
// s 回到更新后的 match
// 这步代表用 * 匹配了一个字符
else if (starIdx != -1){
p = starIdx + 1;
match++;
s = match;
}
//字符不匹配，也没有 *，返回 false
else return false;
} //将末尾多余的 * 直接匹配空串 例如 text = ab, pattern = a*******
while (p < pattern.length() && pattern.charAt(p) == '*')
p++; return p == pattern.length();
}
}
时间复杂度为 O(TP)。
运行结果：
【程序92】
给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
/**
* 给定一个非负整数数组，你最初位于数组的第一个位置。
* 数组中的每个元素代表你在该位置可以跳跃的最大长度。
* 你的目标是使用最少的跳跃次数到达数组的最后一个位置。
*/
public class Subject92 { public static void main(String[] args) {
int[] arrInt = new int[]{2,3,1,1,4,2,1};
System.out.println(new Subject92().jump(arrInt));
} public int jump(int[] nums) {
//小于等于1的都不需要跳
int lengths = nums.length;
if(lengths <= 1){
return 0;
}
int reach = 0; //当前能走的最远距离
int nextreach = nums[0];
int step = 0; //需要步数
for(int i = 0;i<lengths;i++){
//贪心算法核心：这一步是不是可以比上一步得到更多步数，可以则取最新的路线。
nextreach = Math.max(i+nums[i],nextreach);
if(nextreach >= lengths-1) return (step+1);
if(i == reach){
step++;
reach = nextreach;
}
}
return step;
}
}
时间复杂度为 O(n)。
运行结果：
【程序93】
给定一个没有重复数字的序列，返回其所有可能的全排列。
import java.util.ArrayList;
import java.util.List; /**
* 给定一个没有重复数字的序列，返回其所有可能的全排列。
*/
public class Subject93 {
public static void main(String[] args) {
int[] arrInt = new int[]{1,2,3};
List<List<Integer>> integerList1 = new Subject93().permute(arrInt);
System.out.println(integerList1);
} List<List<Integer>> integerList = new ArrayList<>();
List<Integer> integerListTmp = new ArrayList<>(); int index = -1; /**
* 就一步步实现呗
* @param nums
* @return
*/
public List<List<Integer>> permute(int[] nums) { List<Integer> numList = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
numList.add(nums[i]);
integerListTmp.add(nums[i]);
}
index = nums.length;
permute(numList);
return integerList;
} public void permute(List<Integer> numList) {
int sizes = numList.size();
if (sizes <= 0) {
return ;
}
for (int i = 0; i < sizes; i++) {
integerListTmp.set(index- sizes,numList.get(i));
if(sizes <= 1){
List<Integer> numListTmp0 = new ArrayList<>();
numListTmp0.addAll(integerListTmp);
integerList.add(numListTmp0);
return;
}
List<Integer> numListTmp = new ArrayList<>();
numListTmp.addAll(numList);
numListTmp.remove(i);
permute(numListTmp);
}
}
}
时间复杂度为 。
运行结果：
【程序94】
给定一个可包含重复数字的序列，返回所有不重复的全排列。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map; /**
* 给定一个可包含重复数字的序列，返回所有不重复的全排列。
*/
public class Subject94 {
public static void main(String[] args) {
int[] arrInt = new int[]{3,1,3,3};
List<List<Integer>> integerList1 = new Subject94().permuteUnique(arrInt);
System.out.println(integerList1);
} List<List<Integer>> integerList = new ArrayList<>();
List<Integer> integerListTmp = new ArrayList<>(); int index = -1; /**
* 使用排序后，
* 剪枝的方式实现。
* @param nums
* @return
*/
public List<List<Integer>> permuteUnique(int[] nums) {
List<Integer> numList = new ArrayList<>();
//排序
Arrays.sort(nums); for (int i = 0; i < nums.length; i++) {
numList.add(nums[i]);
integerListTmp.add(nums[i]);
}
index = nums.length;
permuteUnique(numList);
return integerList;
} public void permuteUnique(List<Integer> numList) {
int sizes = numList.size();
if (sizes <= 0) {
return ;
}
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < sizes; i++) {
Integer integer = map.get(index- sizes);
if(integer != null){
if(integer == numList.get(i)){ //多余的分支都剪掉
continue;
}else{
map.put(index- sizes,numList.get(i));
}
}else{
map.put(index- sizes,numList.get(i));
} if(integerListTmp.get(index- sizes) != numList.get(i)){
integerListTmp.set(index- sizes,numList.get(i));
}
if(sizes <= 1){
List<Integer> numListTmp0 = new ArrayList<>();
numListTmp0.addAll(integerListTmp);
integerList.add(numListTmp0);
return;
}
List<Integer> numListTmp = new ArrayList<>();
numListTmp.addAll(numList);
numListTmp.remove(i);
permuteUnique(numListTmp);
}
}
}
时间复杂度为 。
运行结果：
【程序95】
给定一个 n×n 的二维矩阵表示一个图像。
将图像顺时针旋转 90 度。
说明：
你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
/**
* 给定一个 n×n 的二维矩阵表示一个图像。
* 将图像顺时针旋转 90 度。
* 说明：
* 你必须在原地旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要使用另一个矩阵来旋转图像。
*/
public class Subject95 {
public static void main(String[] args) {
int[][] arrInt = new int[][]{{1,2,3},{4,5,6},{7,8,9}};
new Subject95().rotate(arrInt);
System.out.println(arrInt);
} public void rotate(int[][] matrix) {
int n = matrix.length;
for (int i = 0; i < (n + 1) / 2; i ++) {
for (int j = 0; j < n / 2; j++) {
int temp = matrix[n - 1 - j][i];
matrix[n - 1 - j][i] = matrix[n - 1 - i][n - j - 1];
matrix[n - 1 - i][n - j - 1] = matrix[j][n - 1 -i];
matrix[j][n - 1 - i] = matrix[i][j];
matrix[i][j] = temp;
}
}
}
}
时间复杂度为 O(n^2)。
运行结果：
【程序96】
给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
示例:
输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
输出:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
说明：
所有输入均为小写字母。
不考虑答案输出的顺序。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map; /**
* 给定一个字符串数组，将字母异位词组合在一起。字母异位词指字母相同，但排列不同的字符串。
* 示例:
* 输入: ["eat", "tea", "tan", "ate", "nat", "bat"],
* 输出:
* [
* ["ate","eat","tea"],
* ["nat","tan"],
* ["bat"]
* ]
* 说明：
* 所有输入均为小写字母。
* 不考虑答案输出的顺序。
*/
public class Subject96 {
public static void main(String[] args) {
String[] strArr = new String[]{"eat", "tea", "tan", "ate", "nat", "bat"};
List<List<String>> listList = new Subject96().groupAnagrams(strArr);
System.out.println(listList);
} List<List<String>> listList = new ArrayList<>();
Map<String,List<String>> map = new HashMap<>();
public List<List<String>> groupAnagrams(String[] strs) {
for (int i = 0; i < strs.length; i++) {
char[] ch = strs[i].toCharArray();
String str = dealChar(ch);
if(map.get(str) == null){
List<String> list = new ArrayList<>();
list.add(strs[i]);
map.put(str,list);
}else{
List<String> list = map.get(str);
list.add(strs[i]);
}
} Iterator<Map.Entry<String, List<String>>> it=map.entrySet().iterator();
while(it.hasNext()){
Map.Entry<String, List<String>> entry=it.next();
listList.add(entry.getValue());
} return listList;
} public String dealChar(char[] ch) {
Arrays.sort(ch);
return new String(ch,0,ch.length);
}
}
时间复杂度为 O(nk)。
运行结果：
【程序97】
实现 pow(x, n) ，即计算 x 的 n 次幂函数。
-100.0 < x < 100.0
n 是 32 位有符号整数，其数值范围是 [?2^31, 2^31 ? 1] 。
import java.util.HashMap;
import java.util.Map; /**
* 实现 pow(x, n) ，即计算 x 的 n 次幂函数。
* -100.0 < x < 100.0
* n 是 32 位有符号整数，其数值范围是 [?2^31, 2^31 ? 1] 。
*/
public class Subject97 { public static void main(String[] args) {
double dou = new Subject97().myPow(1.13183,-2147483648);
System.out.println(dou);
} Map<Integer,Double> map = new HashMap<>(); public double myPow(double x, int n) {
double dou = 1.0; if(n > 0){
if(n < 10){
for (int i =0 ;i < n; i++){
dou = dou*x ;
}
}else{
map.put(1,x);
map.put(2,x*x);
map.put(4,x*x*x*x);
map.put(8,x*x*x*x*x*x*x*x); int index = 8;
while(index <= n/2 && index < 1073741824){
int tmp = index;
index = index*2;
map.put(index,map.get(tmp)* map.get(tmp));
} dou = map.get(index);
int surplus = n - index;
while(surplus > 0){
index = index/2;
if(surplus >= index){
dou = dou*map.get(index);
}else{
continue;
}
surplus = surplus - index;
if(index == 1){
break;
}
}
} }else if(n == 0){
return 1;
}else{
if(n > -10){
for (int i =0 ;i < -n; i++){
dou = dou*(1.0/x) ;
}
}else{
map.put(-1,1.0/x);
map.put(-2,(1.0/x)*(1.0/x));
map.put(-4,(1.0/x)*(1.0/x)*(1.0/x)*(1.0/x));
map.put(-8,(1.0/x)*(1.0/x)*(1.0/x)*(1.0/x)*(1.0/x)*(1.0/x)*(1.0/x)*(1.0/x)); int index = -8;
while(index >= n/2 ){
int tmp = index;
index = index*2;
map.put(index,map.get(tmp)* map.get(tmp));
} dou = map.get(index);
int surplus = n - index;
while(surplus < 0){
index = index/2;
if(surplus <= index){
dou = dou*map.get(index);
}else{
continue;
}
surplus = surplus - index;
if(index == -1){
break;
}
}
}
}
return dou;
}
}
时间复杂度为 O(n)。
运行结果：
以上题目均来自：https://leetcode-cn.com/ ，如果你热爱编码，热爱算法，该网站一定适合你。