LeetCode第28/35題
- 2019 年 10 月 7 日
- 筆記
LeetCode第28題
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"Output: -1
翻譯：
返回大字元串中第一次找到給定小字元串的下標
思路：
String有自帶API：indexOf
程式碼：
class Solution { public int strStr(String haystack, String needle) { return haystack.indexOf(needle); }}
我們來看下SDK源碼
public int indexOf(String str) { return indexOf(str, 0);} public int indexOf(String str, int fromIndex) { return indexOf(this, str, fromIndex);} static int indexOf(String source, String target, int fromIndex) { if (fromIndex >= source.count) { return (target.count == 0 ? source.count : -1); } if (fromIndex < 0) { fromIndex = 0; } if (target.count == 0) { return fromIndex; } char first = target.charAt(0); int max = (source.count - target.count); for (int i = fromIndex; i <= max; i++) { /* Look for first character. */ if (source.charAt(i)!= first) { while (++i <= max && source.charAt(i) != first); } /* Found first character, now look at the rest of v2 */ if (i <= max) { int j = i + 1; int end = j + target.count - 1; for (int k = 1; j < end && source.charAt(j) == target.charAt(k); j++, k++); if (j == end) { /* Found whole string. */ return i; } } } return -1;}
思路也很簡單和暴力，就是遍歷對比字元
LeetCode第35題
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Example 1:
Input: [1,3,5,6], 5Output: 2
Example 2:
Input: [1,3,5,6], 2Output: 1
Example 3:
Input: [1,3,5,6], 7Output: 4
Example 4:
Input: [1,3,5,6], 0Output: 0
翻譯：
給定一個有序數組和一個給定值，在數組中找到這個值所在的下標；如果沒有這個值，那麼返回他應該插入的下標位置
思路：
和選擇排序或插入排序思路相似，就是將定值和已經排好序的數組遍歷比較大小
程式碼：
class Solution { public int searchInsert(int[] nums, int target) { int j= 0; for(int i = 0;i<nums.length;i++){ if(nums[i] < target){ j++; } } return j; }}
如果數組元素比給定值要小，那麼J就+1；如果數組元素比給定值要大，J不操作；那麼下標比J小的元素值就比給定值要小，即J就是我們所需要的下標
