编程合集： https://www.cnblogs.com/jssj/p/12002760.html
前言：不仅仅要实现，更要提升性能，精益求精，用尽量少的时间复杂度和空间复杂度解决问题。
【程序78】
实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
必须原地修改，只允许使用额外常数空间。
以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1
/**
* 实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。
* 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
* 必须原地修改，只允许使用额外常数空间。
* 以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
* 1,2,3 → 1,3,2
* 3,2,1 → 1,2,3
* 1,1,5 → 1,5,1
*/
public class Subject78 { public static void main(String[] args) {
int[] arr = new int[]{2,3,1,3,3};
new Subject78().nextPermutation(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]+" ");
}
} /**
* 下一个最大值
* @param nums
*/
public void nextPermutation(int[] nums) {
int lengths = nums.length;
int size = -1;
for (int i = lengths-1; i >= 0; i--) {
if(i-1 >= 0 && nums[i-1] < nums[i]){
size = i-1;
break;
}
}
//如果没有最大的值了
if(size == -1){
for (int i = 0 ,j= lengths-1; i <= j ; i++,j--) {
int tmp = 0;
tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
}else{ //处理size后边的数据，重新整理成一个最小数组。
//找到比size位置大的数中的最小数。
int tmp = nums[size+1];
int sizeExchange = size+1;
for (int i = size+1; i < lengths ; i++) {
//这里可以优化
if(nums[i] <= tmp && nums[i] > nums[size]){
tmp = nums[i];
sizeExchange = i;
}
}
nums[sizeExchange] = nums[size];
nums[size] = tmp;
//剩余数据重新重小到大排序
for (int i = size+1 ,j= lengths-1; i <= j ; i++,j--) {
int tmp0 = 0;
tmp0 = nums[i];
nums[i] = nums[j];
nums[j] = tmp0;
}
}
}
}
时间复杂度：O(n)
运行结果：
【程序79】
给定一个只包含 ‘(‘ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
import java.util.ArrayList;
import java.util.List;/**
* 给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
*/
public class Subject79 { public static void main(String[] args) { System.out.println(new Subject79().longestValidParentheses("(()()()(()))))))"));
} public int longestValidParentheses(String s) {
int lengths = s.length();
if(lengths <= 0){
return 0;
}
char[] arr = s.toCharArray(); List<Integer> list = new ArrayList<>(); /**
* 将不可以匹配的括号留下，并且记录位置。
*/
for (int i = 0; i < arr.length; i++) {
if('(' == arr[i]){
list.add(i);
}else{
int size = list.size();
if(')' == arr[i] && list.size() > 0 && '(' == arr[list.get(size-1)]){
list.remove(size-1);
}else{
list.add(i);
}
}
} //获取最大间隔时间
int maxLength = 0;
for (int i = 0; i < list.size() ; i++) {
if( i == 0 ){
maxLength = list.get(i);
}else {
int tmp = list.get(i) - list.get(i-1) -1;
if(tmp > maxLength){
maxLength = tmp;
}
}
} if(list.size() > 0){
int endLength = lengths - list.get(list.size()-1) -1;
if(endLength > maxLength){
maxLength = endLength;
}
} else {
maxLength = lengths;
} return maxLength;
}
}
时间复杂度：O(n)
运行结果：
【程序80】
假设按照升序排序的数组在预先未知的某个点上进行了旋转。
( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-1。
你可以假设数组中不存在重复的元素。
你的算法时间复杂度必须是O(logn) 级别。
示例 1:
输入: nums = [4,5,6,7,0,1,2], target = 0
输出: 4
示例2:
输入: nums = [4,5,6,7,0,1,2], target = 3
输出: -1
/**
* 假设按照升序排序的数组在预先未知的某个点上进行了旋转。
* ( 例如，数组[0,1,2,4,5,6,7]可能变为[4,5,6,7,0,1,2])。
* 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回-1。
* 你可以假设数组中不存在重复的元素。
* 你的算法时间复杂度必须是O(logn) 级别。
*
* 示例 1:
* 输入: nums = [4,5,6,7,0,1,2], target = 0
* 输出: 4
*
* 示例2:
* 输入: nums = [4,5,6,7,0,1,2], target = 3
* 输出: -1
*/
public class Subject80 { int [] nums;
int target; public static void main(String[] args) {
int[] nums = new int[]{1};
System.out.println(new Subject80().search(nums,0));
} public int search(int[] nums, int target) {
this.nums = nums;
this.target = target; int n = nums.length; if (n == 0)
return -1;
if (n == 1)
return this.nums[0] == target ? 0 : -1; /**
* 找到旋转节点
*/
int rotate_index = find_rotate_index(0, n - 1); // if target is the smallest element
if (nums[rotate_index] == target)
return rotate_index;
// if array is not rotated, search in the entire array
if (rotate_index == 0)
return search(0, n - 1);
if (target < nums[0])
// search in the right side
return search(rotate_index, n - 1);
// search in the left side
return search(0, rotate_index);
} /**
* 找旋转节点
* @param left
* @param right
* @return
*/
public int find_rotate_index(int left, int right) {
if (nums[left] < nums[right])
return 0; while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] > nums[pivot + 1])
return pivot + 1;
else {
if (nums[pivot] < nums[left])
right = pivot - 1;
else
left = pivot + 1;
}
}
return 0;
} /**
* Binary search 二分查找法
* @param left
* @param right
* @return
*/
public int search(int left, int right) {
while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] == target)
return pivot;
else {
if (target < nums[pivot])
right = pivot - 1;
else
left = pivot + 1;
}
}
return -1;
}
}
时间复杂度：O(logN)
运行结果：
【程序81】
给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
你的算法时间复杂度必须是O(log n) 级别。
如果数组中不存在目标值，返回[-1, -1]。
/**
* 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
* 你的算法时间复杂度必须是O(log n) 级别。
* 如果数组中不存在目标值，返回[-1, -1]。
*/
public class Subject81 {
public static void main(String[] args) {
int[] arr = new int[]{1};
int[] result = new Subject81().searchRange(arr,1);
for (int i = 0; i < result.length; i++) {
System.out.print(result[i]+" ");
}
} /**
* 二分查找法
* @param nums
* @param target
* @return
*/
public int[] searchRange(int[] nums, int target) {
int left = 0;
int right = nums.length-1;
int pivot = -1;
boolean flag = false;
while (left <= right) {
pivot = (left + right) / 2;
if (nums[pivot] == target) {
flag = true;
break;
} else {
if (target < nums[pivot])
right = pivot - 1;
else
left = pivot + 1;
}
}
if(!flag){
pivot = -1;
}
if(pivot != -1){
int leftTmp = pivot;
int rightTmp = pivot;
while(leftTmp >= 0){
leftTmp = leftTmp-1;
if(leftTmp < 0 || nums[leftTmp] != target){
break;
}
}
while(rightTmp <= nums.length-1){
rightTmp = rightTmp+1;
if(rightTmp > nums.length-1 ||nums[rightTmp] != target){
break;
}
}
return new int[]{leftTmp+1,rightTmp-1};
}else{
return new int[]{-1,-1};
}
}
}
时间复杂度：O(log2n)
运行结果：
【程序82】
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
/**
* 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
*/
public class Subject82 { public static void main(String[] args) {
int[] arr = new int[]{1,3,4,5,6,7,9,10};
System.out.println(new Subject82().searchInsert(arr,8));
} public int searchInsert(int[] nums, int target) {
if(nums.length < 0){
return 0;
}
int size = this.search(0,nums.length-1,nums,target);
if(nums[size] == target){
return size;
}else{
if(nums[size] > target){
return size;
}else{
return size+1;
}
}
} /**
* Binary search 二分查找法
* @param left
* @param right
* @return
*/
public int search(int left, int right,int[] nums, int target) {
while (left <= right) {
int pivot = (left + right) / 2;
if (nums[pivot] == target)
return pivot;
else {
if (target < nums[pivot])
right = pivot - 1;
else
left = pivot + 1;
}
}
if(right <= -1){
return left;
}
if(left >= nums.length){
return right;
}
return left <= right? left :right;
}
}
时间复杂度：O(logn)
运行结果：
【程序83】
判断一个9×9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
数字1-9在每一行只能出现一次。
数字1-9在每一列只能出现一次。
数字1-9在每一个以粗实线分隔的3×3宫内只能出现一次。
/**
* 判断一个9x9 的数独是否有效。只需要根据以下规则，验证已经填入的数字是否有效即可。
* 数字1-9在每一行只能出现一次。
* 数字1-9在每一列只能出现一次。
* 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
*/
public class Subject83 {
public static void main(String[] args) {
char[][] board = new char[][]{
{'.','.','.','.','5','.','.','1','.'},
{'.','4','.','3','.','.','.','.','.'},
{'.','.','.','.','.','3','.','.','1'},
{'8','.','.','.','.','.','.','2','.'},
{'.','.','2','.','7','.','.','.','.'},
{'.','1','5','.','.','.','.','.','.'},
{'.','.','.','.','.','2','.','.','.'},
{'.','2','.','9','.','.','.','.','.'},
{'.','.','4','.','.','.','.','.','.'}};
System.out.println( new Subject83().isValidSudoku(board));
} public boolean isValidSudoku(char[][] board) {
int[] rowCnt = new int[9];
int[] colCnt = new int[9];
int[] boxCnt = new int[9];
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if ('.' == board[i][j]) {
continue;
}
//处理成int型
int num = board[i][j] - 48;
// 处理行
if ((rowCnt[i] >> num) % 2 == 1) {
return false;
} else {
rowCnt[i] += 1 << num;
}
// 处理列
if ((colCnt[j] >> num) % 2 == 1) {
return false;
} else {
colCnt[j] += 1 << num;
}
// 处理框
int boxNum = i / 3 * 3 + j / 3;
if ((boxCnt[boxNum] >> num) % 2 == 1) {
return false;
} else {
boxCnt[boxNum] = boxCnt[boxNum] + (1 << num);
}
}
}
return true;
}
}
时间复杂度：O(1)
运行结果：
【程序84】
编写一个程序，通过已填充的空格来解决数独问题。
一个数独的解法需遵循如下规则：
数字1-9在每一行只能出现一次。
数字1-9在每一列只能出现一次。
数字1-9在每一个以粗实线分隔的3×3宫内只能出现一次。
空白格用’.’表示。
/**
* 编写一个程序，通过已填充的空格来解决数独问题。
* 一个数独的解法需遵循如下规则：
* 数字1-9在每一行只能出现一次。
* 数字1-9在每一列只能出现一次。
* 数字1-9在每一个以粗实线分隔的3x3宫内只能出现一次。
* 空白格用'.'表示。
*/
public class Subject84 {
public static void main(String[] args) {
char[][] board = new char[][]{
{'.','.','9','7','4','8','.','.','.'},
{'7','.','.','.','.','.','.','.','.'},
{'.','2','.','1','.','9','.','.','.'},
{'.','.','7','.','.','.','2','4','.'},
{'.','6','4','.','1','.','5','9','.'},
{'.','9','8','.','.','.','3','.','.'},
{'.','.','.','8','.','3','.','2','.'},
{'.','.','.','.','.','.','.','.','6'},
{'.','.','.','2','7','5','9','.','.'}};
new Subject84().solveSudoku(board);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j]+" ");
}
System.out.println();
}
} // box size
int n = 3;
// row size
int N = n * n; int [][] rows = new int[N][N + 1];
int [][] columns = new int[N][N + 1];
int [][] boxes = new int[N][N + 1]; char[][] board; boolean sudokuSolved = false; public boolean couldPlace(int d, int row, int col) {
/*
检查是否可以在（行，列）单元格中放置数字d
*/
int idx = (row / n ) * n + col / n;
return rows[row][d] + columns[col][d] + boxes[idx][d] == 0;
} public void placeNumber(int d, int row, int col) {
/*
在（行，列）单元格中放置数字d
*/
int idx = (row / n ) * n + col / n; rows[row][d]++;
columns[col][d]++;
boxes[idx][d]++;
board[row][col] = (char)(d + '0');
} public void removeNumber(int d, int row, int col) {
/*
删除一个无法找到解决方案的数字
*/
int idx = (row / n ) * n + col / n;
rows[row][d]--;
columns[col][d]--;
boxes[idx][d]--;
board[row][col] = '.';
} public void placeNextNumbers(int row, int col) {
/*
递归调用回溯函数
继续放置数字
直到我们找到解决办法
*/
// 如果我们在最后一个牢房里
// 这意味着我们有办法
if ((col == N - 1) && (row == N - 1)) {
sudokuSolved = true;
}
// 如果还没有
else {
// 如果我们排在最后
// 到下一排
if (col == N - 1) backtrack(row + 1, 0);
// go to the next column
else backtrack(row, col + 1);
}
} public void backtrack(int row, int col) {
/*
回溯
*/
// 如果单元格是空的
if (board[row][col] == '.') {
// 对从1到9的所有数字进行迭代
for (int d = 1; d < 10; d++) {
if (couldPlace(d, row, col)) {
placeNumber(d, row, col);
placeNextNumbers(row, col);
// 如果数独问题解决了，就不必回头了。
// 因为独联解决方案是有希望的
if (!sudokuSolved) removeNumber(d, row, col);
}
}
}
else placeNextNumbers(row, col);
} public void solveSudoku(char[][] board) {
this.board = board; // 初始化行、列和框
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
char num = board[i][j];
if (num != '.') {
int d = Character.getNumericValue(num);
placeNumber(d, i, j);
}
}
}
backtrack(0, 0);
}
}
时间复杂度：O(9！^9)
运行结果：
【程序85】
报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
1. 1
2. 11
3. 21
4. 1211
5. 111221
1被读作”one 1″(“一个一”) , 即11。
11 被读作”two 1s”(“两个一”）, 即21。
21 被读作”one 2″, “one 1″（”一个二”,”一个一”), 即1211。
给定一个正整数 n（1 ≤n≤ 30），输出报数序列的第 n 项。
/**
* 报数序列是一个整数序列，按照其中的整数的顺序进行报数，得到下一个数。其前五项如下：
* 1. 1
* 2. 11
* 3. 21
* 4. 1211
* 5. 111221
* 1被读作"one 1"("一个一") , 即11。
* 11 被读作"two 1s"("两个一"）, 即21。
* 21 被读作"one 2", "one 1"（"一个二","一个一"), 即1211。
* 给定一个正整数 n（1 ≤n≤ 30），输出报数序列的第 n 项。
*/
public class Subject85 { public static void main(String[] args) {
System.out.println(new Subject85().countAndSay(6));
} public String countAndSay(int n) {
if(n == 1){
return "1";
}else{
String str = countAndSay(n-1);
char[] chArr = str.toCharArray();
StringBuilder strTmp = new StringBuilder("");
char ch = chArr[0] ;
int count = 0;
for (int i = 0; i < chArr.length; i++) {
if(ch == chArr[i]){
count++;
}else{
strTmp.append(count).append(ch);
ch = chArr[i];
count = 1;
}
}
strTmp.append(count).append(ch);
return strTmp.toString();
}
}
}
时间复杂度：O(n)
运行结果：
【程序86】
给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的数字可以无限制重复被选取。
说明：
所有数字（包括target）都是正整数。
解集不能包含重复的组合。
import java.util.*;/**
* 给定一个无重复元素的数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
* candidates中的数字可以无限制重复被选取。
* 说明：
* 所有数字（包括target）都是正整数。
* 解集不能包含重复的组合。
*/
public class Subject86 { private List<List<Integer>> res = new ArrayList<>();
private int[] candidates;
private int len; public static void main(String[] args) {
int[] candidates = new int[]{2,3,6,7};
List<List<Integer>> list = new Subject86().combinationSum(candidates,7);
System.out.println(list);
} private void findCombinationSum(int residue, int start, Stack<Integer> pre) {
if (residue == 0) {
// Java 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
res.add(new ArrayList<>(pre));
return;
}
// 优化添加的代码2：在循环的时候做判断，尽量避免系统栈的深度
// residue - candidates[i] 表示下一轮的剩余，如果下一轮的剩余都小于 0 ，就没有必要进行后面的循环了
// 这一点基于原始数组是排序数组的前提，因为如果计算后面的剩余，只会越来越小
for (int i = start; i < len && residue - candidates[i] >= 0; i++) {
pre.add(candidates[i]);
// 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
findCombinationSum(residue - candidates[i], i, pre);
pre.pop();
}
} public List<List<Integer>> combinationSum(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
// 优化添加的代码1：先对数组排序，可以提前终止判断
Arrays.sort(candidates);
this.len = len;
this.candidates = candidates;
findCombinationSum(target, 0, new Stack<>());
return res;
}
}
时间复杂度：O(2^n)
运行结果：
【程序87】
给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
candidates中的每个数字在每个组合中只能使用一次。
说明：
所有数字（包括目标数）都是正整数。
解集不能包含重复的组合。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;/**
* 给定一个数组candidates和一个目标数target，找出candidates中所有可以使数字和为target的组合。
* candidates中的每个数字在每个组合中只能使用一次。
* 说明：
* 所有数字（包括目标数）都是正整数。
* 解集不能包含重复的组合。
*/
public class Subject87 { private List<List<Integer>> res = new ArrayList<>(); public static void main(String[] args) {
int[] candidates = new int[]{10,1,2,7,6,1,5};
List<List<Integer>> list = new Subject87().combinationSum2(candidates,7);
System.out.println(list);
} public List<List<Integer>> combinationSum2(int[] candidates, int target) {
int len = candidates.length;
if (len == 0) {
return res;
}
// 优化添加的代码1：先对数组排序，可以提前终止判断
Arrays.sort(candidates);
findCombinationSum(target, 0, new Stack<>(),candidates);
return res;
} private void findCombinationSum(int residue, int start, Stack<Integer> pre, int[] candidates) {
if (residue == 0) {
// Java 中可变对象是引用传递，因此需要将当前 path 里的值拷贝出来
List list= new ArrayList<>(pre);
res.add(list);
return;
}
// 优化添加的代码2：在循环的时候做判断，尽量避免系统栈的深度
// residue - candidates[i] 表示下一轮的剩余，如果下一轮的剩余都小于 0 ，就没有必要进行后面的循环了
// 这一点基于原始数组是排序数组的前提，因为如果计算后面的剩余，只会越来越小
for (int i = start; i < candidates.length && residue - candidates[i] >= 0; i++) {
if( i-1 >= 0 && candidates[i] == candidates[i-1]){
continue;
}
pre.add(candidates[i]);
// 【关键】因为元素可以重复使用，这里递归传递下去的是 i 而不是 i + 1
findCombinationSum(residue - candidates[i], i, pre,this.copyArr2(candidates,i));
pre.pop();
}
} public int[] copyArr2(int[] candidatesTmp,int index){
int[] candidates = new int[candidatesTmp.length-1];
for (int i = 0,j = 0; i < candidatesTmp.length; i++) {
if(index == i){
continue;
}else{
candidates[j++] = candidatesTmp[i];
}
}
return candidates;
}
}
时间复杂度：O(n!)
运行结果：
以上题目均来自：https://leetcode-cn.com/ ，如果你热爱编码，热爱算法，该网站一定适合你。
