牛客打卡第7天
今日收获
二分查找-II
import java.util.*; public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 如果目标值存在返回下标，否则返回 -1 * @param nums int整型一维数组 * @param target int整型 * @return int整型 */ public int search (int[] nums, int target) { int left = 0; int right = nums.length-1; while(left<=right){ int mid = left + (right-left)/2; if(target < nums[mid]){ right = mid-1; }else if(target > nums[mid]){ left = mid+1; }else{ //对于中值前有与中值重复的数字的遍历，匹配题目中说的从左到右返回第一个相同的索引值 for(int i=0;i<=mid;i++){ if(nums[i] == target) return i; } } } return -1; // write code here } }跳台阶
跳台阶问题--->斐波纳契数列的应用例子import java.util.ArrayList; //代码维护了一个列表：涉嫌以空间换时间的概念 public class Solution { public int jumpFloor(int target) { int count = 0; if(target<=0){ return -1; } ArrayList<Integer> res = new ArrayList<Integer>(); res.add(1); res.add(1); res.add(2); if(target==1) return res.get(1); if(target==2) return res.get(2); for(int i=3;i<=target;i++){ res.add(res.get(i-1)+res.get(i-2)); } return res.get(target); } }反转数字
public class Solution { /** * Java中int数据类型的32位，取值范围[Integer.MIN_VALUE,Integer.MAX_VALUE] * @param x int整型 * @return int整型 */ public int reverse (int x) { // write code here long res = 0; while(x != 0){ res = res*10 + x%10; x = x/10; } if(res < Integer.MIN_VALUE || res > Integer.MAX_VALUE){ return 0; } return (int)res; } }寻找峰值
public class Solution { /** * 寻找最后的山峰: 遍历数组求最值的问题， * 重点注意：排查最后一个元素的情况 * @param a int整型一维数组 * @return int整型 */ public int solve (int[] a) { if(a == null || a.length == 0 || a.length == 1){ return -1; } if (a[a.length-1]>=a[a.length-2]){ return a.length-1; } int tmp = -1; for(int i=0;i<a.length-1;i++){ if(a[i]>=a[i+1]){ tmp = Math.max(tmp,i); } } return tmp; // write code here } }数组中出现一次的数
public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * 哈哈哈哈~双重循环，暴力求解 * @param arr int一维数组 * @param k int * @return int */ public int foundOnceNumber (int[] arr, int k) { int count = 0; for(int a : arr){ for(int i=0;i<arr.length;i++){ if(a == arr[i]){ count += 1; } } if(count == 1){ return a; } count = 0; } return count; // write code here } }螺旋矩阵
//重点：搞清楚螺旋矩阵的四种旋转方向，分开情况依次求解即可 public class Solution { public ArrayList<Integer> spiralOrder(int[][] matrix) { ArrayList<Integer> res = new ArrayList<Integer>(); if(matrix==null||matrix.length==0||(matrix.length==1&&matrix[0].length==0)){ return res; } int m = matrix.length; int n = matrix[0].length; String direction = "right"; int top = 0; int bottom = m-1; int left = 0; int right = n-1; while(true){ for(int i=left;i<=right;i++){ res.add(matrix[top][i]); } top++; if(left>right || top>bottom) break; for(int i= top;i<=bottom;i++){ res.add(matrix[i][right]); } right--; if(left>right || top>bottom) break; for(int i=right;i>=left;i--){ res.add(matrix[bottom][i]); } bottom--; if(left>right || top>bottom) break; for(int i=bottom;i>=top;i--){ res.add(matrix[i][left]); } left++; if(left>right || top>bottom) break; } return res; } }第一个只出现一次的字符
//不好意思哈哈哈~又是暴力求解 public class Solution { public int FirstNotRepeatingChar(String str) { int count = 0; for(int i=0;i<str.length(); i++){ for(int j=0;j<str.length(); j++){ if(str.charAt(i) == str.charAt(j)){ count += 1; } } if(count==1){ return i; } count = 0; } return -1; } }最大公约数
//最大公约数求解有很多种方法：本文用的欧几里得算法 //九章算术中的 更相减损法也很不错！！！ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * 求出a、b的最大公约数。 * @param a int * @param b int * @return int */ public int gcd (int a, int b) { // 欧几里得算法 if(b==0){ return a; } int reminder = a % b; return gcd(b,reminder); // write code here } }把字符转换成整数
//其实python做很舒服，可是最近在练Java public class Solution { public int StrToInt(String str) { int res = 0; int flag = 0; for(int i=0;i<str.length();i++){ if(str.charAt(i)>='0' && str.charAt(i)<='9'){ res = res*10+str.charAt(i)-'0'; }else if(str.charAt(i)=='+'){ if(i>0 || flag!=0) return 0; flag=1; }else if(str.charAt(i)=='-'){ if(i>0||flag!=0) return 0; flag = -1; }else return 0; } return flag>=0?res:res*flag; } }替换空格
//直接用字符串内置方法：贼香！！！ public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * * * @param s string字符串 * @return string字符串 */ public String replaceSpace (String s) { return s.replace(" ","%20"); // write code here } }好的~ 今天的总结就到这里~ 明天继续~
