题目描述
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
//根据数学公式计算:(a1+an)*n/2=s n=an-a1+1
//(an+a1)*(an-a1+1)=2*s=k*l(k>l)
//an=(k+l-1)/2 a1=(k-l+1)/2
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>>list=new ArrayList<ArrayList<Integer>>();
if(sum<3)return list;
int s=(int) Math.sqrt(2*sum);
for(int i=s;i>=2;i--)
{
if(2*sum%i==0)
{
int d=2*sum/i;
if(d%2==0&&i%2!=0||d%2!=0&&i%2==0)
{
int a1=(d-i+1)/2;
int an=(d+i-1)/2;
ArrayList<Integer>temp=new ArrayList<Integer>();
for(int j=a1;j<=an;j++)
temp.add(j);
list.add(temp);
}
}
}
return list;
}
}
题目描述
输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
输出描述:
对应每个测试案例，输出两个数，小的先输出。
#数列满足递增，设两个头尾两个指针i和j，
#若ai + aj == sum，就是答案（相差越远乘积越小）
#若ai + aj > sum，aj肯定不是答案之一（前面已得出 i 前面的数已是不可能），j -= 1
#若ai + aj < sum，ai肯定不是答案之一（前面已得出 j 后面的数已是不可能），i += 1
#O(n)
typedef vector<int> vi;
class Solution {
public:
vi FindNumbersWithSum(const vi& a,int sum) {
vi res;
int n = a.size();
int i = 0, j = n - 1;
while(i < j){
if(a[i] + a[j] == sum){
res.push_back(a[i]);
res.push_back(a[j]);
break;
}
while(i < j && a[i] + a[j] > sum) --j;
while(i < j && a[i] + a[j] < sum) ++i;
}
return res;
}
};
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的运气如何。为了方便起见,你可以认为大小王是0。
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers.length != 5) return false;
int min = 14;
int max = -1;
int flag = 0;
for(int i = 0; i < numbers.length; i++) {
int number = numbers[i];
if(number < 0 || number > 13) return false;
if(number == 0) continue;
if(((flag >> number) & 1) == 1) return false;
flag |= (1 << number);
if(number > max) max = number;
if(number < min) min = number;
if(max - min >= 5) return false;
}
return true;
}
}
求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.sum = 0
def Sum_Solution(self, n):
# write code here
def qiusum(n):
self.sum += n
n -= 1
return n>0 and self.Sum_Solution(n)
qiusum(n)
return self.sum
输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。
/**
* Definition for binary tree
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
if(pre==null||in==null){
return null;
}
java.util.HashMap<Integer,Integer> map= new java.util.HashMap<Integer, Integer>();
for(int i=0;i<in.length;i++){
map.put(in[i],i);
}
return preIn(pre,0,pre.length-1,in,0,in.length-1,map);
}
public TreeNode preIn(int[] p,int pi,int pj,int[] n,int ni,int nj,java.util.HashMap<Integer,Integer> map){
if(pi>pj){
return null;
}
TreeNode head=new TreeNode(p[pi]);
int index=map.get(p[pi]);
head.left=preIn(p,pi+1,pi+index-ni,n,ni,index-1,map);
head.right=preIn(p,pi+index-ni+1,pj,n,index+1,nj,map);
return head;
}
}
一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
public class Solution {
public int JumpFloor(int target) {
if(target==1)
return 1;
if(target==2)
return 2;
return JumpFloor(target-1)+JumpFloor(target-2);
}
}
(不借助额外空间)输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public class Solution {
public void reOrderArray(int [] array) {
for(int i= 0;i<array.length-1;i++){
for(int j=0;j<array.length-1-i;j++){
if(array[j]%2==0&&array[j+1]%2==1){
int t = array[j];
array[j]=array[j+1];
array[j+1]=t;
}
}
}
}
}
