1. 删第k个链表节点。一开始傻乎乎的按照要求写，发现超时。
import java.util.Scanner;
public class Main {
private static Node deleteNode(Node head, int k) {
Node dum = new Node(0);
dum.next = head;
Node runner = dum;
for (int i = 0; i < k-1; i++) {
runner = runner.next;
}
Node nxt = runner.next.next; // runner.next should be deleted
runner.next = nxt;
return dum.next;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
Node dum = new Node(0);
Node tail = dum;
System.out.println("before running");
for(int i = 0; i < n; i++){
Node cur = new Node(sc.nextInt());
tail.next = cur;
tail = cur;
}
Node h = deleteNode(dum.next, k);
Node runner = dum.next;
while (runner != null) {
System.out.print(runner.val + " ");
runner = runner.next;
}
}
}
class Node {
int val;
Node next;
public Node (int v){
val = v;
}
} 优化成直接输出，还是超时，只能通过75%。浪费了30-40分钟（哭了）。请高人赐教，这题怎么写才能过？
```java
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
for(int i = 0; i < k-1; i++){
int val = sc.nextInt();
System.out.print(val + " ");
}
sc.nextInt();
for(int i = k; i < n; i++){
int val = sc.nextInt();
System.out.print(val + " ");
}
}
}
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int k = sc.nextInt();
for(int i = 0; i < k-1; i++){
int val = sc.nextInt();
System.out.print(val + " ");
}
sc.nextInt();
for(int i = k; i < n; i++){
int val = sc.nextInt();
System.out.print(val + " ");
}
}
}
```
2. 给定字符串str，找第k小distinct子串（排序为字典序升序）。
通过测试用例为0。不知道为啥，请高人赐教。
import java.util.*;
public class Main {
static HashSet<String> all = new HashSet();
private static void construct(String str, int start, int len, StringBuilder sb) {
if (sb.length() == len) {
all.add(sb.toString());
return;
}
int buf_len = sb.length();
for (int i = start; i < str.length(); i++) {
sb.append(str.charAt(i));
construct(str, i+1, len, sb);
sb.setLength(buf_len);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int k = sc.nextInt();
int n = str.length();
for (int len = 1; len <= n; len++)
construct(str, 0, len, new StringBuilder());
List<String> res = new ArrayList();
for (String s: all)
res.add(s);
Collections.sort(res);
System.out.println(res.get(k-1));
}
} 3. 给定一个正数，拆成两个非负的数，位数和（每一个数字相加）最大。通过测试用例100%。
import java.util.*;
public class Main {
static HashMap<Long, Long> mem = new HashMap();
private static long getVal(long n){
if (mem.containsKey(n))
return mem.get(n);
long res = 0;
while (n > 0) {
res += n % 10;
n /= 10;
}
mem.put(n, res);
return res;
}
private static long solve(long n) {
if (n <= 18) return n;
long num1 = 9;
long best = 0;
while (n - num1 > 0) {
best = Math.max(best, getVal(num1) + getVal(n - num1));
num1 = num1*10+9;
}
return best;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for (int t = 0; t < T; t++) {
long n = sc.nextLong();
System.out.println(solve(n));
}
}
} 4. 木板长度高度均为1，黑板可以横着擦，竖着擦。黑板高度由数组表示（输入第二行）。如果木板在擦黑板中间断了，需要重新开始擦。求最小的擦的次数。这题我不会做，当时放弃了。
样例如下
```
//5
//2 2 1 2 1
//5
//2 2 1 2 1
```
需要返回3。
需要返回3。
经过参考@〢ヽ夜╰︶￣太美 的代码，考虑如下dp解法。并不保证正确。
public class Main {
public static int paint(int[] arr) {
int n = arr.length;
int highest = 0;
for (int h: arr)
highest = Math.max(highest, h);
// dp[i][j]: the min cost to paint first i blackboards already, height can achieve j
int[][] dp = new int[n+1][highest+1];
for (int j = 1; j <= highest; j++)
dp[0][j] = j;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= highest; j++)
dp[i][j] = n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= highest; j++) {
// paint vertically
int h = Math.min(j, arr[i-1]);
dp[i][h] = Math.min(dp[i][h], dp[i-1][j] + 1);
// paint horizontally
if (arr[i-1] < n) {
int cur = arr[i-1];
if (j >= arr[i-1])
dp[i][cur] = Math.min(dp[i][cur], dp[i-1][j]);
else
dp[i][cur] = Math.min(dp[i][cur], dp[i-1][j] + cur -j);
}
}
}
int res = n;
for (int j = arr[n-1]; j <= highest; j++)
res = Math.min(res, dp[n][j]);
return res;
}
public static void main(String[] args) {
int[] arr = new int[]{2,2,1,2,1};
System.out.println(paint(arr));
}
}
5. 给定字符串str，给定范围[l, r]，求子串能拆成最少的回文串的个数。通过测试案例70-90%。不知道还可以怎么优化了，请高人赐教。
import java.util.*;
public class Main {
static HashMap<String, Integer> mem = new HashMap();
private static int splitPa(String key) {
if (mem.containsKey(key))
return mem.get(key);
int n = key.length();
int best = n;
for (int i = 0; i < n; i++) {
String right = key.substring(i);
if (isPa(right)) {
String left = key.substring(0, i);
best = Math.min(best, 1 + splitPa(left));
}
}
mem.put(key, best);
return best;
}
private static boolean isPa(String str) {
int l = 0;
int r = str.length() - 1;
while (l < r) {
if (str.charAt(l) != str.charAt(r))
return false;
l++;
r--;
}
return true;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();
int Q = sc.nextInt();
mem.put("", 0);
for (int q = 0; q < Q; q++) {
int l = sc.nextInt();
int r = sc.nextInt();
System.out.println(splitPa(str.substring(l-1, r)));
}
}
} 
全部评论
(3) 回帖