文档章节

字符串、数组、链表、栈、二叉树

Jansens
 Jansens
发布于 2016/11/05 15:12
字数 1390
阅读 55
收藏 0

1.1 字符串 确定两个字符串同构

StringA的字符重新排列后,能否变成StringB 详细

import java.util.*;

public class Same {
    public boolean checkSam(String stringA, String stringB) {
        // write code here
        if(stringA.length()!=stringB.length())
            return false;
        int[] recoder = new int[256];
        for(int i=0;i<stringA.length();i++){
            recoder[stringA.charAt(i)]++;
            recoder[stringB.charAt(i)]--;
        }
        for(int i=0;i<256;i++){
            if(recoder[i]!=0)
                return false;
        }
        return true;
    }
}

tips:

  1. 第一步先判断两个字符串的长度是否相等

  2. 字符串的长度为.length()有括号

1.2 数组 清除二维数组行列

将数组中所有为0的元素所在的行列都置为0

import java.util.*;

public class Clearer {
    public int[][] clearZero(int[][] mat, int n) {
        // write code here
        boolean[] row = new boolean[n];
        boolean[] col = new boolean[n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(mat[i][j] == 0){
                    row[i] = true;
                    col[j] = true;
                }
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(row[i]||col[j]){
                    mat[i][j]=0;
                }
            }
        }       
        return mat;
    }
}

tips

  • 读数据和写数据必须分开。

1.3字符串 翻转子串

检查string2是否为sting1旋转而成

public boolean checkReverseEqual(String s1, String s2) {
        // write code here
        if (s1 == null || s2 == null || s1.length() != s2.length())
            return false;
        return (s1+s1).contains(s2);
    }

tips

  • 旋转问题:先将string1 收尾拼接,再检查新的字符串是否含有s2.

1.4链表 链表中倒数第k个结点

输入一个链表,输出该链表中倒数第k个结点

public ListNode FindKthToTail(ListNode head,int k) {
        //需不需要new???
        //ListNode headp = new ListNode(-1);
        if(head == null||k<1) return null;
        ListNode tailp = head;
        ListNode headp = head;
        for(int i=1;i<k;i++){
            tailp = tailp.next;
            if(tailp == null) return null;
        }
        while(tailp.next != null){
            tailp = tailp.next;
            headp = headp.next;
        }
        return headp;
    }

tips

  • new一个obj1对象,然后obj1 = obj2 ,错错错

  • 核心思想:两个指针,相差k-1,tail指到尾,则前指针正好找到想要的位置。

  • 另外一种思路是采用递归,head==null时,将count置零,之后count++。

1.5链表 访问单个节点的删除

删除单向链表中间的某个结点,并且只能访问该结点

public boolean removeNode(ListNode pNode) {
        // write code here
        if(pNode == null || pNode.next == null)
            return false;
        pNode.val = pNode.next.val;
        pNode.next = pNode.next.next;
        return true;
    }

tips

  • 只能访问该节点,则不能删除该节点,因为删除之后则链表与前面断开链接,所有只能修改该节点的值为下一节点的值,再指向下下节点。

1.6链表 链式A+B

链表头为个位,A{1,2,3},B{3,2,1},则返回{4,4,4}

public ListNode plusAB(ListNode a, ListNode b) {
        // write code here
        int flag = 0;
        ListNode result = new ListNode(-1);
        ListNode phead = result;
        while(a!=null || b!=null || flag!=0){
            int sum = flag;
            if(a!=null){
                sum+=a.val;
                a = a.next;
            }
            if(b!=null){
                sum+=b.val;
                b = b.next;
            }
            int val = sum%10;
            flag = sum/10;
            result.next = new ListNode(val);
            result = result.next;
        }
        return phead.next;
    }

tips

  • 之前有一个想法就是先相加公共部分,然后处理多出来的部分,这样处理起来非常麻烦。

  • 如果链表头为高位,则采用栈方法处理。先对两个链表分别压栈,最后弾栈,直至两个都为空并且进位等于0。

1.7链表 回文链表

检查链表是否为回文,{1,2,3,2,1},返回true

 public boolean isPalindrome(ListNode pHead) {
        // 快慢指针
        ListNode fast = pHead;
        ListNode slow = pHead;
        Stack<Integer> stack = new Stack<>();
        while(fast != null && fast.next != null){
            stack.push(slow.val);
            slow = slow.next;
            fast = fast.next.next;     
        }
        if(fast != null)
              slow = slow.next;
        while(slow != null){
            if(slow.val != stack.pop())
                return false;
            slow = slow.next;
        }
        return true;      
    }
    
    public boolean isPalindrome(ListNode pHead) {
        //双栈
        if(pHead == null || pHead.next == null)
            return true;
        Stack stack1 = new Stack();        
        Stack stack2 = new Stack();

        while(pHead!=null){
            stack1.push(pHead.val);
            pHead = pHead.next;    
        }
        while(stack1.size()>stack2.size()){
            stack2.push(stack1.pop());
        }
        if(stack2.size()>stack1.size()){
            stack2.pop();
        }
        while(!stack1.empty() && !stack2.empty()){
            if(stack1.pop() != stack2.pop())
                return false;
        }
        return true;
            
    }

tips

  • 方案1:用快慢指针,当快指针指向链表尾部时,慢指针正好指向中部,并且将慢指针压栈,这里要注意奇偶数的区别。

  • 方案2:先将所有链表数据压到栈1,然后弹出一半到栈2,两者再进行比较。不过该方法显然没有方法一效率高。

