一、字符串的所有可能排列
牛客链接
描述：
输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串 abc,acb,bac,bca,cab 和 cba 。
import java.util.ArrayList;
import java.util.*;
public class Solution {
//交换字符
public void Swap(char[] str,int i,int j){
char tmp = str[i];
str[i] = str[j];
str[j] = tmp;
}
//判断res中是否存在该字符串
public boolean isExist(ArrayList<String> res,char[] str){
//String.valueOf(str)将字符数组转换为字符串
return res.contains(String.valueOf(str));
}
public void PermutationHelp(char[] str,int start,ArrayList<String> res){
if(start == str.length - 1){
//去重
if(!isExist(res,str)){
res.add(new String(str));
}
return;
}
for(int i = start;i < str.length;i++){
//start 和 i 的关系是：表示以谁开始
//第一次就是a和a进行交换（a为开始元素），第二次就是a和b进行交换（b就成为了开始元素）
Swap(str,start,i);
//当确定以哪个字符作为开始，就要在决定另一部分的排列组合种类
//i仅仅是决定以谁作为排列的开始，但是求sub字符串每次开始，都要从start+1开始
//例如以a作为开始元素，这里就需要将bc进行排序
//例如以b作为开始，这里就需要将ac进行排序
PermutationHelp(str,start + 1,res);
//再次交换为最初位置（abc）
Swap(str,start,i);
}
}
public ArrayList<String> Permutation(String str) {
ArrayList<String> res = new ArrayList<>();
if(str != null || str.length() > 0){
//将字符串转换为字符数组
PermutationHelp(str.toCharArray(),0,res);
//按照字典序进行打印
Collections.sort(res);
}
return res;
}
}
二、TopK问题，输出最小的k个数
牛客链接
描述：
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
import java.util.ArrayList;
import java.util.*;
import java.util.Collections;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> list = new ArrayList<>();
if(input == null || k <= 0 || k > input.length){
return list;
}
PriorityQueue<Integer> queue = new PriorityQueue<>(k,Collections.reverseOrder());
for(int i = 0; i< input.length;i++){
if(i < k){
queue.offer(input[i]);
}else if(input[i] < queue.peek()){
queue.poll();
queue.offer(input[i]);
}
}
for(int i = 0;i < k;i++){
list.add(queue.poll());
}
return list;
}
}
三、连续子数组的最大和
牛客链接
描述:
输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。
方法一：可以使用（动规）dp完成
定义状态 f(i): 以i下标结尾的最大连续子序列的和；
状态递推：f(i) = max(f(i-1)+array[i], array[i]) ；【这里一定要注意连续关键字】
状态初始化：f(0) = array[0], max = array[0]；
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
// if(array == null || array.length < 0){
// return -1;
// }
int[] dp = new int[array.length];
dp[0] = array[0];
int max = array[0];
for(int i = 1;i < array.length;i++){
dp[i] = Math.max(dp[i - 1] + array[i],array[i]);
if(max < dp[i]){
max = dp[i];
}
}
return max;
}
}
方法二：对上面动规方法进行的改进
public class Solution {
public int FindGreatestSumOfSubArray(int[] array) {
int total= array[0];
int max = array[0];
//用来检测以i下标结尾的连续子序列的和
for(int i = 1;i < array.length;i++){
if(total > 0){
//如果之前total累计的和>=0,说明当前数据+total，有利于整体增大
total += array[i];
}else{
///如果之前累计的和<0,说明当前数据+total，不利于整体增大,丢弃之前的所有值
//这里有一个基本事实，就是之前的连续数据和是确定的。
//连续，是可以从以前到现在，也可以是从现在到以后。至于要不要加以前，就看以前对整体增大又没有贡献度
total = array[i];
}
if(max < total){
max = total;
}
}
return max;
}
}
四、回文数索引
牛客链接
描述：
给定一个仅由小写字母组成的字符串。现在请找出一个位置，删掉那个字母之后，字符串变成回文。请放心总会有一个合法的解。如果给定的字符串已经是一个回文串，那么输出-1。
输入描述：
第一行包含T，测试数据的组数。后面跟有T行，每行包含一个字符串。
输出描述：
如果可以删去一个字母使它变成回文串，则输出任意一个满足条件的删去字母的位置（下标从0开始）。例如：bcc，我们可以删掉位置0的b字符。
解题思路：
可以从两侧进行统计，如果不同，则删除任意一个，再判定是否是回文，如果是，下标就是删除数据的下标，如果不是，就是另一个元素的下标。
import java.util.Scanner;
public class Main{
public static boolean IsPalindrome(StringBuffer sb,int[] start,int[] end){
int i = 0;
int j = sb.length() - 1;
boolean flg = true;
while(i <= j){
if(sb.charAt(i) != sb.charAt(j)){
flg = false;
break;
}
i++;
j--;
}
if(start != null) start[0] = i;
if(end != null) end[0] = j;
return flg;
}
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
while(num > 0){
StringBuffer sb = new StringBuffer(scanner.next());
//定义前后两个数组存放字符不一样位置的下标
int[] start = new int[1];
int[] end = new int[1];
//如果是回文索引，则输出-1
if(IsPalindrome(sb,start,end)){
System.out.println(-1);
}else{
//如果不是回文索引，则删除后面位置的一个字符，
//再次进行判断
sb.deleteCharAt(end[0]);
if(IsPalindrome(sb,null,null)){
//如果是回文字符串，则返回该位置字符的下标
System.out.println(end[0]);
}else{
//如果上面判断不是回文串，则就是删除前面字符下标得到回文字符串
//因为总有一个合法的解，不是删除前面的，就是删除后面的
System.out.println(start[0]);
}
}
num--;
}
}
}
五、把数组排成最小的数
牛客链接
描述：
输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大，所以你需要返回一个字符串而不是整数；
2.拼接起来的数字可能会有前导0，最后结果不需要去掉前导0；
对于本题，我们要的有效序列是：序列中任何一个元素y，和它前面的任何一个元素x进行有序组合形成xy，比和它后面的任何一个元素z进行有效序列组合yz，满足条件xy < yz（采用字典序列排序）。
import java.util.ArrayList;
import java.util.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers == null){
return new String();
}
ArrayList<Integer> list = new ArrayList<>();
//遍历数组中的每一个数字将其加入到list集合中
for(int number : numbers){
list.add(number);
}
//将集合里面的元素进行排序并进行字符拼接比较大小
Collections.sort(list,new Comparator<Integer>(){
public int compare(Integer x,Integer y){
String A = x + "" + y;
String B = y + "" + x;
//比较AB的大小
return A.compareTo(B);
}
});
String res = new String();
for(Integer r : list){
res += r;
}
return res;
}
}
六、两链表的第一个公共节点
牛客链接
描述：
输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）
解题思路：先分别求出两个链表的长度，然后让较长链表先走两个链表的差值步，再让两个链表一起走，直到遇到他们的第一个公共节点。
/*
public class ListNode {
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode headA = pHead1;
ListNode headB = pHead2;
int len1 = 0;
int len2 = 0;
while(headA != null){
len1++;
headA = headA.next;
}
headA = pHead1;
while(headB != null){
len2++;
headB = headB.next;
}
headB = pHead2;
int len = Math.abs(len1 - len2);
if(len1 > len2){
while(len > 0){
headA = headA.next;
len--;
}
}
else{
while(len > 0){
headB = headB.next;
len--;
}
}
while(headA != null && headB != null){
if(headB == headA){
return headA;
}
headA = headA.next;
headB = headB.next;
}
return null;
}
}
以上。