一.实现strStr()
1.实现strStr()
题目描述
解法一：
运用两层for循环，一个一个字符进行对比（KMP算法）
//解法一：
class Solution {
public static int strStr(String haystack, String needle) {
if(needle.length()==0){
return 0;
}
char[] h=haystack.toCharArray();
char[] n=needle.toCharArray();
for(int i=0;i<h.length;i++){
//当这个if语句为真代表含义:h数组当中的某个元素与n数组中的第一个元素一样
if(h[i]==n[0]){
int j=0;
int temp=i;
for(;j<n.length;j++){
//在遍历的过程中，如果h下标的某个元素与n下标的元素出现不一致的情况，则直接退出这一层循环，i继续往后走
//并且，在得到两个数组元素一致时,判断此时 h数组的下标+n数组的长度 是否大于h数组，如果大于，就直接退出此次循环
if(h[temp]!=n[j] || (i+n.length)>h.length ){
break;
}else{
temp++;
}
}
//如果两个字符串匹配成功了，j的长度会增加到n.length
if(j==n.length){
//匹配成功，返回h数组的下标
return i;
}
}
}
return -1;
}
}
解法二的思路：
1.运用了一层循环，
2.当符合:h字符串中的某个元素==n字符串首元素并且h字符串此时对应的下标+n字符串的长度<=h字符串的长度 此时，就进入下一层if判断；
3.如果符合，h字符串从[i,i+n.length)等于n字符串的内容，就直接返回i下标；
4.如果for循环执行完毕之后，还没有返回i下标，此时，就证明，字符串没有匹配上，返回-1.
//解法二：
class Solution {
//利用substring来判断
public static int strStr(String haystack, String needle) {
if(needle.length()==0){
return 0;
}
int length=needle.length();
for(int i=0;i<haystack.length();i++){
//如果haystack字符串中的某个元素和needle的第一个元素一样，并且此时的下标+needle字符串的长度，小于haystack字符串的长度，就进入下一个if判断
if(haystack.charAt(i)==needle.charAt(0) && (i+length)<=haystack.length()){
//判断，如果haystack从[i,i+length)的字符串与needle的字符串相等，就直接返回下标，否则，继续执行i的循环
if(haystack.substring(i,i+length).equals(needle)){
return i;
}
}
}
//在这，就证明没有匹配上，就直接返回-1
return -1;
}
}
二.搜索插入位置
第二题：搜索插入位置
解题思路：
1.循环遍历整个数组；
2.当数组中某个元素==target时，返回数组下标；
3.因为这个数组是有序数组，所以，当target<数组中某个元素时，返回数组下标；
4.当不符合前两种情况时，就证明，此时的target数值比数组中的所有元素都大，所以，就返回nums.length
class Solution {
public static int searchInsert(int[] nums, int target) {
for(int i=0;i<nums.length;i++){
if(nums[i]==target){
return i;
}
if(target<nums[i]){
return i;
}
}
return nums.length;
}
}
三.最大子数组和
3.最大子数组和
题目描述:
解题思路：
1.创建一个数组，记录每一步的计算结果，最终数组中的最大值，即，为所求最大数组累加和；
2.遍历nums数组，当 temp[i-1]>0:temp[i]=temp[i-1]+nums[i]；
3.当temp[i-1]<0:temp[i]=nums[i];
4.max=Math.max(max,temp[i]);
//动态规划 解决此问题
class Solution {
//使用 动态规划 来解决此问题
public static int maxSubArray(int[] nums) {
int[] temp=new int[nums.length];
int max=nums[0];
temp[0]=nums[0];
//循环遍历nums数组，确定temp数组中每一个下标对应的数值
for(int i=1;i<nums.length;i++){
//当temp[i-1]>0,就说明前面的数和当前数组中的数字的累加和 是 大于 后面这个数的：temp[i]=temp[i-1]+nums[i]
//否则，就说明 累加和 是 小于 后面这个数的，前面的累加和是根本帮不到当前这个数，成为最大累加和的，所以，果断放弃，直接写成：temp[i]=nums[i]
if(temp[i-1]>0){
temp[i]=temp[i-1]+nums[i];
}else{
temp[i]=nums[i];
}
//不断的更新最大值，最终取到 temp这个数组中的最大值
max=Math.max(max,temp[i]);
}
return max;
}
}
四.最后一个单词的长度
4.最后一个单词的长度：
题目描述
解题思路：
此题目标是：计算字符串最后一个单词的长度
1.利用字符串中的trim()方法，去除掉字符串首尾的空格；
2.再将字符串转成char数组；
3.从后往前的遍历这个数组，只要读取到的结果不是空格，result++;
否则，就退出循环，返回result;
class Solution {
public static int lengthOfLastWord(String s) {
//去掉字符串的收尾空格
s=s.trim();
char[] temp=s.toCharArray();
int result=0;
for(int i=temp.length-1;i>=0;i--){
if(temp[i]!=' '){
result++;
}else{
break;
}
}
return result;
}
}
五.加一
5.加一
问题描述：
解题思路：
1.遍历数组，从数组最后一位(digits.length-1)开始看，如果此时对应的元素值是9，给其+1，这一位就变成了0，然后继续进入循环，看上一位（dights.length-2）是否等于9,如果等于，继续将这位的元素设置为0，如此循环下去；
2.在出循环之前，如果某一位对应的元素不是9，则，直接在原有的基础上+1，然后返回 这个数组即可；
3.如果出了这个for循环，就证明，数组中的每一位元素都是9，因而，需要再创建一个数组，数组长度是原数组长度+1，然后给首元素赋值为：1，其余元素默认为0，返回这个新创建的数组。
class Solution {
public static int[] plusOne(int[] digits) {
int length=digits.length;
for(int i=length-1;i>=0;i--){
if(digits[i]==9){
digits[i]=0;
}else{
digits[i]++;
return digits;
}
}
//出了for 循环，就证明是个 类似于这样的数：999,所以，直至，digits[0]=0;
//这种情况下，就说明，除了首元素是1，其余位都是0
int[] temp=new int[digits.length+1];
temp[0]=1;
return temp;
}
}
六.二进制求和
6.二进制求和
解题思路：
1.从最后一位开始计算，从后往前开始遍历这个字符串
2.分别取出字符串的两位，将这两位和进位数 相加；
3.更新进位数，如果所加之和>=2==>进位数=1；carray=sum/2;
4.更新数值位，sum=sum%2;
5.创建一个stringBuilder,将stringBuilder.append(sum);
6.因为这个字符串是从后往前加，所以，需要反转一下，利用reverse()方法。
class Solution {
public static String addBinary(String a, String b) {
int length1=a.length()-1;
int length2=b.length()-1;
int carry=0; //这个代表 进位数字
StringBuilder stringBuilder=new StringBuilder();
while(length1>=0 && length2>=0){
int sum=a.charAt(length1)-'0'+b.charAt(length2)-'0'+carry;
carry=sum/2;
sum=sum%2;
stringBuilder.append(sum);
length1--;
length2--;
}
while(length1>=0){
int sum=a.charAt(length1)-'0'+carry;
carry=sum/2;
sum=sum%2;
stringBuilder.append(sum);
length1--;
}
while (length2>=0){
int sum=b.charAt(length2)-'0'+carry;
carry=sum/2;
sum=sum%2;
stringBuilder.append(sum);
length2--;
}
if(carry>0){
stringBuilder.append(1);
}
return stringBuilder.reverse().toString();
}
}
七.x的平方根
7.x的平方根
解题思路：
1.首先，判断一下，特殊情况，如果 x=1,需要返回1；
2.运用二分查找法；
3.左边设为：0；右边设为：x;
4.计算出中间值int temp=(left+right)/2;
5.计算中间值的平方数；
6.如果平方值大于x,就说明，平方根在平方值的左边，则将右边设为中间值；
7.如果平方值小于x,就说明，平方根在平方值的右边，则将左边设为中间值。
比如：8
left=0;right=9
temp=(0+9)/2=4 44=16>8
则，right=4; temp=(0+4)/2=2 22=4<8;
此时 left=2,right=4; temp=(2+4)/2=3 3*3=9>8;
则 right=3,此时，left=2,不满足2+1<3
退出循环
返回left---->2
class Solution {
public static int mySqrt(int x) {
if(x==1){
return 1;
}
//二分查找法
int left=0;
int right=x;
while(left+1<right){
int temp=(left+right)/2;
long ret=(long)temp*temp;
if(ret>x){
right=temp;
}else{
left=temp;
}
}
return left;
}
}
八.爬楼梯
8.爬楼梯
解题思路：
由题知：
爬一层楼梯有1种方法；
爬两层楼梯有2种方法；
爬三层楼梯有3种方法；
爬四层楼梯有5种方法；
…
由此，可以看出，符合:F(n)=F(n-1)+F(n-2);
所以，可以运用 函数递归调用、动态规划、斐波那契等方法来解决此问题
下面，是运用了斐波那契来求解此问题
//运用斐波那契数列来求解
class Solution {
public static int climbStairs(int n) {
if(n==1){
return 1;
}
int first=1;
int second=2;
for(int i=3;i<=n;i++){
int third=first+second;
first=second;
second=third;
}
return second;
}
}