首页 / 算法 / 【精选】JAVA算法题（十九）
【精选】JAVA算法题（十九）
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【精选】JAVA算法题（十九），小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含5743字，纯文字阅读大概需要9分钟。
内容图文
一、重复的数
题目：
/** * 给定一个整数数组和一个整数 k，判断数组中是否存在两个不同的索引 i 和 j， * 使得 nums [i] = nums [j]，并且 i 和 j 的差的绝对值最大为 k。 * * 示例 1: * 输入: nums = [1,2,3,1], k = 3 * 输出: true * * 示例 2: * 输入: nums = [1,0,1,1], k = 1 * 输出: true * * 示例 3: * 输入: nums = [1,2,3,1,2,3], k = 2 * 输出: false */
同样是判断数组中是否出现过相同的数，但给限定了一个条件，两数所在索引差值不能超过给定整数
最笨的方法肯定是暴力for循环了，不解释，开始循环~
public boolean method1(int[] nums, int k) {
for (int i=0;i<nums.length-1;i++){
int end=i+k+1;
if (end>nums.length){
end=nums.length;
}
for (int j=i+1;j<end;j++){
if (nums[j]==nums[i]){
return true;
}
}
}
return false;
}
但这种办法肯定是低效的，对于判断有没有相同的元素来说Set是最适合的了。Set在添加元素时会返回是否已经包含该元素了，我们可以利用这个特点来进行判断是否含有重复元素。对于范围的限制可以使用remove来在遍历过程中不断移除前面的元素并添加后面的元素。
public boolean method2(int[] nums,int k){
HashSet<Integer> set = new HashSet<>();
int i = 0;
while (i < k && i < nums.length) {
if (!set.add(nums[i])) {
return true;
}
i++;
}
while (i < nums.length) {
if (!set.add(nums[i])) {
return true;
}
set.remove(nums[i - k]);
i++;
}
return false;
}
二、使用队列实现栈
题目：
/** * 使用队列实现栈的下列操作： * * push(x) -- 元素 x 入栈 * pop() -- 移除栈顶元素 * top() -- 获取栈顶元素 * empty() -- 返回栈是否为空 * * 注意: * * 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。 * 你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。 * 你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。 */
很简单，栈是先进后出，队列是先进先出，你只要保证先添加进来的放在最后面就和栈一样了。你可以做这样的操作，当添加进来一个新元素的时候把它之前的所有元素poll出来再放进队列，这样新添加进来的元素便在最前面了，最先出的也就是最新添加进来的。
import java.util.ArrayDeque;
public class ImplementStackUsingQueues {
ArrayDeque<Integer> queue=new ArrayDeque<Integer>();
/** Push element x onto stack. */
public void push(int x) {
queue.add(x);
for(int i=0;i<queue.size()-1;i++){
queue.add(queue.poll());
}
}
/** Removes the element on top of the stack and returns that element. */
public int pop() {
return queue.poll();
}
/** Get the top element. */
public int top() {
return queue.peek();
}
/** Returns whether the stack is empty. */
public boolean empty() {
return queue.isEmpty();
}
}
三、最近祖先
题目：
/** * 给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。 * 百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x， * 满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。” * <p> * 示例 1: * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8 * 输出: 6 * 解释: 节点 2 和节点 8 的最近公共祖先是 6。 * <p> * 示例 2: * 输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4 * 输出: 2 * 解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。 */public class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(int x) { val = x; } }
我开始用了一种比较笨的方法，先用递归把找到p,q的路径节点都存到list里面，然后去遍历list找到最近的相同的两个点，正序遍历的话比较慢，需要遍历完，倒序遍历会快一些。我这里使用的是正序遍历。
public TreeNode method1(TreeNode root, TreeNode p, TreeNode q) {
ArrayList<TreeNode> treeNodesp=new ArrayList<>();
ArrayList<TreeNode> treeNodesq=new ArrayList<>();
createRoute(root,p,treeNodesp);
createRoute(root,q,treeNodesq);
for (int i=0;i<treeNodesp.size();i++){
for (TreeNode treeNode:treeNodesq){
if (treeNodesp.get(i).equals(treeNode)){
return treeNode;
}
}
}
return null;
}
private boolean createRoute(TreeNode root, TreeNode p, ArrayList<TreeNode> treeNodesp) {
if (root==null)return false;
if (root==p){
treeNodesp.add(root);
return true;
}
if (createRoute(root.left,p,treeNodesp)){
treeNodesp.add(root);
return true;
}
if (createRoute(root.right,p,treeNodesp)){
treeNodesp.add(root);
return true;
}
return false;
}
题目中给了一个条件，二叉搜索树！二叉搜索树的特性，左边的数比右边小。可以利用这个特性来定位p,q所在的位置。找到一个节点的值的大小在p,q之间，这就是他俩最近的祖先节点。
public TreeNode method2(TreeNode root, TreeNode p, TreeNode q) {
while(root != null){
// 自上而下 找分界点
if(root.val > p.val && root.val > q.val) root = root.left; // 在右子树
else if(root.val < p.val && root.val < q.val) root = root.right; // 在左子树
else return root;
}
return null;
}
同样的思想，换一种写法
TreeNode res = null;
public TreeNode method3(TreeNode root, TreeNode p, TreeNode q) {
lca(root, p , q);
return res;
}
private void lca(TreeNode root, TreeNode p , TreeNode q){
if((root.val - p.val)*(root.val - q.val) <= 0){
res = root;
}else if(root.val < p.val && root.val < q.val){
lca(root.right, p , q);
}else{
lca(root.left, p , q);
}
}
四、删除节点
题目：
/** * 请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。 * 现有一个链表 -- head = [4,5,1,9] * * 示例 1: * 输入: head = [4,5,1,9], node = 5 * 输出: [4,1,9] * 解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9. * * 示例 2: * 输入: head = [4,5,1,9], node = 1 * 输出: [4,5,9] * 解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9. * * 说明: * 链表至少包含两个节点。 * 链表中所有节点的值都是唯一的。 * 给定的节点为非末尾节点并且一定是链表中的一个有效节点。 * 不要从你的函数中返回任何结果。 */public class ListNode { int val; ListNode next; ListNode(int x) { val = x; } }
题看起来很复杂，其实非常简单，就是给你一个节点，这个节点存在于链表中，且不是头尾节点，链表长度也至少为2，为你规避了一切异常情况，删节点嘛，很简单，赋值该节点的值为下一个节点的值，让该节点的下一个指向下一个的下一个。so easy!
public void method1(ListNode node) {
node.val = node.next.val;
node.next = node.next.next;
}
内容总结
以上是互联网集市为您收集整理的【精选】JAVA算法题（十九）全部内容，希望文章能够帮你解决【精选】JAVA算法题（十九）所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。