思维类型题OJ篇3

古城微笑少年丶 2023-06-23 09:54 2阅读 0赞

### 思维类型题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

如果看不太懂的话，大概可以画一下图，用两个指针初始分别指向第一个值和第二个值，如果两个值相等的话，另一个指针就会一直往前走，直到不相等的时候，把后面指针指向的值赋值给前面指针指向的下一位。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]  
当然题目明确不可使用额外空间，所以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;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191114230344502.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzNzYzMzQ0,size_16,color_FFFFFF,t_70