这篇文章,在我之前的博客地址中,很早之前写过的(源于从外国的文章中看到的,所以算是转载吧)。今天拿出来,已做备份只用。主要讲解的是:字符串,链表,树,图,排序,递归 vs. 迭代,动态规划,位操作,概率问题,排列组合
使用的开发语言:java(有兴趣的朋友可以用c/c++尝试一下)。
1.字符串和数组应用
首先需要注意的是和C++不同,Java字符串不是char数组。没有IDE代码自动补全功能,应该记住下面的这些常用的方法。
toCharArray() //获得字符串对应的char数组 Arrays.sort() //数组排序 Arrays.toString(char[] a) //数组转成字符串 charAt(int x) //获得某个索引处的字符 length() //字符串长度 length //数组大小 substring(int beginIndex) substring(int beginIndex, int endIndex) Integer.valueOf() //string to integer String.valueOf() /integer to string
字符串和数组本身很简单,但是相关的问题需要更复杂的算法来解决。
经典题目: Evaluate Reverse Polish Notation, Longest Palindromic Substring, Word Break, Word Ladder.
2.链表
在Java中,链表的实现非常简单,每个节点Node都有一个值val和指向下个节点的链接next。
class Node { int val; Node next; Node(int x) { val = x; next = null; } }链表两个著名的应用是栈Stack和队列Queue。在Java标准库都都有实现,一个是Stack,另一个是LinkedList(Queue是它实现的接口)。
经典题目: Add Two Numbers, Reorder List, Linked List Cycle, Copy List with Random Pointer.
3. 树
这里的树通常是指二叉树,每个节点都包含一个左孩子节点和右孩子节点,如:
class TreeNode{ int value; TreeNode left; TreeNode right; }下面是与树相关的一些概念:
- 二叉搜索树:左结点 <= 中结点 <= 右结点
- 平衡 vs. 非平衡:平衡二叉树中,每个节点的左右子树的深度相差至多为1(1或0)。
- 满二叉树(Full Binary Tree):除叶子节点以为的每个节点都有两个孩子。
- 完美二叉树(Perfect Binary Tree):是具有下列性质的满二叉树:所有的叶子节点都有相同的深度或 处在同一层次,且每个父节点都必须有两个孩子。
- 完全二叉树(Complete Binary Tree):二叉树中,可能除了最后一个,每一层都被完全填满,且所有节点都必须尽可能想左靠。
- 经典题目:Binary Tree Preorder Traversal , Binary Tree Inorder Traversal, Binary Tree Postorder Traversal,Word Ladder.
4. 图
图相关的问题主要集中在深度优先搜索(depth first search)和广度优先搜索(breath first search)。深度优先搜索很简单,广度优先要注意使用queue. 下面是一个简单的用队列Queue实现广度优先搜索。
public static void breathFirstSearch(GraphNode root, int x){ if(root.val == x) System.out.println("find in root"); Queue queue = new Queue(); root.visited = true; queue.enqueue(root); while(queue.first != null){ GraphNode c = (GraphNode) queue.dequeue(); for(GraphNode n: c.neighbors){ if(!n.visited){ System.out.print(n + " "); n.visited = true; if(n.val == x) System.out.println("Find "+n); queue.enqueue(n); } } } }
5. 排序
下面是不同排序算法的时间复杂度,你可以去wiki看一下这些算法的基本思想。
Algorithm | Average Time | Worst Time | Space |
冒泡排序(Bubble sort) | n^2 | n^2 | 1 |
选择排序(Selection sort) | n^2 | n^2 | 1 |
插入排序(Insertion sort) | n^2 | n^2 | |
快速排序(Quick sort) | n log(n) | n^2 | |
归并排序(Merge sort) | n log(n) | n log(n) | depends |
另外还有BinSort, RadixSort和CountSort 三种比较特殊的排序。
经典题目: Mergesort, Quicksort, InsertionSort.
6.递归 vs. 迭代
问题:有n步台阶,一次只能上1步或2步,共有多少种走法。
步骤1:找到走完前n步台阶和前n-1步台阶之间的关系。
为了走完n步台阶,只有两种方法:从n-1步台阶爬1步走到或从n-2步台阶处爬2步走到。如果f(n)是爬到第n步台阶的方法数,那么f(n) = f(n-1) + f(n-2)。
步骤2: 确保开始条件是正确的。
f(0) = 0;
f(1) = 1;
public static int f(int n){ if(n <= 2) return n; int x = f(n-1) + f(n-2); return x; }递归方法的时间复杂度是指数级,因为有很多冗余的计算:
f(5) f(4) + f(3) f(3) + f(2) + f(2) + f(1) f(2) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1) f(1) + f(0) + f(1) + f(1) + f(0) + f(1) + f(0) + f(1)直接的想法是将递归转换为迭代:
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; }
典型例子:Recursion vs Iteration。
7.动态规划
动态规划是解决下面这些性质类问题的技术:
一个问题可以通过更小子问题的解决方法来解决,或者说问题的最优解包含了其子问题的最优解
有些子问题的解可能需要计算多次
子问题的解存储在一张表格里,这样每个子问题只用计算一次
需要额外的空间以节省时间
爬台阶问题完全符合上面的四条性质,因此可以用动态规划法来解决。
public static int[] A = new int[100]; public static int f3(int n) { if (n <= 2) A[n]= n; if(A[n] > 0) return A[n]; else A[n] = f3(n-1) + f3(n-2);//store results so only calculate once! return A[n]; }
8. 位操作
常用位操作符:
OR (|) | AND (&) | XOR (^) | Left Shift (<<) | Right Shift (>>) | Not (~) |
1|0=1 | 1&0=0 | 1^0=1 | 0010<<2=1000 | 1100>>2=0011 | ~1=0 |
用一个题目来理解这些操作 ,获得给定数字n的第i位:(i从0计数并从右边开始)。如下:
public static boolean getBit(int num, int i){ int result = num & (1<<i); if(result == 0){ return false; }else{ return true; }
9.概率问题
解决概率相关的问题通常需要先分析问题,下面是一个这类问题的简单例子:
一个房间里有50个人,那么至少有两个人生日相同的概率是多少?(忽略闰年的事实,也就是一年365天)
计算某些事情的概率很多时候都可以转换成先计算其相对面。在这个例子里,我们可以计算所有人生日都互不相同的概率,也就是:365/365 * 364/365 * 363/365 * … * (365-49)/365,这样至少两个人生日相同的概率就是1 – 这个值。
public static double caculateProbability(int n){ double x = 1; for(int i=0; i<n; i++){ x *= (365.0-i)/365.0; } double pro = Math.round((1-x) * 100); return pro/100; }
10.排列和组合
组合和排列的区别在于次序是否关键。
相关推荐
Java常用类与基础API--String常见算法题目
内容包括但不限于数组、链表、栈、队列、树、图、排序和搜索算法,以及常见的算法问题解决策略。此外,还提供了大量的实战示例和面试中常见问题的解析,帮助读者深化理解并实际应用。 适用人群: 本资源适合有一定...
Java基础知识,其中包括基本概念+运算符+判断和循环+循环高级和数组+方法+综合练习+面向对象+面向对象综合训练+字符串+集合&学生管理系统+学生管理系统升级版+面向对象进阶(static&继承+多态+包&final&权限+抽象类&...
面试算法题总结
50道最基础,最常见,leetcode 算法题答案总结,提供标准的参考答案以及时间复杂度和空间复杂度的讲解
常见算法面试宝典,原理+代码示例!
python常见排序算法基础教程.docx
⼈⼯智能之机器学习常见算法 摘要 摘要 之前⼀直对机器学习很感兴趣,⼀直没时间去研究,今天刚好是周末,有时间去各⼤技术论坛看看,刚好看到⼀篇关于机器学习不错的⽂章,在这⾥ 就分享给⼤家了. 机器学习⽆疑是当前...
下篇用5章的篇幅介绍了用数据结构解决实际问题的相关程序,包括解决数学问题、数据结构问题、算法经典问题等内容以及信息学奥赛部分试题的程序,最后一章介绍了与算法和数据结构相关的常见面试题。
含一些常见算法,面试必备,供找工作的大侠参考。
JavaSE基础常见算法的解释与讲解
本资源主要是汇集了自己刷题时总结下来的一些经典题目:包括二分、字符串替换、DP问题、动态规划、最长子序列、DFS、BFS、回溯算法等,旨在记录和查看复习,为了不断提升,不断更新补充。也包括链表的一些基础,有...
《Java常用算法手册》分三篇,共13章,分别介绍了算法基础、算法应用和算法面试题。首先介绍了算法概述,然后重点分析了数据结构和基本算法思想;接着,详细讲解了算法在排序、查找、数学计算、数论、历史趣题、游戏...
《Java 基础核心总结》 Java 概述 什么是 Java2 Java 的特点Java 开发环境 JDK JRE Java 开发环境配置 Java 基本语法 数据类型基础语法运算符 Java 执行控制流程条件语句 if 条件语句 if...else 条件语句if...else ...
机器学习基础算法
基于python实现的渗透测试常用加解密算法源码+项目说明.zip 一些渗透测试相关的加解密方法的实现,封装成类或函数,方便编写 Burpy 脚本的时候直接调用 基于Python3实现。 例如网站登录密码加密的rsa、aes。 金融...
很基础很牛逼的51种经典算法详解,好好学习,天天向上
基于python实现常见机器学习算法源码+代码详细注释(包括逻辑回归、K均值、K进邻、贝叶斯、决策树).zip 【资源介绍】 该项目是个人学习项目,代码都经过调试测试,确保可以运行!欢迎下载使用,可用于小白学习、进阶...
AS3、flash基础知识,非常适合新手学习。