172. 階乘后的零
思路
把2御雕，5的倍數(shù)拆成2，5摹察，數(shù)5的個數(shù)（2一定比5多）冤留，這樣5一定和2配對碧囊，所以5的個數(shù)就是末尾0的個數(shù)
AC代碼
class Solution {
public:
int trailingZeroes(int n) {
int ans = 0;
while (n) {
n /= 5;
ans += n;
}
return ans;
}
};
class Solution {
public:
int trailingZeroes(int n) {
return n == 0 ? 0 : n/5 + trailingZeroes(n / 5);
}
};
189. 旋轉(zhuǎn)數(shù)組
思路（遞歸）
-
k %= nums.size();取余數(shù)，不要循環(huán)好多圈 - 把前k個數(shù)和后k個數(shù)交換
- 把從下標k到結(jié)束的數(shù)作為源數(shù)據(jù)調(diào)用本函數(shù)
AC代碼
class Solution {
public:
void rotate(vector<int>& nums, int k) {
go(0, k, nums);
/*
時間復雜度O(n^2/k)
空間復雜度O(1)
*/
}
void go(int beg, int k, vector<int>& nums) {
k %= nums.size() - beg;
if (k == 0) return;
for (int i = beg; i < beg + k; i++) {
swap(nums[i], nums[nums.size() - k + i - beg]);
}
go(beg + k, k, nums);
}
void swap(int& a, int& b) {
int t = a;
a = b;
b = t;
}
};
思路
- 把整個數(shù)組反轉(zhuǎn)一次
- 前0到k-1反轉(zhuǎn)一次
- 后k到結(jié)束反轉(zhuǎn)一次
AC代碼
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums, 0, n - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, n - 1);
/*
時間復雜度O(n)
空間復雜度O(1)
*/
/*------------------------------*/
}
void reverse(vector<int>& nums, int begin, int end) {
while (begin < end) {
int n = nums[begin];
nums[begin++] = nums[end];
nums[end--] = n;
}
}
};
190. 顛倒二進制位
思路
- 循環(huán)模2搀菩，2進制轉(zhuǎn)2進制
- 注意原來的數(shù)的前導0也要添加到后面呕臂，所以循環(huán)條件是循環(huán)次數(shù)32次（因為給的是32位無符號數(shù)）
AC代碼
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ans = 0;
int i = 32;
while (i--)
{
ans *= 2;
ans += n % 2;
n /= 2;
}
return ans;
}
};
191. 位1的個數(shù)
AC代碼
class Solution {
public:
int hammingWeight(uint32_t n) {
int c = 0;
while (n) {
if (n % 2 == 1)c++;
n/=2;
}
return c;
}
};
202. 快樂數(shù)
思路
- 計算，看有沒有重復肪跋，有重復就說明不是快樂數(shù)
- 計算，出現(xiàn)4就不是快樂數(shù)（不是快樂數(shù)的數(shù)稱為不快樂數(shù)（unhappy number）土砂，所有不快樂數(shù)的數(shù)位平方和計算州既，最後都會進入 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 的循環(huán)中。）
AC代碼
class Solution {
public:
bool isHappy(int n) {
map<int, int> m;
while (n != 1) {
m[n]++;
if (m[n] > 1) break;
n = get(n);
}
return n == 1;
}
int get(int n) {
int ans = 0;
while (n) {
ans += (n % 10) * (n % 10);
n /= 10;
}
return ans;
}
};
AC代碼
class Solution {
public:
bool isHappy(int n) {
while (n != 1) {
if (n == 4) {
return false;
}
n = get(n);
}
return true;
}
int get(int n) {
int ans = 0;
while (n) {
ans += (n % 10) * (n % 10);
n /= 10;
}
return ans;
}
};
203. 移除鏈表元素
思路
如果頭結(jié)點是要刪的元素萝映，進行的操作不太一樣吴叶，要單獨考慮，然后進行后面的刪除序臂。評論區(qū)好多用c++的都不管內(nèi)存泄漏蚌卤。不是好習慣实束，堅決杜絕！
AC代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode* move = head, *last = head;
while (head != NULL && head->val == val) {
head = head->next;
delete last;
last = head;
}
move = head;
while (move != NULL) {
if (move->val == val){
last->next = move->next;
delete move;
} else {
last = move;
}
move = last->next;
}
return head;
}
};
204. 計數(shù)質(zhì)數(shù)
思路
用篩法兩個for循環(huán)把不是素數(shù)的都篩出來
但是要提升性能:
- 忽略偶數(shù)
- 如果當前數(shù)已經(jīng)算過了逊彭，就不要算
- 用bool的vector咸灿，bool一字節(jié)，比int短侮叮，也可以加速
AC代碼
class Solution
{
public:
int countPrimes(int n)
{
if (n <= 2)
return 0;
int count = 1;
vector<bool> notPrime(n,0);
for (int i = 3; i < sqrt(n); i += 2)
{
if (notPrime[i] == 1)continue;
for (int j = 3; j * i <= n; j += 2)
{
notPrime[i * j] = 1;
}
}
notPrime[0] = 1;
notPrime[1] = 1;
notPrime[3] = 0;
notPrime[4] = 1;
notPrime[5] = 0;
notPrime[6] = 1;
notPrime[7] = 0;
notPrime[8] = 1;
notPrime[9] = 1;
for (int i = 1; i < n; i += 2)
{
if (notPrime[i] == 0)
count++;
}
return count;
}
};
最快大佬的代碼
思路
看不懂
class Solution {
public:
int countPrimes(int n) {
if (n < 3)
return 0;
size_t len = (n-2) >> 1;
//cout << len << endl;
vector<char> v(len, 0);
int count = 1;
uint i = 0;
auto m = min(len, 0x7FFEuL);
while (i < m) {
if (!v[i]) {
++count;
uint p = (i << 1) + 3;
//if (p < 0x10000) {
uint pp = p * p;
uint j = (pp - 3) >> 1;
while(j < len) {
v[j] = true;
j += p;
}
}
++i;
}
while (i < len) {
if (!v[i])
++count;
++i;
}
return count;
}
};
205. 同構(gòu)字符串
思路
不太會避矢，抄的評論區(qū)代碼，但是要注意囊榜，一個字母a如果替換成b审胸，就不能替換為c
AC代碼
static const int boost = [](){
ios::sync_with_stdio(false);
cin.tie(nullptr);
return 0;
}();
class Solution {
public:
bool isIsomorphic(string s, string t) {
int alphabetS[256], alphabetT[256], num = 0;
memset(alphabetS, 0, sizeof(alphabetS));
memset(alphabetT, 0, sizeof(alphabetT));
int len = s.length();
for (int pos = 0; pos < len; pos++)
{
if(alphabetS[s[pos]] != alphabetT[t[pos]])
return false;
else if (alphabetS[s[pos]] == 0)
alphabetS[s[pos]] = alphabetT[t[pos]] = ++num;
}
return true;
}
};
206. 反轉(zhuǎn)鏈表
思路
- 把結(jié)點全都存到數(shù)組里
- 遞歸，調(diào)用自己卸勺，再把頭結(jié)點變成尾巴結(jié)點
AC代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
vector<ListNode*> v;
ListNode *temp = head;
while (temp != NULL) {
v.push_back(temp);
temp = temp->next;
}
int len = v.size();
for (int i = 0; i < len / 2; i++) {
int swap = v[i]->val;
v[i]->val = v[len - 1 - i]->val;
v[len - 1 - i]->val = swap;
}
return head;
}
};
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL) return head;
ListNode *temp = reverseList(head->next);
head->next->next = head;
head->next = NULL;
return temp;
}
};
217. 存在重復元素
思路
- 調(diào)用api砂沛，先sort，再調(diào)用unique曙求，判斷返回值是不是end()迭代器碍庵，是則沒有重復
AC代碼
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
return unique(nums.begin(), nums.end()) != nums.end();
}
};
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
sort(nums.begin(), nums.end());
int len = nums.size();
for (int i = 1; i < len; i++) {
if (nums[i - 1] == nums[i]) return true;
}
return false;
}
};
225. 用隊列實現(xiàn)棧
思路
queue是先進先出，stack是后進先出圆到。
- 用deque實現(xiàn)
- 每次push的元素后怎抛，讓隊列循環(huán)pop出來再push回去，使得剛剛push的元素變成第一個
AC代碼
class MyStack {
public:
queue<int> data;
MyStack() {
}
void push(int x) {
data.push(x);
int len = data.size() - 1;
while (len--) {
data.push(data.front());
data.pop();
}
}
int pop() {
int x = data.front();
data.pop();
return x;
}
int top() {
return data.front();
}
bool empty() {
return data.empty();
}
};
class MyStack {
public:
deque<int> data;
MyStack() {
}
void push(int x) {
data.push_front(x);
}
int pop() {
int x = data.front();
data.pop_front();
return x;
}
int top() {
return data.front();
}
bool empty() {
return data.empty();
}
};
226. 翻轉(zhuǎn)二叉樹
思路
- 遞歸
- 深度優(yōu)先
- 廣度優(yōu)先
AC代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
go(root);
return root;
}
void go(TreeNode* root) {
if (root == NULL) return;
TreeNode* temp = root->left;
root->left = root->right;
root->right = temp;//廣度優(yōu)先
go(root->left);
go(root->right);
}
};
class Solution {
public:
TreeNode* invertTree(TreeNode* root) {
if (root == NULL) return root;
TreeNode*left = invertTree(root->right);//深度優(yōu)先
TreeNode*right = invertTree(root->left);
root->right = right;
root->left = left;
return root;
}
};
231. 2的冪
思路
- 取2對數(shù)看是不是整數(shù)
- 利用二進制位運算
- 假設(shè)一個無符號數(shù)是全1的芽淡，那么它是2^k-1
- 假設(shè)2^k = n马绝，那么只要一個數(shù)滿足(n)&(n-1) == 0，按位相與
AC代碼
class Solution {
public:
bool isPowerOfTwo(int n) {
return (int)log2(n) == log2(n);
}
};
class Solution {
public:
bool isPowerOfTwo(int n) {
if (n > 0 && ((n)&(n-1)) == 0) return true;
return false;
}
};
232. 用棧實現(xiàn)隊列
思路
- 創(chuàng)建兩個棧s挣菲、m富稻，每次push存到s里面，然后再逐個彈出s中的元素壓到m中（這個過程中s要先拷貝一份）
- 每次pop的時候白胀，從m中pop椭赋，然后再逐個彈出m中的元素壓到s中（這個過程中s要先拷貝一份）
- m用來對頂部元素操作，s來保持隊形
AC代碼
class MyQueue {
public:
stack<int> s;
stack<int> m;
MyQueue() {
}
void push(int x) {
s.push(x);
update(s,m);
}
void update(stack<int> a, stack<int>& b) {
int len = a.size();
while (!b.empty()){
b.pop();
}
while (len--) {
b.push(a.top());
a.pop();
}
}
int pop() {
int x = m.top();
m.pop();
update(m,s);
return x;
}
int peek() {
return m.top();
}
bool empty() {
return m.empty();
}
};
234. 回文鏈表
思路（暫時沒有達到空間O(1)）
vector存結(jié)點地址
AC代碼
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
/*ListNode* temp = head;
vector<ListNode*> v;
while (temp != NULL) {
v.push_back(temp);
temp = temp->next;
}
int len = v.size();
for (int i = 0; i < len / 2; i++) {
if (v[i]->val != v[len - 1 - i]->val) return false;
}
return true;*/
}
};
292. Nim游戲
思路
巴什博奕或杠，n%(m+1)!=0時哪怔，先手總是會贏的
m為每次抽排的最大張數(shù)
AC代碼
class Solution {
public:
bool canWinNim(int n) {
return n%4 != 0;
}
};
242. 有效的字母異位詞
思路
就是看每個字母的使用次數(shù)一不一樣
一個數(shù)組，記錄字母的使用次數(shù)向抢，最后次數(shù)一樣就行认境。
AC代碼
class Solution {
public:
bool isAnagram(string s, string t) {
int a[26] = {0}, b[26] = {0};
for (int i = 0; i < s.length(); i++)
a[s[i] - 'a']++;
for (int i = 0; i < t.length(); i++)
b[t[i] - 'a']++;
for (int i = 0; i < 26; i++) {
if (a[i] != b[i]) return false;
}
return true;
}
};
258. 各位相加
AC代碼
class Solution {
public:
int addDigits(int num) {
while (num/10 != 0) {
int ans = 0;
while (num) {
ans += num%10;
num /= 10;
}
num = ans;
}
return num;
return num == 0 ? 0 : num - 9 * ((num - 1) / 9) ;
}
};
263. 丑數(shù)
思路
如果n % m == 0,說明n中至少有一個m的因數(shù)，循環(huán)n%m == 0時重復n /= m挟鸠，可以去除所有的m的因數(shù)叉信，根據(jù)這個思路，如果是丑數(shù)艘希，把所有2硼身，3硅急，5的因數(shù)去除以后，就是1了
AC代碼
class Solution {
public:
bool isUgly(int num) {
if (num <= 0) return false;
while (num%2 == 0) num /= 2;
while (num%3 == 0) num /= 3;
while (num%5 == 0) num /= 5;
return num == 1;
}
};
268. 缺失數(shù)字
思路
- 0-n 11 個數(shù)中缺了一個佳遂，可以先算出等差數(shù)列的sum(0,n)营袜，然后變量數(shù)組減去所有元素，最后的差就是缺少的元素
- 看不懂的位運算讶迁，異或抵消
AC代碼
class Solution {
public:
int missingNumber(vector<int>& nums) {
int ans = nums.size();
ans = ans*(ans+1)/2;
for (int x : nums) {
ans -= x;
}
return ans;
}
};
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = nums.size();
int len = sum;
for (int i = 0; i < len; i++) {
sum ^= nums[i];
sum ^= i;
}
return sum;
}
};
278. 第一個錯誤的版本
思路
暴力搜索不可取连茧，二分查找保平安
AC代碼
// Forward declaration of isBadVersion API.
bool isBadVersion(int version);
class Solution {
public:
int firstBadVersion(int n) {
long long mid , a = 1, b = n;
if (isBadVersion(1)) return 1;
while (a <= b) {
mid=a+(b-a)/2;
bool bad, left, right;
bad = isBadVersion(mid);
left = isBadVersion(mid - 1);
right = isBadVersion (mid + 1);
if (bad && !left) return mid;
else if (bad && right) b = mid - 1;
else a = mid + 1;
}
if (isBadVersion(n)) return n;
return -1;
}
};
283. 移動零
思路
- 冒泡排序的思想，不過條件換成左邊的數(shù)是0巍糯，則交換一次
- 雙指針啸驯，從左往右遍歷
AC代碼
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int len = nums.size();
for (int i = len - 1; i >= 0; i--) {
for (int j = len - 2; j >= 0; j--) {
if (nums[j] == 0) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
};
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int len = nums.size();
int pos = 0;
for (int i = 0; i < len; i++) {
if (nums[i] != 0) {
nums[pos++] = nums[i];
}
}
for (int i = pos; i < len; i++) {
nums[i] = 0;
}
}
};
290. 單詞模式
思路
- 建立兩個map，驗證映射是一一映射
- 如果當前值在a->b且b->a的映射都是空祟峦，那么添加這兩個映射
- 如果有一個是存在的罚斗，看兩個映射的結(jié)果與當前值是否相等，不相等返回false
- 循環(huán)安全結(jié)束宅楞，返回true
AC代碼
class Solution {
public:
bool wordPattern(string pattern, string str) {
unordered_map<char, string> m;
unordered_map<string, char> n;
vector<string> strs;
stringstream ss(str);
string buf;
while (ss >> buf) {
strs.push_back(buf);
}
if (strs.size() != pattern.length()) return false;
int len = pattern.length();
for (int i = 0; i < len; i++) {
if (m[pattern[i]] == "" && n[strs[i]] == 0) {
m[pattern[i]] = strs[i];
n[strs[i]] = pattern[i];
} else {
if (m[pattern[i]] != strs[i] || n[strs[i]] != pattern[i]) {
return false;
}
}
}
return true;
}
};
303. 區(qū)域和檢索 - 數(shù)組不可變
思路
題目保證數(shù)組不會改變针姿，且要多次調(diào)用sumRange()，采用以下方法提高效率
- 類比數(shù)列的知識厌衙，創(chuàng)建一個vector距淫，存放前i項和
- 在構(gòu)造對象時，變量一遍數(shù)組O(N)婶希，得到所有的前n項和
- 每次調(diào)用函數(shù)時榕暇，直接返回兩個
sj和si-1的差即可 - 為了減少if-else的執(zhí)行，數(shù)據(jù)的第一個地方存一個0喻杈，這樣返回
sj+1-si即可
AC代碼
class NumArray {
public:
vector<int> s;
NumArray(vector<int> nums) {
int sum = 0;
int len = nums.size();
s.push_back(0);
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
s.push_back(sum);
}
}
int sumRange(int i, int j) {
return s[j + 1] - s[i];
}
};
326. 3的冪
思路
- 看3^log3(n)取整 是否等于n本身
- 用到了數(shù)論的知識彤枢，3的冪次的質(zhì)因子只有3，而所給出的n如果也是3的冪次筒饰，故而題目中所給整數(shù)范圍內(nèi)最大的3的冪次的因子只能是3的冪次缴啡，1162261467是3的19次冪，是整數(shù)范圍內(nèi)最大的3的冪次
AC代碼
class Solution {
public:
bool isPowerOfThree(int n) {
if (n <= 0) return false;
return (int)pow(3, round((log(n) / log(3)))) == n;
}
};
class Solution {
public:
bool isPowerOfThree(int n) {
return n > 0 && 1162261467%n == 0;
}
};
342. 4的冪
思路
- 看以log2(num)是否為偶數(shù)
- 查看二進制的所有奇數(shù)位瓷们，全是0即可（參見二進制轉(zhuǎn)10進制公式业栅，奇數(shù)為上的2的指數(shù)都是奇數(shù)）
AC代碼
class Solution {
public:
bool isPowerOfFour(long long num) {
double n = log2(num);
return (int)n == n ? (int)n % 2 == 0 : false;
}
};
class Solution {
public:
bool isPowerOfFour(long long num) {
if (num < 0 || num & (num-1)){//check(is or not) a power of 2.
return false;
}
return num & 0x55555555;//check 1 on odd bits
}
};
344. 反轉(zhuǎn)字符串
AC代碼
class Solution {
public:
void reverseString(vector<char>& s) {
reverse(s.begin(), s.end());
}
};
345. 反轉(zhuǎn)字符串中的元音字母
AC代碼
class Solution {
public://雙指針法
string reverseVowels(string s) {
int left = 0;
int right = s.length() - 1;
char m[128] = {0};
m['a'] = 1;
m['e'] = 1;
m['i'] = 1;
m['o'] = 1;
m['u'] = 1;
m['A'] = 1;
m['E'] = 1;
m['O'] = 1;
m['I'] = 1;
m['U'] = 1;
while (left < right) {
while (left < right && !m[s[left]]) left++;
while (left < right && !m[s[right]]) right--;
//加上left<right的判斷 條件，防止把換過來的字母換回去
char m = s[left];
s[left] = s[right];
s[right] = m;
left++;
right--;
}
return s;
}
};
349. 兩個數(shù)組的交集
思路
- 先把兩個數(shù)組排序去重谬晕，然后map記錄出現(xiàn)次數(shù)式镐，然后把出現(xiàn)次數(shù)大于1的挑出來作為返回值返回
AC代碼
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> m;
vector<int> v;
sort(nums1.begin(), nums1.end());
nums1.erase(unique(nums1.begin(), nums1.end()), nums1.end());
sort(nums2.begin(), nums2.end());
nums2.erase(unique(nums2.begin(), nums2.end()), nums2.end());
for (int x : nums1) {
m[x]++;
}
for (int x : nums2) {
m[x]++;
}
for (auto x : m) {
if (x.second > 1)
v.push_back(x.first);
}
return v;
}
};
