代码面试最常用的5大算法-阿里云开发者社区

开发者社区> 桃子红了呐> 正文

代码面试最常用的5大算法

简介:
+关注继续查看

1.String/Array

复制代码
toCharArray() //get char array of a String
Arrays.sort()  //sort an array
Arrays.toString(char[] a) //convert to string
charAt(int x) //get a char at the specific index
length() //string length
length //array size 
substring(int beginIndex) 
substring(int beginIndex, int endIndex)
Integer.valueOf()//string to integer
String.valueOf()/integer to string
复制代码

2.链表

在Java中实现链表是非常简单的,每个节点都有一个值,然后把它链接到下一个节点。 

复制代码
class Node {
    int val;
    Node next;
 
    Node(int x) {
        val = x;
        next = null;
    }
}
复制代码

比较流行的两个链表例子就是栈和队列。

栈Stack

复制代码
class Stack{
    Node top; 
 
    public Node peek(){
        if(top != null){
            return top;
        }
 
        return null;
    }
 
    public Node pop(){
        if(top == null){
            return null;
        }else{
            Node temp = new Node(top.val);
            top = top.next;
            return temp;    
        }
    }
 
    public void push(Node n){
        if(n != null){
            n.next = top;
            top = n;
        }
    }
}
复制代码

队列Queue

 

复制代码
class Queue{
    Node first, last;
 
    public void enqueue(Node n){
        if(first == null){
            first = n;
            last = first;
        }else{
            last.next = n;
            last = n;
        }
    }
 
    public Node dequeue(){
        if(first == null){
            return null;
        }else{
            Node temp = new Node(first.val);
            first = first.next;
            return temp;
        }    
    }
}
复制代码

3.树&堆

这里的树通常是指二叉树。

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
} 

下面是一些与二叉树有关的概念:

 

 

  • 二叉树搜索:对于所有节点,顺序是:left children <= current node <= right children;
  • 平衡vs.非平衡:它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1,并且左右两个子树都是一棵平衡二叉树;
  • 满二叉树:除最后一层无任何子节点外,每一层上的所有结点都有两个子结点;
  • 完美二叉树(Perfect Binary Tree):一个满二叉树,所有叶子都在同一个深度或同一级,并且每个父节点都有两个子节点;
  • 完全二叉树:若设二叉树的深度为h,除第 h 层外,其它各层 (1~h-1) 的结点数都达到最大个数,第 h 层所有的结点都连续集中在最左边,这就是完全二叉树。

 

堆(Heap)是一个基于树的数据结构,也可以称为优先队列( PriorityQueue),在队列中,调度程序反复提取队列中第一个作业并运行,因而实际情况中某些时间较短的任务将等待很长时间才能结束,或者某些不短小,但具有重要性的作业,同样应当具有优先权。堆即为解决此类问题设计的一种数据结构。

 

4.排序

不同排序算法的时间复杂度,大家可以到wiki上查看它们的基本思想。

 

BinSort、Radix Sort和CountSort使用了不同的假设,所有,它们不是一般的排序方法。 

5.递归和迭代

下面通过一个例子来说明什么是递归。

问题:

这里有n个台阶,每次能爬1或2节,请问有多少种爬法?

步骤1:查找n和n-1之间的关系

为了获得n,这里有两种方法:一个是从第一节台阶到n-1或者从2到n-2。如果f(n)种爬法刚好是爬到n节,那么f(n)=f(n-1)+f(n-2)。 

步骤2:确保开始条件是正确的

f(0) = 0; 
f(1) = 1; 

1
2
3
4
5
public static int f(int n){
    if(n <= 2) return n;
    int x = f(n-1) + f(n-2);
    return x;
}

递归方法的时间复杂度指数为n,这里会有很多冗余计算。

 

 

 

1
2
3
4
f(5)
f(4) + f(3)
f(3) + f(2) + f(2) + f(1)
f(2) + f(1) + f(2) + f(2) + f(1)

该递归可以很简单地转换为迭代。 

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public static int f(int n) {
  
    if (n <= 2){
        return n;
    }
  
    int first = 1, second = 2;
    int third = 0;
  
    for (int i = 3; i <= n; i++) {
        third = first + second;
        first = second;
        second = third;
    }
  
    return third;
} 本文转自TBHacker博客园博客,原文链接:http://www.cnblogs.com/jiqing9006/p/3658017.html,如需转载请自行联系原作者

版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
常用算法和复杂度总结
一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) ...
3161 0
VB编程:Me关键字的使用&VB常用颜色代码
VB编程:Me关键字的使用&VB常用颜色代码
10 0
Java代码复用的三种常用方式:继承、组合和代理(2)
Java代码复用的三种常用方式:继承、组合和代理
10 0
jquery常用代码片段
1)判断一个元素是否存在 使用jQuery判断元素是否存在,非常的简单。对于一个jQuery对象,我们只需要用length属性即可判断元素是否存在,如果存在肯定是大于0,示例代码: 判断这个图片是否存在,如果存在在把这个图片替换 $(document).
803 0
【论文阅读心得】图像识别中一个常用词的中英文释义&mdash;&mdash;artifact
作者:gnuhpc 出处:http://www.cnblogs.com/gnuhpc/ artifact 非自然信号,人工制品 In video systems, something unnatural or unintended observed in the reproduction of an image by the system. 在视频系统中,图象重显时观察到的反常的或非有意安排的某些东西。
717 0
4269
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载