小紅書一共三道編程題，給了一個半小時。
嗯第一道是leetcode原題，不會做。。
第二道是leetcode變體題，漏掉了25其實包含2個5這樣的情況。
第三題依舊不會做。。
1.K個一組翻轉鏈表
題目描述
給出一個鏈表，每 k 個節(jié)點一組進行翻轉，并返回翻轉后的鏈表。
k 是一個正整數(shù)，它的值小于或等于鏈表的長度。如果節(jié)點總數(shù)不是 k
的整數(shù)倍，那么將最后剩余節(jié)點保持原有順序。
示例 :
給定這個鏈表：1->2->3->4->5
當 k = 2 時，應當返回: 2->1->4->3->5
當 k = 3 時，應當返回: 3->2->1->4->5
說明 :
你的算法只能使用常數(shù)的額外空間。
你不能只是單純的改變節(jié)點內部的值，而是需要實際的進行節(jié)點交換。
思路
其實這個題，是從尾到頭開始反轉的。
對每一個段，我們先反轉其后的段，然后將該段反轉后與反轉后段的頭節(jié)點連接。
在這里，其后段返回的頭結點作為當前段的pre初始值
head隨currentNode而走，作為mid節(jié)點。提前保存next以免斷鏈
最后，務必記得將head重新置為next的前一個節(jié)點。因為最后一個next指向的必定是下一個段未反轉前的開頭
import java.util.Scanner;
/**
* @author wuyafang
* @Title: LIstReverse
* @ProjectName ZHAO
* @Description: TODO
* @date 18/9/15下午3:07
*/
public class ListReverse {
public class ListNode{
int val;
ListNode next;
public ListNode(int val){
this.val = val;
}
}
public ListNode createList(String[] strArray){
if(strArray.length==0)return null;
ListNode head = new ListNode(Integer.valueOf(strArray[0]));
ListNode temp = head;
for(int i=1;i<strArray.length;i++){
int tempVal = Integer.valueOf(strArray[i]);
temp.next = new ListNode(tempVal);
temp = temp.next;
}
temp.next = null;
return head;
}
public ListNode reverseList(ListNode head,int k) {
ListNode currentNode = head;
int count =0;
//遍歷k個數(shù)字，找到下一個反轉段開始的節(jié)點;如果不足的話，直接返回原h(huán)ead，說明沒有被反轉
while(currentNode!=null&&count!=k){
count++;
currentNode = currentNode.next;
}
//如果滿足k個長度了
if(count==k){
//先反轉后面的鏈表，返回后面反轉完成后鏈表的頭節(jié)點
currentNode = reverseList(currentNode,k);
while(count>0){
count--;
ListNode next = head.next;
head.next = currentNode;
currentNode = head;
head = next;
}
//末尾的head連接到了下一個段開頭(段最后元素提前保存的next，指向下一個段未反轉前的開頭)。
//所以需要恢復到上一個節(jié)點，才是該段頭節(jié)點
head = currentNode;
}
return head;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line = in.nextLine();
String[] strArray = line.split(" ");
int k = in.nextInt();
ListReverse reverse = new ListReverse();
ListNode head = reverse.createList(strArray);
ListNode reverseList = reverse.reverseList(head,k);
while(reverseList!=null&&reverseList.next!=null){
System.out.print(reverseList.val + " ");
reverseList=reverseList.next;
}
System.out.print(reverseList.val);
}
}
2.求1！*2！*3！*……*n!末尾有多少連續(xù)的0
http://blog.sina.com.cn/s/blog_147841ead0102vehv.html
題目描述
求1！*2！*3！*……*n!末尾有多少連續(xù)的0
輸入n，輸出末尾0的個數(shù)
思路：
其實就是轉化成求因子中有多少個5.
1.可以找規(guī)律
其實簡單分析一下，數(shù)字相乘時，末尾每有一個0都表示有一個因數(shù)10。而10可以轉化成2*5，分解一下階乘，我們發(fā)現(xiàn)2的個數(shù)遠遠超過5，所以n!末尾有多少0的問題轉化成求因數(shù)中有多少個5
2.從單個階乘入手，先求出單個階乘因數(shù)中5的個數(shù)再相加。
比如100!中有24個5做因數(shù)，5，10，15，……，100都有5，其中25，50，75，100中都有2個5，所以一共24個5。即n中5的個數(shù)為 ： n/5+n/5/5+……+1+0
最終代碼如下
import java.util.Scanner;
/**
* @author wuyafang
* @Title: JieCheng
* @ProjectName ZHAO
* @Description: TODO
* @date 18/9/15下午4:04
*/
public class JieCheng {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int count =0;
int zeronumber = 0;
for(int i=1;i<=n;i++){
zeronumber = getFiveNumber(i);
count+=zeronumber;
}
System.out.println(count);
}
//100!里面除了5，10，……，100這個20個被5整除的數(shù)，還有25，50，75，100這四個數(shù)里還包含4個5。因數(shù)里一共24個5.
public static int getFiveNumber(int n){
int count=0;
while(n!=0){
count += n/5;
n=n/5;
}
return count;
}
}
測試用例：
輸入：11 輸出9
輸入100，輸出1124（100！中有24個5）
3.幼兒園分班問題
題目描述
題意大概是幼兒園要分成兩個班，一共有n個小朋友，小朋友提出了m個要求，即不想和誰一個班。輸入第一行為n，第二行為m，接下來是m對輸入，比如1 4 表示1不想和4同班。問是否可以成功分班。成功輸出1，不成功輸出0
輸入：
4
3
1 2
1 3
1 4
輸出：
1
輸入：
4
4
1 2
1 3
1 4
2 3
輸出：
0
思路
這個看論壇上的大佬們說 類似于圖染色算法。
也即給定m種顏色，相鄰兩點的顏色不同。
圖染色問題一般有兩種：
- 給定m種顏色，問能不能成功染色（分班問題即這樣的問題）
- 給定m種顏色，問最少用多少顏色
實際上是dfs，可以遞歸或者回溯來做。
其實這道題只要找到一種就可以返回了。不過接下來的解法會返回所有的可能。
遞歸
參考：https://blog.csdn.net/qq_28888837/article/details/53284828
//這種遞歸的方式，應該是用了貪心的思想。如果不合適，就放棄這種可能。反正會把所有可能列舉，不對的就及時終止。
public void sear(int[][] graph,int[] color,int k){
for(int i=1;i<=m;i++){
color[k]=i;
//符合條件的才繼續(xù)，否則放棄這種選擇
if(isOk(graph,color,k)){
if(k==graph.length-1){
ans++;
//找到符合條件的一個組合了
ArrayList<Integer> sol = new ArrayList<Integer>();
for(int j=0;j<color.length;j++){
sol.add(color[j]);
}
result.add(sol);
}else{
//向下遞歸
sear(graph,color,k+1);
}
}
}
}
回溯
//dfs+回溯法
public void sear1(int[][] graph,int[] color){
int i=0;
//回溯法的終止條件
while(i>=0){
color[i]++;
while(color[i]<=m){
if(isOk(graph,color,i)){
break;
}else{
color[i]++;
}
}
//已搜索到最后一個節(jié)點
if(color[i]<=m && i==color.length-1){
ans++;
//找到符合條件的一個組合了
ArrayList<Integer> sol = new ArrayList<Integer>();
for(int j=0;j<color.length;j++){
sol.add(color[j]);
}
result.add(sol);
}else if(color[i]<=m && i<color.length-1){//繼續(xù)向下搜索
i++;
}else{//不符合條件，需要回退（isOk(i)==false||i>color.length-1）
color[i]=0;
i--;
}
}
}
完整的程序為
import java.util.ArrayList;
import java.util.Scanner;
/**
* @author wuyafang
* @Title: SameClass
* @ProjectName ZHAO
* @Description: TODO
* @date 18/9/15下午3:39
*/
public class SameClass {
private static int m;
private static ArrayList<ArrayList<Integer>> result = new ArrayList<>();
private static int ans =0;
//判斷k節(jié)點是否與其相鄰節(jié)點顏色相同
private boolean isOk(int[][] graph,int[] color,int k){
for(int i=0;i<k;i++){
if(graph[k][i]==1&&color[i]==color[k]){
return false;
}
}
return true;
}
public static void main(String[] args){
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int requestNumber = in.nextInt();
int[][] graph = new int[n][n];//鄰接矩陣代表圖
int[] color = new int[n];
for(int i=0;i<requestNumber;i++){
int first = in.nextInt();
int second = in.nextInt();
graph[first-1][second-1] = 1;
graph[second-1][first-1]= 1;
}
SameClass same = new SameClass();
//設置染色數(shù)。這里班級有兩個。染色數(shù)為2
m=2;
// same.sear(graph,color,0);
same.sear1(graph,color);
if(result.isEmpty()){
System.out.println("無法滿足所有人的請求進行分班");
System.out.println(0);
}else{
System.out.println("可以分班，一共有"+ans+"種分班方式");
System.out.println(result.toString());
System.out.println(1);
}
}
}
