题目二十一 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。
回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
例如，121 是回文，而 123 不是。
class Solution {
public boolean isPalindrome(int x) {
if(x<0){return false;}
int t=x;
int n=0;
while(x!=0){
n*=10;
n+=x%10;
x/=10;
}
if(n==t){return true;}else{return false;}
}
}
算法很简单，只需要生成数的逆序与原来的数字比较即可
题目二十二 盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
class Solution {
public int maxArea(int[] height) {
int k = 0;
int i= 0,j = height.length-1;
while(j>i){
if(height[i]>=height[j]){
int n = height[j] * (j-i);
if(n>k){k=n;}
j--;
continue;
}else{
int n = height[i] *(j-i);
if(n>k){k=n;}
i++;
continue;
}
}
return k;
}
}
此题目用到的是双指针法，通过不断移动指针来缩小问题规模
推导：容器大小与较小的指针以及指针之间的长度有关，因此我们在查找最大容器时，只需要缩小较小的指针即可缩小问题规模。
为什么移动较小的指针？
由于较大指针继续缩小范围，只会使得容器变小，因此较小的指针不会再作为容器的边界了，所以我们才移动较小的指针。
每次更新指针，都将得到的新容器大小与历史最大容器大小比较并更新。
题目二十三 有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。
class Solution {
public boolean isValid(String s) {
ArrayList stack =new ArrayList();
for(int i=0;i< s.length();i++){
char c = s.charAt(i);
if(c =='{'||c=='['||c=='('){
stack.add(c);
}else{
if(stack.size() == 0){
return false;
}
char lc = (Character)stack.get(stack.size()-1);
if(lc == '{'&& c=='}' || lc == '['&&c==']'||lc=='('&&c==')'){
stack.remove(stack.size()-1);
}else{return false;}
}
}
if(stack.size() == 0){return true;}
return false;
}
}
本题使用到了栈的思想，使用ArrayList来实现栈存储。
我们只需要遍历一次字符串，不断将符号入栈，当遇到后括号时，我们对最近一个前括号和当前后括号进行测试，如果满足条件则一起出栈，不满足条件则返回false。当遍历完字符串后，如果字符串满足条件，则栈中内容应该被全部弹出。也就是栈为空则返回true，否则返回false。
注意：当读取到后括号发现栈为空时，用常规的读取前一个括号进行测试的方法已经失效（取值越界），因此直接返回false
题目二十四 括号生成
class Solution22 {
private List<String> strings = new ArrayList<>();
private int l;
private int n;
public List<String> generateParenthesis(int n) {
l = n*2;
this.n = n;
build("(",1,0);
return strings;
}
//深度优先搜索
private void build(String s,int ln,int rn) {
if (s.length() >= l){
strings.add(s);
return;
}
//发现左括号数量小于右括号数量，则进行剪枝
if (rn>ln){
return;
}
//如果左括号数量小于n则继续搜索
if (ln<n){
build(s+"(",ln+1,rn);
}
//如果右括号数量小于n则继续搜索
if (rn<n){
build(s+")",ln,rn+1);
}
}
}
本题使用到了回溯法的思想，通过递归调用实现深度优先搜索，对题目解析可以发现我们要找到的是符合规范的所有括号序列，但是在搜索过程中很明显，当左括号数量只要小于右括号数量时，则不符合规则，进行剪枝，直接返回。
因此我们需要维护变量ln和rn来记录当前方法栈左括号和右括号数量
当字符串满足生成数量时则返回
题目二十五 三数之和
class Solution23 {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> ans = new ArrayList<>();
for (int i = 0; i < nums.length; i++) {
if (i != 0 && nums[i-1] == nums[i]){
continue;
}//如果和前一个重复，则不构建此元组
int k = nums.length -1;
int target = -nums[i];
for (int j = i+1; j < nums.length; j++) {
if (j != i+1 && nums[j-1] == nums[j]){
continue;
}//如果和前一个重复，则不构建此元组
//第三个指针在第二层循环内是不断递减的
while (k > j && nums[k] + nums[j] > target){
k--;
}
//后续的序列都不满足条件
if (k == j){
break;
}
//满足条件，构建元组
if (nums[k] + nums[j] == target){
ArrayList<Integer> list = new ArrayList<>();
list.add(nums[i]);
list.add(nums[j]);
list.add(nums[k]);
ans.add(list);
}
}
}
return ans;
}
}
本题需要考虑到3元组的唯一性，我们可以通过构造(a,b,c) 其中a<=b<=c的关系来保证元组唯一性
由于题目提供的是乱序数字，我们先对数组进行排列
通过三指针法来遍历，第一层指针遍历所有的a，当遇到后一个与前一个数字相同时，我们应当避免，否则会产生重复。
第二层指针同理需要避免。当我们确定了a和b时，只需要找到第三个c即可
注意由于a+b必然是不断变大的，因此当我们在a不变，b不断变大的过程，c应当也是不断缩小的，当c和b的指针相遇时，则代表此序列在之后的a+b+c只会是不断变大，如果此时a+b+c>0那么就打破第二层循环，继续寻找新序列
因此第三层循环应该和第二层循环同时进行
题目二十六 删除有序数组中的重复项
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
class Solution {
public int removeDuplicates(int[] nums) {
int s =nums[0];
int k =1;
for(int i=1;i <nums.length;i++){
if(nums[i] != s){
s = nums[i];
nums[k++] = s;
}else{
continue;
}
}
return k;
}
}
由于题目提供的是已经排列好的顺序表，因此只需要维护一个int类型的s来记录前一个数字和当前数字是否重复即可，重复的跳过，不重复的更新k位置数值，并让k指针右移
题目二十七 按列翻转得到最大值等行数
给定 m x n 矩阵 matrix 。
你可以从中选出任意数量的列并翻转其上的 每个 单元格。（即翻转后，单元格的值从 0 变成 1，或者从 1 变为 0 。）
返回 经过一些翻转后，行与行之间所有值都相等的最大行数 。
class Solution {
public int maxEqualRowsAfterFlips(int[][] matrix) {
Map<String,Integer> status = new HashMap();
int n = matrix.length;
int m= matrix[0].length;
StringBuilder key = new StringBuilder();
//1开头反转
for(int i =0;i <n; i++){
key.setLength(0);
if(matrix[i][0] ==1){
for(int j=0;j<m;j++){
key.append((matrix[i][j] == 0)?1:0);
}
}else{
for(int j=0;j<m;j++){
key.append(matrix[i][j]);
}
}
Integer num = status.get(key.toString());
if(num ==null){
status.put(key.toString(),1);
}else{
status.put(key.toString(),num+1);
}
}
Integer max = 0;
for(Integer value : status.values()){
if(value > max){
max = value;
}
}
return max;
}
}
本题使用到了Hash表来存储相同性质序列的出现次数，依据题意，我们可以分析出当存在相同序列或互逆（0和1相反）的序列出现，则必定能通过相同的列翻转形成值相等的行。可以分析出相同性质的序列只有0或1开头的两种情况，因此我们将1开头情况的行先都转换为0开头同性质的行，我们只需要统计出矩阵中出现次数的最多的行即可。
题目二十八 八数码难
八数码问题也叫九宫问题，是人工智能中状态搜索中的经典问题，其中，该问题描述为：在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。
package com.os467;
import java.util.*;
/**
* -----------测试数据(有解)------------
* 2,8,3,6,1,4,7,0,5
* 1,2,3,4,5,6,7,8,0
*
* 0,1,2,3,4,5,6,7,8
* 3,1,2,4,5,6,7,8,0
*
* 1,2,3,4,5,6,7,8,0
* 0,8,7,6,5,4,3,2,1
*
* 0,1,2,3,4,5,6,7,8
* 1,2,0,3,4,5,6,7,8
*
*-------------测试数据(无解)------------
* 1,2,3,4,5,6,7,8,0
* 1,2,3,4,5,6,8,7,0
*
*/
public class NineNumber {
public static void main(String[] args) {
Table table = new Table();
long start = System.currentTimeMillis();
table.start();
long end = System.currentTimeMillis();
System.out.println("算法共计用时"+((double)(end - start)/(double)1000)+"秒");
}
}
class Location{
private int i;
private int j;
public Location(int i, int j) {
this.i=i;
this.j=j;
}
public int getI() {
return i;
}
public void setI(int i) {
this.i = i;
}
public int getJ() {
return j;
}
public void setJ(int j) {
this.j = j;
}
public List<Location> getNear() {
List<Location> locations = new ArrayList<>();
if (i-1 >= 0){
Location up = new Location(i-1,j);
locations.add(up);
}
if (j-1 >= 0){
Location left = new Location(i,j-1);
locations.add(left);
}
if (j+1 <= 2){
Location right = new Location(i,j+1);
locations.add(right);
}
if (i+1 <= 2){
Location down = new Location(i+1,j);
locations.add(down);
}
return locations;
}
}
/**
* 九宫表
*/
class Table {
private static Comparator comparator = new Comparator<Table>() {
@Override
public int compare(Table o1, Table o2) {
return o1.getFx() - o2.getFx();
}
};
private static StringBuilder stringBuilder = new StringBuilder();
private String memoryWay;
/**
* 3*3二维矩阵
*/
private int[][] table = new int[3][3];
//曼哈顿之和
private int sumMHD;
//遍历深度
private int level;
//哈希记忆表
private static HashSet<String> hashSet = new HashSet<>();
private static List<Table> tableList = new ArrayList<>();
//终止状态
private static int[][] table0 = new int[3][3];
public Table(){
level = 1;
System.out.println("请输入九宫格初始状态(用逗号隔开 0代表空位):");
Scanner scanner = new Scanner(System.in);
String s = scanner.nextLine();
System.out.println("请输入九宫格终止状态(用逗号隔开 0代表空位):");
String s1 = scanner.nextLine();
String[] numbers = s.split(",");
String[] numbers1 = s1.split(",");
fillTable(table,numbers);
fillTable(table0,numbers1);
}
/**
* 序列检测
* @return
*/
private boolean checkReachable() {
int[] nums = new int[9];
int[] nums0 = new int[9];
//装换为整型
for (int i = 0,k = 0; i < table.length; i++) {
for (int j = 0; j < table[0].length; j++,k++) {
nums[k] = table[i][j];
nums0[k] = table0[i][j];
}
}
//初始状态逆序x和终止状态逆序x0
int x = 0, x0 = 0;
//检查逆序
for (int i = 0; i < nums.length; i++) {
for (int j = i - 1; j >= 0; j--) {
if (nums[j] > nums[i] && nums[i] != 0){
x++;
}
if (nums0[j]>nums0[i] && nums0[i] != 0){
x0++;
}
}
}
System.out.println("起始状态序列逆序数为"+x);
System.out.println("终止状态序列逆序数为"+x0);
if (x%2 != x0%2){
System.out.println("排序奇偶性不同");
//奇偶性不同
return false;
}
System.out.println("排序奇偶性相同");
return true;
}
public Table(int[][] table,int level) {
this.level = level;
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[0].length; j++) {
this.table[i][j] = table[i][j];
}
}
}
public int getSumMHD() {
return sumMHD;
}
public void setSumMHD(int sumMHD) {
this.sumMHD = sumMHD;
}
public int getFx(){
return level + sumMHD;
}
public int getLevel() {
return level;
}
public void setLevel(int level) {
this.level = level;
}
/**
* 初始化表
* @param table
* @param numbers
*/
private void fillTable(int[][] table, String[] numbers) {
for (int i = 0,k = 0; i < 3; i++) {
for (int j = 0; j < 3; j++,k++) {
table[i][j] = Integer.parseInt(numbers[k]);
}
}
}
/**
* 开始解决八数码难问题
*
*
*
*/
public void start() {
if (!checkReachable()){
System.out.println("无解!");
return;
}
//计算初始曼哈顿距离
sumMHD = calculateSumMHD(this, table0);
//记录初始状态路径值
memoryWay = getPrint();
Table move = move(this);
System.out.println(move.memoryWay);
}
/**
* 开始移动九宫格
* @param table
* @return
*/
private Table move(Table table) {
Stack<Table> stack = new Stack<>();
stack.add(table);
while (!stack.isEmpty()){
//弹出栈顶元素
Table popTable = stack.pop();
table = popTable;
level = popTable.level;
//需要先获取到0的位置
Location zeroLocate = getZeroLocate(table.table);
if (zeroLocate == null){
throw new RuntimeException("没有空位置");
}
List<Location> near = zeroLocate.getNear();
//0可以移动的位置得到新的状态(不进入重复状态)
for (Location target : near) {
//计算出移动后新的曼哈顿距离
Table movedTable = getMovedTable(table.table, zeroLocate, target, level+1);
int sumMHD = calculateSumMHD(movedTable, table0);
movedTable.setSumMHD(sumMHD);
movedTable.memoryWay = table.memoryWay + movedTable.getPrint();
String only = movedTable.getOnly();
if (!hashSet.contains(only)){
tableList.add(movedTable);
hashSet.add(only);
}
}
//获取到下一步的移动状态列表，如果存在曼哈顿距离为0的表，则代表成功抵达终止状态
for (int i = 0; i < tableList.size(); i++) {
int sumMHD = tableList.get(i).getSumMHD();
if (sumMHD == 0){
return tableList.get(i);
}
}
//根据Fx挑选最小的进行搜索
//默认第一个
Table next = tableList.get(0);
int fx = next.getFx();
int index = 0;
for (int i = 1; i < tableList.size(); i++) {
int fx1 = tableList.get(i).getFx();
if (fx1 < fx){
index = i;
fx = fx1;
}
}
next = tableList.get(index);
//从tableList中移除
tableList.remove(index);
//入栈
stack.add(next);
}
return null;
}
private String getOnly(){
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[0].length; j++) {
stringBuilder.append(table[i][j]);
}
}
String s = stringBuilder.toString();
stringBuilder.setLength(0);
return s;
}
private String getPrint() {
stringBuilder.append("第");
stringBuilder.append(level);
stringBuilder.append("步,曼哈顿距离为");
stringBuilder.append(getSumMHD());
stringBuilder.append(",当前代价为");
stringBuilder.append(getFx());
stringBuilder.append("\n");
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[0].length; j++) {
stringBuilder.append(table[i][j]+" ");
}
stringBuilder.append("\n");
}
stringBuilder.append("\n");
String s = stringBuilder.toString();
stringBuilder.setLength(0);
return s;
}
private Location getZeroLocate(int[][] table) {
return getTargetLocate(0,table);
}
/**
* 计算曼哈顿距离之和
* @param movedTable
* @param table0 目标状态
*/
private int calculateSumMHD(Table movedTable, int[][] table0) {
int[][] table = movedTable.table;
int sum = 0;
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[0].length; j++) {
int num = table[i][j];
if (num != 0){
Location startLocate = getTargetLocate(num, table);
Location endLocate = getTargetLocate(num, table0);
int iL = Math.abs(startLocate.getI() - endLocate.getI());
int jL = Math.abs(startLocate.getJ() - endLocate.getJ());
sum += (iL + jL);
}
}
}
return sum;
}
private Table getMovedTable(int[][] table, Location zero, Location target, int level) {
Table newTable = new Table(table,level);
int i = zero.getI();
int j = zero.getJ();
int i1 = target.getI();
int j1 = target.getJ();
newTable.table[i][j] = newTable.table[i1][j1];
newTable.table[i1][j1] = 0;
return newTable;
}
private Location getTargetLocate(int num,int[][] table) {
for (int i = 0; i < table.length; i++) {
for (int j = 0; j < table[i].length; j++) {
if (table[i][j] == num){
return new Location(i,j);
}
}
}
return null;
}
}
使用了启发式函数A*算法 + 哈希集合降低了时间复杂度，A*会计算并挑出当前代价最小的分支进行遍历，而哈希集合防止了分支走入重复计算的状态
A*算法代价计算：当前遍历深度 + 当前状态的优劣程度(此问题由曼哈顿距离大小决定)
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以邮件至 1300452403@qq.com
