維護幸苦，如有打卡歡迎關注公眾號bigsai回復進群，如有幫助歡迎點贊支持！

移除元素

給你一個數組 nums 和一個值 val，你需要 原地 移除所有數值等于 val 的元素，并返回移除后數組的新長度。
不要使用額外的數組空間，你必須僅使用 O(1) 額外空間并 原地 修改輸入數組。
元素的順序可以改變。你不需要考慮數組中超出新長度后面的元素。

示例 1:

給定 nums = [3,2,2,3], val = 3,
函數應該返回新的長度 2, 并且 nums 中的前兩個元素均為 2。
你不需要考慮數組中超出新長度后面的元素。

示例 2:

給定 nums = [0,1,2,2,3,0,4,2], val = 2,
函數應該返回新的長度 5, 并且 nums 中的前五個元素為 0, 1, 3, 0, 4。
注意這五個元素可為任意順序。
你不需要考慮數組中超出新長度后面的元素。

說明:

為什么返回數值是整數，但輸出的答案是數組呢?
請注意，輸入數組是以「引用」方式傳遞的，這意味著在函數里修改輸入數組對于調用者是可見的。
你可以想象內部操作如下:
// nums 是以“引用”方式傳遞的。也就是說，不對實參作任何拷貝
int len = removeElement(nums, val);
// 在函數里修改輸入數組對于調用者是可見的。
// 根據你的函數返回的長度, 它會打印出數組中 該長度范圍內 的所有元素。
for (int i = 0; i < len; i++) {
print(nums[i]);
}

分析：
用一個index標記當前真正的位置，在遍歷的過程中如果當前位置數值和目標數值不相等那么就賦值，如果和待刪除數據相等那么跳過不賦值。這就是遍歷一次重新賦值的過程。

ac代碼為：

public int removeElement(int[] nums, int val) {int index=0;for(int i=0;i<nums.length;i++){if(nums[i]==val)continue;nums[index++]=nums[i];}return index;}

實現 strStr()

題目描述：

給定一個 haystack 字符串和一個 needle 字符串，在 haystack 字符串中找出 needle 字符串出現的第一個位置 (從0開始)。如果不存在，則返回 -1。

示例 1:

輸入: haystack = “hello”, needle = “ll”
輸出: 2

示例 2:

輸入: haystack = “aaaaa”, needle = “bba”
輸出: -1

說明:

當 needle 是空字符串時，我們應當返回什么值呢？這是一個在面試中很好的問題。
對于本題而言，當 needle 是空字符串時我們應當返回 0 。這與C語言的 strstr() 以及 Java的 indexOf() 定義相符

分析
由于數據量的問題，本題使用KMP算法效率并不是很好(KMP需要預處理)，相反使用普通方法效率就很高.使用sunday算法效果也比較普通，就很神奇。

普通的匹配又稱雙指針啥的其實就是一個暴力匹配，但是同為暴力匹配官方給的方法速度要快很多，個人寫法為：

public int strStr(String haystack, String needle) {if(needle==null||"".equals(needle))return 0;char a[]=haystack.toCharArray();char b[]=needle.toCharArray();for(int i=0;i<a.length-b.length+1;i++){int j=-1;while(j++<b.length){if(a[i+j]!=b[j]){break;}if(j==b.length-1)return i; }}return -1;}

官方給的簡潔寫法：

public int strStr(String haystack, String needle) {int L = needle.length(), n = haystack.length();for (int start = 0; start < n - L + 1; ++start) {if (haystack.substring(start, start + L).equals(needle)) {return start;}}return -1;}

kmp方法筆者也實現了，但是由于數據問題效果一般般，當然kmp算法這里就不作詳細介紹：

