?

題目：對于一個給定的 source 字符串和一個 target 字符串，你應該在 source 字符串中找出 target 字符串出現的第一個位置(從0開始)。如果不存在，則返回?-1。

分析：命名有意義；正常的for循環即可；一定有非空檢查；數組不要越界

1）常規算法：

2,not ac :循環條件不對，j在循環內定義，判斷i+ j,返回值cuo ,

robinhap not ac ：target長度沒判斷，31 ^,長度選錯，循環變量錯，targethash算錯，targetHash = targetHash * 31 % BASE + target.charAt(i) % BASE;沒double check

class Solution {/*** Returns a index to the first occurrence of target in source,* or -1 if target is not part of source.* @param source string to be scanned.* @param target string containing the sequence of characters to match.*/public int strStr(String source, String target) {// write your code here//非空檢查if (source == null || target == null) {return -1;}for (int i = 0; i < source.length() - target.length() + 1; i++) {int j = 0;for (j = 0; j < target.length(); j++) {if (source.charAt(i + j) != target.charAt(j)) {break;}}// loop overif (j == target.length()) {return i;}}return -1;} } View Code

?

2）Rabin-Karp算法：利用hash表的原理，把字符串轉為數字。最后通過比較hash值是否相同

思路：
base
1、異常檢測
2、target長度，為空檢測
3、計算31^m（power）：邊乘邊模
4、targethash: 邊乘邊加邊模
5、hashcode :邊乘邊加邊模
i < mi-1:繼續
i>m-1:abcd - a ,負數檢測
hashcode == targethash
double check

not ac : abcd -a ，hashCode = hashCode - source.charAt(i - m) * power % BASE;忘記模；判斷hashcode 是否小于0，寫在外面了

class Solution {/*** Returns a index to the first occurrence of target in source,* or -1 if target is not part of source.* @param source string to be scanned.* @param target string containing the sequence of characters to match.*/public int BASE = 1000000;public int strStr(String source, String target) {// write your code here//非空檢查if (source == null || target == null) {return -1;}int m = target.length();//target長度檢查if (m <= 0) {return 0;}//31^mint pow = 1;for (int i = 0; i < m; i++) {pow = pow * 31 % BASE;}//targetcodeint targetCode = 0;for (int i = 0; i < m; i++) {targetCode = (targetCode * 31 + target.charAt(i)) % BASE;}//hashCodeint hashCode = 0;for (int i = 0; i < source.length(); i++) {hashCode = (hashCode * 31 + source.charAt(i)) % BASE;if (i < m - 1) {continue;}// i// abcd - aif (i >= m) {hashCode = hashCode - (pow * source.charAt(i - m)) % BASE;}// hashcode < 0 ?if (hashCode < 0) {hashCode = hashCode + BASE;}//hash值是否相等if (hashCode == targetCode) {//double checkif (source.substring(i - m + 1, i + 1).equals(target)) {return i - m + 1;}}}return -1;} } View Code

?

轉載于:https://www.cnblogs.com/lingli-meng/p/6511499.html

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的一、字符串问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。