Ip的组成有几种
import java.util.ArrayList;
public class IpAddress {
public static void main(String[] args) {
String s = "25525511135";
System.out.println(restoreIpAddresses(s));
}
public static ArrayList<String> restoreIpAddresses(String s) {
ArrayList<String> res = new ArrayList<String>();
if (s.length() < 4) return res;
for (int i = 1; i < 4 && i < s.length() - 2; i++) {
for (int j = i + 1; j < i + 4 && j < s.length() - 1; j++) {
for (int k = j + 1; k < j + 4 && k < s.length(); k++) {
String s1 = s.substring(0, i);
String s2 = s.substring(i, j);
String s3 = s.substring(j, k);
String s4 = s.substring(k, s.length());
if (isValid(s1) && isValid(s2) && isValid(s3) && isValid(s4)) {
res.add(s1 + "." + s2 + "." + s3 + "." + s4);
}
}
}
}
return res;
}
private static boolean isValid(String s) {
if (s.length() == 0 || s.length() > 3 || (s.charAt(0) == '0' && s.length() > 1) || Integer.parseInt(s) > 255)
return false;
return true;
}
}
二维字符矩阵找单词
import java.util.Scanner;
public class WordSearch {
public static void main(String[] args) {
Scanner sc=new Scanner(System.in);
int m=sc.nextInt();
int n=sc.nextInt();
char[][] board=new char[m][n];
for (int i = 0; i < m; i++) {
board[i] = sc.next().toCharArray();
}
String word = sc.next();
boolean res=exist(board,word);
System.out.println(res);
}
public static 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++) {
if (dfs(board, word, 0, i, j, visited))
return true;
}
}
return false;
}
public static boolean dfs(char[][] board, String word, int index, int rowindex, int colindex, boolean[][] visited) {
if (index == word.length())
return true;
if (rowindex < 0 || colindex < 0 || rowindex >=board.length || colindex >= board[0].length)
return false;
if (visited[rowindex][colindex])
return false;
if (board[rowindex][colindex] != word.charAt(index))
return false;
visited[rowindex][colindex] = true;
boolean res = dfs(board, word, index + 1, rowindex - 1, colindex,
visited)
|| dfs(board, word, index + 1, rowindex + 1, colindex, visited)
|| dfs(board, word, index + 1, rowindex, colindex + 1, visited)
|| dfs(board, word, index + 1, rowindex, colindex - 1, visited);
visited[rowindex][colindex] = false;
return res;
}
}
二十六进制加法
import java.util.ArrayList;
import java.util.Scanner;
public class Twentysix {
//全局变量进位
private static int jinWei = 0;
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
System.out.println(hexPlus26(sc.next(), sc.next()));
}
}
private static String hexPlus26(String str1, String str2) {
ArrayList<StringBuffer> arr;
StringBuffer sbResult = new StringBuffer();
//将两个字符串用'a'从最高位补全，并为可能出现最长字符串最高位进一的情况，在最高位补一个a
if (str1.length() >= str2.length()) {
arr = completeStr(str1, str2);
} else {
arr = completeStr(str2, str1);
}
StringBuffer sb1 = arr.get(0);
StringBuffer sb2 = arr.get(1);
for (int i = sb1.length() - 1; i >= 0; i--) {
int plusResult = (int) sb1.charAt(i) - 97 + (int) sb2.charAt(i) - 97 + jinWei;
//如果发生进位，将全局变量jinWei改成1，并在下一次循环中加上，否则为0
if (plusResult > 25) {
sbResult.append(Character.toString((char) (plusResult - 26 + 97)));
jinWei = 1;
} else {
sbResult.append((char) (plusResult + 97));
jinWei = 0;
}
}
//如果最后没发生进位，去掉之前加的a
if (sbResult.charAt(sbResult.length() - 1) == 'a') {
sbResult.deleteCharAt(sbResult.length() - 1);
}
return sbResult.reverse().toString();
}
private static ArrayList<StringBuffer> completeStr(String str1, String str2) {
StringBuffer sb1 = new StringBuffer();
StringBuffer sb2 = new StringBuffer();
ArrayList<StringBuffer> arr = new ArrayList<StringBuffer>();
int lengthDiff = str1.length() - str2.length();
//为可能出现最长字符串最高位进一的情况，在最高位先补一个a（代表0）
sb1.append("a");
sb2.append("a");
//将两个字符串长度用a补齐
for (int i = 0; i < lengthDiff; i++) {
sb2.append("a");
}
//将原字符串加到最后边
sb1.append(str1);
sb2.append(str2);
arr.add(sb1);
arr.add(sb2);
return arr;
}
}
包围的区域
输入：
4
X X X X
X O O X
X X O X
X O X X
输出:
X X X X
X X X X
X X X X
X O X X
import java.util.Scanner;
public class SurroundedRegions {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
int n=sc.nextInt();
char[][] board=new char[n][n];
for (int i=0;i<n;i++){
board[i]=sc.next().toCharArray();
}
if (board==null||board.length==0) return;
int row = board.length;
int col = board[0].length;
for(int j=0;j<col;j++){
dfs(board,0,j);
dfs(board,row-1,j); //第一行和最后一行
}
for(int i=1;i<row-1;i++){
dfs(board,i,0);
dfs(board,i,col-1); //第一列和最后一列抛去和上一个循环相交的格子
}
for(int i=0;i<row;i++)
for(int j=0;j<col;j++){
if (board[i][j]=='D') board[i][j] = 'O';
else if (board[i][j]=='O') board[i][j] = 'X';
}
for(int i=0;i<row;i++){
for(int j=0;j<col;j++){
System.out.print(board[i][j]);
}
System.out.println();
}
}
public static void dfs(char[][] board, int x, int y){
if (x<0||x>=board.length||y<0||y>=board[0].length||board[x][y]!='O') return;
board[x][y] = 'D';
dfs(board,x-1,y);
dfs(board,x+1,y);
dfs(board,x,y-1);
dfs(board,x,y+1);
}
}
完成数独
public class Solution {
public void solveSudoku(char[][] board) {
ArrayList<Integer> empty = new ArrayList<Integer>();
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(board[i][j]=='.'){
empty.add(i*9+j);
}
int len = empty.size();
dfs(empty,board,0,len);
}
public boolean dfs(ArrayList<Integer> empty, char[][] board, int cur, int len){
if(cur==len) return true;
int index = empty.get(cur);
int row = index/9;
int col = index%9;
for(int v=1;v<=9;v++){
if(isValid(v,row,col,board)){
board[row][col] = (char)(v+'0');
if(dfs(empty,board,cur+1,len))
return true;
board[row][col] = '.';
}
}
return false;
}
public boolean isValid(int v, int row, int col, char[][] board){
for(int i=0;i<9;i++){
if(board[row][i] - '0'==v) return false;
if(board[i][col] - '0'==v) return false;
int row_s = 3*(row/3) + i/3;
int col_s = 3*(col/3) + i%3;
if(board[row_s][col_s] - '0'==v) return false;
}
return true;
}
}
N皇后问题
https://blog.csdn.net/u011095253/article/details/9158473
public class Solution {
public ArrayList<String[]> solveNQueens(int n) {
ArrayList<String[]> res = new ArrayList<String[]>();
int[] loc = new int[n];
dfs(res,loc,0,n);
return res;
}
public void dfs(ArrayList<String[]> res, int[] loc, int cur, int n){
if(cur==n)
printboard(res,loc,n);
else{
for(int i=0;i<n;i++){
loc[cur] = i;
if(isValid(loc,cur))
dfs(res,loc,cur+1,n);
}
}
}
public boolean isValid(int[] loc, int cur){
for(int i=0;i<cur;i++){
if(loc[i]==loc[cur]||Math.abs(loc[i]-loc[cur])==(cur-i))
return false;
}
return true;
}
public void printboard(ArrayList<String[]> res, int[] loc, int n){
String[] ans = new String[n];
for(int i=0;i<n;i++){
String row = new String();
for(int j=0;j<n;j++){
if(j==loc[i]) row += "Q";
else row += ".";
}
ans[i] = row;
}
res.add(ans);
}
}
