写Leetcode中C++一些基本语法和算法
文章由两部分组成1.一些基础的语法2.一些惊艳的算法小结构一些基础的语法C++中字符串操作排序sort(s)即将字符串s改变了顺序集合1容器std::vector<T>定义时 vector<int> value;也可以vecotr<i
文章由两部分组成
1.一些惊艳的算法小结构
2.一些基础的语法
一些惊艳的想法
算法说明
647题
长度n 的字符串会生成 2n−1 组回文中心
int n = s.size(), ans = 0;
for (int i = 0; i < 2 * n - 1; ++i) {
int l = i / 2, r = i / 2 + i % 2;
while (l >= 0 && r < n && s[l] == s[r]) {
这样我们只要从 00 到 2n - 22n−2 遍历 ii，就可以得到所有可能的回文中心，这样就把奇数长度和偶数长度两种情况统一起来了。
90 求子集
给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
说明：解集不能包含重复的子集。
如果无重复的话，返回值肯定是2^n,即每个数组要么加进去，要么不加进去；
方法一，计算某位置数字重复了k次，分别处理
方法二，保留上次位置start，如果是重复的话，就从最后的位置开始添加
毕竟[1,2,2]
中2加一次可以
加2 ，2 可以，但是不能在之前[1],[1,2]再加一次2，就会编程[1],[1,2],[1,2,2],[1,2]
所以在上次结尾位置再加单个2.就不用数重复几次k了。少一次嵌套的循环
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
nums.sort()
start , res = 0 , [[]]
for i in range(len(nums)):
if i==0 or nums[i]!=nums[i-1]: start = 0
n_res = len(res)
while start < n_res:
clone = res[start].copy()
clone.append(nums[i])
res.append(clone)
start += 1
return res
119. Pascal’s Triangle II 中 ，优美的跳过循环中的第一个元素
class Solution23(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
row = [1] * (rowIndex+1)
for i in range(rowIndex):
for j in range(i-1,-1,-1):
row[j+1] += row[j]
return row
中 for i in range(i-1 , -1 , -1)
看似普通的，不过平时很少用-1，且range下限也是-1，我很多时候下限就是普通的 0
仔细一琢磨，针对这道题，题目里需要在i=0的时候不对row做操作，从第二个元素才开始做操作
因而i=0时，j并不循环，这个for直接跳过，直接到下一次循环i=1
备注：
for i in range(1,0,-1):
print(i) # 能打印出1
#range函数左闭右包[) 左边元素是取得到的，右边元素取不到
for i in range(-1,-1,-1):
print(i) # 并不输出任何元素，左右发生冲突时取不到
494 dfs中两个变量作为字典的key的一种小技巧
String key = u + “_” + cur;
if (cache.containsKey(key)) return cache.get(key);
把两个key组成一个字符串！！！ 作为不可变变量的key！
448. Find All Numbers Disappeared in an Array，空间复用？O(1)解决O(n)的空间复杂度
题目是输入[4,3,2,7,8,2,3,1]，输出数组里没出现的正的数字，数字为1-n,本题输出[5,6]，题目不难O(n)很容易解决，要求空间复杂度为O(1)，过分
def findDisappearedNumbers(self, nums):
for i,each in enumerate(nums):
if nums[abs(each)-1]>0:
nums[abs(each)-1] *= -1
res = [i+1 for i,each in enumerate(nums) if each >0]
return res
不让单独申请内存，空间复杂度要O(1)
那么就把输入进来的nums改变了。利用输入数组都是正数的特点，在他们的基础上加上正负号的标记flag，来作为信息记录的位置，传说中的“空间复用”。巧妙在使用numerate，利用从零到一的位置序列信息，把具体数字当做索引，把相应位置置位-1，代表这个位置的原本那个数字“出现过”了
另一种空间复用的方法：异或 。 使用异或方法，可以在很多出现过偶数的数字中找到唯一的出现了奇数次的数字
509. Fibonacci Number 动态规划入门->优美的斐波那契数列
最简单的迭代，可是每次F(N)都会重新计算，复杂度怎么也有 O ( n n ) O(n^n) O(nn)也许
def fib(self, N):
if N == 0:
return 0
elif N==1:
return 1
return self.fib(N-1) + self.fib(N-2)
迭代太费劲，有人用全局变量把每个F(n)放在字典里，查到n，则直接返回，不用迭代，把复杂度降低到O(n)
最好的思路是动态规划，用两个数来回迭代，网上累加。（从0向上增加，而不是从上向下迭代）所以我写的代码大概是这样：
def fib(self, N):
if N==0:
return 0
elif N==1:
return 1
flist = [0,1]
res = 0
for i in range(2,N+1):
flist[0] , flist[1] = flist[1] , flist[0]
res = sum(flist)
flist[1] = res
return res
大概就是这样，不过两个特殊情况0,1，看到别人可以融合在一个非常优美的代码中：
def fib(self, N):
a, b = 0, 1
for _ in range(N):
a , b = b , a+b
return a
看完这个代码我思索了一会，用纸调试了一下。雾草，这么强。
Python字典初始化
一般adic = {}， 然后一个一个往里加，如果没有，就新建一个，如果有就增加values
adic = {}
for one in arr1:
if one not in adic:
adic[one] = 1
else:
adic[one] += 1
原来利用python字典，可以更方便，有默认语法
hm = {}
for i in arr1:
hm[i] = hm.get(i,0) + 1
如果字典中没有i 就创建，并且值为0 代码行数少了不少，也很方便
有限长度下 O ( n 2 ) O(n^2) O(n2) 退化为 O ( n ) O(n) O(n)的方法
1010.Pairs of Songs With Total Durations Divisible by 60中判断有几组数字之和为60的倍数。
常理是不断循环，一共有两个嵌套循环，因而复杂度为n平方。
但是由于60 是一个定长数字，最多60长的数组就可以解决
def numPairsDivisibleBy60(self, time: List[int]) -> int:
res = 0
count = [0] * 60
for one in range(len(time)):
index = time[one] % 60
res += count[(60 - index)%60]
count[index] += 1
return res
也可以使用字典代替数组，但是都是归一化到60长。通过i 可以直接指定找到60-i位置的情况。况且字典查询一个数字时间O(1)，而不是O(n)，因而n方的复杂度降低为n
989. Add to Array-Form of Integer， Python中把数字当字符串的技巧
这道题用数组描述整数， A = [1,2,0,0], K = 34 ，想求A+K= 1234，难点在于进位
def addToArrayForm(self, A: List[int], K: int) -> List[int]:
a_string = "".join([str(x) for x in A])
return [int(x) for x in str(int(a_string)+K)]
骚操作之后得到a_string的一个完整字符串，然后转换成整型，然后相加，再变成字符串，一个一个写进数组中，写的时候每个单个数字再变回str
有点麻烦，不过代码比较短，不用每位*10什么的来获得原来的数字
查询要慎用
a 是一个数组，查询里面有无b if b in a
看似简单的一句话
是一个O(n)的操作，如果在大循环内部，就会变成n方！
特别要循环的话，可以
a = set(a)
if b in a
查询set集合中的元素是一个O(1)的操作
643. Maximum Average Subarray I 字符串中截取操作也费时
截取长数组中一部分字符串，求和
def findMaxAverage(self, nums: List[int], k: int) -> float:
res = -sys.maxsize
for index in range(len(nums)-k+1):
res = max(res,sum(nums[index:index+k]))
return res/k
中要进行n次nums[index:index+k]，提交后超时，因而选用+nums第index + k个，减第一个index的方式求和，勉强能通过
不过，在时间要求不高的地方，可以用一行写两个for循环！！！
n = [x for line in rowBound for x in line[columnBound[0]:columnBound[1]]]
震惊，至于吗，这么节约代码的行数
相当于
for line in rowBound:
for x in line[columnBound[0]:columnBound[1]]:
b.append(x)
不过确实一行应该会比三行运行的更快一些
665. Non-decreasing Array确定数组更改一个数字就可以变成非降数列
[2,3,3,1,4] 中,第一个不满足的是[3,1]部分，改1为3就能递增
[2,1,6,6]中第一个不满足的是[1,6]组合，改1为2就能递增
因而大致有两种情况，要么改第一个数字，要么改第二个数字。
def isorder(self, subnums):
for one in range(len(subnums) - 1):
if subnums[one] > subnums[one+1] :
return False
return True
def checkPossibility(self, nums: List[int]) -> bool:
for i in range(len(nums)-1):
if nums[i] > nums[i+1]:
A = nums.copy()
B = nums.copy()
del A[i]
del B[i+1]
return self.isorder(A) or self.isorder(B)
return True
这个方法简单粗暴。两种情况都看一下，有一个满足情况就行。 也不看不符合的数字改成谁比较好，直接删了，反正非降，可以相等。因而对改成几要求不高，和前面，后面相等就行。只不过空间占用O(n)
事必躬亲的方法：
- Get the point where it is decreasing.
- If not found, return true
- The two element we will try is the point where it starts decreasing or its next element
- The check method will basically ignore the provided index and see if it is strictly increasing
class Solution {
public boolean checkPossibility(int[] nums) {
if (nums == null || nums.length == 0)
return true;
int i = getDecreasing(nums);
return i == -1 || check(nums, i) || check(nums, i + 1);
}
private boolean check(int[] nums, int i) {
for (int j = 1; j < nums.length; j++) {
int prev = j - 1 == i ? j - 2 : j - 1;
if (j != i && prev >= 0 && nums[prev] > nums[j])
return false;
}
return true;
}
private int getDecreasing(int[] nums) {
for (int i = 1; i < nums.length; i++) {
if (nums[i - 1] > nums[i])
return i - 1;
}
return -1;
}
}
字典初始化
index_map = {x:i for i, x in enumerate(order)}
这也太简单了，直接把每个元素遍历，且值是序号
一行搞定！
953. Verifying an Alien Dictionary比较字符串大小
按照给定order顺序来比较words中单词是否按升序排列
words = ["hello","leetcode"], order = "hlabcdefgijkmnopqrstuvwxyz"
这个结题有两个亮点
1. while(j<nums && words[i-1][j]==words[i][j]) j++;快速往后排到第一个不一样的字符。跳过中间未知个数的相同字符。注意这一步之后要判断是否有一个单词被完全比较完了
2. 比较时如果有异常，就return false，否则就continue。比较长度为两个单词最短的那个。剪短代码包含了题中想比较的东西。
bool isAlienSorted(vector<string>& words, string order) {
if(words.size()<=1) return true;
for(int i=1 ; i<words.size() ; i++){
int n_pre = words[i-1].size();
int n_now = words[i].size();
int nums = n_pre < n_now? n_pre : n_now;
int j=0;
while(j<nums && words[i-1][j]==words[i][j]) j++;
if(j == nums){
if (n_pre > n_now) return false;
else continue;
}
if( order.find(words[i][j]) < order.find(words[i-1][j]) ) return false;
}
return true;
}
1071. Greatest Common Divisor of Strings 求两个字符串的最大公约数
str1 = “ABABAB”, str2 = “ABAB” 则输出AB
str1 = “ABCABC”, str2 = "ABC"输出ABC str1 = “LEET”, str2 = "CODE"输出“”空
讲真还挺难想
class Solution{
public:
string gcdOfStrings(string str1, string str2)
{
int i, j;
for (i = 0, j = 0; i < str1.length () && j < str2.length (); i++, j++) {
if (str1 [i] != str2 [j])
return "";
}
if (i == str1.length () && j == str2.length ())
return str1;
if (i == str1.length ())
return gcdOfStrings (str1, str2.substr (j));
else
return gcdOfStrings (str2, str1.substr (i));
}
};
递归方法，放在这的话，其实还没理解明白。
class Solution(object):
def gcdOfStrings(self, str1, str2):
n1 = len(str1)
n2 = len(str2)
if n2>n1:
str1,str2 = str2,str1
n1,n2 = n2,n1
if n1%n2==0 and str1==str2*(n1/n2):
return str2
i=2
while n2>i:
lval = str2[:n2/i]
rval = str2[n2/i:]
if lval*(i-1)==rval and n1%len(lval)==0:
return lval
i+=1
return ""
Python方法，第一步，让n2是短的那个，第二步如果n1是几倍n2则返回n2
第三关键，（由于第二步考虑了n1是几倍的n2，因而i=1的情况被考虑过了）
直接考虑i=2的情况，即n1比n2长
分成两个字符串，lval和rval 其中rval由N倍的lval组成就对了，找到最大N，最短lval就对了
if lval*(i-1)==rval and n1%len(lval)==0:
return lval
还要判断长的n1是不是由lval组成的
双指针
双指针可以解决：链表找到倒数第N个数，按某种规则倒序等
917. Reverse Only Letters
Input: “ab-cd”
Output: “dc-ba”
非英文部分不动，只颠倒英文字母。用双指针从前，后往中间不断找到字母，再交换顺序。则完成特定规则的倒序。这个也适合其他变种的倒序。
def reverseOnlyLetters(self, S: str) -> str:
i , j= 0 , len(S)-1
alist = list(S)
while(i<j):
if not alist[i].isalpha():
i+=1
continue
if not alist[j].isalpha():
j-=1
continue
alist[i] , alist[j] = alist[j] , alist[i]
i+=1
j-=1
return "".join(alist)
819. Most Common Word 找出句子中最常见单词
Input:
paragraph = "Bob hit a ball, the hit BALL flew far after it was hit."
banned = ["hit"]
Output: "ball"
有几个细节，1要求大小写都视作小写，2 忽略非字母 （标点数字等）
代码中构造的for循环比较有特点，自己控制 i++ 而不是默认 i++ 通过两个while push_back挑选出一个单词
使用C++11中的isalpha() tolower()简单完成判断
banned中是忽略的单词
public:
string mostCommonWord(string paragraph, vector<string>& banned) {
unordered_map<string , int> m;
int psize = paragraph.size();
for(int i=0; i<psize;){
string s="";
while(i<psize && isalpha(paragraph[i])) { s.push_back(tolower(paragraph[i])); i++; }
while(i<psize && !isalpha(paragraph[i])) i++;
m[s]++;
}
for(auto x: banned) m[x] =0;
string res = "";
int count = 0;
for(auto x:m)
if(x.second>count) res = x.first , count = x.second;
return res;
}
};
824. Goat Latin 对字符串中一系列单词进行改造
由于要处理空格，第一个单词前面没有空格。其实可以先加上，这样就不用把i=1变成特殊情况if 最后return res.substr(1); 就跳过了第一个空格。和某些链表操作方法相同
string toGoatLatin(string S) {
unordered_set<char> vowel({'a', 'e', 'i', 'o', 'u', 'A', 'E', 'I', 'O', 'U'});
istringstream iss(S);
string res, w;
int i = 0, j;
while (iss >> w) {
res += ' ' + (vowel.count(w[0]) == 1 ? w : w.substr(1) + w[0]) + "ma";
for (j = 0, ++i; j < i; ++j) res += "a";
}
return res.substr(1);
}
其中res += ' ' + (vowel.count(w[0]) == 1 ? w : w.substr(1) + w[0]) + "ma";最为简洁。在单句代码中加入三目判断。
不过这道题的Python代码简直精髓的简短
def toGoatLatin(self, S):
vowel = set('aeiouAEIOU')
def latin(w, i):
if w[0] not in vowel:
w = w[1:] + w[0]
return w + 'ma' + 'a' * (i + 1)
return ' '.join(latin(w, i) for i, w in enumerate(S.split()))
哇~~~~~~~~~~~~ 精髓
77题. Combinations
Input: n = 4, k = 2
Output:
[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4] ]
输出所有可能的长度为k的排列组合
使用DFS深度优先搜索
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
res = []
self.dfs(range(1 , n+1) , k , 0 , [] , res)
return res
def dfs(self , nums , k , index , path , res):
if(k==0):
res.append(path)
return
for i in range(index , len(nums)):
self.dfs(nums , k-1 , i+1 , path+[nums[i]] , res)
是一道middle题目，Ummmm… 只能把代码背下来了，果然不是三四行看一眼就能懂的easy级别
代码中通过k来作为本轮循环中还需要append几个元素，k=0时本轮就可以append并返回了
i作为index，通过range（index, len(nums)）来控制本轮添加哪个数字，这个数字在某一轮中是个递增的数字
nums一直传着，取值用。res一直传着，通过append操作改变res因而不需要返回值。
path就比较复杂了，是当前已经append得到的中间结果。
Length of Last Word
判断最后一个单词长度（注意哪儿都有可能有空格，包括最后一个位置）
方法1
从前往后，不断算某个单词长度，上一个单词长度pre，如果最后是0 ， 返回pre
但是，不是链表，因而可以直接访问最后一个元素
方法2
直接从后往前
int lengthOfLastWord(string s){
int len=0 , tail = s.length()-1;
while(tail>=0 && s[tail]==' ')tail--;
while(tail>=0 && s[tail]!=' '){len++ ; tail--;}
return len
}
从后往前则规则简单很多
二进制转换十进制
循环res = res*2 + head.val这种是常见算法
稍微可以更快，用移位代替乘法， 逻辑或 代替加法
res = res<<1 | head.val毕竟移位一次就是*2 ， head.val不是0就是1因而才可以用逻辑或来代替
112. Path Sum，二叉树中查询是否有分支之和等于sum
DFS ， BFS深度优先，广度优先搜索
BFS宽度优先
不用递归，直接单循环。往pool里存以后可能要去处理的内容
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False #不判断的话下一行root.val可能出错
pool = [ (root , sum-root.val) ] # 第一个val就已经要被val减
while pool:
root , val = pool.pop(0) #从0位置取，才是真正的宽度优先，
# 先取层数较浅的那一个
if not root.left and not root.right and val==0:
# 注意这里是val==0，而不再是sum-root.val，此时是正确节点的子节点（空的节点，且这个节点的父节点在所需要的那条路径）
return True
if root.left:
pool.append((root.left , val - root.left.val))
# 注意这里是将左边的root.left.val节点放入pool中
if root.right:
pool.append((root.right , val - root.right.val))
return False
DFS 深度优先
迭代版本：
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root: return False
pool = [ (root , root.val) ]
while pool:
root , val = pool.pop()
if not root.left and not root.right and val==sum:
return True
if root.left:
pool.append((root.left , val + root.left.val))
if root.right:
pool.append((root.right , val + root.right.val))
return False
递归版本：
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
res = []
self.dfs( root , sum , res)
return any(res)
def dfs(self , root , sum , res):
if root:
if not root.left and not root.right and root.val==sum: res.append(True)
if root.left:
self.dfs(root.left , sum-root.val , res)
if root.right:
self.dfs(root.right , sum-root.val , res)
但是好像有点繁琐：
def hasPathSum(self, root: TreeNode, sum: int) -> bool:
if not root : return False
if not root.left and not root.right and root.val==sum: return True
return self.hasPathSum(root.left , sum-root.val) or self.hasPathSum(root.right , sum-root.val)
这个虽然是递归算法，不过运行起来时间最短，内存最小。值得推荐
这几个算法最重要的是口算临界点，即root.val == sum 还是root.va l== 0 还是什么
====
101. Symmetric Tree判断二叉树是否对称
迭代，递归两个版本，先看迭代版本，用pool存储要判断的节点：
def isSymmetric(self, root: TreeNode) -> bool:
if not root : return True
pool = [(root.left , root.right)]
while(len(pool)):
le , ri = pool.pop(0) # 一定要从0取
if not le and not ri: continue
if not le or not ri: return False
# print("___",le.val , ri.val)
if le.val==ri.val:
# 一定要insert到0位置，而不是append到末尾
pool.insert(0,(le.left , ri.right))
pool.insert(0,(le.right , ri.left))
else:
return False
return True
递归版本看起来短一些
def isSymmetric(self, root: TreeNode) -> bool:
def isSym(L,R):
if not L and not R: return True
if L and R and L.val == R.val:
return isSym(L.left, R.right) and isSym(L.right, R.left)
return False
return isSym(root, root)
即分别从两个反方向看分支的子树是否是相等的
176 SQL操作
表格名字Employee的数据库中有Id ， Salary两个元素，找出第二高工资的工资
SELECT(
SELECT DISTINCT Salary FROM Employee ORDER BY Salary DESC LIMIT 1 OFFSET 1
)AS SecondHighestSalary
SELECT Person.FirstName,Person.LastName,Address.City,Address.State
FROM Person LEFT JOIN Address ON Person.PersonId=Address.PersonId
# distinct 去重
SELECT DISTINCT P1.Email
以Person表为主（LEFT JOIN）找出每个Person的地址信息，在Address表中；（若以Address为主则为RIGHT JOIN）
110.判断是不是平衡二叉树
就是树里深度差距最大为1
def isBalanced(self, root: TreeNode) -> bool:
return self.dfs(root) > -1
def dfs(self , root):
if root == None: return 0
left = self.dfs(root.left)
right = self.dfs(root.right)
if left==-1 or right ==-1 or abs(left-right)>1:
return -1
return 1+max(left,right)
最有意思的是一旦有出现一个 -1 出现，那么上层的迭代就都会返回-1，而不会走return 1+max(left,right)这个路径了。
第一个-1出现肯定是因为abs(left-right)>1 ， 上层会因为left 或者right有一个-1而不断return -1
每个节点只计算一次，因而是一个自底向上的O(N)时间复杂度的算法
需要队列时，python可从collections包中使用deque，有aque.popleft()
from collections import deque
node = aque.popleft()
69mySqrt
求一个数字的平方根，取到整数，即输入8，本应2.8，只输出2
def mySqrt(self, x: int) -> int:
low = 0
high = x//2+1
while low<high:
mid = (low+high+1)//2
square = mid**2
if square >x:
high = mid-1
print("hi",high, " ",low)
else:
print("low",low, " ",high)
low = mid
return low
关键的边界点是mid = (low+high+1)//2
== 一定取右中位数才不会死循环，否则会死循环==
因为2.8取2，low=2时，high会从5不断-1减到2然后return low
high = x//2+1减少一些计算量，注意+1 ， 否则输入0会报错
29 两数相除
不用系统除法完成除法运算，输入整数，不超过
[
−
2
3
1
,
2
3
1
−
1
]
[−2 ^31 , 2^31 − 1]
[−231,231−1]
整数除法能溢出的话，只能是2的-31 除以 -1
if (dividend==-1*(2<<31) and divisor==-1): return (2<<31 - 1)
while a>=b:
temp , i = b , 1
while a>=temp:
a -= temp
res += i
i = i<<1
temp = temp<<1
return res
40 组合数字
（有序数组中）一些循环中，后面数字和第一个数字比较，但是想跳过相同的数字，即从不同的数字开始比较时
for index in range(begin , len(candidates)):
if index>begin and candidates[index-1]==candidates[index]:
continue
其中两个细节，index>begin,这样就当循环是第一个数字时不进行后面的判断，防止index-1这个索引不存在
第二个就是后一个与前一个一样时，continue跳过
53.最大子序列和
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1 , len(nums)):
if nums[i-1]>0:
nums[i] += nums[i-1]
print(nums)
return max(nums)
把nums每个位置改成了，这个位置之前的子序列最大的和
既然i之前的位置都变成sum了，那么sum>0就可以加在i位置了
54 螺旋矩阵
输入一个矩阵，按照顺时针的顺序将元素放在一个res列表里
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
res = []
if not matrix: return res
i , j , di , dj = 0 , 0 , 0 , 1
m , n = len(matrix ) , len(matrix[0])
for _ in range( m*n ):
res.append(matrix[i][j])
matrix[i][j] = ''
if matrix[ (i+di)%m ][ (j+dj)%n ] == '':
di , dj = dj , -di
i += di
j += dj
return res
通过
if matrix[ (i+di)%m ][ (j+dj)%n ] == ‘’:
di , dj = dj , -di
两行，完美使得di , dj更改的顺序符合顺时针旋转，
di dj每次碰壁之后交换位置，且两次碰壁之后才更改正负号
151 字符串里的单词顺序（单词内部不变）
def reverseWords(self, s: str) -> str:
if s == "":
return ""
ls = s.split()
if ls == []:
return ""
result = ""
for i in range(len(ls)-1):
result += ls[len(ls)-1-i] + " "
result += ls[0]
return result
但是基本就是用的库，没有自己写处理过程，以下代码才是核心
翻转整个字符串，翻转空格之间的字符串，自己写比较容易，去除多余空格考虑因素较多（开头的空格，中间的空格，末尾的空格）
s是一个列表
一下代码很优雅了
def clean_space(s):
i = 0
j = 0
while j < n:
# 找到一个单词 在这里的作用是，如果连续多个空字符 那么计算让计数位置不断递增
# 直到遇到的字符不再是空字符为止
while j < n and s[j] == " ":
j += 1
# 单词朝前移
while j < n and s[j] != " ":
s[i] = s[j]
i += 1
j += 1
# 移动下一个单词
while j < n and s[j] == " ":
j += 1
if j < n:
s[i] = " "
i += 1
return "".join(s[:i])
260 只出现一次的数字
其余数字出现两次，有两个数字出现一次，要求空间O1
先求出掩码mask
for i in nums:
temp ^= i
return temp
然后得到这两个一次数字的异或值，找到该值最后一位1，就可以区分出一个数字这位是0，一个数字这位是1
如何找到：
index = x &(-x)
常见位运算
- 去掉最后一位的1
n&n(-1)
- 计算汉明权重（Hamming Weight）
int hammingWeight(uint32_t n) {
int res = 0;
while (n != 0) {
n = n & (n - 1);
res++;
}
return res;
}
⼀个数如果是 2 的指数，那么它的⼆进制表⽰⼀定只含有⼀个 1
if n<=0: reutrn false
return （n&(n-1) ）==0
装B的位运算
- 判断两个数是否异号
int x = -1, y = 2;
bool f = ((x ^ y) < 0); // true 可以避免if else还有溢出的判断 - 交换两个数
int a = 1, b = 2;
a ^= b;
b ^= a;
a ^= b; // 现在 a = 2, b = 1
- 加1
int n = 1;
n = -~n; // 现在 n = 2 - 减1
int n = 2;
n = ~-n; // 现在 n = 1
堆
最大堆和最小堆，两者的差别在于节点的排序方式。
在最大堆中，父节点的值比每一个子节点的值都要大。但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点
性质
普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。
二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。
堆在搜索过程很不利。
i是数组中的索引
parent(i) = floor((i - 1)/2)
left(i) = 2i + 1
right(i) = 2i + 2
注意 right(i) 就是简单的 left(i) + 1。左右节点总是处于相邻的位置。
在最大堆中，父节点的值总是要大于（或者等于）其子节点的值。这意味下面的公式对数组中任意一个索引 i都成立：
array[parent(i)] >= array[i]
但这就是交易：我们节约了空间，但是要进行更多计算。幸好这些计算很快并且只需要O(1)的时间。
一个高度为 h 的堆有 h+1 层。
下面这个对的高度是3，所以它有4层：
如果一个堆有 n 个节点，那么它的高度是 h = floor(log2(n))。这是因为我们总是要将这一层完全填满以后才会填充新的一层。上面的例子有 15 个节点，所以它的高度是 floor(log2(15)) = floor(3.91) = 3。
如果最下面的一层已经填满，那么那一层包含
2
h
2^h
2h 个节点。同样是上面这个例子，最下面的一层有8个节点，实际上就是
2
3
=
8
2^3 = 8
23=8。前面的三层一共包含7的节点，即：
2
3
−
1
=
8
−
1
=
7
2^3 - 1 = 8 - 1 = 7
23−1=8−1=7。
C++一些基础的语法
字符排序
sort(s)即将字符串s改变了顺序
基于区域的for循环
for(a : b) 整体更新区域内所有值
int values[] {1,3,5,7,9};
int total {};
for(auto x:values)
total += x;
totla即values中的累加和25
集合set
构造set集合的目的是为了快速的检索，不可直接去修改键值。且每个值不会重复！
unordered_set< int > set;
插入set.insert(i);
begin() 返回指向第一个元素的迭代器
count() 返回某个值元素的个数（只能是0或者1,即存在与否）
find() 返回一个指向被查找到元素的迭代器
erase(n1)删除n1这个值
在#include的头文件下
std::set_intersection() :这个函数是求两个集合的交集。
std::set_union() :求两个集合的并集
std::set_difference（）：差集
的
*集合会自动排序！从小到大。即*set.begin()为最小值，set.rbegin()为最大值
引用与指针的区别
1引用是变量的别名，因而不能为空，要初始化，且“始终不渝”不能再指向别的变量。2 ，++操作时本身数值增1。3，引用大小看变量大小。安全 4引用只能有一级，&&不合法
（编译器不会为引用对象新开辟内存空间， 它和它引用的对象共用同一块内存空间 。）
1 指针则可以空，可以指向别的变量。2 ，++操作时指向了变量的下一个变量3指针大小基本就是4字节 4指针可以有多级
（指针只不过是一个存着地址的普通变量。）
有const时的区别
常量引用 指向常量的引用,也不能赋值 int i=10; const int& ref = i;
常量指针 指向常量的指针,定义"const int* pointer=&a"告诉编译器，pointer是常量，不能将pointer作为左值进行操作。即不能point=10
引用常量VS指针常量
引用天生就指定完不能变了，本身就是引用常量
指针常量 在指针定义语句的指针名前加const，表示指针本身是常量.在定义指针常量时必须初始化.
指针常量定义"int const pointer=&b"告诉编译器，pointer是常量，不能作为左值进行操作，但是允许修改间接访问值，即*pointer可以修改。
all in all 常量const,修饰后面一个单词，后面跟int说明变量是常量 ， 后面跟p ，说明指针是称量
引用到底存在的意义是什么（起别名的用处）：
当你如下调用时：
int b;
f(b);
编译器会把zdb的值赋给a,在函数体内操作a；
而如果函数定义为：int f(int& a){…}
当你调用时，没有这个赋值的过程，因为此时a是实参的别名，相当回于直接操作了实参b；
好处：
1 节约空间，少了一个实参赋值给形参的过程
2 可以直接操作实参，而不是形参
且规避了使用指针的风险（安全）
容器
std::vector <T>
定义时 vector <int> value;
也可以vecotr <int> values(20，1);使用时更快(初始化为1）
添加数据value.push_back(i); 删除末尾value.pop_back
value.size()输出大小 value.capacity()输出容量
value[3] 等价于 value.at[5]，后者若越界，则会触发out_of_range异常
std::array <N,T>
int cur = sub.back();获取列表最后一个元素的值，但是列表不删除
sub.pop_back(); 列表最后一个元素被删除
类似python中str.split(" ")的C++语法
字符串与整型转换
#include <sstream>
string text = "888";
int aint=0
stringstream ss;
ss<<text;
ss>>aint;
//此时就改好了，记得之后再使用ss中转时要初始化！！有两步：
ss.str("");
ss.clear();
读入未知个数的数字
输入任意个数字，求和 20 19 21
stringstream ss;
cin >> n;
getline(cin, s); // 读取到回车换行
ss.clear();
ss.str(s);
sum=0;
while (1)
{
ss >> a;
if ( ss.fail() ) break;
sum+=a;
}
分割字符串
string s = "aaa,bbb,ccc";
istringstream ss(s);
string temp;
while (getline(ss, temp, ‘,‘))
cout << temp << endl;
或者
string str="i am a boy";
stringstreamss(str);
string s;
while(ss>>s) {
cout<<s<<endl;
列表生成式
循环嵌套语法格式
[exp for iter_var_A in iterable_A for iter_var_B in iterable_B]
工作过程：
每迭代iterable_A中的一个元素，就把ierable_B中的所有元素都迭代一遍。
相当于这样的过程：
L = []
for iter_var_A in iterable_A:
for iter_var_B in iterable_B:
L.append(exp)
Python装饰器
由于函数也是一个对象，而且函数对象可以被赋值给变量，所以，通过变量也能调用该函数。
函数对象有一个__name__属性，可以拿到函数的名字：
>>> def now():
... print('2015-3-25')
>>> f = now
>>> f()
2015-3-25
>>> now.__name__
'now'
>>> f.__name__
'now'
现在，假设我们要增强now()函数的功能，比如，在函数调用前后自动打印日志，但又不希望修改now()函数的定义，这种在代码运行期间动态增加功能的方式，称之为“装饰器”（Decorator）。
权威｜前沿｜技术｜干货｜国内首个API全生命周期开发者社区
更多推荐
1
0- 0
已为社区贡献1条内容
所有评论(0)