19- 顺时针打印矩阵
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
这道题难的不是码代码，难的是debug。边界问题很烦人。
class Solution:
# matrix类型为二维列表，需要返回列表
def printMatrix(self, matrix):
if not matrix or not matrix[0]:
return []
m, n = len(matrix), len(matrix[0])
rtn = []
for time in range((min(m, n)-1)//2+1):
rtn.extend(matrix[time][time:n-time])
rtn.extend([matrix[x][n-time-1] for x in range(time+1, m-time)])
if m - time - 1 != time:
rtn.extend([matrix[m-time-1][y] for y in range(n-time-2, time-1, -1)])
if n - time - 1 != time:
rtn.extend([matrix[x][time] for x in range(m-time-2, time, -1)])
return rtn
28-数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
这道题最省事的解法，就是用一个哈希表存储所有数字的出现次数。在Python里，直接用 collections里的Counter类统计即可。如果想在空间复杂度为O(1)下解决此题，可以先找出数组中最有可能超过数组长度一半的数。这个“最有可能”意味着，它不一定多于数组长度一半，也不一定是数组中最频繁的元素。具体做法，就是顺序遍历数组元素。使用一个rtn来记录一个数，用count来计数。每次看到一个等于rtn的数，count就加一。否则，count减一。如果count到零了，就将rtn替换成当前见到的数。如果有一个数出现次数大于数组长度一半，rtn最后的值必然是这个数。这个count有点像这个数的出现次数减去其他数的出现次数（但也不尽然）。可以肯定的是，如果数组中存在一个个数大于数组长度一半的数，最后rtn一定是这个数。最后，我们还需要验证数rtn是否真的出现次数比数组长度一半多。这个验证只需要通过重新遍历一次数组，统计rtn出现次数就行了。
class Solution:
def MoreThanHalfNum_Solution(self, numbers):
rtn = None
count = 1
for each in numbers:
if each != rtn:
if count == 1:
rtn = each
else:
count -= 1
else:
count += 1
count = 0
for each in numbers:
if each == rtn:
count += 1
if count > len(numbers) // 2:
return rtn
return 0
class Solution {
public:
int MoreThanHalfNum_Solution(vector<int> numbers) {
if (!numbers.size()) return 0;
int rtn = numbers[0], count = 0;
for (int each: numbers) {
if (!count) {
rtn = each, ++count;
} else {
if (each == rtn) ++count;
else --count;
}
}
count = 0;
for (int each: numbers) {
if (each == rtn) ++count;
}
if (count > numbers.size()/2) return rtn;
return 0;
}
};
31-整数中1出现的次数
求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数） 。比如 1~13中包含1的数字有1、10、11、12、13，因此共出现6次 。
Python大法好……
class Solution:
def NumberOf1Between1AndN_Solution(self, n):
return ''.join(map(str, range(n+1))).count('1')
这个解法时间复杂度是O(n)，在牛客网评论区有人给出了时间复杂度O(lgn)的解法。但我觉得那个解法过于冗杂，思路是通过数学归纳出每一位应该有多少个1。有兴趣可以去评论区看一下。
class Solution {
public:
int NumberOf1Between1AndN_Solution(int n) {
int sum = 0;
string tmp;
for (int i = 1; i <= n; ++i) {
tmp = to_string(i);
sum += count(tmp.begin(), tmp.end(), '1');
}
return sum;
}
};
32-把数组排成最小的数
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
如果数组的两个数x和y，把它们拼成xy和yx，有xy<yx，那么在数组能拼成的最小数字中，x肯定出现在y前面。否则，将这个“最小数字”中的x和y互换一下位置，可以得到一个更小的数字。因此，只要将数组按这个规则排序就可以了，排序结果就是在最小数字中元素的出现次序。
from functools import cmp_to_key
class Solution:
def PrintMinNumber(self, numbers):
if not numbers:
return ""
numbers = map(str, numbers)
numbers.sort(key=cmp_to_key(lambda x, y: -1 if x+y<y+x else 1))
return ''.join(numbers)
class Solution {
public:
string PrintMinNumber(vector<int> numbers) {
vector<string> num_str;
for (int each: numbers) num_str.push_back(to_string(each));
sort(num_str.begin(), num_str.end(), [] (string &x, string &y) { return x+y < y+x; });
string rtn;
for (string &str: num_str) rtn += str;
return rtn;
}
};
41-和为S的连续正数序列
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序。序列的长度要大于1。
由于是连续正数序列，所以可以通过设置一个滑动窗口来求序列和。如果窗口的范围是[low, high+1)。如果窗口的和小于tsum，就让high加一。如果小于tsum，就让low+1。直到窗口内任意元素的值都大于tsum，这时low>=high。
class Solution:
def FindContinuousSequence(self, tsum):
low, high = 1, 2
acc = 3
rtn = []
while low < high:
if acc < tsum:
high += 1
acc += high
elif acc > tsum:
acc -= low
low += 1
else:
rtn.append(list(range(low, high+1)))
acc -= low
low += 1
return rtn
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
int low = 1, high = 2, acc = 3;
vector<vector<int>> rtn;
while (low < high) {
if (acc < sum) acc += (high++ + 1);
else if (acc > sum) acc -= low++;
if (acc == sum) {
vector<int> tmp(high-low+1);
iota(tmp.begin(), tmp.end(), low);
rtn.push_back(tmp);
acc -= low++;
}
}
return rtn;
}
};
42-和为S的两个数字
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
相当基础的双指针题目了吧。题目里说，“输出两个数的乘积最小的”。我记得小学数学课时学过，两个数如果和等于S，那么在它们的差最大时，积是最小的。因此，指针碰上的第一对满足和为S的数就是答案了。
class Solution:
def FindNumbersWithSum(self, array, tsum):
low, high = 0, len(array)-1
while low < high:
if array[low] + array[high] > tsum:
high -= 1
elif array[low] + array[high] < tsum:
low += 1
else:
return [array[low], array[high]]
return []
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array, int sum) {
int low = 0, high = array.size() - 1, acc;
while (low < high) {
acc = array[low] + array[high];
if (acc < sum) ++low;
else if (acc > sum) --high;
else return {array[low], array[high]};
}
return {};
}
};
43-左旋转字符串
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。
Python做的话很简单。评论区说了一种方法：将s[left:]和s[:left]先翻转一次，再将s翻转一次。这种方法可能对C/C++用户比较友好。
class Solution:
def LeftRotateString(self, s, n):
if not s:
return s
left = n % len(s)
return s[left:] + s[:left]
class Solution {
public:
string LeftRotateString(string str, int n) {
if (!str.length()) return "";
n %= str.length();
reverse(str.begin(), str.begin()+n);
reverse(str.begin()+n, str.end());
reverse(str.begin(), str.end());
return str;
}
};
47-求1+2+3+…+n
求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
这题没有什么实际意义，只是考考小聪明。使用与的短路规则，可以代替if判断。然后用递归可代替循环。
class Solution:
def __init__(self):
self.ans = 0
def Sum_Solution(self, n):
self.ans += n
n and (self.Sum_Solution(n-1))
return self.ans
class Solution {
int ans = 0;
public:
int Sum_Solution(int n) {
ans += n;
n && Sum_Solution(n-1);
return ans;
}
};
48-不用加减乘除的加法
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
两个数的异或值就是它们相加（没有进位）的结果。两个数的与值并左移一位就是它们相加的进位。由于Python没有位数限制，如果相加结果是负数，需要截取前32位。最后还需将其取补码，变成一个负数。
class Solution:
def Add(self, num1, num2):
while num2:
tmp = num1^num2
num2 = (num1&num2)<<1
num1 = tmp & 0xFFFFFFFF
return (num1 if num1 >> 31 == 0 else num1 - 0x100000000)
class Solution {
public:
int Add(int num1, int num2) {
int tmp;
while (num2) {
tmp = num1 ^ num2;
num2 = (num1 & num2) << 1;
num1 = tmp;
}
return num1;
}
};
50-数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
这道题用集合来做是最简单的，不过也有空间复杂度为O(1)，时间复杂度也为O(n)的做法。由于数组中的数字范围都是在0到n-1以内，所以每遇到数组中的一个数字x，可以把数组第x个元素加n，表示数字x存在于数组内。如果我们在标记一个数字时，发现它对应的位置numbers[x]已经是一个不小于n的数字，说明x已经在数组中出现过，那么就返回x。
class Solution:
# 这里要特别注意~找到任意重复的一个值并赋值到duplication[0]
# 函数返回True/False
def duplicate(self, numbers, duplication):
n = len(numbers)
for i in range(len(numbers)):
if numbers[numbers[i]%n] >= n:
duplication[0] = numbers[i] % n
return True
numbers[numbers[i]%n] += n
return False
class Solution {
public:
bool duplicate(int numbers[], int length, int *duplication) {
for (int i = 0; i < length; ++i) {
if (numbers[numbers[i] % length] < length) numbers[numbers[i] % length] += length;
else {
*duplication = numbers[i] % length;
return true;
}
}
return false;
}
};
51-构建乘积数组
给定一个数组A[0,1,…,n-1],请构建一个数组B[0,1,…,n-1],其中B中的元素B[i]=A[0]*A[1]*…*A[i-1]*A[i+1]*…*A[n-1]。不能使用除法。
可以发现，rtn[i] = prod(A[:i]) * prod(A[i+1:])。因此，可以先用两个数组，算出所有正向的连乘，和反向的连乘，再将它们乘起来。因为连乘是序列化的，所以其实可以只用一个数组，另一个数组用一个临时变量在求连乘乘积时动态地更新就可以了。
class Solution:
def multiply(self, A):
C, D = [1 for _ in range(len(A))], [1 for _ in range(len(A))]
for i in range(1, len(A)):
C[i] = A[i-1] * C[i-1]
for i in range(len(A)-2, -1, -1):
D[i] = A[i+1] * D[i+1]
return [C[i]*D[i] for i in range(len(A))]
class Solution {
public:
vector<int> multiply(const vector<int> &A) {
if (!A.size()) return {};
vector<int> multi(A.size(), 1);
for (int i = 1; i < A.size(); ++i) {
multi[i] = A[i-1] * multi[i-1];
}
int prod = 1;
for (int i = A.size()-1; i >= 0; --i) {
prod *= A[i];
multi[i] *= prod;
}
return multi;
}
};
54-字符流中第一个不重复的字符
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。如果当前字符流没有存在出现一次的字符，返回#字符。
使用一个字符字典来存储出现过的字符。在字符第一次出现时，存储它们的下标。在第二次遇到这个字符时，将存储值改为-1，表示已经出现过。
class Solution:
def __init__(self):
self.count = {}
self.idx = 1
def FirstAppearingOnce(self):
min_v, min_i = self.idx, '#'
for key, value in self.count.items():
if min_v > value > 0 and value < min_v:
min_v, min_i = value, key
return min_i
def Insert(self, char):
if char not in self.count:
self.count[char] = self.idx
elif self.count[char] > 0:
self.count[char] = -1
self.idx += 1
class Solution {
public:
// Insert one char from stringstream
void Insert(char ch) {
if (m[ch]++ == 0) q.push(ch);
}
// return the first appearence once char in current stringstream
char FirstAppearingOnce() {
while (!q.empty()) {
if (m[q.front()] == 1) return q.front();
q.pop();
}
return '#';
}
private:
queue<char> q;
unordered_map<char, int> m;
};