数字在升序 数组中出现的次数
统计一个数字在升序数组中出现的次数。
示例1
输入：[1,2,3,3,3,3,4,5],3
返回值：4
public class Solution {
public int GetNumberOfK(int [] array , int k) {
int a=Binary(array,k);
int b=Binary(array,k+1);
return b-a;
}
private int Binary(int [] n,int m)
{
int l=0;
int h=n.length;
while(l<h)
{
int mid=l+(h-l)/2;
if(n[mid]>=m)
h=mid;
else
l=mid+1;
}
return l;
}
}二叉搜索树的第k小节点
给定一棵二叉搜索树，请找出其中的第k小的结点。
示例1
输入：{5,3,7,2,4,6,8},3
返回值：{4}
说明：按结点数值大小顺序第三小结点的值为4
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
//利用中序遍历
import java.util.Stack;
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k)
{
if (pRoot == null || k <= 0 )
return null;
int i = 1;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode p = pRoot;
while (p != null || !stack.isEmpty())
{
while (p != null)
{
stack.push(p);
p = p.left;
}
p = stack.pop();
if (i++ ==k)
return p;
p = p.right;
}
return null;
}
}二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
示例1
输入：{1,2,3,4,5,#,6,#,#,7}
返回值：4
/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
//传统方法
import java.util.LinkedList;
import java.util.Queue;
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
Queue<TreeNode> q=new LinkedList<>();
q.add(root);
int count=0,depth=0,countnext=1;
while(q.size()>0)
{
TreeNode t=q.poll();
count++;
if(t.left!=null)
q.add(t.left);
if(t.right!=null)
q.add(t.right);
if(count==countnext)
{
count=0;
countnext=q.size();
depth++;
}
}
return depth;
}
}
//利用递归
public class Solution {
public int TreeDepth(TreeNode root) {
if(root==null)
return 0;
int nleft=TreeDepth(root.left);
int nright=TreeDepth(root.right);
return nleft>nright?nleft+1:nright+1;
}
}数组中只出现一次的两个数字
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
//num1,num2分别为长度为1的数组。传出参数
//将num1[0],num2[0]设置为返回结果
import java.util.Map;
import java.util.HashMap;
public class Solution {
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
Map<Integer,Integer> map= new HashMap<>();
for(int i:array)
{
if(map.containsKey(i))
map.remove(i);
else
map.put(i,i);
}
int c=0;
for (Map.Entry<Integer, Integer> entry : map.entrySet())
{
if(c==0)
{
num1[0]=entry.getKey();
c++;
}
else
num2[0]=entry.getKey();
}
}
}和为s的连续整数序列
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
返回值描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
示例1
输入：9
返回值：[[2,3,4],[4,5]]
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int ssum) {
ArrayList<ArrayList<Integer>> b=new ArrayList<>();
int f=1,l=2;
while(f<=ssum/2)
{
int sum=(f+l)*(l-f+1)/2;
if(sum==ssum)
{
ArrayList<Integer> a=new ArrayList<>();
for(int j=f;j<=l;j++)
a.add(j);
b.add(a);
f++;
l++;
}
else if(sum<ssum)
l++;
else
f++;
}
return b;
}
}滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
窗口大于数组长度的时候，返回空
示例1
输入：[2,3,4,2,6,2,5,1],3
返回值：[4,4,6,6,6,5]
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size)
{
ArrayList<Integer> list=new ArrayList<>();
if(num==null)
return null;
if(size==0)
return list;
for(int i=0;i<=num.length-size;i++)
{
int max=num[i];
for(int j=1;j<size;j++)
{
if(num[i+j]>max)
max=num[i+j];
}
list.add(max);
}
return list;
}
}扑克牌中的顺子
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
示例1
输入：[0,3,2,6,4]
返回值：true
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers.length!=5)
return false;
int[] a=new int[14];
boolean flag=false;
for(int i=0;i<14;i++)
a[i]=0;
for(int i=0;i<numbers.length;i++)
a[numbers[i]]++;
int min=0,max=0;
for(int i=1;i<14;i++)
{
if(a[i]>1)
return false;
if(a[i]!=0 && min==0)
min=i;
if(a[i]!=0 && i>max)
max=i;
}
if(max-min<5)
flag=true;
return flag;
}
}圆圈中剩下的数
每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
如果没有小朋友，请返回-1
示例1
输入：5,3
返回值：3
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n<1 || m<1)
return -1;
int i=-1,count=n,step=0;
int[] a=new int[n];
while(count>0)
{
i++;
if(i>=n)
i=0;
if(a[i]==-1)
continue;
step++;
if(step==m)
{
a[i]=-1;
step=0;
count--;
}
}
return i;
}
}
京公网安备 11010502036488号