41.和為S的連續(xù)正數(shù)序列
小明很喜歡數(shù)學,有一天他在做數(shù)學作業(yè)時,要求計算出9~16的和,他馬上就寫出了正確答案是100片迅。
但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個數(shù))。
沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22扁耐。
現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
這個題最直觀的想法就是從1,2開始用枚舉法算出所有的連續(xù)正數(shù)序列的和碍彭，直到第一個數(shù)和第二個數(shù)的和大于我們要求的數(shù)，例如求到了50,51則算法結(jié)束挣柬。
那么有沒有更節(jié)省時間的方法呢，我們注意到睛挚，例如4,5,6,7和5,6,7,8他們之間是有重疊的部分的邪蛔，所以我們可以從最原始的sum=1+2=3開始，當sum<target的時候扎狱，我們就將數(shù)組長度往后擴展一位侧到，同時sum要加上這個新添加的數(shù)，當sum>target的時候淤击，我們先減去數(shù)組的第一個數(shù)匠抗，再將數(shù)組前部縮短一位，直到左右兩個指針重合的時候循環(huán)結(jié)束污抬。
代碼如下
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
if(sum<=1){
return new ArrayList<ArrayList<Integer>>();
}
int l = 1,h = 2,Sum = 3;
ArrayList<ArrayList<Integer>> ret = new ArrayList<ArrayList<Integer>>();
//當l和h相等時中止循環(huán)
while(l<h){
//和小于sum時h往前走一位汞贸，且記得Sum += h
//和大于sum時先Sum -= l，l再往前走一位
//和等于sum時存下這個數(shù)組印机，然后h再往前走一位循環(huán)繼續(xù)
if(Sum<sum){
h++;
Sum += h;
}else if(Sum>sum){
Sum -= l;
l++;
}else if(Sum==sum){
ArrayList<Integer> tmp = new ArrayList<Integer>();
for(int i=l;i<=h;i++){
tmp.add(i);
}
ret.add(tmp);
h++;
Sum += h;
}
}
return ret;
}
}
42.和為S的兩個數(shù)字
輸入一個遞增排序的數(shù)組和一個數(shù)字S矢腻，在數(shù)組中查找兩個數(shù)，使得他們的和正好是S射赛，如果有多對數(shù)字的和等于S多柑，輸出兩個數(shù)的乘積最小的。
這個題就很簡單了楣责，41題的終極簡化版竣灌，用左右指針逼近就可以了，至于乘積最小的兩個數(shù)秆麸，用兩個變量去保村更新那和為S的數(shù)就可以了
代碼寫的有點冗余
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
if(array.length<=1){
return new ArrayList<Integer>();
}
int l = 0,h = array.length-1;
boolean flag = false;
//初始化這個乘積初嘹，初始化兩個變量
int mul = (int)Math.pow(array[array.length-1],2),first = array[0],last = array[array.length-1];
while(l<h){
if(array[l]+array[h]>sum){
h--;
}else if(array[l]+array[h]<sum){
l++;
}else{
flag = true;
if(array[l]*array[h]<=mul){
mul = array[l]*array[h];
first = array[l];
last = array[h];
}
l++;
}
}
ArrayList<Integer> ret = new ArrayList<Integer>();
ret.add(first);
ret.add(last);
if(flag){
return ret;
}else{
return new ArrayList<Integer>();
}
}
}
43.左旋字符串
匯編語言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個簡單的任務(wù)蛔屹，就是用字符串模擬這個指令的運算結(jié)果削樊。
對于一個給定的字符序列S，請你把其循環(huán)左移K位后的序列輸出。
例如漫贞，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果甸箱，即“XYZdefabc”。是不是很簡單迅脐？OK芍殖，搞定它！
這個題就直接算出n對字符串長度取余得到N谴蔑，將字符串的前N位放在最后就好了
代碼如下
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length()==0){
return str;
}
char[] ch = str.toCharArray();
int l = n%ch.length;
char[] ret = new char[ch.length];
int cnt = 0;
//旋轉(zhuǎn)
for(int i = l;i<ch.length;i++){
ret[cnt] = ch[i];
cnt++;
}
for(int j = 0;j<l;j++){
ret[cnt] = ch[j];
cnt++;
}
//拼接
String res = "";
for(char k:ret){
res += k;
}
return res;
}
}
44.翻轉(zhuǎn)單詞順序列
磐憧ィ客最近來了一個新員工Fish，每天早晨總是會拿著一本英文雜志隐锭，寫些句子在本子上窃躲。同事Cat對Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來翻看钦睡，但卻讀不懂它的意思蒂窒。例如，“student. a am I”荞怒。后來才意識到洒琢，這家伙原來把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“I am a student.”褐桌。Cat對一一的翻轉(zhuǎn)這些單詞順序可不在行衰抑，你能幫助他么？
直接用Split將字符串切割成字符串數(shù)組就行
String[] res = str.split(" ")
然后逆序?qū)⒆址當?shù)組中res中字符串按逆序間隔空格拼接起來;
為了AC100%記住荧嵌，要判定str是否為空字符串;
public class Solution {
public String ReverseSentence(String str) {
//切割
String[] res = str.split(" ");
if(res.length==0){
return str;
}
String ret = "";
//翻轉(zhuǎn)拼接
for(int i = res.length-1;i>0;i--){
ret += res[i]+" ";
}
ret += res[0];
return ret;
}
}
45.撲克牌順子
LL今天心情特別好,因為他去買了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張^_^)...
他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿Ｇ河弧！
“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13完丽。
上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”恋技。
LL決定去買體育彩票啦。
現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何逻族， 如果牌能組成順子就輸出true，否則就輸出false骄崩。
為了方便起見,你可以認為大小王是0聘鳞。
這個題的思路就是先對數(shù)組進行排序，然后統(tǒng)計數(shù)組中0的個數(shù)要拂，再看后面的數(shù)組抠璃，一旦發(fā)現(xiàn)有兩個相等的數(shù)，就無法組成順子脱惰，直接返回false搏嗡；然后統(tǒng)計兩兩數(shù)字之差減1然后求和，例如1,2之差是1，他們本身就已經(jīng)是順子了采盒，無需用0來填補旧乞，而1,4則需要兩個0,即4-1-1,最后統(tǒng)計完這個和sum小于等于0的個數(shù)的話肯夏，那么就可以組成順子
代碼流程如下
1.排序
2.初始化變量cnt_0用來計算0的個數(shù)份帐；初始化一個tmp變量用來存儲上一個非0的數(shù)字；初始化一個變量sum來記錄差值的和
3.遍歷排序數(shù)組{
如果當前數(shù)等于0{
cnt_0++懒叛；
}否則{
如果tmp等于0{
tmp = num;
}否則{
如果num==tmp{
返回false
}否則{
sum += num-tmp-1;
tmp = num;
}
}
}
}
4.判斷sum是否小于cnt_0,即是否有足夠的癩子可以填充空缺
代碼如下
import java.util.Arrays;
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers.length==0){
return false;
}
Arrays.sort(numbers);
int cnt_0 = 0;
int tmp = 0;
int sum = 0;
for(int num:numbers){
if(num==0){
cnt_0++;
}else{
if(tmp==0){
tmp=num;
}else{
if(num==tmp){
return false;
}else{
sum += num-tmp-1;
tmp = num;
}
}
}
}
if(sum<=cnt_0){
return true;
}else{
return false;
}
}
}
