給定一個(gè)長(zhǎng)度為 n 的整數(shù)數(shù)組 nums，數(shù)組中所有的數(shù)字都在 0～n?1 的范圍內(nèi)。
數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個(gè)數(shù)字重復(fù)了，也不知道每個(gè)數(shù)字重復(fù)了幾次。
請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字。
注意：如果某些數(shù)字不在 0～n?1 的范圍內(nèi)，或數(shù)組中不包含重復(fù)數(shù)字，則返回 -1；
樣例
給定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
代碼：
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
for(int i=0;i<nums.size();i++)
{
if(nums[i]<0||nums[i]>=nums.size())
return -1;
}
for(int i=0;i<nums.size();i++)
{
while(nums[i]!=i&&nums[i]!=nums[nums[i]])
{
int temp=nums[i];
nums[i]=nums[temp];
nums[temp]=temp;
}
if(nums[i]!=i&&nums[i]==nums[nums[i]])
return nums[i];
}
return -1;
}
};
思路就是 先看一下有沒(méi)有不在范圍內(nèi)的元素，如果有 就返回-1
然后我們?cè)诳雌渲械拿恳粋€(gè)元素 如果他的值不等于他的下標(biāo)
思路比較簡(jiǎn)單不多講了，時(shí)間復(fù)雜度是 O(n)，額外的空間復(fù)雜度是 O(1)。
不修改數(shù)組找出重復(fù)的數(shù)字
給定一個(gè)長(zhǎng)度為 n+1 的數(shù)組nums，數(shù)組中所有的數(shù)均在 1～n 的范圍內(nèi)，其中 n≥1。
請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)，但不能修改輸入的數(shù)組。
樣例
給定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。
返回 2 或 3。
思考題：如果只能使用 O(1) 的額外空間，該怎么做呢？
思路
如果不考慮思考題的條件下，只要新建一個(gè)unordered_map 然后在依次存放的過(guò)程中看是否已經(jīng)有過(guò)改元素并退出即可。但如果考慮該情況下，我們可以使用二分法來(lái)解答此題。
二分算法模板
已知數(shù)組長(zhǎng)度為n+1 切所有的數(shù)字均在1~n的范圍內(nèi) 按照抽屜原理，必然有一個(gè)數(shù)字重復(fù) 按照這個(gè)思路，我們可以對(duì) 1~n的區(qū)間進(jìn)行二分查找
我們把L的值定位1，R的值定位N，然后將所有數(shù)據(jù)的值按照 [L,mid]和[mid+1，R]兩個(gè)區(qū)間盡心分類，并統(tǒng)計(jì)每個(gè)區(qū)間內(nèi)數(shù)字的個(gè)數(shù) 應(yīng)為必然存在某個(gè)數(shù)字出現(xiàn)了兩次，則 這兩個(gè)區(qū)間中必然有一個(gè)其中數(shù)字的個(gè)數(shù)大于區(qū)間，然后將原區(qū)間縮減到該區(qū)間，繼續(xù)執(zhí)行二分直到找到某個(gè)區(qū)間長(zhǎng)度為1，則數(shù)字便為重復(fù)出現(xiàn)的數(shù)字
具體代碼如下：
int duplicateInArray(vector<int>& nums) {
int l=1,r=nums.size()-1;
while(l<r)
{
int mid=(l+r)/2,count=0;
for(int i=0;i< nums.size();i++)
if(nums[i]>=l&&nums[i]<=mid)
count++;
if(count<=mid-l+1)
l=mid+1;
else
r=mid;
}
return l;
}
二維數(shù)組中的查找
在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。
請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
樣例
輸入數(shù)組：
[
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
]
如果輸入查找數(shù)值為7，則返回true，
如果輸入查找數(shù)值為5，則返回false。
思路：此題我們可以從右上角往左下角查詢，如果改值大于要查找的值，則把行號(hào)-1，否則把列號(hào)+1
代碼如下
bool searchArray(vector<vector<int>> array, int target)
{
if(array.empty()||array[0].empty())
return false;
int i=0,j=array.size()-1;
while(i<array[0].size()&&j>=0)
{
if(array[i][j]==target)
return true;
if(array[i][j]>target)
j--;
else
i++;
}
return false;
}
題目：
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)，把字符串中的每個(gè)空格替換成"%20"。
你可以假定輸入字符串的長(zhǎng)度最大是1000。
注意輸出字符串的長(zhǎng)度可能大于1000。
樣例
輸入："We are happy."
輸出："We%20are%20happy."
string replaceSpaces(string &str) {
string str1="";
string::const_iterator it=str.begin();
while(it!=str.end())
{
if(*it!=' ')
str1+=*it;
else
str1+="%20";
it++;
}
return str1;
}
這個(gè)沒(méi)啥講的。。
輸入一個(gè)鏈表的頭結(jié)點(diǎn)，按照 從尾到頭 的順序返回節(jié)點(diǎn)的值。
返回的結(jié)果用數(shù)組存儲(chǔ)。
樣例
輸入：[2, 3, 5]
返回：[5, 3, 2]
這道題比較經(jīng)典也比較簡(jiǎn)單，開(kāi)始自己用遞歸做的后來(lái)發(fā)現(xiàn)大佬們直接可以用庫(kù)函數(shù) 把兩個(gè)都貼上來(lái)
遞歸：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> v;
void AddToList(ListNode* l)
{
if(l==NULL)
{
return;
}
else
AddToList(l->next);
v.push_back(l->val);
}
vector<int> printListReversingly(ListNode* head) {
AddToList(head);
return v;
}
};
類函數(shù)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
vector<int> printListReversingly(ListNode* head) {
vector<int> result;
while(head!=NULL)
{
result.push_back(head->val);
head=head->next;
}
return vector<int>(result.rbegin(),result.rend());
}
};
vector.rbegin 和rend 相當(dāng)于begin 和End 的翻轉(zhuǎn)
輸入一棵二叉樹(shù)前序遍歷和中序遍歷的結(jié)果，請(qǐng)重建該二叉樹(shù)。
注意:
二叉樹(shù)中每個(gè)節(jié)點(diǎn)的值都互不相同；
輸入的前序遍歷和中序遍歷一定合法；
樣例
給定：
前序遍歷是：[3, 9, 20, 15, 7]
中序遍歷是：[9, 3, 15, 20, 7]
返回：[3, 9, 20, null, null, 15, 7, null, null, null, null]
返回的二叉樹(shù)如下所示：
題解：
首先我們來(lái)看一下先序遍歷和中序遍歷的遍歷規(guī)則
先序遍歷：
1：根節(jié)點(diǎn)->左子樹(shù)->右子樹(shù)
2：先序遍歷的結(jié)果，第0個(gè)元素是根節(jié)點(diǎn)
3：根節(jié)點(diǎn)->所有左子樹(shù)->所有右子樹(shù)，子數(shù)內(nèi)所有的值是連續(xù)的
例如 實(shí)例中的先序遍歷結(jié)果
[3(根節(jié)點(diǎn)) ,9(左子樹(shù)), 20,15,7(右子樹(shù))]
中序遍歷:
1：左子樹(shù)->根節(jié)點(diǎn)->右子樹(shù)
2：根節(jié)點(diǎn)的左邊必然都是左子樹(shù)，根節(jié)點(diǎn)的右邊必然都是右子樹(shù)
然后通過(guò)以上這些原理，結(jié)合遞歸的思想
這是開(kāi)始時(shí)的狀況
按照上面的性質(zhì)，前序遍歷的首個(gè)元素 為根節(jié)點(diǎn) 也就是3 記為r0
r如圖，我們可以得出3 是根節(jié)點(diǎn)，那么在中序遍歷中找到3（因?yàn)轭}目規(guī)定數(shù)字不會(huì)重復(fù)出現(xiàn)）所以3左側(cè)的所有成員就是此節(jié)點(diǎn)下所有左子樹(shù)的元素，右邊的成員是3所有右子樹(shù)的元素
此時(shí) 我們把左子樹(shù)單獨(dú)拿出來(lái)看 其中只有元素9，說(shuō)明9下面沒(méi)有其他節(jié)點(diǎn)，此次結(jié)束。 將9記記為l0,并且返回此節(jié)點(diǎn)
同理，單獨(dú)拿出右子樹(shù)來(lái)看：
20位根節(jié)點(diǎn) 基座r0 15 和7 分別是左右子樹(shù)的所有元素，切都沒(méi)有子節(jié)點(diǎn) 所以分別將15 7記為r0l1,r0r1 此時(shí)所有均已便利完畢，將r0l1和r0r1設(shè)為r1的左右節(jié)點(diǎn)
再將l0 r0設(shè)為左右節(jié)點(diǎn)
推導(dǎo)過(guò)程完畢，下面上具體代碼
/*
* 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:
vector<int> preOrder,inOrder;
map<int,int> hash_map;
TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
preOrder = preorder;
inOrder = inorder;
for(int i=0;i<inOrder.size();i++)
hash_map[inOrder[i]]=i;
return dfs(0,preOrder.size()-1,0,inOrder.size()-1);
}
TreeNode* dfs(int preL,int preR,int inL,int inR)
{
if(preL>preR) return nullptr;
int rootPos=hash_map[preOrder[preL]];
TreeNode* root = new TreeNode(preOrder[preL]);
TreeNode* left=dfs(preL+1,preL+rootPos-inL,inL,rootPos-1);
TreeNode* right=dfs(preL+rootPos-inL+1,preR,rootPos+1,inR);
root->left=left;
root->right=right;
return root;
}
};
具體流程位
1：首先看當(dāng)前集合vec的元素?cái)?shù)量是否為0，如果是，則返回nullptr 說(shuō)明
2：取到當(dāng)前樹(shù)的根節(jié)點(diǎn)（前序遍歷集合中的首個(gè)元素）并找到該元素在中序遍歷中的下標(biāo)，rootPos，則 下標(biāo)在區(qū)間[0，rootPos-1]為左子樹(shù)，[rootPos+1,vec.size()-1]為右子樹(shù)
3：講第二部獲得的左子樹(shù)和右子樹(shù)繼續(xù)進(jìn)行上述兩部操作
4：用遞歸的思想先從左右子樹(shù)開(kāi)始創(chuàng)建，最后添加到根節(jié)點(diǎn)
重點(diǎn)在在于函數(shù)dfs
在dfs的四個(gè)參數(shù)分別代表著 當(dāng)前進(jìn)行操作樹(shù) 前序遍歷的起始位置，結(jié)束為止 中序遍歷的起始位置，結(jié)束位置
難點(diǎn)是這兩行 里面的參數(shù)計(jì)算的實(shí)際意義
TreeNode* left=dfs(preL+1,preL+rootPos-inL,inL,rootPos-1) TreeNode* right=dfs(preL+rootPos-inL+1,preR,rootPos+1,inR);
這里我們使用具體例子來(lái)講解，求的是被紅色圈中的子樹(shù)這一步的dfs
按照?qǐng)D中左子樹(shù)的結(jié)果，preL 5 preR 5 inL 4 inR 4 rootPos 4
可得出下一次 left： preL 6 preR 5 preL<preR 說(shuō)明無(wú)任何子樹(shù)返回 nullptr
同理right 也為nullPtr 所以有 if(preL>preR) return nullptr
這道題到此結(jié)束，刷題路上第一道碰到的第一道話費(fèi)時(shí)間這么久的題 如果大家有什么問(wèn)題建議自己跑一遍邏輯推演一下
19. 二叉樹(shù)的下一個(gè)節(jié)點(diǎn)
給定一棵二叉樹(shù)的其中一個(gè)節(jié)點(diǎn)，請(qǐng)找出中序遍歷序列的下一個(gè)節(jié)點(diǎn)。
注意：
如果給定的節(jié)點(diǎn)是中序遍歷序列的最后一個(gè)，則返回空節(jié)點(diǎn);
二叉樹(shù)一定不為空，且給定的節(jié)點(diǎn)一定不是空節(jié)點(diǎn)；
樣例
假定二叉樹(shù)是：[2, 1, 3, null, null, null, null]， 給出的是值等于2的節(jié)點(diǎn)。
則應(yīng)返回值等于3的節(jié)點(diǎn)。
解釋：該二叉樹(shù)的結(jié)構(gòu)如下，2的后繼節(jié)點(diǎn)是3。
2
/ \
1 3
這里我們先了解一下中序遍歷的性質(zhì)
如上圖的二叉樹(shù)，中序遍歷結(jié)果相當(dāng)于各個(gè)元素X周坐標(biāo)不變，Y周坐標(biāo)統(tǒng)一之后的排序，如圖
我們可以從中發(fā)現(xiàn)兩個(gè)性質(zhì)
1：如果當(dāng)前節(jié)點(diǎn)有右孩子，那么當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為該節(jié)點(diǎn)的右孩子 的最左節(jié)點(diǎn)（遞歸查找是否有左孩子）如F 的下一個(gè)節(jié)點(diǎn)為H
2：如果沒(méi)有，那么就往上找，找到 p=p->father知道沒(méi)有父節(jié)點(diǎn)或者p->father->left==p
例如D 的下一個(gè)節(jié)點(diǎn)為F G的沒(méi)有下一個(gè)節(jié)點(diǎn)最后查找結(jié)果p=F，F(xiàn)沒(méi)有父節(jié)點(diǎn)father為null
上代碼
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode *father;
* TreeNode(int x) : val(x), left(NULL), right(NULL), father(NULL) {}
* };
*/
class Solution {
public:
TreeNode* inorderSuccessor(TreeNode* p)
{
if(p->right)
{
p=p->right;
while(p->left)
p=p->left;
return p;
}
while(p->father&&p->father->right==p)
p=p->father;
return p->father;
}
};
20. 用兩個(gè)棧實(shí)現(xiàn)隊(duì)列
這道題，，簡(jiǎn)單粗暴直接上代碼就好
class MyQueue {
public:
stack<int> sta,cache;
/** Initialize your data structure here. */
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
sta.push(x);
}
void copy(stack<int> &a,stack<int> &b)
{
while(a.size())
{
b.push(a.top());
a.pop();
}
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
copy(sta,cache);
int num=cache.top();
cache.pop();
copy(cache,sta);
return num;
}
/** Get the front element. */
int peek() {
copy(sta,cache);
int num=cache.top();
copy(cache,sta);
return num;
}
/** Returns whether the queue is empty. */
bool empty() {
return sta.empty();
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* bool param_4 = obj.empty();
*/
21. 斐波那契數(shù)列
輸入一個(gè)整數(shù) n ，求斐波那契數(shù)列的第 n 項(xiàng)。
假定從0開(kāi)始，第0項(xiàng)為0。(n<=39)
樣例
輸入整數(shù) n=5
返回 5
int Fibonacci(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
else
return Fibonacci(n-1)+Fibonacci(n-2);
}
很經(jīng)典的一道遞歸題 代碼比較簡(jiǎn)單但是。。。這只是性能最差的一種，如果是面試的話并不會(huì)出彩
具體分析：
在計(jì)算 f(n-1) 和f(n-2)的過(guò)程中會(huì)有大量已經(jīng)經(jīng)過(guò)計(jì)算的結(jié)果再次計(jì)算，所以將已經(jīng)計(jì)算過(guò)得結(jié)果填表
下面的是手寫(xiě)偽代碼 可能通不過(guò)主要看思路
map<int,int>hash_map;
int Fibonacci(int n) {
if(n==0)
return 0;
else if(n==1)
return 1;
if(hash_map[n])
return hash_map[n];
hash_map[n] = Fibonacci(n-1)+Fibonacci(n-2);
return hash_map[n];
}
但后來(lái)看大佬講解發(fā)現(xiàn)大佬還有一種方法。。相對(duì)簡(jiǎn)潔
還是偽代碼，大概看思路
時(shí)間復(fù)雜度和上面的一樣是O(n)但沒(méi)有開(kāi)辟額外空間而且使用非遞歸算法不用擔(dān)心爆棧的問(wèn)題
int f(int n)
{
int a=0,b=1;
while(n--)
{
int c=a+b;
a=b;
b=c;
}
return a;
}
然后放下大佬的擴(kuò)展閱讀
求解斐波那契數(shù)列的若干方法
斐波那契數(shù)列雖然比較簡(jiǎn)單，但在此基礎(chǔ)上能擴(kuò)展出很多變形和相關(guān)
把一個(gè)數(shù)組最開(kāi)始的若干個(gè)元素搬到數(shù)組的末尾，我們稱之為數(shù)組的旋轉(zhuǎn)。
輸入一個(gè)升序的數(shù)組的一個(gè)旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素。
例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個(gè)旋轉(zhuǎn)，該數(shù)組的最小值為1。
數(shù)組可能包含重復(fù)項(xiàng)。
注意：數(shù)組內(nèi)所含元素非負(fù)，若數(shù)組大小為0，請(qǐng)返回-1。
樣例
輸入：nums=[2,2,2,0,1]
輸出：0
先上自己最傻的遍歷算法。。。從頭到尾
int findMin(vector<int>& nums) {
int res=-1;
for(int i=0;i<nums.size();i++)
if(nums[i]<res||res==-1)
res=nums[i];
return res;
}
時(shí)間復(fù)雜度是O(n)的算法
然后我們繼續(xù)分析一下這道題目 先不考慮題目中的連續(xù)問(wèn)題
題目中在旋轉(zhuǎn)之前，數(shù)組a0是單調(diào)遞增的，旋轉(zhuǎn)之后，我們可以把它看做兩個(gè)新的數(shù)組min和max
也就是旋轉(zhuǎn)后 數(shù)組變成了 [max,min] 那么尋找最小元素就相當(dāng)于是尋找min[0]元素
而我們?cè)倏?strong>max和min的性質(zhì)
由于原數(shù)組是單調(diào)遞增的，所以如果在沒(méi)有重復(fù)元素的情況下，max中的任意元素必然大于min中的任意元素
如果考慮到存在重復(fù)元素的情況下，就會(huì)有
如果max[0]==min[size()-1]那么我們從后往前去掉min中所有與max[0]相等的元素，那么就會(huì)有和上面相同的結(jié)論: max中的任意元素必然大于min中的任意元素
這時(shí)候我們就可以用二分來(lái)進(jìn)行考慮
先上代碼
int findMin(vector<int>& nums) {
int n=nums.size()-1;
if(n<0)
return -1;
while(nums[n]==nums[0]&&n>0)
n--;
if(nums[n]>=nums[0])
return nums[0];
int l=0,r=n;
while(l<r)
{
int mid=(l+r)>>1;
if(nums[mid] < nums[0])
r = mid;
else
l = mid + 1;
}
return nums[r];
}
首先 排除沒(méi)有元素的情況
其次，max[0]==min[size()-1] 執(zhí)行這一步操作
然后一步是對(duì)特殊情況 如果[max,min]的min元素?cái)?shù)量為0，那么就是整個(gè)就是單調(diào)遞增的，直接返回nums[0]
這種情況下，雖然時(shí)間負(fù)責(zé)度還是O(n)但是可以保證，可以保證除去最壞情況其他狀況都要比上面的時(shí)間負(fù)責(zé)度更低
矩陣中的路徑
請(qǐng)?jiān)O(shè)計(jì)一個(gè)函數(shù)，用來(lái)判斷在一個(gè)矩陣中是否存在一條包含某字符串所有字符的路徑。
路徑可以從矩陣中的任意一個(gè)格子開(kāi)始，每一步可以在矩陣中向左，向右，向上，向下移動(dòng)一個(gè)格子。
如果一條路徑經(jīng)過(guò)了矩陣中的某一個(gè)格子，則之后不能再次進(jìn)入這個(gè)格子。
注意：
輸入的路徑不為空；
所有出現(xiàn)的字符均為大寫(xiě)英文字母；
樣例
matrix=
[
["A","B","C","E"],
["S","F","C","S"],
["A","D","E","E"]
]str="BCCE" , return "true"
str="ASAE" , return "false"
這道題目相相對(duì)簡(jiǎn)單，直接暴力搜索所有的路徑，代碼也相對(duì)比較簡(jiǎn)單，直接遞歸搜索所有就OK注意的是要把已經(jīng)搜索過(guò)的路徑用一個(gè)里面沒(méi)有出現(xiàn)過(guò)的符號(hào)代替防止搜索時(shí)再次重復(fù)搜索 失敗是將路徑擦除
上代碼
class Solution {
public:
bool hasPath(vector<vector<char>>& matrix, string str) {
for(int i=0;i<matrix.size();i++)
for(int j=0;j<matrix[i].size();j++)
if(dfs(matrix,str,0,i,j))
return true;
return false;
}
bool dfs(vector<vector<char>> mat,string str,int u,int x,int y)
{
char c=mat[x][y];
if(c!=str[u]) return false;
if(u==str.size()-1) return true;
mat[x][y]='*';
int dx[4]={0,1,0,-1};int dy[4]={1,0,-1,0};
for(int i=0;i<4;i++)
{
int a=dx[i]+x,b=dy[i]+y;
if(a>=0&&a<mat.size()&&b>=0&&b<mat[x].size())
if(dfs(mat,str,u+1,a,b))
return true;
}
mat[x][y]=c;
return false;
}
};
到此為止劍指offer第一周的題目就刷完了，11到題花了大概三天時(shí)間吧，難度也不是很大，和群里的大佬們差距還是太大。希望有朝一日能夠紅黑樹(shù)快速冪各種數(shù)據(jù)結(jié)構(gòu)算法談笑風(fēng)生
也是自己第一次開(kāi)始認(rèn)真刷題，希望能堅(jiān)持下去。畢業(yè)工作一年深深感受到自己基礎(chǔ)太差，加油吧。
2019/2/28
