有趣的算法题-1
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了有趣的算法题-1,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含5093字,纯文字阅读大概需要8分钟。
内容图文
![有趣的算法题-1](/upload/InfoBanner/zyjiaocheng/855/974753f76e1a47729bfa090b3cd51c85.jpg)
java结构中:
Queue:offer,poll,isEmpty,peek
定义队列:Queue<Integer> queue = new LinkedList<Integer>();
Stack:push,pop,Empty,peek
一 二维数组中查找:
在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
1.int[][] array, target,row = (二维数组的行数) col = (二维数组的列数)
2.从左下角或右上角开始扫描。
3.当target == 值时返回,当target<值时row++,当target>值时col--;
4.row界为row<array.length, col >= 0;
二 :替换空格:
请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
1. 若改字符串是StringBuffer长度可变类型的,则可新建一个StringBuffer从前往后遍历,遇到' '时就改变。
2.若是不可变类型的,则先遍历一遍字符串,查看空格个数n,最后新建一个长度为2*n+str.length长度的数组存放新的数。
三:重建二叉树:
输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
1.用递归的方法:pre[0],用来建一个根节点root,查找在in[]数组中与pre[0]相同的index记为i。
2.root.left = construct(Arrays.copyOfRange(pre,1,i+1), Arrays.copyOfRange(in, 0, i))
3.root.right = construct(Arrays.copyOfRange(pre, i+1, pre.length), Arrays.copyOfRange(in, i+1, in.length))
5. return root
四:用两个栈来实现队列:
1.stack1 和stack2同时为空时队列为空。
2.stack1不空,stack2空时,把stack1的元素先搬到Stack2中。
3.进队列时,直接往stack1进就好。
五:二进制中1的个数:
输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。
1.public int NumberOf1(int n) {
int count = 0;
while(n != 0){
n = n & (n-1);
count++;
}
return count;
}
一个数减1后,最右边的那个1后边(包括自己)所有的0会变为1.
六:数值的整数次方
给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
class Solution {
public:
double Power(double base, int exponent) {
long long p = abs((long long)exponent);
double r = 1.0;
while(p){
if(p & 1) r *= base;
base *= base;
p >>= 1;
}
return exponent < 0 ? 1/ r : r;
}
};
七:递归法翻转链表
1.
public class Solution {
public ListNode ReverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode reverse = ReverseList(head.next);
head.next.next = head;
head.next = null;
return reverse;
}
}
八:树的子结构
输入两棵二叉树A,B,判断B是不是A的子结构。(ps:我们约定空树不是任意一个树的子结构)
1.用一个函数isSubTree判断以此root1, root2为根的树是否相同。
2.用一个函数HasSubTree寻找他们具有相同的根时进入isSubTree.
九:顺时针打印矩阵
1.用一个标记start记录打印的圈数.endrow = row - start -1; endcol = col - start - 1;
2.要考虑一个数,一行,一列的(两行,两列)的时候。
十:栈的压入和弹出顺序
1.pushA:入栈顺序,popA:出战顺序,push入栈指针,pop出栈指针
2.用push == pushA.length 判断是否入栈完毕
3.while循环出完相同的元素,用stack.peek前要判断stack.empty。否则空栈时用stack.peek会出错。
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public boolean IsPopOrder(int [] pushA,int [] popA) {
boolean isPossible = false;
if(pushA.length == 0 || popA.length == 0)
return isPossible;
Stack<Integer> stack = new Stack<Integer>();
int push = 0;
int pop = 0;
while(push != pushA.length){
stack.push(pushA[push]);
while(!stack.empty() && stack.peek() == popA[pop]){
pop++;
stack.pop();
}
push++;
}
if(stack.empty())
return true;
else
return false;
}
}
十:判断二叉树是否为后续遍历序列
1.sequence为要判断的序列。
2.取序列最后的一个数为root.
3.把序列从前往后遍历小于root为左,直到找到大于root的为第一个右子树的节点,将右子树节点与root比较。
4.若在右子树中还找到数字小于root,则判断这颗树为false,若start >= end时 证明判断到结束,这棵树为后续遍历二叉搜索树。
5.将左右子树分别遍历。
十一:二叉树中和为某一值的路径
import java.util.ArrayList;
/**
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>> FindPath(TreeNode root,int target) {
int countSum = 0;
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
if(root == null)
return list;
ArrayList<Integer> al = new ArrayList<Integer>();
findPath(root, target, countSum, al, list);
return list;
}
public void findPath(TreeNode root, int target, int countSum, ArrayList<Integer> al, ArrayList<ArrayList<Integer>> list){
if(root == null)
return;
countSum += root.val;
if(root.left == null && root.right == null){
if(target == countSum){
al.add(root.val);
list.add(new ArrayList<Integer>(al));
al.remove(al.size()-1);
}
return;
}
al.add(root.val);
findPath(root.left, target, countSum, al, list);
findPath(root.right, target, countSum, al, list);
al.remove(al.size()-1);
}
}
十二:复杂链表的复制:
输入一个复杂链表(每个节点中有节点值,以及两个指针,一个指向下一个节点,另一个特殊指针指向任意一个节点),返回结果为复制后复杂链表的head。(注意,输出结果中请不要返回参数中的节点引用,否则判题程序会直接返回空)
1.先将所有节点在原链表后面复制一个。
2.将random的指针根据上一个节点定义。
3.将链表断开。将复制的链表抽出来。
内容总结
以上是互联网集市为您收集整理的有趣的算法题-1全部内容,希望文章能够帮你解决有趣的算法题-1所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。