1.8栈和队列 用两个栈实现队列

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
     
    public void push(int node) {
        stack1.push(node);
    }
     
    public int pop() {
        if(stack1.isEmpty() && stack2.isEmpty()){
            throw new RuntimeException("the queue is empty!");
        }
        if(stack2.isEmpty()){
          while(!stack1.isEmpty()){
              stack2.push(stack1.pop());
          }
        }
        return stack2.pop();
         
    }
}

tips

  • throw new RuntimeException("the queue is empty!");下次可以用

1.9栈和队列 双栈排序

要求只有一个缓存栈,并且排好序的栈最大元素在栈顶。

 public ArrayList<Integer> twoStacksSort(int[] numbers) {
        // write code here
        ArrayList<Integer> arrayList = new ArrayList();
        Stack<Integer> stack1 = new Stack();
        Stack<Integer> stack2 = new Stack();
         
        for(int i=0;i<numbers.length;i++){
            stack1.push(numbers[i]);
        }
         
        while(!stack1.isEmpty()){
            int temp = stack1.pop();
            while(!stack2.isEmpty() && stack2.peek()>temp){
                stack1.push(stack2.pop());
            }
            stack2.push(temp);
        }
         
        while(!stack2.isEmpty()){
            arrayList.add(stack2.pop());
        }
        return arrayList;
    }

tips

while(!stack2.isEmpty() && stack2.peek()>temp){
        stack1.push(stack2.pop());
     }
stack2.push(temp);
  • 代码的简洁性!思维不要太僵硬,可以多层条件一起考虑,不必非要一层一层考虑分析。

  • 不要先考虑stack2是否为空,再嵌套考虑栈顶是否大于temp。。。

2.0 树 检查二叉树是否平衡

树的平衡指左右高度相差不能大于1

public boolean isBalance(TreeNode root) {
        // 遍历整个树的所有节点
        if(root == null)return true;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        int cha = Math.abs(left-right);
        if(cha>1)return false;
        else return true;
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        int right = getHeight(root.right);
        return Math.max(left,right)+1;
    }
  • 另一种解法:一边检查高度一边检查是否平衡

public boolean isBalance(TreeNode root) {
        // write code here
        if(root == null)return true;
        if(getHeight(root) == -1)return false;
        return true;
    }
    public int getHeight(TreeNode root){
        if(root == null) return 0;
        int left = getHeight(root.left);
        if(left == -1) return -1;
        int right = getHeight(root.right);
        if(right == -1) return -1;
        if(Math.abs(left-right)>1) return -1;
        else return Math.max(left,right)+1;
    }

tips

  • 这样的改进的好处在于不用遍历所有的树节点

© 著作权归作者所有

Jansens
粉丝 10
博文 53
码字总数 128340
作品 0
闸北
高级程序员
私信 提问
【剑指Offer】Java、Python题解

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 https://blog.csdn.net/meiqi0538/article/details/98089913 本文首发于我的个人博客:AIAS编...

皮乾东
08/01
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
2018/06/03
0
0
《程序员代码面试指南》Python实现(个人读书笔记)

说明   最近一直在读左神的书——《程序员代码面试指南—IT名企算法与数据结构题目最优解》,为了记录自己的学习成果,并且方便以后查看,将自己读书时的想法与使用python实现的代码记录在...

qq_34342154
2017/09/09
0
0
Android 面试文档分享

一、概述 最近在准备面试的东西,整理了一些读书笔记分享给各位 百度网盘地址,大家可以自由下载,以下内容完全原创。 前两部分是对于一些 经典书籍的读书笔记 和 面试题,都是上学看书的时候...

泽毛
2017/11/10
0
0
【剑指offer纪念版】-- 面试题目录

2.实现Singleton模式 3.二维数组中的查找 4.替换空格 5.从尾到头打印链表 6.重建二叉树 7.用两个栈实现队列 8.旋转数组的最小数字 9.斐波那契数列 【剑指offer纪念版】--9 斐波那契数列 10.二...

细节探索者
01/19
56
0

没有更多内容

加载失败,请刷新页面

加载更多

JMM内存模型(一)&volatile关键字的可见性

在说这个之前,我想先说一下计算机的内存模型: CPU在执行的时候,肯定要有数据,而数据在内存中放着呢,这里的内存就是计算机的物理内存,刚开始还好,但是随着技术的发展,CPU处理的速度越...

走向人生巅峰的大路
18分钟前
40
0
你对AJAX认知有多少(2)?

接着昨日内容,我们几天继续探讨ajax的相关知识点 提到ajax下面几个问题又是必须要了解的啦~~~ 8、在浏览器端如何得到服务器端响应的XML数据。 通过XMLHttpRequest对象的responseXMl属性 9、 ...

理性思考
27分钟前
4
0
正则表达式基础(一)

1.转义 转义的作用: 当某个字符在表达式中具有特殊含义,例如字符串引号中出现了引号,为了可以使用这些字符本身,而不是使用其在表达式中的特殊含义,则需要通过转义符“\”来构建该字符转...

清自以敬
30分钟前
4
0
idea中@Data标签getset不起作用

背景:换电脑以后在idea中有@data注解都不生效 解决办法:idea装个插件 https://blog.csdn.net/seapeak007/article/details/72911529...

栾小糖
36分钟前
4
0
Apache Kudu 不能删除不存在的数据

使用Apache Kudu客户端,对KafkaConnect Sink 进行扩展。 使用的Apache Kudu 的Java 客户端。突然有天发现作业无法提交,一直报错。 后来才发现这是Kudu自身的一种校验机制。为了忽略这种校验...

吐槽的达达仔
46分钟前
5
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部