一、复杂链表的复制:
参考牛客网的chancy:https://www.nowcoder.com/questionTerminal/f836b2c43afc4b35ad6adc41ec941dba
1、题目:
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
2、解题思路:
3、代码实现:
public class Test12 {
public RandomListNode Clone(RandomListNode pHead){
if(pHead == null){
return null;
}
RandomListNode currentNode = pHead;
//1、遍历链表,复制每个节点,如复制节点A得到A1,将结点A1插到节点A后面;
while(currentNode!=null){
RandomListNode cloneNode = new RandomListNode(currentNode.label);
RandomListNode nextNode=currentNode.next;
currentNode.next=cloneNode;
cloneNode.next=nextNode;
currentNode=nextNode;
}
//2、重新遍历链表,复制新结点的随机指针给新结点,如A1.random=A.random.next;
currentNode=pHead;
while(currentNode!=null){
currentNode.next.random = currentNode.random == null?null:currentNode.random.next;
currentNode=currentNode.next.next;
}
//3、拆分链表,将链表拆分为为原链表和复制后的链表
currentNode=pHead;
RandomListNode pCloneHead= pHead.next;
while(currentNode!=null){
RandomListNode cloneNode=currentNode.next;
currentNode.next=cloneNode.next;
cloneNode.next=currentNode.next==null?null:currentNode.next.next;
currentNode=currentNode.next;
}
return pCloneHead;
}
}
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
二、字符串的排列:
1、题目:
输入入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
2、解题思路:
参考链接:牛客网的HAHA7877:https://www.nowcoder.com/questionTerminal/fe6b651b66ae47d7acce78ffdd9a96c7
3、代码实现:
public class Test14 {
public ArrayList<String> Permutation(String str) {
List<String> res= new ArrayList<>();
if(str!=null && str.length()>0){
PermutationHelper(str.toCharArray(),0,res);
Collections.sort(res);
}
return (ArrayList) res;
}
private void PermutationHelper(char[] charArray, int i, List<String> list) {
if(i==charArray.length-1){
String str = String.valueOf(charArray);
if(!list.contains(str)){
list.add(str);
}
}else{
for(int j=i;j<charArray.length;j++){
swap(charArray,i,j);
PermutationHelper(charArray,i+1,list);
swap(charArray,i,j);
}
}
}
private void swap(char[] charArray, int i, int j) {
char temp=charArray[i];
charArray[i]=charArray[j];
charArray[j]=temp;
}
}
三、数组中出现次数超过一半的数字
1、题目:
中有一个数字出现的次数超过数组长度的一半,请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次,超过数组长度的一半,因此输出2。如果不存在则输出0。2
2、解题思路:
由于目标数 超过数组长度的一半,对数组同时去掉两个不同的数字,到最后剩下的一个数就是该数字。在其基础上把最后剩下的数组回到原来的数组中,将数组遍历一遍统计出现次数进行最终判断。
3、代码是实现:
public class Test15 {
//方法二:
public int MoreThanHalfNum_Solution(int [] array) {
int length = array.length;
if(array==null || length==0){
return 0;
}
int result=array[0];
int times =1;
for(int i=1;i<length;i++){
if(times==0){
result = array[i];
times = 1;
}else{
if(result == array[i]){
times++;
}else{
times--;
}
}
}
times=0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}
if(times*2<=length){
return 0;
}
return result;
}
//方法一:
public int MoreThanHalfNum_Solution1(int [] array) {
int length=array.length;
if(array== null || length<=0){
return 0;
}
if(length==1){
return array[0];
}
int[] tempArray = array.clone();
for(int i=0;i<length;i++){
if(tempArray[i]==0){
continue;
}
for(int j=i+1;j<length;j++){
if(tempArray[i]!=tempArray[j] && tempArray[j]!=0){
tempArray[i]=0;//此处用0代表抹去该数字
tempArray[j]=0;
break;
}
}
}
//找出未被抹去的数字
int result = 0;
for(int i=0;i<length;i++){
if(tempArray[i]!=0){
result = tempArray[i];
break;
}
}
int times=0;
for(int i=0;i<length;i++){
if(result==array[i]){
times++;
}
}
if(times*2<=length){
return 0;
}
return result;
}
}
四、连续子数组的最大和:
1、题目:
一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢?例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组,返回它的最大连续子序列的和,你会不会被他忽悠住?(子向量的长度至少是1)
2、代码实现:
public class Test17 {
//方法一:
public int FindGreatestSumOfSubArray(int[] array) {
if(array.length==0 || array==null){
return 0;
}
int curSum=0;
int manSun=0x80000000;//最小的负数-0
for(int i=0;i<array.length;i++){
if(curSum<=0){
curSum=array[i];//记录当前最大值
}else{
curSum+=array[i];
}
if(curSum>manSun){
manSun=curSum;
}
}
return manSun;
}
//方法二:
public int FindGreatestSumOfSubArray2(int[] array) {
int res=array[0];//记录当前所有子数组的和的最大值
int max=array[0];//包含array[i]的连续数组最大值
for(int i=1;i<array.length;i++){
max=Math.max(max+array[i],array[i]);
res=Math.max(res, max);
}
return res;
}
}
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/114694.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...