思維類型題OJ篇
-
-
- 2、 最短回文串
- 3、求衆數 II
- 4、替換空格
- 5、删除排序數組中的重複項
- 6、移除元素
- 7、Pow(x,n)計算
-
2、 最短回文串
難度：困難 類型： 字元串
給定一個字元串 s，你可以通過在字元串前面添加字元将其轉換為回文串。找到并傳回可以用這種方式轉換的最短回文串。
示例1
輸入: “aacecaaa”
輸出: “aaacecaaa”
示例2
輸入: “abcd”
輸出: “dcbabcd”
方法一：建立原字元串 ss 的反轉，記為 rev，這将用于從字元串開頭找到最大的回文子串，尋找更大的回文子串一旦得到最大的回文子串，就可以傳回結果
string shortestPalindrome(string s){
int n = s.size();
string rev(s);
reverse(rev.begin(), rev.end());
int j = 0;
for (int i = 0; i < n; i++) {
if (s.substr(0, n - i) == rev.substr(i))
return rev.substr(0, i) + s;
}
return "";
}
方法二：KMP 字元串比對算法
string shortestPalindrome(string s) {
int n = s.size();
string r = s;
reverse(r.begin(), r.end());
string str = s + "#" + r;
vector<int> next(2 * n + 2);
getNext(str, next);
return r.substr(0, n - next[2 * n + 1]) + s;
}
void getNext(string& str, vector<int>& next) {
next[0] = -1;
int i = 0, j = -1;
while (i < str.size()) {
if (j == -1 || str[i] == str[j]) {
next[++i] = ++j;
}
else j = next[j];
}
}
方法三：startswith 判斷參數字元是否是指定字元串的開頭，
開頭
的概念預設是參數字元的長度，另外參數字元也可以指定範圍。
def shortestPalindrome(s):
r = s[::-1]
for i in range(len(s) + 1):
# startswith() 方法用于
# 檢查字元串是否是以指定子字元串開頭
# 如果是則傳回 True，否則傳回 False
if s.startswith(r[i:]):
return r[:i] + s
3、求衆數 II
給定一個大小為 n 的數組，找出其中所有出現超過 ⌊ n/3 ⌋ 次的元素。
說明: 要求算法的時間複雜度為 O(n)，空間複雜度為 O(1)
示例1
輸入: [3,2,3]
輸出: [3]
示例2
輸入: [1,1,1,3,3,2,2,2]
輸出: [1,2]
可以利用庫函數 count 來計算一個數在清單中出現的次數。
def majorityElement(self, nums: List[int]) -> List[int]:
n = len(nums)
res = []
for i in range(n):
if nums.count(nums[i])>n//3:
res.append(nums[i])
return set(res)
優化版本
def majorityElement(nums):
n = len(nums)
dic = {}
for x in nums:
if x in dic:
dic[x]+=1
else:
dic[x]=1
return [x for x in dic.keys() if dic[x]>n/3]
在C++ 中可以使用哈希表，但是這并不符合題意，題目要求時間複雜度O（N），空間為O（1）
下面這種思路利用的是一種計數方法，因為衆數的概念是出現的次數要大于n/3次，是以無論任何的數組，裡面的衆數最多有兩個
那我們定義兩個清單，由于要求空間複雜度是O(1)，是以清單中一共放兩個元素，初始化都為0
第一個元素代表 nums 中的值，第二個代表的是出現的次數
這種方法也叫 投票法
超過 n/3 的數最多隻能有兩個，選兩個候選人 a , b，每個候選人的表示方法為[數值，票數]
周遊數組
目前元素為 a 時，a 的票數+1
目前元素為 b 時，b 的票數+1
目前元素既不等于 a 也不等于 b 時
- 如果目前有候選人票數為0，新元素上位，票數更新為1
- 如果目前所有候選人票數都大于0，a,b兩人票數均-1
def majorityElement(nums):
candidate1 = [0, 0]
candidate2 = [0, 0]
for n in nums:
# nums =[1,1,1,3,3,2,2,2]
if n == candidate1[0]:
candidate1[1] += 1
elif n == candidate2[0]:
candidate2[1] += 1
elif candidate1[1] == 0:
candidate1 = [n, 1]
elif candidate2[1] == 0:
candidate2 = [n, 1]
else:
candidate1[1] -= 1
candidate2[1] -= 1
return [x for x in set([candidate1[0], candidate2[0]]) if nums.count(x) > len(nums)/3]
C++ 寫法
vector<int> majorityElement(vector<int>& nums) {
vector<int>v1{0,0};
vector<int>v2{0,0};
for(auto&e:nums){
if(e == v1[0]){
v1[1]++;
}else if(e == v2[0]){
v2[1]++;
}else if(v1[1] ==0){
v1[0] = e;
v1[1] = 1;
}else if(v2[1] ==0){
v2[0] = e;
v2[1] = 1;
}else{
v1[1] -=1;
v2[1] -=1;
}
}
// 此時 v1[0] 和 v2[0]是出現次數最多的兩個數
// 然後還要進行判斷是否大于n/3次
int count1=0,count2=0;
int n = nums.size()/3;
vector<int>res;
for(auto&e:nums){
if(e==v1[0]){
++count1;
}
if(e==v2[0]){
++count2;
}
}
if(count1>n){
res.push_back(v1[0]);
}
if(count2>n && v1[0] != v2[0]){
res.push_back(v2[0]);
}
return res;
}
4、替換空格
請實作一個函數，将一個字元串中的每個空格替換成“%20”
例如，當字元串為We Are Happy.則經過替換之後的字元串為We%20Are%20Happy
思路：如果這個是面試題，我猜面試官一定會讓學生原地進行修改，如果可以申請輔助空間，也就沒啥意思了；我們周遊一遍字元串找到空格的個數，并且計算最終的字元串長度，然後字元串從後往前周遊，這樣時間複雜度為 O(N)，空間複雜度O(1)
參考代碼，C 語言
void replaceSpace(char *str,int length) {
if(str == nullptr){
return;
}
int blank;
for(int i = 0;i<length;++i){
if(str[i] == ' '){
++blank;
}
}
int newlength = length + 2 * blank;
int size = newlength-1;
for(int i = length-1;i>=0;--i){
if(str[i] != ' '){
str[size--] = str[i];
}else{
str[size] = '0';
str[size-1] = '2';
str[size-2] = '%';
size -=3;
}
}
str[newlength] = '\0';
}
5、删除排序數組中的重複項
給定一個排序數組，你需要在原地删除重複出現的元素，使得每個元素隻出現一次，傳回移除後數組的新長度。
不要使用額外的數組空間，你必須在原地修改輸入數組并在使用 O(1) 額外空間的條件下完成
示例1
給定數組 nums = [1,1,2],
函數應該傳回新的長度 2, 并且原數組 nums 的前兩個元素被修改為 1, 2。
你不需要考慮數組中超出新長度後面的元素。
示例2
給定 nums = [0,0,1,1,1,2,2,3,3,4],
函數應該傳回新的長度 5, 并且原數組 nums 的前五個元素被修改為 0, 1, 2, 3, 4。
你不需要考慮數組中超出新長度後面的元素。
def removeDuplicates(self, nums: List[int]) -> int:
if not nums:
return 0
i = 0
for j in range(1,len(nums)):
if nums[i]!=nums[j]:
i+=1
nums[i] = nums[j]
return i+1
如果看不太懂的話，大概可以畫一下圖，用兩個指針初始分别指向第一個值和第二個值，如果兩個值相等的話，另一個指針就會一直往前走，直到不相等的時候，把後面指針指向的值指派給前面指針指向的下一位。
當然題目明确不可使用額外空間，是以python的庫函數set 就不能使用了，如果可以使用set 幾乎一行代碼就可以搞定了！
return len(set(nums));
6、移除元素
給定一個數組 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。
注意這五個元素可為任意順序。
你不需要考慮數組中超出新長度後面的元素。
def removeElement(nums,val):
i ,n = 0,len(nums)
for j in range(0,n):
if nums[j]!=val:
nums[i] = nums[j]
i+=1
return i
利用兩個指針，一個記錄最後剩下的元素個數，一個變量數組，當正在周遊的元素值和給定的值不相等時進行更新。
這個思路其實和上一題的思路是完全的相同的，隻是
i+=1
這條語句的位置和指派語句
nums[i] = nums[j]
位置颠倒了一下。這題的意思是和 val 相等的節點都是要删掉的，是以先把它覆寫掉，指針再往後走一步。而上一題要求重複的元素留下一個，是以是先走一步，然後在覆寫。
另外可以使用庫函數 pop 删除元素，簡單利索
def removeElement(nums, val):
for i in range(len(nums)-1,-1,-1):
if nums[i]==val:
nums.pop(i)
return len(nums)
這裡稍微總結一下range 函數用法：
range 的三個參數：第一個是起始位置，第二個是最終位置，第三個是間隔數，例：
nums = [1,2,3,4,5,6,7,8,9]
for j in range(0, len(nums),2):
print(nums[j],end=' ')# 1 3 5 7 9
如果第三個參數是負數，代表是從後往前走
當然删除元素的方法有很多，remove 也可以喲！
def removeElement(nums, val):
while val in nums:
nums.remove(val)
return len(nums)
7、Pow(x,n)計算
實作 pow(x, n) ，即計算 x 的 n 次幂函數。
示例1
輸入: 2.00000, 10
輸出: 1024.00000
示例2
輸入: 2.10000, 3
輸出: 9.26100
示例3
輸入: 2.00000, -2
輸出: 0.25000
解釋: 2-2 = 1/2/2 = 1/4 = 0.25
可以通過循環的方式去寫，但是可能會導緻時間不夠用，是以我們在判斷 n 是否是偶數，如果是，則可以拆分為兩個部分，這樣時間就會少一半。就比如，210 轉換為 45
def myPow(self, x: float, n: int) -> float:
if n == 0:
return 1
res = 1
flag = True
if n<0:
n = -n
flag = False
while n:
if n%2==0:
n /=2
x *=x
res*=x
n-=1
if flag==False:
return 1/res
return res
當然用遞歸也是一種好辦法
def myPow(self, x, n):
if n==0: return 1
if n<0:
return self.myPow(1/x, -n)
half = self.myPow(x, n/2)
if n%2 == 0:
return half*half
if n>0:
return half*half*x
使用折半計算，每次把 n 縮小一半，這樣n最終會縮小到0，任何數的0次方都為1，這時候我們再往回乘，如果此時 n 是偶數，直接把上次遞歸得到的值算個平方傳回即可，如果是奇數，則還需要乘上個x的值
class Solution {
public:
double myPow(double x, int n) {
double res = 1.0;
int i = n;
while(i!=0){
if(i%2!=0){
res*=x;
}
x*=x;
i/=2;
}
return n<0?1/res:res;
}
};
![LeetCode_Heap_313. Super Ugly Number 超級醜數【堆逾時，動态規劃】【C++】【中等】[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)