public int[] getNext(String needle) {char[] p = needle.toCharArray();int[] next = new int[p.length];next[0] = -1;int j = 0;int k = -1;while (j < p.length - 1) {if (k == -1 || p[j] == p[k]) {next[++j] = ++k;} else {k = next[k];}}return next;}public int KMP(String haystack, String needle) {char[] t = haystack.toCharArray();char[] p = needle.toCharArray();int i = 0; // 主串的位置int j = 0; // 模式串的位置int[] next = getNext(needle);while (i < t.length && j < p.length) {if (j == -1 || t[i] == p[j]) { // 當j為-1時，要移動的是i，當然j也要歸0i++;j++;} else {// i不需要回溯了// i = i - j + 1;j = next[j]; // j回到指定位置}if(j==p.length) {return i-j;}}return -1;}public int strStr(String haystack, String needle) {if(needle==null||"".equals(needle))return 0;return KMP(haystack, needle);}

同樣使用sunday算法 (后面會專門講解)效果也是一般般

public int strStr(String haystack, String needle) {if(needle==null||"".equals(needle))return 0;int lastchar[]=new int [200];char a[]=haystack.toCharArray();char p[]=needle.toCharArray();for(int i=0;i<p.length;i++){lastchar[p[i]]=i+1;}int i=0;int j=0;int len=a.length-p.length+1;while (i<a.length) {int index=i-(lastchar[a[i]]-1);//a[i] 字符if(lastchar[a[i]]!=0&&index>=0&&index<len)//可以匹配{while (j<p.length) {//嘗試匹配if(p[j]!=a[index+j])break;j++;}if(j==p.length){return index;}else {i=index+p.length;j=0;}}else {i++;}}return -1;}

兩數相除

題目描述

給定兩個整數，被除數 dividend 和除數 divisor。將兩數相除，要求不使用乘法、除法和 mod 運算符。
返回被除數 dividend 除以除數 divisor 得到的商。
整數除法的結果應當截去（truncate）其小數部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:

輸入: dividend = 10, divisor = 3
輸出: 3
解釋: 10/3 = truncate(3.33333…) = truncate(3) = 3

示例 2:

輸入: dividend = 7, divisor = -3
輸出: -2
解釋: 7/-3 = truncate(-2.33333…) = -2

提示：

被除數和除數均為 32 位有符號整數。
除數不為 0。
假設我們的環境只能存儲 32 位有符號整數，其數值范圍是[?2^31, 2^31 ? 1]。本題中，如果除法結果溢出，則返回 2^31 ? 1。

分析
需要計算除法的數值是多少，并且還遇到以下問題：

• 數值可能越界
• 不能使用乘除法

數值越界問題可以特殊情況考慮即可。但是不能使用乘除法怎么去知道除法的結果是多少呢？

法一：加法累加
這可能是最笨的方法了，除以幾，就用這個數去疊加找到結果。

當然這樣如果數字很大，除數為1，2這種的會很慢，只能勉強ac。

public static int divide(int dividend, int divisor) {int zhengfu=1;long divd=dividend,divs=divisor;if(dividend>0&&divisor<0){divs=-divisor;zhengfu=-1;}else if(dividend<0&&divisor>0){divd=-divd;zhengfu=-1;}else if (dividend<0&&divisor<0) {divd=-divd;divs=-divs;}if(Math.abs(divd)<Math.abs(divs))return 0;long i=0,index=0;if(divs==1)i=divd+1;elsewhile (index<=divd) {i++;index+=divs;}long va=(zhengfu==1?(i-1):(1-i));if(va>Integer.MAX_VALUE)return Integer.MAX_VALUE;if(va<Integer.MIN_VALUE)return Integer.MIN_VALUE;return (int) va;}

用什么方法可以優化算法呢？這就涉及到二進制的問題了。在二進制中：

• 2=0010 表示有2個1
• 4=0100表示有4個1
• 6=0110表示有4+2個1

同樣任何一個數都可以用二進制來表示，1101表示8+4+1.同理我們將這種思想帶到本題進行計算，只不過基礎單位不為1而已：

因為我們使用加法實現數值乘以二的效果，所以利用這個每次找到范圍內的最大個數(數值疊加同時需要其他變量統計次數)。然后處理完這部分數據繼續操作剩下的數值直到停止。當然具體實現上可以考慮剪枝(除數為±1的時候，同時要妥善解決正負數和越界問題，這里就用long處理，全部轉成正數然后用一個標記正負)。

實現代碼為：

public static int divide(int dividend, int divisor){if(divisor==1)return dividend;if(divisor==-1)return dividend==Integer.MIN_VALUE?Integer.MAX_VALUE:-dividend;long value=0;//記錄總次數結果int time=1;//臨時每次的次數long divd=dividend,divs=divisor;//轉成long處理int zhengfu=1;//判斷是正數還是負數if(divd<0){divd=-divd;zhengfu=-zhengfu;}if(divs<0){divs=-divs;zhengfu=-zhengfu;}long team=divs;//臨時數據2倍疊加while (team<=divd) {if(team+team>divd){value+=time;divd-=team;team=divs;time=1;continue;}team+=team;time+=time;}return (int) (zhengfu==1?value:-value);}

結語

好吧，本次打卡結束，歡迎點贊支持，如果打卡歡迎關注公眾號bigsai回復進群即可加入打卡。

總結

以上是生活随笔為你收集整理的LeetCode 27移除元素28实现strStr()29两数相除的全部內容，希望文章能夠幫你解決所遇到的問題。

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