刷题笔记 ACM形式

• 1. 将16进制的数转为10进制的数
• 2 回溯法模板 (leetcode 79 单词搜索)
• 3. NC2 重排链表
• 4.输入两个字符串，从第一字符串中删除第二个字符串中所有的字符

1. 将16进制的数转为10进制的数

import java.util.*; public class Main {private final static int BASE = 16;private static Map<Character, Integer> map = new HashMap<Character, Integer>(){{put('0', 0);put('1', 1);put('2', 2);put('3', 3);put('4', 4);put('5', 5);put('6', 6);put('7', 7);put('8', 8);put('9', 9);put('A', 10);put('B', 11);put('C', 12);put('D', 13);put('E', 14);put('F', 15);put('a', 10);put('b', 11);put('c', 12);put('d', 13);put('e', 14);put('f', 15);}};public static int getDecimal(String number) {int res = 0;for (char ch : number.toCharArray()) {res = res * BASE + map.get(ch);}return res;}public static void main(String[] args) {Scanner in = new Scanner(System.in);while (in.hasNext()) {String number = in.next();int res = getDecimal(number.substring(2)); // 截取第二位到最后一位System.out.println(res);}} }

2 回溯法模板 (leetcode 79 单词搜索)

自己写的只能通过大部分案例 如下：

class Solution {static boolean flag = false;public boolean exist(char[][] board, String word) {int m = board.length;int n = board[0].length;boolean[][] visit = new boolean[m][n];for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){visit[i][j] = false;}}for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(board[i][j] == word.charAt(0))backtracking(board,word,visit,i,j,0);}}return flag;}public void backtracking(char[][] board, String s, boolean[][] visit, int i, int j,int index){if(i<0 || i>=board.length || j<0 || j>=board[0].length || visit[i][j] == true)return;if(index < s.length()){if(s.charAt(index) != board[i][j])return;}elsereturn;if(index == s.length()-1)flag = true;visit[i][j] = true;if(s.charAt(index) == board[i][j]){backtracking(board,s,visit,i-1,j,index+1);backtracking(board,s,visit,i+1,j,index+1);backtracking(board,s,visit,i,j-1,index+1);backtracking(board,s,visit,i,j+1,index+1); }visit[i][j] = false; } }

正确做法如下

class Solution {boolean find = false;public boolean exist(char[][] board, String word) {int m = board.length;int n = board[0].length;boolean[][] visited = new boolean[m][n];for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {backtracking(i, j, board, word, visited, 0);if(find) {break;}}}return find;}public void backtracking(int i, int j, char[][] board, String word, boolean[][] visited, int pos) {if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) {return;}if (board[i][j] != word.charAt(pos) || visited[i][j] || find) {return;}if (pos == word.length() - 1) {find = true;return;}visited[i][j] = true;backtracking(i + 1, j, board, word, visited, pos + 1);backtracking(i - 1, j, board, word, visited, pos + 1);backtracking(i, j + 1, board, word, visited, pos + 1);backtracking(i, j - 1, board, word, visited, pos + 1);visited[i][j] = false;} }

3. NC2 重排链表

public class Solution {public void reorderList(ListNode head) {if(head == null || head.next == null)return;// 快满指针找到中间节点ListNode fast = head;ListNode slow = head;while(fast.next != null && fast.next.next != null){fast = fast.next.next;slow = slow.next;}// 拆分链表，并反转中间节点之后的链表ListNode after = slow.next;slow.next = null;ListNode pre = null;while(after != null){ListNode temp = after.next;after.next = pre;pre = after;after = temp;}// 合并两个链表ListNode first = head;after = pre;while(first != null && after != null){ListNode ftemp = first.next;ListNode aftemp = after.next;first.next = after;first = ftemp;after.next = first; after = aftemp; }} }

4.输入两个字符串，从第一字符串中删除第二个字符串中所有的字符

例如，输入”They are students.”和”aeiou”，则删除之后的字符串变成”Thy r stdnts.
思路：首先要将第一个字符串中的每个字符截取出来，截取成单个字符，然后用contains方法进去比较，如果第二个字符串中包含有第一个字符串中的字符，就舍弃掉，如果不包含则保留使用StringBuffer的append方法进行拼接；实现如下

import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner scanner=new Scanner(System.in);String s1=scanner.nextLine();String s2=scanner.nextLine();String[] arr1=s1.split("");StringBuffer sb=new StringBuffer();for (int i=0;i<arr1.length;i++){if (!s2.contains(arr1[i])){sb.append(arr1[i]);}}System.out.println(sb.toString());} }

总结

以上是生活随笔为你收集整理的牛客网刷题（Hw题库)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。