剑指 offer
赋值运算符
class CMyString {public : CMyString (char * pData = nullptr ); CMyString (const CMyString& str); CMyString& operator =(const CMyString &str); ~CMyString (void ); - private : char * m_pData; } CMyString& CMyString::operator =(const CMyString &str){ if (this != &str){ CMyString strtmp (str); char * ptmp = strtmp.m_pData; strtmp.m_pData = m_pData; m_pData = ptmp; } return *this ; }
面试题3：数组中重复的数字
题目一：找出数组中重复的数字。 在一个长度为n的数组里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如，如果输入长度为7的数组(2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。
int findRepeatNumber (vector<int >& nums) vector<bool > map (nums.size(), false ) ; for (auto i: nums){ if (map[i]) return i; else map[i] = true ; } return 0 ; } int findRepeatNumber (vector<int >& nums) int i=0 ; while (i<nums.size ()){ if (nums[i] == i) i++; else { if (nums[nums[i]] == nums[i]) return nums[i]; else swap (nums[nums[i]], nums[i]); } } return 0 ; }
在一个长度为n+1的数组里的所有数字都在1～n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。
int countRange (vector<int > nums, int start, int end) int count = 0 ; for (int i=0 ; i<nums.size (); i++){ if (nums[i]>=start && nums[i]<=end) count++; } return count; } int findRepeatNumber (vector<int >& nums) int start = 1 ; int end = nums.size ()-1 ; while (end>=start){ int mid = ((end-start)>>1 )+start; int count = countRange (nums, start, middle); if (end == start){ if (count>1 ) return start; else break ; } if (count>(mid-start+1 )) end = mid; else start = mid+1 ; } return 0 ; }
面试题4：二维数组中的查找
题目：在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
bool findNumberIn2DArray (vector<vector<int >>& matrix, int target) if (matrix.empty ()) return false ; int width = matrix[0 ].size (); int height = matrix.size (); int i=height-1 , j=0 ; while (i>=0 && j<width){ if (matrix[i][j]==target) return true ; else if (target<matrix[i][j]) i--; else if (target>matrix[i][j]) j++; } return false ; }
字符串存储问题
int tmain (int argc, _TCHAR* argv[]) char str1[] = "hello world" ; char str2[] = "hello world" : char * str3 = "hello world" ; char * str4 = "hello world" : if (strl == str2) printf ("str1 and str2 are same\n" ); else printf ("str1 and str2 are not same\n" ); if (str3 == str4) printf ("str3 and str4 are same.\n" ); else printf ("str3 and str4 are not same. \n" ); return 0 }
面试题5：替换空格
题目：请实现一个函数，把字符串中的每个空格替换成"%20"。例如， 输入“We are happy.”，则输出“We%20are%20happy.”
新分配字符串
string replaceSpace (string s) { string ans; for (char i:s){ if (i == ' ' ) ans.append ("%20" ); else ans.push_back (i); } return ans; }
在原有字符串上修改(先估计大小, 后从后往前更新)
string replaceSpace (string s) { int space_count = 0 ; for (char i:s){ if (i == ' ' ) space_count+=1 ; } int i=s.length ()-1 ; int length = s.length () + space_count*2 ; s.resize (length); length -= 1 ; for (; i>=0 && length>=i; i--){ if (s[i] == ' ' ){ s[length--] = '0' ; s[length--] = '2' ; s[length--] = '%' ; } else s[length--] = s[i]; } return s; }
面试题6：从尾到头打印链表
题目：输入一个链表的头节点，从尾到头反过来打印出每个节点的值。 链表节点定义如下：
struct ListNode { int m_nkey; ListNode* m_pNext; };
不改变原链表结构
vector<int > reversePrint (ListNode* head) { stack<int > s; ListNode* p = head; while (p){ s.push (p->val); p = p->next; } vector<int > ans; while (!s.empty ()){ ans.push_back (s.top ()); s.pop (); } return ans; }
链表反转
vector<int > reversePrint (ListNode* head) { vector<int > ans; ListNode* cur = head, * pre = NULL , *next; while (cur){ next = cur->next; cur->next = pre; pre = cur; cur = next; } while (pre){ ans.push_back (pre->val); pre = pre->next; } return ans; }
树
树的遍历: 递归迭代, 宽度遍历
树的特例: 二叉搜索树, 堆, 红黑树
面试题7：重建二叉树
题目：输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如，输入 前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则 重建如图所示的二叉树并输出它的头节点。二叉树节点的定义如下：
struct BinaryTreeNode { int m_nValue; BinaryTreeNode* m_pLeft; BinaryTreeNode* m_pRight; }
class Solution {public : vector<int > preorder; vector<int > inorder; TreeNode* buildTree (vector<int >& preorder, vector<int >& inorder) { if (preorder.empty () || inorder.empty ()) return nullptr ; this ->inorder = inorder; this ->preorder = preorder; return ConstructCore (0 , this ->inorder.size ()-1 , 0 , this ->preorder.size ()-1 ); } TreeNode* ConstructCore (int startin, int endin, int startpre, int endpre) { int rootvalue = preorder[startpre]; TreeNode* root = new TreeNode (rootvalue); if (startpre == endpre) if (startin == endin && preorder[startpre] == inorder[startin]) return root; else cout<<"invalid" ; int rootin = startin; while (rootin<=endin && inorder[rootin]!=rootvalue) ++rootin; if (rootin == endin && inorder[rootin]!=rootvalue) cout<<"invalid" ; int leftlength = rootin - startin; int leftpreend = startpre + leftlength; if (leftlength>0 ){ root->left = ConstructCore (startin, rootin-1 ,startpre+1 , leftpreend); } if (leftlength<endpre-startpre) { root->right = ConstructCore (rootin+1 , endin, leftpreend+1 , endpre); } return root; } };
面试题8：二叉树的下一个节点
题目：给定一棵二叉树和其中的一个节点，如何找出中序遍历序列的 下一个节点？树中的节点除了有两个分别指向左、右子节点的指针，还有 1个指向父节点的指针。
TreeNode* solution (TreeNode* pnode) { TreeNode* ans = nullptr ; if (pnode->right != nullptr ){ TreeNode* pright = pnode->right; while (pright->left!=nullptr ) pright = pright->left; ans = pright; } else if (pnode->parent!=nullptr ){ TreeNode* pcur = pnode; TreeNode* pparent = pnode->parent; while (pparent!=nullptr && pcur == pparent->right){ pcur = pparent; pparent = pparent->parent; } ans = pparent; } }
面试题9：用两个栈实现队列
题目：用两个栈实现一个队列。队列的声明如下，请实现它的两个函 数 appendTail 和 deleteHead，分别完成在队列尾部插入节点和在队列头部删 除节点的功能。
class CQueue {public : CQueue () { } void appendTail (int value) s1.push (value); } int deleteHead () if (s2.empty ()){ while (!s1.empty ()){ int tmp = s1.top (); s1.pop (); s2.push (tmp); } } if (s2.empty ()){ cout<<"invalid" ; return -1 ; } int ret = s2.top (); s2.pop (); return ret; } private : stack<int > s1; stack<int > s2; };
面试题10：斐波那契数列
题目一：求斐波那契数列的第n项。 写一个函数，输入n，求斐波那契（Fibonacci）数列的第n项。
注意取模!
class Solution {public : int fib (int n) vector<int > hash {0 , 1 }; if (n<2 ) return hash[n]; long long n1=0 ; long long n2=1 ; long long ans = 0 ; for (int i=2 ; i<=n; i++){ ans = (n1+n2)%int (1e9 +7 ); n1 = n2%int (1e9 +7 ); n2 = ans%int (1e9 +7 ); } return ans%int (1e9 +7 ); } };
快速排序
int Partition (int data[], int length, int start, int end) if (data==nullptr ||length<=0 ||start<=0 ||end>=length) return -1 ; int index = start; swap (&data[index], &data[end]); int small = start-1 ; for (index=start; index<end; index++){ if (data[index]<data[end]){ ++small; if (small!=index) swap (&data[index], &data[small]); } } ++small; swap (&data[small], &data[end]); return small; } void QuickSort (int data[], int length, int start, int end) if (start == end) return ; int index = Partition (data, length, start, end); if (index>start) QuickSort (data, length, start, index-1 ); if (index<end) QuickSort (data, length, index+1 , end); }
面试题11：旋转数组的最小数字
题目：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为 数组的旋转。输入一个递增排序的数组的一个旋转，输出旋转数组的最小 元素。例如，数组(3, 4, 5, 1, 2}为{1, 2, 3, 4, 5}的一个旋转，该数组的最小值为1。
int minArray (vector<int >& numbers) if (numbers.empty ()) return -1 ; int start = 0 ; int end = numbers.size ()-1 ; int mid = start + ((end-start)>>1 ); while (start<end){ mid = start + ((end-start)>>1 ); if (numbers[mid]>numbers[end]) start = mid+1 ; else if (numbers[mid] < numbers[end]) end = mid; else end-=1 ; } return numbers[start]; }
面试题12：矩阵中的路径
题目：请设计一个函数，用来判断在一个矩阵中是否存在一条包含某 字符串所有字符的路径。路径可以从矩阵中的任意一格开始，每一步可以 在矩阵中向左、右、上、下移动一格。如果一条路径经过了矩阵的某一格， 那么该路径不能再次进入该格子。
class Solution { int row, col; public : bool check (vector<vector<char >>& board, int i, int j, string word, int k) if (i<0 || i>=row || j<0 || j>=col || board[i][j]!=word[k]) return false ; if (k == word.size ()-1 ) return true ; board[i][j] == '\0' ; bool res = check (board, i+1 , j, word, k+1 )|| check (board, i-1 , j, word, k+1 )|| check (board, i, j+1 , word, k+1 )|| check (board, i, j-1 , word, k+1 ); board[i][j] = word[k]; return res; } bool exist (vector<vector<char >>& board, string word) if (board.empty ()) return false ; row = board.size (); col = board[0 ].size (); for (int i=0 ; i<row; i++) for (int j=0 ; j<col; j++) if (check (board, i, j, word, 0 )) return true ; return false ; } };
面试题14：剪绳子
题目：给你一根长度为n的绳子，请把绳子剪成m段（m、n都是整数， n>1并且m＞1)，可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的段，此时得到的最大乘积是18。
class Solution {public : int cuttingRope (int n) if (n<=3 ) return n-1 ; vector<int > hash (n+1 ) ; hash[1 ] = 1 ; hash[2 ] = 2 ; hash[3 ] = 3 ; int ans = 0 ; for (int i=4 ; i<=n; i++){ for (int j=1 ; j<=i/2 ; j++){ ans = max (ans, hash[j]*hash[i-j]); hash[i] = ans; } } return hash[n]; } };
面试题15：二进制中1的个数
题目：请实现一个函数，输入一个整数，输出该数二进制表示中1 的 个数。例如，把9表示成二进制是1001，有2位是1。因此，如果输入9, 则该函数输出2。
class Solution {public : int hammingWeight (uint32_t n) int ans = 0 ; while (n>0 ){ ans += n&1 ; n=n>>1 ; } return ans; } }; class Solution {public : int hammingWeight (uint32_t n) int ans = 0 ; while (n>0 ){ n = n&(n-1 ); ++ans; } return ans; } };
把一个整数减去1之后再和原来的整数做位与运算，得到的结果相当 于把整数的二进制表示中最右边的1变成0。很多二进制的问题都可以用这 种思路解决。
面试题 16：数值的整数次方
题目：实现函数 double Power(double base, int exponent)，求 base 的 exponent 次方。不得使用库函数，同时不需要考虑大数问题
class Solution {public : double qpow (double a, unsigned int n) double ans = 1 ; while (n){ if (n&1 ) ans*=a; a*=a; n>>=1 ; } return ans; } double myPow (double x, int n) if (x==0.0 ) return 0 ; if (n==0 ) return 1 ; double ans = 1 ; if (n<0 ){ unsigned int nnew = (unsigned int )n; ans = 1.0 /qpow (x, -nnew); } else { ans = qpow (x, n); } return ans; } };
注意 unsigned int 用法
快速幂
int qpow (int a, int n) if (n==0 ) return 1 ; else if (n&1 == 1 ) return qpow (a, n-1 ) * a; else { int tmp = qpow (a, n>>1 ); return tmp*tmp; } } int qpow (int a, int n) int ans = 1 ; while (n){ if (n&1 ) ans*=a; a*=a; n>>=1 ; } return ans; }
面试题17：打印从1到最大的n位数
题目：输入数字 n，按顺序打印出从1到最大的n位十进制数。比如输 入3，则打印出1、2、3一直到最大的3位数999。
?大数问题, 字符串表示数
面试题18：删除链表的节点
题目一：在0(1)时间内删除链表节点。 给定单向链表的头指针和一个节点指针，定义一个函数在0(1)时间内 删除该节点。链表节点与函数的定义如下：
struct ListNode { int val; ListNode *next; ListNode (int x) : val (x), next (NULL ) {} }; class Solution {public : ListNode* deleteNode (ListNode** head, ListNode* tobedelete) { ListNode* next = tobedelete->next; if (*head == tobedelete){ delete tobedelete; tobedelete = nullptr ; *head = nullptr ; } else if (next!=nullptr ){ tobedelete->val = next->val; tobedelete->next = next->next; delete next; next = nullptr ; } else { ListNode* cur = *head; while (cur->next!=tobedelete) cur = cur->next; cur->next = nullptr ; delete tobedelete; tobedelete = nullptr ; } } };
题目二：删除链表中重复的节点。 在一个排序的链表中，如何删除重复的节点？
面试题19：正则表达式匹配
截屏2022-08-31 14.19.11
class Solution {public : string m_s; string m_p; char star = '*' ; char dot = '.' ; bool isMatch (string s, string p) m_p = p; m_s = s; return isMatchIndex (0 , 0 ); } bool isMatchIndex (int i_s, int i_p) if (i_s == m_s.size () && i_p == m_p.size ()) return true ; if (i_s!=m_s.size () && i_p == m_p.size ()) return false ; if (i_p+1 <m_p.size () && m_p[i_p+1 ] == star){ if ((m_p[i_p]==dot && i_s!=m_s.size ()) || m_p[i_p]==m_s[i_s]) return isMatchIndex (i_s+1 , i_p+2 ) || isMatchIndex (i_s+1 , i_p) || isMatchIndex (i_s, i_p+2 ); return isMatchIndex (i_s, i_p+2 ); } if ((m_p[i_p] == dot && i_s!=m_s.size ()) || m_p[i_p] == m_s[i_s]){ return isMatchIndex (i_s+1 , i_p+1 ); } return false ; } };
面试题 20：表示数值的字符串
题目：请实现一个函数用来判断字符串是否表示数值（包括整数和小 数）。例如，字符串"+100"、"5e2”、"-123"、"3.1416"及"-1E-16"都表示数 值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。
class Solution {public : string m_s; void fit (string& s) while (s.front ()==' ' ) s.erase (s.begin ()); while (s.back ()==' ' ) s.pop_back (); } int isInt (int &i) while (m_s[i]>=48 && m_s[i]<=57 ) ++i; return i; } int isE (int &i) if (m_s[i]=='e' || m_s[i]=='E' ) return ++i; return i; } int isPN (int &i) if (m_s[i]=='-' || m_s[i]=='+' ) return ++i; return i; } int isdot (int &i) if (m_s[i]=='.' ) return ++i; return i; } bool isNumber (string s) m_s = s; fit (m_s); int cur = 0 ; vector<int > check; check.push_back (isPN (cur)); check.push_back (isInt (cur)); check.push_back (isdot (cur)); check.push_back (isInt (cur)); if (check[0 ]==check[3 ]) { cout<<"no number" ; return false ; } if (check[1 ]!=check[2 ] && (check[0 ]+1 ==check[3 ])) { cout<<"no dot" ; return false ; } check.push_back (isE (cur)); check.push_back (isPN (cur)); check.push_back (isInt (cur)); if (check[3 ]!=check[4 ] && check[5 ]==check[6 ]) { cout<<"no e" ; return false ; } if (check[3 ]==check[4 ] && check[4 ]!=check[5 ]) return false ; if (cur==m_s.size ()) return true ; return false ; } };
面试题 21：调整数组顺序使奇数位于偶数前面
题目：输入一个整数数组，实现一个函数来调整该数组中数字的顺序， 使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。
class Solution {public : bool isOdd (int i) return i&1 ; } vector<int > exchange (vector<int >& nums) { int even = 0 ; int odd = nums.size ()-1 ; while (even<odd){ bool isodd = isOdd (nums[odd]); bool iseven = !isOdd (nums[even]); if (!isodd) odd--; if (!iseven) even++; if (isodd && iseven){ swap (nums[odd], nums[even]); odd--; even++; } } return nums; } };
注意解耦合
面试题 22：链表中倒数第k个节点
题目：输入一个链表，输出该链表中倒数第k个节点。为了符合大多 数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。例 如，一个链表有6个节点，从头节点开始，它们的值依次是1、2、3、4、5、 6。这个链表的倒数第3 个节点是值为4的节点。
class Solution {public : ListNode* getKthFromEnd (ListNode* head, int k) { int forward = 0 ; ListNode* p = head; while (p!=NULL ){ p = p->next; forward++; } if (k>forward) return NULL ; int reverse = forward - k; p = head; while (reverse!=0 ){ p = p->next; reverse--; } return p; } }; class Solution {public : ListNode* getKthFromEnd (ListNode* head, int k) { ListNode* p1 = head; while (p1!=NULL && k>0 ){ p1 = p1->next; k--; } ListNode* p2 = head; while (p1!=NULL ){ p1 = p1->next; p2 = p2->next; } return p2; } };
面试题 23：链表中环的入口节点
题目：如果一个链表中包含环，如何找出环的入口节点？例如，在如 图3.8所示的链表中，环的入口节点是节点3。
class Solution {public : ListNode *detectCycle (ListNode *head) { if (head == nullptr ) return nullptr ; ListNode* pslow = head->next; if (pslow==nullptr ) return nullptr ; ListNode* pfast = pslow->next; while (pfast!=nullptr && pfast!=pslow){ pslow = pslow->next; pfast = pfast->next; if (pfast) pfast = pfast->next; } if (pfast==nullptr ) return nullptr ; ListNode* pcircle = pfast->next; int circle_len = 1 ; while (pcircle!=pfast){ pcircle = pcircle->next; circle_len++; } ListNode* pcirclestart = head; pcircle = head; for (int i=0 ; i<circle_len; i++) pcircle = pcircle->next; while (pcircle!=pcirclestart){ pcircle = pcircle->next; pcirclestart = pcirclestart->next; } return pcirclestart; } };
先快慢指针, 后转圈统计环长, 后先后指针找环开始端
24 反转链表
class Solution {public : ListNode* reverseList (ListNode* head) { ListNode* cur = head; ListNode* next = nullptr ; ListNode* pre = nullptr ; while (cur){ next = cur->next; cur->next = pre; pre = cur; cur = next; } return pre; } }; class Solution { public ListNode* reverseList (ListNode* head) if (head == null || head->next == null) return head; ListNode* newhead = reverseList (head->next); head->next->next = head; head->next = null; return newhead; } };
面试题 25：合并两个排序的链表
题目：输入两个递增排序的链表，合并这两个链表并使新链表中的节 点仍然是递增排序的。例如，输入图3.11中的链表1和链表2，则合并之 后的升序链表如链表 3 所示。链表节点定义如下：
class Solution {public : ListNode* mergeTwoLists (ListNode* l1, ListNode* l2) { ListNode* cur = l1; ListNode head; cur = &head; while (l1!=nullptr && l2!=nullptr ){ if (l1->val<l2->val){ cur->next = l1; l1 = l1->next; } else { cur->next = l2; l2 = l2->next; } cur = cur->next; } if (l1 == nullptr ) cur->next = l2; else cur->next = l1; return head.next; } };
首节点
面试题26：树的子结构
题目：输入两棵二叉树A和B，判断B是不是A的子结构。二叉树节 点的定义如下：
class Solution {public : bool isSubStructure (TreeNode* A, TreeNode* B) return (A!=nullptr && B!=nullptr ) && (recur (A, B) || isSubStructure (A->left, B) || isSubStructure (A->right, B)); } bool recur (TreeNode* A, TreeNode* B) if (B==nullptr ) return true ; if (A==nullptr || A->val!=B->val) return false ; return recur (A->left, B->left) && recur (A->right, B->right); } };
面试题
实现一个trie树
要提供insert（插入一个word），search（查询，返回命中的word列表）（最好C++实现）
线段相交
https://blog.csdn.net/wlxsq/article/details/47356905
问题描述：最近阿里的某同学（阳阳）从阿里毕业了（实现了财富自由），但是他从小就有一个梦想，他想回到他的老家经营一个农场，因此就需要在农场设计一些沟渠用来排水。为了设计这个沟渠，他不惜花费重金请来了物理系毕业的大学同学（天天）来帮他设计整个农场的沟渠系统。假设每条构建都是一条折线（即有多条首尾相连的线段组成），由于阳阳特别相信风水（风水先生告诉他，他的农场的沟渠路线的相交点不能超过5个），由于天天设计的沟渠系统十分复杂，作为程序员的你，能否设计一个程序帮助阳阳判断，这个沟渠系统能否满足要求。
程序输入：
第一行：整数 N （表示多条沟渠）
第2-(N+1)行：第一个数M(沟渠折线的顶点，沟渠的线段数 = M -1), 后面接着 2 * M个float，每两个float表示一个点。
输出：bool：true(符合要求)， false（不符合要求）。
程序输入示例：
2
4 1.7 1.8 2.4 2.9 3.8 4.5 5.9 7.0
3 1.0 1.0 2.0 1.0 2.0 8.0
质串
假设一个字符串由n个字符构成，字符只能是a或者b，如果一个字符串能由他的某个子串重复多次拼接而成，那么这种串就被命名为 "复数串"， 否则就被命名为 "质串"。
例如：abab 为复数串（因为它可以有ab重复2次拼接二次） abba为质串。
请你设计一个程序，判断一个长度为n的串，有多少个是『质串』,最后的结果 mod 2022 。
例如：n = 1, 那么长度为1的所有串中，有2个质串，分别是 a 和 b。
n = 2, 那么长度为2的所有串中，有2个质串，分别是 ab 和 ba。
n = 3, 那么长度为3的所有串中，有6个质串，分别是（aab, aba, baa, abb, bab, bba）.
判断一个数是否为质数
bool isPrime (int n) if (n<=1 ) return false ; for (int =2 ; i*i<=n; i++) if (n%i==0 ) return false ; return true ; }
素数筛(埃氏)
int prime[n+1 ], isprime[n+1 ];int sieve (int n) int p=0 ; for (int i=0 ; i<=n; i++) isprime[i] = 1 ; isprime[0 ] = 0 ; isprime[1 ] = 1 ; for (int i=2 ; i<=n; i++){ if (isprime[i]){ prime[p++] = i; for (int j=2 *i; j<=n; j+=i) isprime[j] = 0 ; } } return p; }
欧拉筛
const int maxn = 100 ;int prime[maxn] {0 };int vis[maxn] {0 };void eulasieve () for (int i=2 ; i<maxn; i++){ if (!vis[i]) prime[++prime[0 ]] = i; for (int j=1 ; j<=prime[0 ]&&i*prime[j]<=maxn; j++){ vis[i*prime[j]] = 1 ; if (i%prime[j] == 0 ) break ; } } }
其他 leetcode
点灯
每个点是一个按钮，每个按钮里面有一个小灯。如上图，红色代表灯亮，白色代表灯灭。每当按下按钮，此按钮的灯以及其上下左右四个方向按钮的灯状态会改变（如果原来灯亮则灯灭，如果原来灯灭则灯亮）。如果小张通过按按钮将灯全部熄灭则能可以打开箱子。
现在小张给你一些密码锁的状态，请你告诉他最少按几次按钮能够把灯全部熄灭。
Input
第一行两个整数n, m
接下来n行，每行一个长度为m的01字符串，0表示灯初始状态灭，1表示灯初始状态亮。
Output
一行一个整数，表示最少按几次按钮可以把灯全部熄灭。 #include <vector> #include <string> #include <iostream> using namespace std;#define MAX 1024 void change (int i, int j, vector<vector<bool >> &map) void changefirstline (vector<vector<bool >> map, int j, int count) int dfs (vector<vector<bool >> &map, int count) int ans = MAX;void changefirstline (vector<vector<bool >> map, int j, int count) if (j<map[0 ].size ()){ changefirstline (map, j+1 , count); change (0 , j, map); changefirstline (map, j+1 , count+1 ); } else ans = min (dfs (map, count), ans); } int dfs (vector<vector<bool >> &map, int count) int n = map.size (); int m = map[0 ].size (); for (int i=0 ; i<n-1 ; i++){ for (int j=0 ; j<m; j++){ if (map[i][j]){ change (i+1 , j, map); ++count; } } } for (int j=0 ; j<m; j++) if (map[n-1 ][j]) return MAX; return count; } void change (int i, int j, vector<vector<bool >> &map) int n = map.size (); int m = map[0 ].size (); map[i][j] = !map[i][j]; vector<pair<int , int >> direction{{1 ,0 }, {-1 ,0 }, {0 ,1 }, {0 ,-1 }}; for (auto p : direction){ int newi = i+p.first; int newj = j+p.second; if (newi>=n || newi<0 || newj>=m || newj<0 ) continue ; map[newi][newj] = !map[newi][newj]; } } int main () int n, m; scanf ("%d %d\n" , &n, &m); vector<vector<bool >> map (n, vector <bool >(m, false )); for (int i=0 ; i<n; i++){ for (int j=0 ; j<m; j++){ char c = getchar (); if (c=='1' ) map[i][j] = true ; } getchar (); } changefirstline (map, 0 , 0 ); cout<<ans<<endl; }
二进制加法
和十进制不同的是：二进制运算“逢二进一”。下面举一个二进制加法的运算实例:
11101
- 110
100011 下面请你模拟这个过程。
Input 第一行输入一个正整数 T 表示接下来有 T 组数据； 接下来 T 行，每行输入两个二进制串 a 和 b 中间用空格隔开，并且没有前导 0。 Output 对于每组数据，请按模拟二进制加法，按题目描述的格式输出正确的运算结果，注意换行，没有多余的空格和换行。
#include <vector> #include <string> #include <iostream> using namespace std;struct tri { string var1; string var2; string res; }; void calculate (tri &t) string fillblank (const string& s, int len) ;void print (const tri &t) void rev (string &str) void rev (string &str) int len = str.length (); int n = len-1 ; int i = 0 ; while (i<=n){ swap (str[i],str[n]); n = n-1 ; i = i+1 ; } } void calculate (tri &t) if (!(t.res.empty ())) return ; string::reverse_iterator i1 = t.var1.rbegin (); string::reverse_iterator i2 = t.var2.rbegin (); int bit1=0 ; int bit2=0 ; int bitres = 0 ; int carry = 0 ; while (i1!=t.var1.rend () || i2!=t.var2.rend () || carry!=0 ){ if (i1==t.var1.rend ()) bit1 = 0 ; else { bit1 = *i1-48 ; i1++; } if (i2==t.var2.rend ()) bit2 = 0 ; else { bit2 = *i2-48 ; i2++; } bitres = (bit1+bit2+carry)%2 ; carry = (bit1+bit2+carry)>>1 ; t.res.push_back (bitres+48 ); } rev (t.res); return ; } void print (const tri &t) int len = t.res.size (); string div (len+2 , '-' ) ; string blank (" " ) ; cout<<blank<<fillblank (t.var1, len)<<endl; cout<<"+ " <<fillblank (t.var2, len)<<endl; cout<<div<<endl; cout<<blank<<t.res<<endl; } string fillblank (const string& s, int len) { string res = s; while (res.size ()<len) res.insert (0 , " " ); return res; } int main () int t; cin>>t; vector<tri> v (t) ; for (int i=0 ; i<t; i++){ cin>>v[i].var1 >>v[i].var2; calculate (v[i]); } for (auto i:v) print (i); }
大实数加减法
#include <vector> #include <string> #include <iostream> using namespace std;struct tri { string var1; string var2; string res; }; void calculate (tri &tr) void print (tri t) void rev (string &str) void rev (string &str) int len = str.length (); int n = len-1 ; int i = 0 ; while (i<=n){ swap (str[i],str[n]); n = n-1 ; i = i+1 ; } } void fit (string& str, int len_i, int len_f) if (str.front ()=='.' ||str.empty ()) str.insert (0 , "0" ); int dot = str.find ('.' )==-1 ? str.size () : str.find ('.' ); int i = len_i - dot; for (int j=0 ; j<i; j++){ str.insert (0 , " " ); } int back0 = len_i+len_f - str.size (); if (len_f!=0 ) back0+=1 ; for (int j=0 ; j<back0; j++){ str.append (" " ); } } void calculate (tri &tr) if (!(tr.res.empty ())) return ; tri t = tr; int dot1 = t.var1.find ("." ); if (dot1==-1 ){ dot1 = t.var1.size (); t.var1.push_back ('.' ); } int dot2 = t.var2.find ("." ); if (dot2==-1 ){ dot2 = t.var2.size (); t.var2.push_back ('.' ); } string &s = dot1<dot2 ? t.var1 : t.var2; for (int i=0 ; i<abs (dot1-dot2); i++){ s.insert (0 , "0" ); } string &s2 = t.var1.size ()<t.var2.size () ? t.var1 : t.var2; while (t.var1.size ()!=t.var2.size ()){ s2.push_back ('0' ); } string::reverse_iterator i1 = t.var1.rbegin (); string::reverse_iterator i2 = t.var2.rbegin (); int bit1=0 ; int bit2=0 ; int bitres = 0 ; int carry = 0 ; while (i1!=t.var1.rend () && i2!=t.var2.rend ()){ if (*i1=='.' ){ t.res.push_back ('.' ); i1++; i2++; continue ; } bit1 = *i1-48 ; i1++; bit2 = *i2-48 ; i2++; bitres = (bit1+bit2+carry)%10 ; carry = (bit1+bit2+carry)/10 ; t.res.push_back (bitres+48 ); } t.res.push_back (carry+48 ); rev (t.res); while (t.res.front ()=='0' ) t.res.erase (0 , 1 ); if (t.res.front ()=='.' ) t.res.insert (0 , "0" ); if (t.res.back ()=='.' ) t.res.pop_back (); tr.res = t.res; return ; } void print (tri t) int len_i = 0 ; int len_f = 0 ; if (t.var1.find ('.' ) == -1 ) len_i = t.var1.size (); if (t.var2.find ('.' ) == -1 ) len_i = max (len_i, (int )t.var2.size ()); if (t.res.find ('.' ) == -1 ) len_i = max (len_i, (int )t.res.size ()); else len_f = t.res.size () - t.res.find ('.' )-1 ; len_i = max (len_i , (int )t.var1.find ('.' )); len_i = max (len_i, (int )t.var2.find ('.' )); len_i = max (len_i, (int )t.res.find ('.' )); fit (t.var1, len_i, len_f); fit (t.var2, len_i, len_f); fit (t.res, len_i, len_f); string div (t.res.size()+3 , '-' ) ; string blank (" " ) ; cout<<blank<<t.var1<<endl; cout<<"+ " <<t.var2<<endl; cout<<div<<endl; string s = t.res; cout<<blank<<s<<endl; } int main () tri t; cin>>t.var1 >>t.var2; calculate (t); print (t); }
#include <vector> #include <string> #include <iostream> using namespace std;const string target = "fattyhappy" ;const int length = 10 ;pair<int , int > check (int index, string str) { pair<int , int > ans (-1 , -1 ) ; string sub = str.substr (index, length); int count = 0 ; vector<int > v; for (int i=0 ; i<length; i++){ if (sub[i] != target[i]){ count++; v.push_back (i); } } if (count==0 ) return pair <int , int >(2 +index, 3 +index); else if (count==1 ){ for (int i=0 ; i<str.size (); i++){ if (i>=index && i<index+length) continue ; if (str[i] == target[v.front ()]){ ans.first = min (i, index+v.front ()); ans.second = max (i, index+v.front ()); return ans; } } } else if (count==2 ){ swap (sub[v[0 ]], sub[v[1 ]]); if (sub == target){ ans.first = v[0 ]+index; ans.second = v[1 ]+index; return ans; } } return ans; } pair<int , int > findexchange (string str) { pair<int , int > ans; ans.first = -1 ; int len = str.size (); for (int i=0 ; i+length<=len; i++){ ans = check (i, str); if (ans.first!=-1 ){ return ans; } } return ans; } int main () int t = 0 ; cin>>t; vector<string> v (t) ; for (int i=0 ; i<t; i++) cin>>v[i]; for (int i=0 ; i<t; i++){ pair<int , int > ans = findexchange (v[i]); if (ans.first == -1 ) cout<<"-1" <<endl; else cout<<ans.first+1 <<" " <<ans.second+1 <<endl; } }
#include <vector> #include <string> #include <iostream> #include <stack> using namespace std;enum direction {LEFT=-1 , RIGHT=1 , EMPTY=0 };struct brid { bool valid=false ; direction d; int count=0 ; string str; }; void rev (string &str) int len = str.length (); int n = len-1 ; int i = 0 ; while (i<=n){ swap (str[i],str[n]); n = n-1 ; i = i+1 ; } } void check (brid& b) string& str = b.str; stack<char > s; int length = str.size (); for (int i=0 ; i<length; i++){ if (s.empty ()) s.push (str[i]); else { if (s.top ()=='(' && str[i]==')' ) s.pop (); else s.push (str[i]); } } str.clear (); while (!s.empty ()){ str.push_back (s.top ()); s.pop (); } rev (str); b.valid = true ; if (b.str.find ('(' )!=-1 ){ b.d = LEFT; if (b.str.find (')' )!=-1 ){ b.valid = false ; return ; } } else b.d = RIGHT; if (b.str.empty ()) b.d = EMPTY; b.count = b.str.size (); } int main () int t = 0 ; cin>>t; vector<string> v (t) ; vector<brid> vnew; int ans = 0 ; for (int i=0 ; i<t; i++){ cin>>v[i]; brid b; b.str = v[i]; check (b); if (b.valid) vnew.push_back (b); } t = vnew.size (); for (int i=0 ; i<t; i++){ for (int j=i+1 ; j<t; j++){ if (vnew[i].valid && vnew[j].valid&&(vnew[i].d + vnew[j].d) == 0 && vnew[i].count == vnew[j].count ) { vnew[i].valid = false ; vnew[j].valid = false ; ans++; } } } cout<<ans<<endl; }
任务安排
截屏2022-08-27 22.50.56
#include <stdio.h> #include <stdlib.h> #define N 500000 typedef struct timelimit { long long int s; long long int e; }timelimit; timelimit T[N]; int compare (const void * a,const void * b) { return (*(timelimit*)a).e-(*(timelimit*)b).e; } int main () { long long int n, ans = 0 , i; scanf ("%lld" ,&n); for (i=0 ;i<n;i++) { scanf ("%lld" ,&(T[i].s)); scanf ("%lld" ,&(T[i].e)); } qsort (T, n, sizeof (timelimit), &compare); long long int end = 0 ; for (i=0 ;i<=n-1 ;i++) { if (T[i].s>=end) { end = T[i].e; ans=ans+1 ; } } printf ("%lld\n" ,ans); return 0 ; }
刷房子
#include <vector> #include <iostream> #include <algorithm> #include <stack> using namespace std;typedef struct building_ { int h; int c; }building; int main () int n; cin>>n; vector<vector<int >> ans (n); for (int i=0 ; i<n; i++){ int amount; cin>>amount; vector<building> buildings (amount) ; for (int j=0 ; j<amount; j++) cin>>buildings[j].c; for (int j=0 ; j<amount; j++) cin>>buildings[j].h; stack<building> s; vector<vector<int >> colors (amount); ans[i].push_back (1 ); colors[0 ].push_back (buildings[0 ].c); for (int j=0 ; j<amount; j++){ int tallest = j; vector<int > newcolor; int k; for (k=j-1 ; k>=0 ; k--){ if (buildings[k].h<=buildings[tallest].h){ } else { colors[j] = colors[k]; if (find (colors[j].begin (), colors[j].end (), buildings[j].c)==colors[j].end ()){ colors[j].push_back (buildings[k].c); } break ; } } if (k==-1 ) colors[j].push_back (buildings[j].c); ans[i].push_back (colors[j].size ()); } } for (int i=0 ; i<ans.size (); i++){ for (int j=0 ; j<ans[i].size ()-1 ; j++){ cout<<ans[i][j]<<" " ; } cout<<ans[i].back ()<<endl; } }
简单难度题目合集
这里的题目难度比较小， 大多是模拟题，或者是很容易看出解法的题目，另外简单题目一般使用暴力法都是可以解决的。 这个时候只有看一下数据范围，思考下你的算法复杂度就行了。
当然也不排除很多 hard 题目也可以暴力模拟，大家平时多注意数据范围即可。
以下是我列举的经典题目（带 91 字样的表示出自 91 天学算法 活动）：
unordered_map
递归?
使用快慢指针来记录遍历的坐标。
开始时这两个指针都指向第一个数字
如果两个指针指的数字相同，则快指针向前走一步
如果不同，则两个指针都向前走一步
当快指针走完整个数组后，慢指针当前的坐标加 1 就是数组中不同数字的个数
前缀和, 动态规划
how to recursive
try iteration
二叉搜索树是一种节点值之间具有一定数量级次序的二叉树，对于树中每个节点：
若其左子树存在，则其左子树中每个节点的值都不大于该节点值；
若其右子树存在，则其右子树中每个节点的值都不小于该节点值。
异或
???
unordered_map count, insert
例如使用 a, b 两个指针分别指向 A, B 这两条链表, 两个指针相同的速度向后移动,
当 a 到达链表的尾部时,重定位到链表 B 的头结点
当 b 到达链表的尾部时,重定位到链表 A 的头结点。
a, b 指针相遇的点为相交的起始节点，否则没有相交点
多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
投票算法
trick count 5
位运算
就是n & (n - 1) 可以消除 n 最后的一个 1 的原理。
重要※
⭐️
hash
迭代
use for and function call
!
中等难度题目合集
中等题目是力扣比例最大的部分，因此这部分我的题解也是最多的。 大家不要太过追求难题，先把中等难度题目做熟了再说。
这部分的题目要不需要我们挖掘题目的内含信息， 将其抽象成简单题目。 要么是一些写起来比较麻烦的题目， 一些人编码能力不行就挂了。因此大家一定要自己做， 即使看了题解”会了“，也要自己码一遍。自己不亲自写一遍，里面的细节永远不知道。
以下是我列举的经典题目（带 91 字样的表示出自 91 天学算法 活动）：
困难难度题目合集
困难难度题目从类型上说多是：
图
设计题
游戏场景题目
中等题目的 follow up
从解法上来说，多是：
图算法
动态规划
二分法
DFS & BFS
状态压缩
剪枝
从逻辑上说， 要么就是非常难想到，要么就是非常难写代码。 这里我总结了几个技巧：
看题目的数据范围， 看能否暴力模拟
暴力枚举所有可能的算法往上套，比如图的题目。
总结和记忆解题模板，减少解题压力
以下是我列举的经典题目（带 91 字样的表示出自 91 天学算法 活动）：
