3.数组中的重复数字
1.用set
HashSet set1=new HashSet();
for(int i=0;i<array.length;i++){
if(set1.contains(array[i])){
System.out.println(array[i]);
break;
}else{
set1.add(array[i]);
}
}
2.用一个数组代替哈希表
int []array={2,3,1,0,2,5,3};
int []hasharray=new int[array.length];
for(int i=0;i<array.length;i++){
if(hasharray[array[i]]>0){
System.out.println(array[i]);
break;
}else{
hasharray[array[i]]++; }
}
4.二维数组中的查找
1.从右上角查找
2.查找的范围是从左下角到目前节点的小矩形，注意边界问题
public class LC04 {
public static void main(String[] args) {
int matrix[][]={{1, 4, 7, 11, 15},{2,5,8,12,19},
{3,6,9,16,22},{10,13,14,17,24},{18,21,23,26,30}};
boolean ans= findNumberIn2DArray(matrix,50);
System.out.println(ans);
}
public static boolean findNumberIn2DArray(int[][] matrix, int target) {
int row=matrix.length;
int column=matrix[0].length;
int temp=matrix[0][column-1]; //右上角的元素
int i=0,j=column-1;
while(i<row&&j>=0){ //判断不越界
if(matrix[i][j]==target){
return true;
}
if(matrix[i][j]>target){
j--;
}else{
i++;
}
}
return false;
}
}
5.替换空格
public class Solution {
public static String replaceSpace(String s) {
StringBuilder sb=new StringBuilder();
for(int i=0;i<s.length();i++){
char c1=s.charAt(i);
//if(" ".equals(c1)){
if(c1==' '){
sb.append("%20");
}else{
sb.append(s.charAt(i));
}
}
return sb.toString();
}
public static void main(String[] args) {
//String s1=replaceSpace("We are happy.");
String s1="We are happy";
String s2=s1.replace(" ","%20");
System.out.println(s2);
}
}
针对于" “.equals(c1)判定失败的问题：
System.out.println(” “.equals(” “)); //true
System.out.println(” ".equals(’ ')); //false
因为c1是字符，所以不行。
replace和replaceAll是JAVA中常用的替换字符的方法
public String replace(char oldChar, char newChar) 在字符串中用newChar字符替代oldChar字符，返回一个新的字符串
public String replaceAll(String regex,String replacement)使用给定的 replacement 字符串替换此字符串匹配给定的正则表达式的每个子字符串。
区别：
1)replace的参数是char和CharSequence，即可以支持字符的替换，也支持字符串的替换(CharSequence即字符串序列的意思,说白了也就是字符串)；
2)replaceAll的参数是regex，即基于正则表达式的替换，比如，可以通过replaceAll(“\d”, “*”)把一个字符串所有的数字字符都换成星号;
相同点：
都是全部替换，即把源字符串中的某一字符或字符串全部换成指定的字符或字符串，如果只想替换第一次出现的，可以使用replaceFirst()，这个方法也是基于规则表达式的替换，但与replaceAll()不同的是，只替换第一次出现的字符串；
另外，如果replaceAll()和replaceFirst()所用的参数据不是基于规则表达式的，则与replace()替换字符串的效果是一样的，即这两者也支持字符串的操作；
还有一点注意:：执行了替换操作后,源字符串的内容是没有发生改变的。
6.从尾到头打印链表
因为是反向的输出，所以用栈。递归也可以
public class LC06 {
public static class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
}
}
public static int[] reversePrint(ListNode head) {
LinkedList<Integer> stack=new LinkedList<Integer>();
while(head!=null){
stack.addLast(head.val);
stack.add(head.val);
head=head.next;
}
int []ans=new int[stack.size()];
for(int i=0;i<ans.length;i++){
ans[i]=stack.removeLast();
}
return ans;
}
public static void main(String[] args) {
ListNode node1=new ListNode(1);
ListNode node2=new ListNode(2);
ListNode node3=new ListNode(3);
node1.next=node2;
node2.next=node3;
int[] a=reversePrint(node1);
for (int i = 0; i < a.length; i++) {
System.out.println(a[i]);
}
}
}
7.重建二叉树（⭐）
树
~~~~~~~~
1
~~~~
2
~~~~
3
4
~~
5
~~
6
~~
7
前序 1 2 4 5 3 6 7
中序 4 2 5 1 6 3 7
public class LC07 {
public static class TreeNode{
int val;
TreeNode leftNode;
TreeNode rightNode;
TreeNode(int val){
this.val=val;
}
}
static HashMap<Integer, Integer> map = new HashMap<>();//标记中序遍历
static int []preorder;
public static TreeNode buildTree(int[] preorder, int[] inorder) {
LC07.preorder =preorder;
for (int i = 0; i < inorder.length; i++) {
//中序数组的值 -> 值在中序数组中的位置
map.put(inorder[i], i);
}
//三个索引分别为
//当前根的的索引
//递归树的左边界，即数组左边界
//递归树的右边界，即数组右边界
return recur(0,0,preorder.length-1);
}
static TreeNode recur(int pre_root, int in_left, int in_right){
if(in_left > in_right) return null;// 相等的话就是自己
TreeNode root = new TreeNode(preorder[pre_root]);//获取root节点
int idx = map.get(preorder[pre_root]); //获取在中序遍历中根节点所在索引，以方便获取左子树的数量
root.leftNode=recur(pre_root+1,in_left,idx-1);
//右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
root.rightNode=recur(pre_root+idx-in_left+1,idx+1,in_right);
return root;
}
public static void main(String[] args) {
int[] preorder={3,9,20,15,7};
int[] inorder={9,3,15,20,7};
TreeNode node1=buildTree(preorder,inorder);
bfs(node1);
}
public static void bfs(TreeNode node){
if(node!=null){
System.out.println(node.val);
bfs(node.leftNode);
bfs(node.rightNode);
}
}
}
8.用两个栈实现队列
如果出队列里有值，直接出值。出队列里没值了，再把入队列里的东西全塞进出队列里。文章来源：https://www.toymoban.com/news/detail-623327.html
public class LC09 {
static class CQueue {
Stack<Integer> A,B;
public CQueue() {
A=new Stack<>();
B=new Stack<>();
}
public void appendTail(int value) {
A.add(value);
}
public int deleteHead() {
if(!B.isEmpty()){
return B.pop();
}
if(A.isEmpty()) return -1;
while(!A.isEmpty()){
B.push(A.pop());
}
return B.pop();
}
}
public static void main(String[] args) {
CQueue q1=new CQueue();
q1.appendTail(3);
System.out.println(q1.deleteHead());
System.out.println(q1.deleteHead());
System.out.println(q1.deleteHead());
}
}
10.青蛙跳台阶
文章来源地址https://www.toymoban.com/news/detail-623327.html
public class LC10 {
public static int numWays(int n) {
if(n==0 || n==1) return 1;
int a=1,b=2;
int temp=2;
int ans1=b;
while(temp<n){
ans1=(a+b)%1000000007;
a=b;
b=ans1;
temp++;
}
return ans1;
}
public static void main(String[] args) {
System.out.println(numWays(7));
}
}
到了这里，关于剑指offer-3-10的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
