基础类型 OJ 题篇 3

蔚落 2023-06-20 09:15 3阅读 0赞

### 基础类型 OJ 题篇 ###

*   *   *  1、计数质数
         *  2、同构字符串
         *  3、逆波兰表达式求值
         *  4、翻转字符串里的单词

### 1、计数质数 ###

统计所有小于非负整数 n 的质数的数量

> 示例  
> 输入: 10  
> 输出: 4  
> 解释: 小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7

删选法：如果 2 不是质数，那么 2 的倍数都不是，如果 3 不是质数，那么 3 的倍数也都不是了…

int countPrimes(int n) { 
            if(n<2){ 
                return 0;
            }
            vector<bool>flag(n+1,true);
            int cnt = 0;
            for(int i = 2;i<n;++i){ 
                if(flag[i]){ 
                    for(int j = i+i;j<n;j+=i){ 
                        flag[j] = false;
                    }
                    ++cnt;
                }
            }
            return cnt;
        }

python 写法

def countPrimes(self, n: int) -> int:
            if n<2:
                return 0
            temp = [1]*(n+1)
            temp[0] = temp[1] = temp[n] = 0
            for i in range(2,n):
                if temp[i]:
                    temp[i*i:n:i] = [0]*len(temp[i*i:n:i])
            return sum(temp)

### 2、同构字符串 ###

给定两个字符串 s 和 t，判断它们是否是同构的。

如果 s 中的字符可以被替换得到 t ，那么这两个字符串是同构的。

所有出现的字符都必须用另一个字符替换，同时保留字符的顺序。两个字符不能映射到同一个字符上，但字符可以映射自己本身

> 示例1  
> 输入: s = “egg”, t = “add”  
> 输出: true

> 示例2  
> 输入: s = “foo”, t = “bar”  
> 输出: false

> 示例3  
> 输入: s = “paper”, t = “title”  
> 输出: true

可以使用一个字典结构将 s 中的 字符和 t 中的字符一一对应，然后如果发现不对应则返回 fasle, 最后返回 true

def isIsomorphic(self, s: str, t: str) -> bool:
    		if len(set(s))!=len(set(t)):
                return False
            if s =='' and t=='':
                return True
            dic = { }
            for i in range(len(s)):
                if s[i] not in dic:
                    dic[s[i]] = t[i]
                else:
                    if dic[s[i]] != t[i]:
                        return False
            return True

另外还有一种思路是：利用 set 以及 zip函数

def isIsomorphic(self, s: str, t: str) -> bool:
    	return len(set(s))==len(set(t)) == len(set(zip(s,t)))

zip 函数是将两个字符串进行组合，例如：  
a = \[1,2,3\]  
b = \[4,5,6\]  
c = zip(a,b)  
print(list( c )) = \[(1,4),(2,5),(3,6)\]

### 3、逆波兰表达式求值 ###

根据逆波兰表示法，求表达式的值

有效的运算符包括 +, -, \*, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：

整数除法只保留整数部分。  
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

> 示例1  
> 输入: \[“2”, “1”, “+”, “3”, “\*”\]  
> 输出: 9  
> 解释: ((2 + 1) \* 3) = 9

> 示例2  
> 输入: \[“4”, “13”, “5”, “/”, “+”\]  
> 输出: 6  
> 解释: (4 + (13 / 5)) = 6

> 示例3  
> 输入: \[“10”, “6”, “9”, “3”, “+”, “-11”, “”, “/”, “”, “17”, “+”, “5”, “+”\]  
> 输出: 22  
> 解释:  
> ((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5  
> = ((10 \* (6 / (12 \* -11))) + 17) + 5  
> = ((10 \* (6 / -132)) + 17) + 5  
> = ((10 \* 0) + 17) + 5  
> = (0 + 17) + 5  
> = 17 + 5  
> = 22

思路：遍历 tokens 中的字符，如果是数字则进栈，否则取出最后进入的两个数和当前 tokens 进行字符的运算

int evalRPN(vector<string>& tokens) { 
            stack<int>s;
            for(int i=0;i<tokens.size();++i){ 
                if(!(tokens[i]=="+" || tokens[i]=="-" || tokens[i]=="*"||tokens[i]=="/")){ 
                    s.push(stoi(tokens[i]));
                }else{ 
                    int a = s.top();
                    s.pop();
                    int b = s.top();
                    s.pop();
                    if(tokens[i]=="+"){ 
                        s.push(a+b);
                    }
                    // 后出栈的作为被减数，一定不要相反
                    else if(tokens[i]=="-"){ 
                        s.push(b-a);
                    }
                    else if(tokens[i]=="*"){ 
                        s.push(a*b);
                    }
                    // 后出栈的是被除数 
                    else{ 
                        s.push(b/a);
                    }
                }
            }
            return s.top();
        }

python 写法

def evalRPN(self, tokens: List[str]) -> int:
            stack = []
            for token in tokens:
                if token not in ['-','+','*','/']:
                    stack.append(int(token))
                else:
                    b = stack.pop()
                    a = stack.pop()
                    if token == '+':
                        result = a+b
                    elif token == '-':
                        result = a-b
                    elif token =='*':
                        result = a*b
                    elif token =='/':
                        result = a//b
                        # 由于 python 的除法运算符和 c++ 不一样
                        # 比如 -5//2 == -3 所以要加 1 变为 -2
                        # 如果用 C++写，则直接 result = a/b就行了
                        result = result + 1 if result<0 and a%b!=0 else result
                    stack.append(result)          
            return stack[0]

### 4、翻转字符串里的单词 ###

给定一个字符串，逐个翻转字符串中的每个单词

> 示例 1  
> 输入: “the sky is blue”  
> 输出: “blue is sky the”

> 示例 2  
> 输入: " hello world! "  
> 输出: “world! hello”  
> 解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

> 示例 3  
> 输入: “a good example”  
> 输出: “example good a”  
> 解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个

c++ 利用 stringstream 输入输出流

string reverseWords(string s) { 
            stringstream ss;
            ss<<s;
            string res,temp;
            while(ss>>temp){ 
                res = " " + temp + res;
            }
            if(res !=""){ 
                res.erase(res.begin());
            }
            return res;
        }

python 写法

def reverseWords(self, s: str) -> str:
            res = []
            # 将字符串转换为列表，以空格隔开
            # 另外如果 s 中有多余的空格，也会删除
            ss = s[::-1].split()
            for i in ss:
                res.append(i[::-1])
            # 最后将列表按照空格的间隔方式转换为字符串
            return ' '.join(res)