我点击提交的时候才发现没有c++的,结果悲剧了,没有提交上来。 #include <iostream> #include <string> #include <stdio.h> #include <stdlib.h>//#include <time.h> std::string test4(int m,int n , int t){ int * pa = (int*)malloc(sizeof(int)*m*n); for(int i = 0 ; i < m*n ;++i){ std::cin>>pa[i]; } int r_start = 0; int r_end = m;
//std::cout<<time(0)<<std::endl; //对行进行2分查找,通过第一个循环找出符合条件的行 while(r_start <= r_end){ int r_m = (r_start + r_end) / 2; int index = r_m * n ; if(pa[index + n - 1] < t){ r_start = r_m + 1; }else{ if(pa[index + n - 1] == t ){ return "True"; }else{ if(pa[index] == t){ return "True"; }else{ int c_start = 0; int c_end = n;
public class HelloWorld { public static void main(String[] args) {
java.util.Scanner scan = new java.util.Scanner(System.in);
int m = scan.nextInt();
int n = scan.nextInt();
int t = scan.nextInt();
int array[][] = new int[m][n];
int i=0,j=0;
for(;i<m;i++){
for(j=0;j<n;j++){
array[i][j] = scan.nextInt();
}
}
for(i=0,j=0;i<m-1 && j<n-1;){
if(array[i][j]==t || array[i+1][j]==t || array[i][j+1]==t){
System.out.println("True");return;
}else if(array[i+1][j]<t && array[i][j+1]<t){
if(array[i+1][j]>array[i][j+1]){
i++;
}else{
j++;
}
}else if(array[i+1][j]<t){
i++;
}else if(array[i][j+1]<t){
j++;
}else{
System.out.println("False");return;
}
}
System.out.println("False");
}}
int row = 0,col = arr[0].length - 1;
while(row < arr.length && col >= 0){
if(arr[row][col] == n) return true;
else if (arr[row][col] < n) ++row;
else --col;
}
return false;
}
private int[][] arrays;// 数组
private int value;// 要查找的值
int m = 0;
int n = 0; public void buildData(int m, int n) {
arrays = new int[m][n];
} public void receiveData() {
Scanner sac = new Scanner(System.in);// 接收输入
System.out.println("输入行数:");
m = sac.nextInt();
System.out.println("输入列数:");
n = sac.nextInt();
buildData(m, n);//创建数组
// 接收查找的值
System.out.println("输入要查找的值:");
value = sac.nextInt();
// 接收数据
System.out.println("输入数据:");
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int v = sac.nextInt();
arrays[i][j] = v;
}
}
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
System.out.print(arrays[i][j] + " ");
}
System.out.println();
}
} public boolean find(int value, int row, int col) {
// 使用二分查找
for (int i = row; i < m; i++) {
int start = 0;
int end = col;
int middle = (start + end) % 2 == 0 ? (start + end) / 2
: (start + end) / 2 + 1;
while (middle < end) {
int v = arrays[i][middle];
if (value > v) {
start = middle;
} else if (value < v) {
end = middle;
} else {// 查找到
System.out.println("find data : row:" + (i + 1) + ",col:"
+ (middle + 1));
return true;
}
middle = (start + end) % 2 == 0 ? (start + end) / 2
: (start + end) / 2 + 1;
}
// 该行未查找到
if (middle == col) {// 查到该行末尾
continue;// 继续在下一行查找
} else if (middle == 0) {// 查到该行首位,则未查到
return false;
} else {// 迭代
find(value, row + 1, middle);
}
}
return false;
} public boolean start() {
receiveData();
return find(value, 0, n);
} public static void main(String[] args) {
YangArrayFind ya = new YangArrayFind();
ya.start();
}
}搞定
在线提交代码了没?http://hero.pongo.cn/Question/Details?ID=18&ExamID=18。
给一个浮点数序列,取最大乘积连续子串的值,例如 -2.5,4,0,3,0.5,8,-1,则取出的最大乘积连续子串为3,0.5,8。也就是说,上述数组中,3 0.5 8这3个数的乘积3*0.5*8=12是最大的,而且是连续的。
输入:
输入的第一行为n,表示序列数的个数
输入的第二行是n个浮点数序列
输出:
输出最大乘积子串的起点数,终点数,最大乘积结果值。
输入样例:
7
-2.5 4 0 3 0.5 8 -1
输出样例:
3 8 12在线编译提交代码:http://hero.pongo.cn/Question/Details?ID=19&ExamID=19。
首先直接定位到最右上角的元素,再配以二分查找,比要找的数(6)大就往左走,比要找数(6)的小就往下走,直到找到要找的数字(6)为止,如下图所示:
http://img.my.csdn.net/uploads/201112/16/0_1324051600jHJ9.gif
一 不含0元素
1 数字全部大于0
(1) 数字全部大于1
直接输出
(2)含有小于1的数字
先将大于1的连续整数乘在一起,小于1的乘在一起(*注1)
例如:1,2,0.1,10,3,0.2,0.5,10,2
处理后变为:2,0.1,30,0.01,20
2 含有小于0的数字
(1) 以小于0的数字为界进行分块,每块均属于 第1种情况
例如:1,-2,0.1,10,-3,-0.2,0.5,10,2
处理后变为:子串1:1
子串2:0.1,10
子串3:0.5,10,2
计算出每块的所得的结果中的最大值 记为 rs1
(2) 将小于0的乘在一起,大于0的乘在一起(递归进行)(*注2)
例如:1,-2,0.1,10,-3,-0.2,0.5,-10,2
处理后变为:1,-2,0.03,-10,2
二 含0元素
按0为界限进行分块,每块均属于情况一描述
综合上述,针对各种类型的串,都可以转化为一下两种情况:
a 不含负数的串,并且大于1和小于1的数间隔排列的串
例如:2,0.1,30,0.01,20
b 含负数的串,并且正数和负数间隔排列的串
例如:1,-2,0.03,-10,2
对于a类型的串,(以arr[] ={2,0.1,30,0.01,20}为例)
声明: max 为最大结果 , 不考虑数组越界
1 首先找出最大值 假定为 max=arr[m]
2 如果 arr[m-1]*arr[m-2]<1 且 arr[m+1]*arr[m+2]<1 则
最大结果为 max 结束计算 return max
否则
最大值为arr[m-1]*arr[m-2]和arr[m+1]*arr[m+2之中最大的值乘以max
即:max = Max(arr[m-1]*arr[m-2],arr[m+1]*arr[m+2])*max;
并将arr[m-1],arr[m-2],arr[m] 或者 arr[m],arr[m+1],arr[m+2] 合并为一个数 max
3 进行1操作
对于b类型的串,(以arr[] ={1,-2,0.03,-10,2}为例)
其结果只有两种,要么是其中最大的一个整数,要么是含有偶数个负数的串
对于后面一种,没想好怎么算
不知道想的对不对
public static void into(){
Scanner scanner=new Scanner(System.in);
int num=scanner.nextInt();
double[] arrs=new double[num];
for(int i=0;i<arrs.length;i++){
arrs[i]=scanner.nextInt();
}
double max=0;
double start=0;
double end=0;
double x=0;
for (int i=0;i<num;i++) {
x=arrs[i];
for (int j = i+1; j < num; j++) {
x*=arrs[j];
if(x>max){
max=x;
start=arrs[i];
end=arrs[j];
}
}
}
System.out.println(start+","+end+","+max);
}
public static void main(String[] args) {
into();
}不考虑效率的情况
果然不考虑效率
此外,朋友们,别忘了,你可以在线提交你的代码:http://hero.pongo.cn/Question/Details?ID=18&ExamID=18。
恩,产品还在不断测试完善当中,暂不支持C/C++,不过,我们正在努力改进,争取平台早日支持C/C++语言。
(从侧面也说明了一点,因为暂不支持C和C++,故才特意发到Java板块来,没想到在此Java板块也有人问起为何不支持C和C++的问题,由此说明,这个需求有多强烈,已经记录下了,谢谢)
* 查询结果包装类
* 为尾递归的伪引用参数传递
*/
public class Result {
boolean res=false;
public void and(boolean r){
res =res||r;
}
public boolean getResult(){
return res;
}
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
int [][]NX={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}}; //初始数组
for(int i=0;i<NX.length;i++){
for(int j=0;j<NX[0].length;j++){
System.out.print(NX[i][j]+" ");
}
System.out.println();
}
System.out.println("\n");
Scanner in =new Scanner(System.in);
System.out.print("please input :> ");
int n=Integer.MIN_VALUE;
while((n=in.nextInt())!=Integer.MIN_VALUE){ //模拟输入
System.out.println("RESULT:>> "+isXExist(NX, n)); //打印输出
System.out.print("please input :> ");
}
}
private static boolean isXExist(int[][] NX, int n) {
// TODO Auto-generated method stub
Result res =new Result(); //包装boolean结果,模拟传引用参数
check(NX, 0, 0, NX.length, NX[0].length, n, res);//因为普通递归,可能抛出Overflow的Exception,所以采用懒递归
return res.getResult();
} /*首先判断是否在当前区域,不在,返回false
* 在,将区域以中间点为基准点,递归分组为左上、右上、右下、左下,继续递归
* C/C++可以直接传引用,省略包装过程和包装类,改起来应该 very easy了
* */
private static void check(int[][] NX, int x, int y,int xlen, int ylen, int n ,Result res) {
System.out.println("("+x+" , "+y+") ["+xlen+" , "+ylen+"]"+" n="+n+" res="+res.getResult());
if(n<NX[x][y] || n>NX[x+xlen-1][y+ylen-1]){
res.and(false);
}else if(n==NX[x][y] || n==NX[x+xlen-1][y+ylen-1]){
res.and(true);
System.out.println("res=true");
}else{
if(!res.getResult())
check(NX, x, y, xlen/2, ylen/2, n, res);
if(!res.getResult())
check(NX, x+xlen/2, y, xlen-xlen/2, ylen-ylen/2, n, res);
if(!res.getResult())
check(NX, x+xlen/2, y+ylen/2, xlen-xlen/2, ylen-ylen/2, n, res);
if(!res.getResult())
check(NX, x, y+ylen/2, xlen/2, ylen-ylen/2, n, res);
}
}}
public void and(boolean r){
res =res||r;
}改成如下
public void or(boolean r){
res =res||r;
}相应的调用也改成or……也就一个名字,随便了
package yxh;
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
/**
* 1 暂不考虑异常处理</br>
* 2 在此我们假定输入的数据中不含0元素,</br>
* 因为如果有0元素的话,输入的数据就可以以0为界进行分块,从而转化为不含0元素的子串
* @author LZC
*
*/
public class PlusArr {
/**
* 该类表示合并后的集合中的每个元素 他记录了合并的开始位置、结束位置和合并后的结果
* @author LZC
*/
class Element {
/** **记录该元素是从数组中哪个位置开始运算的*** */
public int startIndex;
/** **记录该元素是从数组中哪个位置结束运算的*** */
public int endIndex; /** *数组中从startIndex(包含)位置到endIndex(不包含)位置连乘的结果*** */
public double value;
public Element() { }
/**
* @param startIndex ��
* @param endIndex ��
* @param value
*/
public Element(int startIndex, int endIndex, double value) {
super();
// TODO Auto-generated constructor stub
this.endIndex = endIndex;
this.startIndex = startIndex;
this.value = value;
}
public String toString() {
return value + "(" + startIndex + "," + endIndex + ") ";
}
}
/**
* @param args
*/
//测试数据
//double[] srcArr = { 2, 6, 0.2, 0.6, 0.1, 7, 0.4, 10, 0.8, 20, 5 }; public static void main(String[] args) {
// TODO Auto-generated method stub
PlusArr plus = new PlusArr();
System.out.println("数组数组序列(用英文逗号','隔开)");
Scanner r = new Scanner(System.in);
String input = r.nextLine();
System.out.println(input);
/**在此我们假定输入的数据中不含0元素,因为如果有0元素的话,输入的数据就可以以0为界进行分块,从而转化为不含0元素的子串**/
/** *将负数作为界限,进行分块* */
String[] negativeSplit = input.split("-[\\d]*.?[\\d]*");
int len = negativeSplit.length;
/** *如果只有一块,则说明该串中不含有负数* */
if (len == 1) {
/** 将输入的数字序列进行分隔* */
String[] strArr = input.split(",");
/** 得到对应的数组* */
double[] douArr = plus.toDoubleArr(strArr);
/** 数组进行合并操作* */
List<Element> list = plus.mergerArr(douArr);
/** 计算出最大乘积的连续子串* */
double max = 0;
int index = 0;
/***找出当前集合中最大值,并记录其位置***/
for (int i = 2; i < list.size() - 2; i++) {
if (list.get(i).value > max) {
index = i;
max = list.get(i).value;
}
}
Element rsEle = plus.findMaxValue(list,index);
/**输出**/
System.out.println(rsEle);
System.out.print("最大连乘积为"+rsEle.value+"=");
for(int i=rsEle.startIndex;i<rsEle.endIndex;i++){
System.out.print(douArr[i]+" * ");
} } else if (len > 1) {
/** *如果多于一块,则说明该串中含有负数* */ /** 这部分还没想好怎么弄** */
}
}
/**
* 将字符串数组转为double数组
* @param strArr
* @return
*/
double[] toDoubleArr(String[] strArr) {
/**暂不考虑异常情况**/
double[] douArr = new double[strArr.length];
for (int i = 0; i < strArr.length; i++) {
douArr[i] = Double.parseDouble(strArr[i]);
}
return douArr;
} /**
*
* 复杂度 O(n) n表示数组长度
*
* @param 待处理的数组
*
* @return 合并后的结果(不含负数的 且大于1和小于1的数字间隔排列的集合)��
*/
public List<Element> mergerArr(double[] arr) {
List<Element> elementList = new LinkedList<Element>();
/** ***在elementList链表的前后各加上两个值为1的元素,方便后面的计算**** */
elementList.add(new Element(-1, -1, 1));
elementList.add(new Element(-1, -1, 1)); int tag = 2;
elementList.add(new Element(0, 0, arr[0])); for (int i = 1; i < arr.length; i++) { if ((arr[i] - 1) * (arr[i - 1] - 1) < 0) {
tag++;
elementList.add(new Element(i, arr.length, arr[i]));
elementList.get(tag - 1).endIndex = i;
}
/** ***如果相邻元素同大于0或同小于0,则合并为一个**** */
else {
elementList.get(tag).value = elementList.get(tag).value
* arr[i];
}
}
/** ***在elementList链表的前后各加上两个值为1的元素,方便后面的计算**** */
elementList.add(new Element(-1, -1, 1));
elementList.add(new Element(-1, -1, 1));
return elementList;
}
/**
* 复杂度 小于O(n) 因为每递归一次,list的长度减少2
* @param list 不含负数的 且大于1和小于1的数字间隔排列的集合
* @param index 当前最大元素的位置
* @return 最大元素
*/
Element findMaxValue(List<Element> list,int index) {
Element maxEle = list.get(index);
/** *****当前最大值左边两个元素的乘积******** */
double rs1 = list.get(index - 2).value * list.get(index - 1).value;
/** *****当前最大值右边两个元素的乘积******** */
double rs2 = list.get(index + 2).value * list.get(index + 1).value; /** *****如果左右两个元素的乘积均小于1,则结果即为maxEle******** */
if (rs1 <= 1 && rs2 <= 1) {
return maxEle;
}
/** *****如果左边两个元素的乘积大于右边两个元素的乘积,</br>
*********则乘以rs1 否则乘以rs2 ******** */
if (rs1 > rs2) {
maxEle.startIndex = list.get(index - 2).startIndex;
maxEle.value = maxEle.value * rs1;
list.remove(index);
list.remove(index - 1);
list.remove(index - 2);
index = index-2;
list.add(index, maxEle);
} else {
maxEle.endIndex = list.get(index + 2).endIndex;
maxEle.value = maxEle.value * rs2; list.remove(index + 2);
list.remove(index + 1);
list.remove(index);
list.add(index, maxEle);
}
// System.out.println(list);
/** **进行递归*** */
findMaxValue(list,index);
return maxEle; }
}
如果你实在是只会C/C++,实在是纠结于不想写Java/C#代码,那就麻烦你在线敲好代码,然后在本地编译测试好后(shengl),直接提交代码吧。不为难用户,重在参与!
import java.util.Scanner;/*
* 结果封装类,保存计算结果(没办法,java只支持传值参)
*/
public class Max {
public int start=0 ,end=0;
public double total=0;
/**
* 入口
*/
public static void main(String[] args) {
//double []num={-1,2,4,0,6,-1,-10,-7,-0.1,-9,-2,100,-0.6,-19,0,110};
//输入数据
System.out.print("Please input the Array size:>");
Scanner in =new Scanner(System.in);
int N =in.nextInt();
double []num =new double[N];
System.out.print("Please input the Numbers:>");
for(int i=0;i<N;i++)
num[i] =in.nextDouble();
//回显输入
System.out.print("Your Numbers:> ");
for(int i=0;i<N;i++)
System.out.print(num[i]+" ");
System.out.println();
//定义结果集
Max result=new Max();
run(num, result); //运行计算
//打印结果
System.out.println("The MAX Product= "+result.total+" ~~~~~index range 【 "+result.start+" -> "+result.end+" 】");
}
/*因为是连续乘积,所以可以穷举 所有的计算组合,组合数量也不大;
* 然后,筛选 乘积最大的组合
* 备注:主要分析:按<=-1,-1~0,0,0~1,>=1切割分组,当这几种分组穿插组合之后,要考虑的情况实在有点复杂,所以选择穷举,简单方便;
* 如果数字很多,可以考虑先按上述分组,合并部分可合并项,例如>=1的可以合并为一项,单个分组为偶数个<=-1可合并为一项等等,然后再穷举
*/
private static void run(double[] num, Max result) {
System.out.println("开始穷举");
for(int i=0;i<num.length;i++){ //遍历所有穷举点
double n =num[i];
System.out.println("########### "+n+" -> index = "+i+" ##########"); //打印穷举点
if(n==0) continue; //遇到0终止当前穷举,并以下一项为基准点开始新穷举,因为0乘以任何数都为0
for(int j=i+1;j<num.length;j++){
if(num[j]==0) break; //遇到0,中断组合
n*=num[j]; //计算当前组合的乘积
System.out.println("product : "+n+" index range: 【"+i+" -> "+j+"】 "); //打印穷举组合
if(result.total<n){ //当前穷举组合比已知组合乘积都大,则重置最大穷举组合为当前组合
result.start =i;
result.end =j;
result.total =n;
}
}
System.out.println();
}
}}
依据的话主要是根据向下增长和向右增长这两个特点。但上一行的所有数据又不一定比下一行的数据大,所以暂时只能想到这些了~
不会java和c# 先说说我的想法吧
递归思路,比如找6:
在数组的对角线上:
先找到比6大的最小值10,那么红框里的数组都比6大;
再找到比6小的最大值4,那么蓝框里的数组都比4大;
如果找到6,则返回;
否则递归查找蓝框和红框外的数组
#include <iostream>
#include <string>
#include <stdio.h>
#include <stdlib.h>//#include <time.h>
std::string test4(int m,int n , int t){ int * pa = (int*)malloc(sizeof(int)*m*n);
for(int i = 0 ; i < m*n ;++i){
std::cin>>pa[i];
}
int r_start = 0;
int r_end = m;
//std::cout<<time(0)<<std::endl;
//对行进行2分查找,通过第一个循环找出符合条件的行
while(r_start <= r_end){
int r_m = (r_start + r_end) / 2;
int index = r_m * n ;
if(pa[index + n - 1] < t){
r_start = r_m + 1;
}else{
if(pa[index + n - 1] == t ){
return "True";
}else{
if(pa[index] == t){
return "True";
}else{
int c_start = 0;
int c_end = n;
//对符合条件的行进行2分查找,找出匹配的值,如果没有值相等,去找下一个匹配的行
while(c_start <= c_end){
int c_m = (c_start + c_end ) / 2;
if(pa[index + c_m] > t){
c_end = c_m - 1;
}else if(pa[index + c_m] < t){
c_start = c_m + 1;
}else{
return "True";
}
}
}
r_end = r_m - 1;
}
}
}
//std::cout<<time(0)<<std::endl;
return "False";
}
int main(int argc, const char * argv[])
{
while(!std::cin.eof()) {
int m = 0 , n = 0 , t = 0;
std::cin>>m;
std::cin>>n;
std::cin>>t;
std::cout<<test4(m,n,t)<<std::endl;
}
return 0;
}
{
public static void main(String[] args)
{
int[][] arrays = new int[][]
{
{1,2,8,9},{2,4,9,12},{4,7,10,13}
};
int x = 0;
int y = 3;
int z = 10;
int middleTemp = arrays[0][3];
int yTemp = 3;
int temp = 0;
for(x = 0;x <= 2;x++)
{
for(; y>=0;y--)
{
if(z == middleTemp)
{
temp = 1;
System.out.println(temp);
return;
}
else if(middleTemp > z)
{
middleTemp = arrays[x][y-1];
}
else if(middleTemp < z)
{
//yTemp = y;
middleTemp = arrays[x+1][y];
break;
}
}
}
}
}
小弟小菜鸟!弱弱的问一句,这题是这意思不?
第一题伪代码如下:
//定义矩阵块
Class Matrix {
int left, top, right, buttom;
}//查找杨氏矩阵
boolean findMatrix(double[][] A, double target) {
Queue q = new Queue(); //存放矩阵的队列
Matrix mx = new Matrix();
mx.left=0;
mx.top=0;
mx.right=A[0].length;
mx.buttom=A.length;
q.add(mx);
while (!q.isEmpty()) {
mx = q.header;
q.removeHeader();
if (!isNotResult(mx, A, target)) {
if (mx.left==mx.right && mx.top==mx.bottom) {
//已经找到了
return true;
} else {
//切蛋糕
int midX = (int)((mx.left+mx.right)/2.0);
int midY = (int)((mx.top+mx.bottom)/2.0);
//左上角子矩阵
Matrix mx1 = new Matrix();
mx1.left = mx.left;
mx1.top = mx.top;
mx1.right = midX;
mx1.bottom = midY;
q.add(mx1);
//右上角子矩阵
Matrix mx2 = new Matrix();
mx2.left = midX;
mx2.top = mx.top;
mx2.right = mx.right;
mx2.bottom = midY;
q.add(mx2);
//左下角子矩阵
Matrix mx3 = new Matrix();
mx3.left = mx.left;
mx3.top = midY+1;
mx3.right = midX;
mx3.bottom = mx.bottom;
q.add(mx3);
//右下角子矩阵
Matrix mx4 = new Matrix();
mx4.left = midX;
mx4.top = midY+1;
mx4.right = mx.right;
mx4.bottom = mx.bottom;
q.add(mx4);
} //while
return false;
}
}//判断指定的杨氏矩阵肯定不包含需要的结果
boolan isNotResult(Matrix mx, double[][] A, double target) {
if (A[mx.left][mx.top]>target || A[mx.right][mx.bottom]<target) {
return true;
} else {
return false;
}
}main() {
A[][]={{...},{...},{...},...} //原始矩阵
Target = ...; //存放查找值
print(findMatrix(A,Target));
}
矩阵查找:#include "stdafx.h"
#include <iostream>
using namespace std;
bool searchMem(int a[50][50],int row, int col,int value);
int main(int argc, char* argv[])
{
int value = 0,m=0,n=0,i,j;
printf("please input value number:");
std::cin>>value;
printf("please input row number:");
std::cin>>m;
printf("please input col number:");
std::cin>>n;
int array[50][50] = {0};
for(i =0;i<m;i++)
for(j=0;j<n;j++)
cin>>array[i][j];
bool isValue = searchMem(array,m,n,value);
cout<<isValue<<endl;
return 0;
}
bool searchMem(int a[50][50],int row, int col,int value){
bool Have = false;
bool isLeftEnd = false;
bool isRightEnd = false;
bool EndCenter = false;
bool isEnd = false;
int iLeft=0,jLeft=0;
int iRight = 0, jRight = 0;
int iCenter=0;
while(!Have&&!isEnd){
//cout<<"left:"<<a[iLeft][jLeft]<<endl;
//cout<<"right:"<<a[iRight][jRight]<<endl;
//cout<<"center:"<<a[iCenter][iCenter]<<endl;
if(a[iCenter][iCenter]==value){
Have = true;
break;
}
if(a[iCenter][iCenter]<value&&(!EndCenter)){
iLeft++;
jRight++;
}//如果中心值比value小 则用它的正下方的值和右边的值与value比较来判断是否跳到下一个中心值;
if(a[iLeft][jLeft]<value&&a[iRight][jRight]<value&&EndCenter){
iCenter++;
if(iCenter>=row&&iCenter<col){//判断是否是到了最后一行
isLeftEnd = true;
EndCenter = true;
iCenter--;
}else if(iCenter<row&&iCenter>=col){//判断是否是到了最后一列
isRightEnd = true;
EndCenter = true;
iCenter--;
}
iLeft = jLeft = iRight = jRight = iCenter;
continue;
}else{
EndCenter = true;
} if(a[iLeft][jLeft]=value||a[iRight][jRight]){
Have = true;
break;
}
if(!isLeftEnd){
if(a[iLeft][jLeft]>value){
jLeft--;
}else{
iLeft++;
}
if(jLeft<0||iLeft>row){
isLeftEnd = true;
}
}
if(!isRightEnd){
if(a[iRight][jRight]>value){
iRight--;
}else{
jRight++;
}
if(iRight<0||jRight>col){
isRightEnd = true;
}
}
if(isRightEnd&&isLeftEnd){
isEnd = true;
}
}
return Have;
}
定义字符串循环右移操作:把一个长度为N的字符串内的元素循环右移K位,要求时间复杂度为O(N),空间复杂度为O(1),请编写代码实现。
输入样例:N=8的字符串abcdefgh;
输出样例:K=4,即字符元素右移4位,得到efghabcd。本来不想做的,看看也是2颗星,还是想了下……坑爹的,想去提交代码的时候,提示已经提交过了,都不知道自己有做过==... 如下:import java.util.Scanner;public class StringMove {
public static void main(String[] args) {
char[] str ={'a','b','c','d','e','f','g'};
int k=0;
System.out.print("please input K:>");
Scanner in =new Scanner(System.in);
k =in.nextInt(); //模拟输入
k=k%str.length; //超过字符串长度,对其取模
System.out.println("src:>"+new String(str)); //回显
//腾出[0]的空间,并保存该字符
char ch=str[0];
int emptyIndex =0;
//找到应该挪到当前空位置的字符,并将其挪到空位置上;置空位置为当前新挪出的位置,继续挪动
//(str.length+index-k)%str.length 预防负数下标
for(int index=(str.length-k)%str.length; index!=0 ; emptyIndex=index,index=(str.length+index-k)%str.length){
str[emptyIndex] =str[index];
}
str[emptyIndex] =ch;//将转移的字符挪到其应在的位置,完成全部挪动
System.out.println("des:>"+new String(str));
}}
X->X^T,就是翻转的意思,例如abc->cba
Scanner scanner = new Scanner(System.in);
int num = scanner.nextInt();
double[] arr = new double[num];
for (int i = 0; i < arr.length; i++) {
arr[i] = scanner.nextInt();
}
double start=0,end=0,max=0,multi=0;
for(int i=0;i<arr.length-2;i++){
multi=arr[i]*arr[i+1]*arr[i+2];
if(multi>max){
max=multi;
start=arr[i];
end=arr[i+2];
}
}
System.out.print("开始"+start+"结束"+end+"乘积"+max);
}
设有数组A={a[i]|1<=i<=L},求F(A)= max(a[i]*a[i+1]*...a[i+k])
1. 如果数组长度L=1,那么这个唯一元素就是它的最大乘积子串
2. 如果数组长度L>1,则必有F(A)>=0,F(A)=0的唯一条件是数组A仅由非正数组成,且任意2个负数元素之间必定有0元素分割。
所以,如果数组A包含0元素,可以先对数组A以值为0的元素作为分割符进行拆分,对每一个子数组求最大乘积子串F(A1'),F(A2')...则F(A)=max(0, F(A1'),F(A2'),...)于是问题变成了如何计算一个不包含0数组的最大乘积子串。
如果数组A均为正数,则从前往后进行相乘,只要乘出来的结果>1,则可以一直乘下去(在此过程中需要记录乘出来的最大结果)。如果到了第i个元素,发现a[1]*...*a[i-1]>=1 && a[1]*...*a[i]<1,那么就表示可以将数组A拆分为2段
A1={a[1]...a[i-1]}以及A2={a[i+1]...a[L]}。
则有F(A)=max(F(A1),F(A2))。由于F(A1)在此前的计算中已经记录下来了,所以直接计算F(A2)就可以了。
算法复杂度为O(L)对于包含负数的串就不能直接用上述方法计算,一个简单的例子是-10,0.3,0.3,-4
这个要再想想
public static boolean isLive(int[][] j, int t) {
int row = j.length;
int cel = j[0].length;
int mrow = j[0][1] - j[0][0];
int mcel = j[1][1] - j[0][0];
int j1 = j[0][0];
int max = j1 + (mrow + mcel) * (3 - 1);
if (t < j1) {
if ((t - j1) % mrow == 0) {
return true;
} else if ((t - j1) % mcel == 0) {
return true;
} else if (((t - j1) % (mrow + mcel)) == 0) {
return true;
}
}
return false;
}
刚刚想到一个办法可以处理带负数的序列。
假设序列A={a[i],1<=i<=L,L>1}={b[1][1],b[1][2],...b[1][i1],c[1],b[2][1],b[2][2],b[2][i2],c[2],...c[n-1],b[n][1],b[n][2],...b[n][in]},其中所有的b[i][j]均>0,而所有的c[i]均<0,求最大乘积子串F(A)
当L>1时,有F{A)>0。假设F(A)对应的子序列为a[i]~a[j],则a[i]~a[j]中必包含偶数个c[]元素。
因此可以将其中出现的c[]元素两个两个的连成一组将a[i]~a[j]切分开来。则其中每一组或者仅包含一个正数元素,或者是在其头尾有负数,而中间均为正数。
例如序列2,3,-4,5,6,-7,8,9,-10,11,12,-13,14就可以拆分为
2,3,{-4,5,6,-7},8,9,{-10,11,12,-13},14 这样7组。可以发现每一组的乘积均为正数。所以从某种程度上将,其实我们可以将两个最靠近的负数连同它们中间的正数乘在一起作为一个元素。
当然了,F(A)也可能连一个负数都不包含,这表明F(A)对应的子序列或者在第1个负数之前,或者在最后一个负数之后,或者在2个相近的负数之间,总之,它是在一个正数子串里面。
另外一个需要考虑的是,如果F(A)中包含几个负数元素,那么它的第1个负数元素究竟是第奇数个负元素呢还是第偶数个元素?这牵涉到要将哪两个负数归为1组。
譬如序列2,3,-4,5,6,-7,8,9,-10,11,12,-13,14,
如果考虑子串2,3,-4,5,6,-7,8,则应当将原始串视作2,3,{-4,5,6,-7},8,9,{-10,11,12,-13},14
而如果考虑子串6,-7,8,9,-10,11,则应当将原始串视作2,3,-4,5,6,{-7,8,9,-10},11,12,-13,14.
所以对一个非0序列A={a[i],1<=i<=L,L>1}={b[1][1],b[1][2],...b[1][i1],c[1],b[2][1],b[2][2],b[2][i2],c[2],...c[n-1],b[n][1],b[n][2],...b[n][in]}
我们可以将它进行如下分解:
分解1:第1组b[1][1],...b[1][i1],{c[1],b[2][1],...b[2][i2],c[2]},b[3][1],...b[3][i3],{c[3],b[4][1],...,b[4][i4],c[4]},...
第2组(如果n是偶数)c[n-1]
第3组(如果n是偶数)b[n][1],...b[n][in]
分解2: 第4组b[1][1],...b[1][i1]
第5组c[1]
第6组b[2][1],...b[2][i2],{c[2],b[3][1],...b[3][i3],c[3]},b[4][1],...,b[4][i4],{c[4],b[5][1],...,b[5][i5],c[5]},...
第7组(如果n是奇数)c[n-1]
第8组(如果n是奇数)b[n][1],...,b[n][in]
则有F(A)=max(F(第1组),F(第2组),F(第3组),F(第4组),F(第5组),F(第6组),F(第7组),F(第8组),
F(b[1][1],..,b[1][i1]),
F(b[2][1],..,b[2][i2]),
...
F(b[n][1],..,b[n][in]),
)
这里每一个计算F的序列,或者仅由一个负数组成(则F的值就是这一个唯一的元素),或者是一个正数序列,则可以用上面讲过的正数序列求最大乘积算法。
本方法的时间复杂度应当是O(L)
char a[]="abcdefgh";
char b[8];
int k=4;
ZeroMemory(b,sizeof(b));
memcpy(b,&a[k],sizeof(a)-k);
memcpy(&b[k],a,k);
TRACE("%s\n",b);
vs2008编译通过. 用memcpy就能解决。
talk is cheap,show me the code?
如果实在是只会C 语言的话,也可以贴代码。
或许可以这样?
<script>
var str = window.prompt("请输入密码","password")
alert(str);
</script>
void modifyString(char* src,char* des ,int index,OPSTR op,char ch=NULL)
{
//函数没有处理异常情况,所有均按正常操作处理.比如index没有超过数组边界什么的
switch(op)
{
case ADD:
memcpy(des,src,index);
des[index]=ch;
memcpy(&des[index+1],&src[index],strlen(src)-index);
break;
case DEL:
memcpy(des,src,index);
memcpy(&des[index],&src[index+1],strlen(src)-index-1);
break;
case REPLACE:
memcpy(des,src,strlen(src));
des[index]=ch;
break;
}
}
//使用函数 如下.
char a[]="abcdefgh";
char b[10];
//add char
ZeroMemory(b,sizeof(b));
modifyString(a,b,4,ADD,'A');
TRACE("%s==>Add char A into index %d ==>%s\n",a,4,b);
//del char
ZeroMemory(b,sizeof(b));
modifyString(a,b,4,DEL);
TRACE("%s==>Del char index %d ==>%s\n",a,4,b);
//replace char
ZeroMemory(b,sizeof(b));
modifyString(a,b,4,REPLACE,'E');
TRACE("%s==>REPLACE char index %d ==>%s\n",a,4,b);输出结果如下.abcdefgh==>Add char A into index 4 ==>abcdAefgh
abcdefgh==>Del char index 4 ==>abcdfgh
abcdefgh==>REPLACE char index 4 ==>abcdEfgh