《剑指offer》复习
重要总结(常用）:
1 字符串转字符数组：char[] num=s.toCharArrays();
获取子字符串：String son=s.substring(a,b); 或 String son=s.substring(a);(0~a)
判断有无此字符：s.contains
连接：concat
其他类型转String：s=String.valueOf(Object o)；
比较字符串：比较值：equals 或者 compareTo(s)
2 字符转整型：int value=num[i]-'0'
3 ASCII码：0:48 9:57
4 数组：s.length; 字符串：s.length()
迭代器：Iterator it=xx.iterator(); //xx可以是任意数据结构如List,set
while(it.hasNext()){
syso(it.next());
}
5、StringBuffer:
append()、insert()、delete()、get()、indexOf()、charAt()、length()
6、关于List的操作：有序，不去重
import java.util.*;
List<T> list=new ArrayList<T>
（1）增加：add() ：
list.add("a");// 向集合中追加元素
list.add(1, "b");// 向集合的制定位置中追加元素
list.addAll(list);// 向集合追加一个collection，只可追加collection，由于java不提供collection的实现，由它的下级接口来实现
list.addAll(4, list);// 与上述含义相同， “4”意为追加元素所放的位置
（2）减少：remove()：
list.remove(7);// 根据集合中元素下标位置来删除元素
（3）清除：clear()
将list释放，元素清空，且无返回值
list.clear()；
（4）求数组长度： list.size()
（5）取集合元素：list.get(0);// 根据元素下标来取集合中的元素
（6）比较集合元素：
list.contains("a,b,c") // 此方法是用来比较的，与equals比较相似，现在list的元素中有[a, b, a, b, a, b, a],来和"a,b,c"比较会返回false，
// 但是注意再用来比较String字符串的时候会进行局部的比较，两组字符串部分相同的情况下会返回true
（7）为了将List转为数组，JDK提供了toArray
//实现方式一：
String [] array=(String[]) list.toArray(new String[list.size()]);
for(String arrays: array) {
System.out.println(arrays);
}
//方式二：
String [] arr=new String [list.size()];
list.toArray(arr);
for(String arrs: arr) {
System.out.println(arrs);
}
（8）判断是否为空:
//在集合中判断是否为空 ，不空返回false，空会返回true，常常会与null！=list来共同判定集合是否为空，
//null！=list和list.isempty最大的区别是：一个人要喝水，前者判断是否有水杯，后者判断的是水杯是否有水
System.out.println(list.isEmpty());//false
System.out.println(null!=list);//true
（9）打印集合元素
//方式一：
Iterator it=list.iterator();
while(it.hasNext()) {
String string=(String) it.next();
System.out.println(string);
}
//方式二：
for (Object o:list) {
System.out.println(o);
}
//方式三：
for(int s=0;s<list.size();s++) {
System.out.println(list.get(s));
}
7、关于set的操作：去重，无序
import java.util.Set;
（1）创建：Set<String> set=new HashSet<String>();
（2）新增：重复新增的值会被覆盖：set.add("abc“）；
（3）修改：因为Set没有下标也没有key，所以没有修改的方法
（4）删除：remove(Object) ：删除某个元素值 set.remove("abc");
删除其中一整个set：removeAll（Set）：
Set<String> removeSet=new HashSet<String>();
removeSet.add("a");
removeSet.add("b");
removeSet.add("c");
set.removeAll(removeSet);
（5）遍历输出set中的元素：
第一种方法：直接for输出
Set<String> ss=new HashSet<String>();
for (String s : ss) {
System.out.print(s+", ");
}
第二种：迭代器输出：
Iterator<String> iterator = ss.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next()+", ");
}
第三种：转换成数组
String [] strs=new String[ss.size()];
ss.toArray(strs);
for (String s : strs) {
System.out.print(s+", ");
}
8、队列：
import. java.util.Queue；
import java.util.LinkedList;
（1）创建： Queue<Integer> queue=new LinkedList<Integer>();
（2）新增入队：queue.add(); //如果队列已满，则抛出一个IIIegaISlabEepeplian异常
put() //新增，队列已满则阻塞
（3）移除并返回队列头部的元素 ：queue.remove() //如果队列为空，则抛出一个NoSuchElementException异常
（4） 返回队列头部的元素：element() //如果队列为空，则抛出一个NoSuchElementException异常
（5）返回队列头部的元素：peek() //如果队列为空，则返回null
9、栈：
(1) 创建：Stack<Integer> s=new Stack<>();
Stack<String > set=new Stack<String>();
(2) 入栈：
第一种：s.push(1)；//添加成功返回该元素
第二种：s.add(1) //添加成功返回true
(3) 出栈：s.pop(); //如果是空栈，会抛出异常：EmptyStackException
(4) 返回栈顶：s.peek()
(5)判断是否为空：s.empty()
(6)返回对象在堆栈中的位置，以 1 为基数:
int search(Object element)
10、图：Map
（1）创建：Map<K,V> map=new HashMap<K,V>();
Map<Integer,String> map=new HashMap<Integer,String>();
（2）添加：map.put(K,V)
map.put(1,"abc");
putAll(Map<? extends K,? extends V> m) 从指定映射中将所有映射关
系复制到此映射中（可选操作）。
（3）取值：
取map中的key值：map.keySet()
取map中的value值：map.values()
取指定Key的value值：value get(key); 可以用于判断键是否存在的情况。当指定的键不存在的时候，返回null。
第一种：Map<Integer,String> map = new HashMap<Integer, String>();
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
第二种：只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet：
//遍历map中的键
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
//遍历map中的值
for (String value : map.values()) {
System.out.println("Value = " + value);
}
第三种：使用迭代器Iterator：
Map<Integer,String> map = new HashMap<Integer, String>();
Iterator<Map.Entry<Integer, String>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, String> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
第四种：通过键找值遍历（效率低）
for (Integer key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key = " + key + ", Value = " + value);
（4）删除： remove(Key) 删除关联对象，指定key对象
map.remove(2);
（5）清空集合：clear()
map.clear();
（6）判断：
1、boolean isEmpty() 长度为0返回true否则false
2、boolean containsKey(Object key) 判断集合中是否包含指定的key
3、boolean containsValue(Object value) 判断集合中是否包含指定的value
关于集合类的排序：
假如有List<String> name=Arrays.asList("amy","tom","Bob");
正序排序：Collections.sort(name);
倒序排序：jdk1.8以前：重写Collections类的compare()方法：
Collections.sort(name,new Comparator<String>() {
public int compare(String a,String b){
return b.compareTo(a);
}
});
jdk1.8之后，
Collections.sort(name,(a,b)->b.compareTo(a));
1、二维数组赋值：int[][] array={{1,2,3},{2,4,5}};
2、char 比较用单引号 if(a==' ') String比较用" "
3、题目：从尾到头打印链表
(1)倒序要想到Stack，先进慢出。
**Stack：**Stack<Integer> stack=new Stack<>();
stack.isEmpty()：判断是否为空 while(!stack.isEmpty()){...}
stack.push()：进栈
stack.pop()：出栈
(2)ListNode：线性表 ListNode listNode（标记的是第一个位）
listNode==null：判断是否为空 while(listNode!=null)
listNode.val：当前值（按正序）
listNode=listNode.next：下一位
4、题目：求斐波那契数列的第n位（递归）
0,1,1,2,3,5,8,13...
image
5、题目：跳台阶（斐波那契数列题型变形）
image
image
但用递归性能消耗较大，所以可以选择用循环，动态规划，用数组存储已经计算出的值。
public int climbStairs(int n) {
int dp[]=new int[n+1];
dp[0]=1;
dp[1]=2;
for(int i=2;i<n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n-1];
}
6、题目：变态跳台阶
image
思路：列出前几项先找规律，发现F(0)=0,F(1)=1,F(2)=2,F(3)=4,F(4)=8,F(5)=16...即从2开始，每个数为前一项的2倍，所以
image
7、题目：二进制中1的个数
（1）已知一个数求其二进制：(负数是得到其补码)
String s=Integer.toBinaryString(n);
或者：char[] ch=Integer.toBinaryString(n).toCharArray();
(2)求a的b次方：Math.pow(a,b)
(3)整数数组排序：Arrays.sort(array)
8、题目：合并两个排序的链表（代码的鲁棒性，递归）
题目描述
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
image
9、题目：反转链表
题目描述：输入一个链表，反转链表后，输出新链表的表头。
思路：当前链表值为head，创建两个新链表pre，next，分别指向当前值的前一位和后一位。反转链表就是让每个head都指向前一位。
遍历整个数组，next保存下一个指针，主要是让每次的head.next从指向下一位改为指向前一位pre,再让pre等于当前值，head等于next的值，就可以从前往后使指针都指向它的前一位，从而实现反转链表。最后pre是指向最后一位的，即新链表的表头，只要将其返回即可。
代码如下：
image
总结链表：ListNode node;
链表下一位指针：node.next
10、题目：重建二叉树
题目描述
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
思路：前序遍历是根左右，中序遍历是左根右，前序遍历的根节点（起始节点）就是该二叉树的根节点，在中序遍历中循环找与该根节点值相同的值（题目规定无重复值），则该节点前的数为二叉树的左节点，后为该树的右节点，根据这种思想，递归继续所有节点，不断返回。
代码如下：
image
总结二叉树：
TreeNode root=new TreeNode(xx); //xx同样是TreeNode
root.left=xx;
root.right=xx;
root.val //节点的值
11、题目：树的子结构
题目描述：
输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
思路及代码如下：
image
image
12、题目：包含min函数的栈
总结栈：
Stack<Integer> stack=new Stack<Integer>();
入栈：stack.push(node);
出栈：stack.pop()
获得栈顶：stack.peek();
判断栈是否为空：stack.empty()
13、题目：栈的压入、弹出序列
题目描述
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
image
代码如下：
image
**14、关于迭代器: **Iterator<V> iterator=new Iterator<>();
判断是否为最后一位（常常在while语句）：iterator.hasNext()
下一个值：iterator.next()
例子：
Iterator<Stack> iterator=stack.iterator();
while(iterator.hasNext()){
int tmp=iterator.next();
if(min>tmp){ min=tmp; }
}
15、求丑数：
一般方法：但是时间太长了
image
16、题目：把数组排成最小的数
image
解题思路：
* 先将整型数组转换成String数组，然后将String数组排序，最后将排好序的字符串数组拼接出来。关键就是制定排序规则。
* 排序规则如下：
* 若ab > ba 则 a > b，
* 若ab < ba 则 a < b，
* 若ab = ba 则 a = b；
* 解释说明：
* 比如 "3"< "31"但是 "331"> "313"，所以要将二者拼接起来进行比较
代码如下：
image
image
17题目：数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
思路：
要转换思路，数组中出现次数超过一半，则数组的中间位置的数肯定是那个数，所以我们只要先将数组进行排序，然后取数组中间的那个数的值，并统计数组中该数有多少个，若超过一半，则输出该数，否则输出0。
18、题目：和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
代码：
image
19、题目：第一个只出现一次的字符
思路：用了HashMap<Character,Integer>对字符串进行统计，如果是已经在hashmap中出现过的，则取原来的值，并加一；如果是原来没有的，则增加这个字符。最后，还是遍历字符串，输出第一个只出现一次的（在hashmap中统计是1的）。
此处用到：hashMap<object,value>
创建：HashMap<Character,Integer> hashmap=new HashMap<>();
包含：hashmap.contains(object);
存值：hashmap.put(object,value)
取值：value=hashmap.get(object）
移除：hashmap.remove(object)
代码如下：
image
20、二进制中1的个数：
n&(n-1): 一个数减1与它自己，会除去它最右的1
所以相当于在计算1的个数：
int count=0;
while(n){
n=n&(n-1);
count++;
}
21、>>带符号右移，相当于÷2,正数补充0，负数补充1；>>>无符号右移，补充0
<<带符号左移，相当于*2； <<<无符号左移
22、高质量代码：
1.规范性
2.完整性：
考虑功能性、边界值、以及各种可能的错误输入。
三种错误处理的方法：
（1）函数用返回值来告知调用者是否出错。如0、1...
（2）当错误发生时设置一个全局变量，在返回值中传递计算结果
（3）异常。可根据不同出错原因定义不同的异常类型，函数运行出错，则抛出一个异常。
3.鲁棒性：
也叫健壮性。程序能够判断输入是否合乎规范要求，并对不符合要求的输入予以合理的处理。
23、树：常用遍历或递归
题目一：树的子结构
题目描述：输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）
用递归实现：（较简洁）
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
boolean result=false;
if(root1==null||root2==null){
return false;
}
if(root1.val==root2.val){//根节点相同，调用比较子树值
result=isSubTree(root1,root2);
}
if(!result){//根节点不同，比较左子树
result=isSubTree(root1.left,root2);
}
if(!result){//根节点，比较右子树
result=isSubTree(root1.right,root2);
}
return result;
}
public boolean isSubTree(TreeNode node1,TreeNode node2){
if(node2==null){//子树已经到达了叶节点，说明已经判断结束，返回true
return true;
}
if(node1==null){
return false;
}
if(node1.val!=node2.val){
return false;
}
//遍历比较其左子树和右子树
return isSubTree(node1.left,node2.left)&&isSubTree(node1.right,node2.right);
}
}
24.题目：分行从上到下打印二叉树：
思路：用一个辅助队列来保存将要打印的节点。需要两个变量：toBePrinted表示在当前层中还没有打印的节点数；nextLevel表示下一层节点数。
import java.util.ArrayList;
import java.util.Queue;
import java.util.LinkedList;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list=new ArrayList<ArrayList<Integer>>();
if(pRoot==null){
return list;
}
ArrayList<Integer> temp=new ArrayList<>();
Queue<TreeNode> queue=new LinkedList<TreeNode>();
int nextLevel=0;//下一层节点数
int toBePrinted=1;//当前层还未打印的节点数
queue.add(pRoot);
while(!queue.isEmpty()){
TreeNode pNode=queue.peek();
temp.add(pNode.val);//将节点值存入数组链表中
if(pNode.left!=null){
queue.add(pNode.left);
nextLevel++;
}
if(pNode.right!=null){
queue.add(pNode.right);
nextLevel++;
}
queue.pop(); //弹出此时的父节点
toBePrinted--;
if(toBePrinted==0){
list.add(new ArrayList<Integer>(temp));
temp.clear();
toBePrinted=nextLevel;
nextLevel=0;
}
}
return list;
}
}
25、题目：之字形打印二叉树
思路：需要2个辅助栈，当打印奇数层，先保存左节点再保存右节点到第一个栈；当打印偶数层，先保存右子节点，再保存左子节点到第二个栈。
import java.util.*;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> aList=new ArrayList<ArrayList<Integer>>();
if(pRoot==null)
return aList;
Stack<TreeNode> s1=new Stack<TreeNode>();
s1.add(pRoot);
Stack<TreeNode> s2=new Stack<TreeNode>();
while(!s1.isEmpty()||!s2.isEmpty()){
if(!s1.isEmpty()){
ArrayList<Integer> aList2=new ArrayList<Integer>();
while(!s1.isEmpty()){
TreeNode p=s1.pop();
aList2.add(p.val);
if(p.left!=null)
s2.add(p.left);
if(p.right!=null)
s2.add(p.right);
}
aList.add(aList2);
}
else {
ArrayList<Integer> aList2=new ArrayList<Integer>();
while(!s2.isEmpty()){
TreeNode p=s2.pop();
if(p.right!=null)
s1.add(p.right);
if(p.left!=null)
s1.add(p.left);
aList2.add(p.val);
}
aList.add(aList2);
}
}
return aList;
}
}
25、题目：二叉树的深度
题目描述
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
思路：递归求左子树节点数和右子树节点，比较大小a>b?c:d
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null){
return 0;
}
int nleft=TreeDepth(root.left);
int nright=TreeDepth(root.right);
return nleft>nright?(nleft+1):(nright+1);
}
}
26、二叉树的镜像
思路：求一棵树的镜像的过程：先前序遍历该树每个节点，如果该节点有子节点，则交换其两个字节点；当交换完所有非叶节点的左、右子节点后，就得到了树的镜像。
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root==null){ return; }
if(root.left==null&&root.right==null){
return;
}
TreeNode temp=root.left;
root.left=root.right;
root.right=temp;
if(root.left!=null){
Mirror(root.left);
}
if(root.right!=null){
Mirror(root.right);
}
}
}
27、题目：二叉树的下一个节点（画图找规律）
题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。
思路：节点为空，返回空
找规律，分两类：
1、有右子树，下一个为右子树最左子节点
2、无右子树：分为 a.是父节点的左孩子，下一个为父节点；b.是父节点的右孩子，则一直找其父节点，直到当前节点为父节点的左孩子位置，否则直到找到根节点，结束
/*
public class TreeLinkNode {
int val;
TreeLinkNode left = null;
TreeLinkNode right = null;
TreeLinkNode next = null;
TreeLinkNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public TreeLinkNode GetNext(TreeLinkNode pNode)
{
if(pNode==null){
return null;
}
if(pNode.right!=null){
TreeLinkNode node=pNode.right;
while(node.left!=null){
node=node.left;
}
return node;
}
while(pNode.next!=null){
if(pNode.next.left==pNode){
return pNode.next;
}
pNode=pNode.next;
}
return null;
}
}
28、题目：对称的二叉树
题目描述
请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
思路：遍历，比较二叉树正常的前序遍历和对称前序遍历的序列是否相同来判断是否对称。
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
boolean isSymmetrical(TreeNode pRoot)
{
return isSymmetrical(pRoot,pRoot);
}
boolean isSymmetrical(TreeNode pRoot1,TreeNode pRoot2){
if(pRoot1==null&&pRoot2==null){
return true;
}
if(pRoot1==null||pRoot2==null){
return false;
}
if(pRoot1.val!=pRoot2.val){
return false;
}
return isSymmetrical(pRoot1.left,pRoot2.right)&&isSymmetrical(pRoot1.right,pRoot2.left);
}
}
27、题目：字符串的排列
题目描述：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
Java：
import java.util.*;
public class Solution {
public ArrayList<String> Permutation(String str) {
ArrayList<String> list=new ArrayList<String>();
if(str!=null&&str.length()>0){
PermutationHelper(str.toCharArray(),0,list);
Collections.sort(list);
}
return list;
}
public void PermutationHelper(char[] chars,int i,ArrayList<String> list){
if(i==chars.length-1){//全排列只剩下一个字符，则将该字符串添加到list中
list.add(String.valueOf(chars));
}else{
Set<Character> charSet=new HashSet<Character>();
for(int j=i;j<chars.length;j++){
if(j==i||!charSet.contains(chars[j])){
charSet.add(chars[j]);
swap(chars,i,j);
PermutationHelper(chars,i+1,list);
swap(chars,j,i);
}
}
}
}
private void swap(char[] cs,int i,int j){
char temp=cs[i];
cs[i]=cs[j];
cs[j]=temp;
}
}
C++：
28、正则匹配：
*：前面字符零次或多次
.：1任意一个字符
+：一次或多次
？：零次或一次
\： 将下一个字符标记为一个特殊字符、或一个原义字符、或一个 向后引用、或一个八进制转义符
29、题目：栈的压入、弹出序列
题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：需要一个辅助栈，把输入的第一个序列中的数字依次压入该辅助栈，并按照第二个序列的顺序依次从该栈中弹出。
如果下一个弹出的数字为栈顶数字，直接弹出；下一个弹出数字不在栈顶，把压栈序列中还未入栈的数字压入辅助栈，直到下一个需要弹出的数字压入栈顶；如果所有数字压入栈后仍未找到下一个弹出数字，则该序列不是弹出序列。
通过判断最后栈是否为空，来判断是否是弹出序列。
import java.util.Stack;
import java.util.ArrayList;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
if(pushA.length == 0 || popA.length == 0)
return false;
Stack<Integer> s = new Stack<Integer>();
//用于标识弹出序列的位置
int popIndex = 0;
for(int i = 0; i< pushA.length;i++){
s.push(pushA[i]);
//如果栈不为空，且栈顶元素等于弹出序列
while(!s.empty() &&s.peek() == popA[popIndex]){
//出栈
s.pop();
//弹出序列向后一位
popIndex++;
}
}
return s.empty();//s为空，则true；s不为空，则false
}
}
30、判断一个数是不是2的n次方？
将2的幂次方写成二进制形式后，很容易就会发现有一个特点：二进制中只有一个1，并且1后面跟了n个0； 因此问题可以转化为判断1后面是否跟了n个0就可以了。
用按位与，则是与了之后去掉第一个1，其余全是0
if(n&(n-1)==0){ //是 }
else { //否 }
2、转化成字符串，判断最后一次出现“1"的位置是第0位，即首位
String s=Integer.toBinaryString(n);
if(n < 1)
return false;
else if(s.lastIndexOf("1") == 0) //判断最后一次出现“1"的位置是第0位
return true;
else
return false;
31、LRU算法：java实现。
使用LinkedHashMap实现
LinkedHashMap底层就是用的HashMap加双链表实现的，而且本身已经实现了按照访问顺序的存储。此外，LinkedHashMap中本身就实现了一个方法removeEldestEntry用于判断是否需要移除最不常读取的数，方法默认是直接返回false，不会移除元素，所以需要重写该方法。即当缓存满后就移除最不常用的数。
package LRU;
import java.util.LinkedHashMap;
import java.util.Map;
public class LRU<K, V> {
private static final float hashLoadFactory=0.75f;
private LinkedHashMap<K, V> map;
private int cacheSize;
public LRU(int cacheSize){
this.cacheSize=cacheSize;
int capacity=(int)Math.ceil(cacheSize/hashLoadFactory)+1;
map=new LinkedHashMap<K,V>(capacity,hashLoadFactory,true){
private static final long serialVersionUID=1;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size()>LRU.this.cacheSize;
}
};
}
public synchronized V get(K key){
return map.get(key);
}
public synchronized void put(K key,V value){
map.put(key, value);
}
public synchronized void clear(){
map.clear();
}
public synchronized int userSize(){
return map.size();
}
public void print(){
for(Map.Entry<K, V> entry:map.entrySet()){
System.out.println(entry.getValue()+"--");
}
System.out.println();
}
}
32、字符串中第一个只出现一次的字符：
1、用Hashtable：
map.get(key)
map.remove(key)
map.put(key,value)
map.contains(key) //键是否存在
遍历键： for(Object key: map.keySet()){ key}
遍历值：for(Object value:map.values()) { value }
package Test;
import java.util.Hashtable;
import java.util.Iterator;
import java.util.Map;
public class 第一个只出现一次的字符 {
//第一个只出现一次的字符
public static void main(String[] args) {
// TODO Auto-generated method stub
//Scanner scanner=new Scanner(System.in);
Hashtable<Character, Integer> map=new Hashtable<>();
String s="abaccdeff";
for(int i=0;i<s.length();i++){
if(!map.contains(s.charAt(i))){
map.put(s.charAt(i), 1);
}else{
int time=map.get(s.charAt(i));
map.remove(s.charAt(i));
map.put(s.charAt(i), time++);
}
}
for(Character key:map.keySet()){
System.out.println(key);
break;
}
}
}
2、因为其中也可能存在小写、大写、数字，每个字符char是8位，因此总共有可能256 种可能。
1、创建一个长度为256的数组，每个字母根据其ASCII码值作为数组的下标对应数组的对应项，而数组中存储的是每个字符对应的次数。
2、先将该字符串转化为字符数组。字符char==>int，才可存入统计数组中。
···
public static void main(String[] args) {
// TODO Auto-generated method stub
String s="abaccdeff";
int count[]=new int[256];
char array[]=s.toCharArray(); //先将字符串转化为字符数组
for(int i=0;i<array.length;i++){
int t=array[i]; //将char类型的数据转化为int,再存到统计数组中
count[t]++;
}
for(int i=0;i<array.length;i++){
if(count[array[i]]==1){
System.out.println((char)array[i]); //int要转化为char
break;
}
}
···
33、字符串的公共子串
package 剑指offer;
import Test.rev;
public class 两个字符串的公共字符串 {
public static void main(String[] args) {
// TODO Auto-generated method stub
String s1="hgjhgabcadef";
String s2="hgajhgade";
String s=getCommon(s1,s2);
System.out.println(s);
}
public static String getCommon(String s1,String s2){
String maxString,minString;
if(s1.length()>=s2.length()){
maxString=s1;
minString=s2;
}else{
maxString=s2;
minString=s1;
}
String current;
//// 遍历较短的字符串，并依次减少短字符串的字符数量，判断长字符是否包含该子串
for(int i=0;i<minString.length();i++){
for(int begin=0,end=minString.length()-i;end<=minString.length();begin++,end++){
//随着i增加，字符串的长度在减小,从length减少到0
current=minString.substring(begin, end);
if(maxString.contains(current)){
return current;
}
}
}
return null;
}
}
34、队列的最大值：
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；
思路：建双向队列Deque存数组下标，和存最大值的数组list
1、当前队列是否为空，不空且当前元素大于队尾元素while(!queue.isEmpty()&&num[i]>=num[queue.getLast() ，则弹出队尾；
2、队头元素是否还在窗口内(不在：while(!queue.isEmpty()&&queue.getFirst()<i-(size-1))
3、队尾插入元素：queue.offerLast(i);
4、将对头元素插入返回的数组中：list.add(num[queue.getFirst()
import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size) {
ArrayList<Integer> arr = new ArrayList<>();
if (num==null)
return arr;
if (num.length<size||size<=0)
return arr;
Deque<Integer> queue = new LinkedList<>();
for (int i=0;i<num.length;i++){
while (!queue.isEmpty()&&num[i]>=num[queue.getLast()])
queue.pollLast();
while (!queue.isEmpty()&&queue.getFirst()<i-(size-1))
queue.pollFirst();
queue.offerLast(i);
if (i+1>=size)
arr.add(num[queue.getFirst()]);
}
return arr;
}
}
35、数组中的逆序对：
要用归并排序的方式。copy作为辅助数组，每轮将较大数从后往前复制到另一个辅助数组中，存每轮较大的数
package 剑指offer;
public class 数组中的逆序对 {
public static void main(String[] args) {
// TODO Auto-generated method stub
int a[]={7,5,3,4};
int copy[]=new int[a.length];
for(int i=0;i<a.length;i++){
copy[i]=a[i];
}
System.out.println(Inverse(a, copy, 0, a.length-1));
}
public static int Inverse(int[] data,int[] copy,int start,int end){
if(start==end){//归并到最后一位了
copy[start]=data[start];return 0;
}
//copy数组是辅助数组，一直在调整的，将较大的数字复制到辅助数组之后
int length=(end-start)/2;
int left=Inverse(copy,data,start,start+length);
int right=Inverse(copy, data, start+length+1, end);
int i=start+length;
int j=end;
int indexCopy=end;
int count=0;
while(i>=start&&j>=start+length+1){
if(data[i]>data[j]){//有逆序对,将较大的数字(data[i])复制到辅助数组之后
copy[indexCopy--]=data[i--];
count+=j-start-length;
}else{//无逆序对，将较大的数字(data[j])复制到辅助数组之后
copy[indexCopy--]=data[j--];
}
}
for(;i>=start;i--){
copy[indexCopy--]=data[i];
}
for(;j>=start+left+1;j--){
copy[indexCopy--]=data[j];
}
return left+right+count;
}
}
36、Arrays类对于数组的操作：
（1）Arrays.sort()
对于int[] num：有Arrays.sort(num);
（2）Arrays.copy()
char[] a=Arrays.copyOf(value, len+len1);
将字符串value的值复制到char[] a中，并且a的数组长度为len+len1
37、对ArrayList排序：Collections.sort(list)；
而且常有对这个方法的重写
String无contains方法，判断s中有无一个字符：s.indexOf(char) 返回-1即查找不到，否则直接返回该字符在s中的位置
基本类型转String：String.valueOf(xx)
如String s=String.valueof(b); //int b,double b,char b
其他类型转String：toString()
String转基本类型：Integer.parseInt(s); Double.parseDouble(s)
hashmap的contains方法，而不是containsof()
38、整数反转：
这道题要注意int的取值范围是-231~231-1（即-2147483648~2147483648)
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
示例 3:
输入: 120
输出: 21
class Solution {
public int reverse(int x) {
int rev=0;
while(x!=0){
int pop=x%10;
x/=10;
if(rev>Integer.MAX_VALUE/10||(rev==Integer.MAX_VALUE/10&&pop>7))
return 0; //超过最大界限
if(rev<Integer.MIN_VALUE/10||(rev==Integer.MIN_VALUE/10&&pop<-8)){
return 0; //超过最小界限
}
rev=rev*10+pop;
}
return rev;
}
}
39、用Set：去重，不排序
注意不能写：Set<Integer> set=new Set<>();
一般写成HashSet：HashSet<Integer> set=new HashSet<>();
（1）添加：set.add(E e)；set.add(2)；
（2）输出：
HashSet会去重，但是是无序的，即存值的顺序和 弹出的顺序 不一致，而且没有自置的排序算法。
通常是存进ArrayList中，再排序(list不去重，但是有序)
递归：
ArrayList<Integer> list=new List<>();
for(Integer value：set){
list.add(value);
}
Collections.sort(list)；
（3）清除：set.remove(E e)； set.remove(1)；
(4)判断是否存在set.contains(E e)；
40、最大子序和：
例子1：{-1}： -1
例子2：{1,-4,2,7,-3}：9
（1）累加，抛弃法：
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length==0) return 0;
int max=nums[0];
int sum=0;
for(int i=0;i<nums.length;i++){
if(sum<=0){
sum=nums[i];
}else{
sum+=nums[i];
}
if(sum>max){
max=sum;
}
}
return max;
}
}
41、和40题有点像，求字符串中包含的最长不重复子串的长度。
（1）滑动窗口思想：
用set当作窗口存，如果重复了，窗口头右移一位；如果不重复，当前值加入窗口set，窗口大小j-i与max比，取最大。
public int GetNum(String s){
if(s==null) return 0;
Set<Character> set=new HashSet<>();
int i=0;//窗口头
int j=0; //窗口尾
int max=0;
while(i<s.length()&&j<s.length()){
if(!set.contains(s.charAt(j)){
set.add(s.charAt(j));
j++;
if(j-i>max) {max=j-i;}
}else{
set.remove(s.charAt(i));
i++;
}
}
}
42、关于map的遍历：
第一种：Map<Integer,String> map = new HashMap<Integer, String>();
for (Map.Entry<Integer, String> entry : map.entrySet()) {
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
第二种：只需要map中的键或者值，你可以通过keySet或values来实现遍历，而不是用entrySet：
//遍历map中的键
for (Integer key : map.keySet()) {
System.out.println("Key = " + key);
}
//遍历map中的值
for (String value : map.values()) {
System.out.println("Value = " + value);
}
第三种：使用迭代器Iterator：
Map<Integer,String> map = new HashMap<Integer, String>();
Iterator<Map.Entry<Integer, String>> entries = map.entrySet().iterator();
while (entries.hasNext()) {
Map.Entry<Integer, String> entry = entries.next();
System.out.println("Key = " + entry.getKey() + ", Value = " + entry.getValue());
}
第四种：通过键找值遍历（效率低）
for (Integer key : map.keySet()) {
Integer value = map.get(key);
System.out.println("Key = " + key + ", Value = " + value);
43、有效的括号：
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
思路：用hashmap存储符号的对应关系，闭括号为key，开括号为value；再用一个stack存储，字符串中开括号入栈，闭括号出栈；如果map中没有这个key，即遇到开符号(、[、{,则入栈；遇到闭符号，则取栈顶，看是不是符合其map.get(key)对应的value值
class Solution {
public boolean isValid(String s) {
HashMap<Character,Character> map=new HashMap<>();
map.put(')','(');
map.put(']','[');
map.put('}','{');
/*如果map中没有这个key，即遇到开符号(、[、{,则入栈；
遇到闭符号，则取栈顶，看是不是符合其map.get(key)对应的value值
*/
Stack<Character> stack=new Stack<>();
for(int i=0;i<s.length();i++){
char ch=s.charAt(i);
if(map.containsKey(ch)){
char top=stack.empty()?'#':stack.pop();
if(top!=map.get(ch)){
return false;
}
}else{
stack.push(ch);
}
}
return stack.isEmpty();
}
}
44、一些方法应用：
a. 其他类型转换为String类型：
String.valueOf(a) a可以是boolean类型、char、char[]、int、long、double、float、甚至是Object类
则转换后输出s，也会得到原值【char[] ch={‘a','b','c','d'}；】
但不可以是int[],double[]...这些用这个方法不会报错，但输出s是类似哈希值的东西（地址）
b. 数组复制：一个数组直接复制到另一个数组
System.arraycopy（原数组，原数组复制位置，新数组，新数组复制位置，复制串长度）
System.arraycopy(digits,0,res,1,digits.length);
题目：加一
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储一个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
思路：用反向迭代的方法，1.循环从最后一位开始逐位执行加一操作：
1.1 如果该位置加之后的值没有进位(<10)，则直接返回此时的整个数组；
1.2 如果该位置加之后的值产生了进位（=10），设该位为0，判断前一位是否为首位
1.2.1 前一位不是首位，则前一位的数字加一，重复循环判断前一位的值。
1.2.2 前一位是首位，则继续循环，下一轮循环会退出。
2.循环结束，仍未返回，说明首位也产生了进位。重新定义一个数组（长度比原先的大一位），将数组首位设为1，并将原数组直接复制到该数组的1到末位。返回。
public int[] plusOne(int[] digits) {
digits[digits.length-1]+=1;
for(int i=digits.length-1;i>=0;i--){
if(digits[i]<10){
//说明此时加一已经不用再进位了，可以直接返回
return digits;
}else{
/*说明加一之后需要进位，那么当前位为0,如果前一位不是第一位的话，前一位加1；
前一位是第一位，则继续循环，循环退出。
*/
digits[i]=0;
if(i!=0){
digits[i-1]+=1;
}
}
}
/*当执行完循环还未返回，说明首位也进位，则要重新定义一个大一位的数组，将首位设置为1，
其他位置直接将原先数组的值复制过来
*/
int[] res=new int[digits.length+1];
res[0]=1;
System.arraycopy(digits,0,res,1,digits.length);
return res;
}
