刪除鏈表中重復(fù)的結(jié)點(diǎn)
我的：
//方法1：
ListNode* deleteDuplication(ListNode* pHead)
{
ListNode* rHead=new ListNode(0);
ListNode* rtemp=rHead;
ListNode* temp=pHead;
if(pHead==NULL||pHead->next==NULL) return pHead;
int value = NULL;
while(temp->next!=NULL){
if(temp->val == temp->next->val){
value = temp->val;
}else{
if(value==NULL||temp->val != value){
rtemp->next = temp;
rtemp = rtemp->next;
}
}
temp = temp->next;
}
if(temp->val!=value){
rtemp->next = temp;
rtemp = rtemp->next;
}
rtemp->next = NULL;
return rHead->next;
}
//方法2：遞歸
ListNode* deleteDuplication(ListNode* pHead)
{
if (pHead==NULL)
return NULL;
if (pHead!=NULL && pHead->next==NULL)
return pHead;
ListNode* current;
if ( pHead->next->val==pHead->val){
current=pHead->next->next;
while (current != NULL && current->val==pHead->val)
current=current->next;
return deleteDuplication(current);
}
else {
current=pHead->next;
pHead->next=deleteDuplication(current);
return pHead;
}
}
//方法3：非遞歸的代碼：
1. 首先添加一個(gè)頭節(jié)點(diǎn)，以方便碰到第一個(gè)，第二個(gè)節(jié)點(diǎn)就相同的情況
2.設(shè)置 pre ，last 指針， pre指針指向當(dāng)前確定不重復(fù)的那個(gè)節(jié)點(diǎn)，而last指針相當(dāng)于工作指針，一直往后面搜索。
if (pHead==null || pHead.next==null){return pHead;}
ListNode Head = new ListNode(0);
Head.next = pHead;
ListNode pre = Head;
ListNode last = Head.next;
while (last!=null){
if(last.next!=null && last.val == last.next.val){
// 找到最后的一個(gè)相同節(jié)點(diǎn)
while (last.next!=null && last.val == last.next.val){
last = last.next;
}
pre.next = last.next;
last = last.next;
}else{
pre = pre.next;
last = last.next;
}
}
return Head.next;
//方法4：
ListNode* deleteDuplication(ListNode* pHead)
{
if(pHead==NULL||pHead->next==NULL) return pHead;
else
{
//新建一個(gè)節(jié)點(diǎn)，防止頭結(jié)點(diǎn)要被刪除
ListNode* newHead=new ListNode(-1);
newHead->next=pHead;
ListNode* pre=newHead;
ListNode* p=pHead;
ListNode* next=NULL;
while(p!=NULL && p->next!=NULL)
{
next=p->next;
if(p->val==next->val)//如果當(dāng)前節(jié)點(diǎn)的值和下一個(gè)節(jié)點(diǎn)的值相等
{
while(next!=NULL && next->val==p->val)//向后重復(fù)查找
next=next->next;
pre->next=next;//指針賦值，就相當(dāng)于刪除
p=next;
}
else//如果當(dāng)前節(jié)點(diǎn)和下一個(gè)節(jié)點(diǎn)值不等，則向后移動(dòng)一位
{
pre=p;
p=p->next;
}
}
return newHead->next;//返回頭結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
}
}
劍指：方法3,4一樣
二叉樹的下一個(gè)結(jié)點(diǎn)
我的：
//方法1：
int flag = false;
TreeLinkNode* result=NULL;
void zhong(TreeLinkNode* root, TreeLinkNode* pNode){
if(root==NULL) return;
if(root->left!=NULL) zhong(root->left,pNode);
if(flag){
result = root;
flag = false;
return ;
}
if(root == pNode){
flag = true;
}
if(root->right!=NULL) zhong(root->right,pNode);
}
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
TreeLinkNode* root = pNode;
while(root->next!=NULL){
root = root->next;
}
zhong(root,pNode);
return result;
}
//方法2：
//分析二叉樹的下一個(gè)節(jié)點(diǎn)，一共有以下情況：
//1.二叉樹為空，則返回空；
//2.節(jié)點(diǎn)右孩子存在，則設(shè)置一個(gè)指針從該節(jié)點(diǎn)的右孩子出發(fā)，一直沿著指向左子結(jié)點(diǎn)的指針找到的葉子節(jié)點(diǎn)即為下一個(gè)節(jié)點(diǎn)；
//3.節(jié)點(diǎn)不是根節(jié)點(diǎn)。如果該節(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子，則返回父節(jié)點(diǎn)；否則繼續(xù)向上遍歷其父節(jié)點(diǎn)的父節(jié)點(diǎn)，重復(fù)之前的判斷，返回結(jié)果。
classSolution{
public:
TreeLinkNode* GetNext(TreeLinkNode* pNode)
{
if (pNode == NULL)
returnNULL;
if (pNode->right != NULL)
{
pNode = pNode->right;
while (pNode->left != NULL)
pNode = pNode->left;
returnpNode;
}
while (pNode->next != NULL)
{
TreeLinkNode *proot = pNode->next;
if (proot->left == pNode)
returnproot;
pNode = pNode->next;
}
returnNULL;
}
};
PS：方法2：
思路：首先知道中序遍歷的規(guī)則是：左根右，然后作圖
image
結(jié)合圖，我們可發(fā)現(xiàn)分成兩大類：1、有右子樹的，那么下個(gè)結(jié)點(diǎn)就是右子樹最左邊的點(diǎn)；（eg：D，B，E，A，C，G） 2、沒(méi)有右子樹的，也可以分成兩類，a)是父節(jié)點(diǎn)左孩子（eg：N，I，L） ，那么父節(jié)點(diǎn)就是下一個(gè)節(jié)點(diǎn) ； b)是父節(jié)點(diǎn)的右孩子（eg：H，J，K，M）找他的父節(jié)點(diǎn)的父節(jié)點(diǎn)的父節(jié)點(diǎn)...直到當(dāng)前結(jié)點(diǎn)是其父節(jié)點(diǎn)的左孩子位置。如果沒(méi)有eg：M，那么他就是尾節(jié)點(diǎn)。
劍指：方法2
對(duì)稱的二叉樹
我的：
//方法1：
bool judge(TreeNode* lRoot, TreeNode* rRoot){
if(lRoot==NULL&&rRoot==NULL) return true;
if(lRoot==NULL&&rRoot!=NULL) return false;
if(lRoot!=NULL&&rRoot==NULL) return false;
if(lRoot->val != rRoot->val) return false;
return judge(lRoot->left,rRoot->right)&&judge(lRoot->right,rRoot->left);
}
bool isSymmetrical(TreeNode* pRoot)
{
if(pRoot==NULL) return true;
return judge(pRoot->left,pRoot->right);
}
//方法2：
代碼很簡(jiǎn)單，關(guān)鍵還是知道怎么樣才能判斷一個(gè)
二叉樹是否對(duì)稱，只要采用前序、中序、后序、層次遍歷等任何一種遍歷方法，分為先左后右和先
右后左兩種方法，只要兩次結(jié)果相等就說(shuō)明這棵樹是一顆對(duì)稱二叉樹。
迭代版本
class Solution {
public:
bool isSymmetric(TreeNode* root) {
if(root==NULL) return true;
queue<TreeNode*> q1,q2;
TreeNode *left,*right;
q1.push(root->left);
q2.push(root->right);
while(!q1.empty() and !q2.empty())
{
left = q1.front();
q1.pop();
right = q2.front();
q2.pop();
//兩邊都是空
if(NULL==left && NULL==right)
continue;
//只有一邊是空
if(NULL==left||NULL==right)
return false;
if (left->val != right->val)
return false;
q1.push(left->left);
q1.push(left->right);
q2.push(right->right);
q2.push(right->left);
}
return true;
}
};
//方法3：
/*
* DFS使用stack來(lái)保存成對(duì)的節(jié)點(diǎn)
* 1.出棧的時(shí)候也是成對(duì)成對(duì)的 ，
1.若都為空，繼續(xù)；
2.一個(gè)為空，返回false;
3.不為空，比較當(dāng)前值，值不等，返回false；
* 2.確定入棧順序，每次入棧都是成對(duì)成對(duì)的，如left.left， right.right ;left.rigth,right.left
*/
boolean isSymmetricalDFS(TreeNode pRoot)
{
if(pRoot == null) return true;
Stack<TreeNode> s = new Stack<>();
s.push(pRoot.left);
s.push(pRoot.right);
while(!s.empty()) {
TreeNode right = s.pop();//成對(duì)取出
TreeNode left = s.pop();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成對(duì)插入
s.push(left.left);
s.push(right.right);
s.push(left.right);
s.push(right.left);
}
return true;
}
/*
* BFS使用Queue來(lái)保存成對(duì)的節(jié)點(diǎn)，代碼和上面極其相似
* 1.出隊(duì)的時(shí)候也是成對(duì)成對(duì)的
1.若都為空，繼續(xù)；
2.一個(gè)為空，返回false;
3.不為空，比較當(dāng)前值，值不等，返回false；
* 2.確定入隊(duì)順序，每次入隊(duì)都是成對(duì)成對(duì)的，如left.left， right.right ;left.rigth,right.left
*/
boolean isSymmetricalBFS(TreeNode pRoot)
{
if(pRoot == null) return true;
Queue<TreeNode> s = new LinkedList<>();
s.offer(pRoot.left);
s.offer(pRoot.right);
while(!s.isEmpty()) {
TreeNode right = s.poll();//成對(duì)取出
TreeNode left = s.poll();
if(left == null && right == null) continue;
if(left == null || right == null) return false;
if(left.val != right.val) return false;
//成對(duì)插入
s.offer(left.left);
s.offer(right.right);
s.offer(left.right);
s.offer(right.left);
}
return true;
}
劍指：方法1
按之字形順序打印二叉樹
我的：
//方法1：先遍歷后打印
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > result;
if(pRoot==NULL) return result;
queue<TreeNode*> nodes;
nodes.push(pRoot);
bool flag = true;
while(!nodes.empty()){
vector<int> temp;
int le = nodes.size();
for(int i = 0;i<le;i++){
TreeNode* node = nodes.front();
nodes.pop();
temp.push_back(node->val);
if(node->left!=NULL) nodes.push(node->left);
if(node->right!=NULL) nodes.push(node->right);
}
result.push_back(temp);
}
for(int i = 0;i<result.size();i++){
if(i%2==1) reverse(result[i].begin(),result[i].end());
}
return result;
}
//方法2：stack來(lái)保存逆序
vector<vector<int> > Print(TreeNode* pRoot) {
bool flag = true;
queue<TreeNode> le;
vector<vector<int> > result;
if(pRoot==NULL) return result;
le.push(*pRoot);
while(!le.empty()){
vector<int> r;
stack<int> ri;
for(int i =0,n=le.size();i<n;i++){
TreeNode temp = le.front();
if(flag){
r.push_back(temp.val);
}else{
ri.push(temp.val);
}
le.pop();
if(temp.left!=NULL) le.push(*temp.left);
if(temp.right!=NULL) le.push(*temp.right);
}
while(!ri.empty()){
TreeNode temp = ri.top();
r.push_back(temp.val);
ri.pop();
}
result.push_back(r);
flag = !flag;
}
return result;
}
//方法3：
public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
int layer = 1;
//s1存奇數(shù)層節(jié)點(diǎn)
Stack<TreeNode> s1 = new Stack<TreeNode>();
s1.push(pRoot);
//s2存偶數(shù)層節(jié)點(diǎn)
Stack<TreeNode> s2 = new Stack<TreeNode>();
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
while (!s1.empty() || !s2.empty()) {
if (layer%2 != 0) {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s1.empty()) {
TreeNode node = s1.pop();
if(node != null) {
temp.add(node.val);
System.out.print(node.val + " ");
s2.push(node.left);
s2.push(node.right);
}
}
if (!temp.isEmpty()) {
list.add(temp);
layer++;
System.out.println();
}
} else {
ArrayList<Integer> temp = new ArrayList<Integer>();
while (!s2.empty()) {
TreeNode node = s2.pop();
if(node != null) {
temp.add(node.val);
System.out.print(node.val + " ");
s1.push(node.right);
s1.push(node.left);
}
}
if (!temp.isEmpty()) {
list.add(temp);
layer++;
System.out.println();
}
}
}
return list;
}
劍指：方法3
把二叉樹打印成多行
我的：
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > result;
if(pRoot==NULL) return result;
queue<TreeNode*> nodes;
nodes.push(pRoot);
while(!nodes.empty()){
vector<int> temp;
int le = nodes.size();
for(int i = 0;i<le;i++){
TreeNode* node = nodes.front();
nodes.pop();
temp.push_back(node->val);
if(node->left!=NULL) nodes.push(node->left);
if(node->right!=NULL) nodes.push(node->right);
}
result.push_back(temp);
}
return result;
}
//方法2：遞歸BFS
//用遞歸做的
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> list = new ArrayList<>();
depth(pRoot, 1, list);
return list;
}
private void depth(TreeNode root, int depth, ArrayList<ArrayList<Integer>> list) {
if(root == null) return;
if(depth > list.size())
list.add(new ArrayList<Integer>());
list.get(depth -1).add(root.val);
depth(root.left, depth + 1, list);
depth(root.right, depth + 1, list);
}
}
劍指：一樣
序列化二叉樹
我的：不會(huì)
//方法1：
string result="";
void xian(TreeNode *root){
if(root==NULL) result=result+"#!";
else{
char temp = root->val+'0';
result=result+to_string(root->val)+'!';
xian(root->left);
xian(root->right);
}
}
char* Serialize(TreeNode *root) {
if(root==NULL) return NULL;
xian(root);
char *ret = new char[result.length() + 1];
int i;
for(i = 0; i < result.length(); i++){
ret[i] = result[i];
}
ret[i] = '\0';
return ret;
// strcpy(ret, result.c_str());
}
TreeNode* Deserialize(char *&str) {
if(str == NULL) return NULL;
TreeNode* node = NULL;
if(*str!='#'){
int temp = 0;
while(*str!='!'){
temp = 10*temp+int(*str-'0');
str++;
}
str++;
node = new TreeNode(temp);
node->left = Deserialize(str);
node->right = Deserialize(str);
}else str+=2;
return node;
}
PS：
序列化二叉樹：把一棵二叉樹按照某種遍歷方式的結(jié)果以某種格式保存為字符串。需要注意的是，序列化二叉樹的過(guò)程中，如果遇到空節(jié)點(diǎn)，需要以某種符號(hào)（這里用#）表示。以下圖二叉樹為例，序列化二叉樹時(shí)，需要將空節(jié)點(diǎn)也存入字符串中。
反序列化二叉樹：根據(jù)某種遍歷順序得到的序列化字符串，重構(gòu)二叉樹。
劍指：
一樣
二叉搜索樹的第k個(gè)結(jié)點(diǎn)
我的：
//方法1：
int flag=0;
TreeNode* result = NULL;
void zhong(TreeNode *root, int k ){
if(root!=NULL);
{
if(root->left!=NULL)zhong(root->left, k);
if(++flag==k){
result = root;
}
if(root->right!=NULL)zhong(root->right,k);
}
}
TreeNode* KthNode(TreeNode* pRoot, int k)
{
if(pRoot== NULL) return NULL;
zhong(pRoot,k);
return result;
}
PS：中序遍歷，非遞歸
void zhong(TreeNode *root){
stack<TreeNode*> temp;
while (root != NULL || ! temp.empty()) {
while (root != NULL) {
temp.push(root);
root = root->left;
}
root = temp.top();
temp.pop();
cout<<root->val<<endl;
root = root->right;
}
}
劍指：遞歸中序
數(shù)據(jù)流中的中位數(shù)
我的：
//方法1：
priority_queue<int, vector<int>, less<int> > large;
priority_queue<int, vector<int>, greater<int> > small;
int count = 0;
void Insert(int num)
{
count++;
large.push(num);
int lsize = large.size();
int ssize = small.size();
if(lsize-ssize>1){
int temp = large.top();
large.pop();
small.push(temp);
}
if(!large.empty()&&!small.empty()&&large.top()>small.top()){
int temp = large.top();
large.pop();
int temp2 = small.top();
small.pop();
large.push(temp2);
small.push(temp);
}
}
double GetMedian()
{
if(!large.empty()){
if(count%2==0){
return (large.top()+small.top())/2.0;
}else return large.top();
}
return NULL;
}
//方法2：
劍指：一樣
class Solution {
private:
vector<int> min;
vector<int> max;
public:
void Insert(int num)
{
if(((min.size()+max.size())&1)==0)//偶數(shù)時(shí) ，放入最小堆
{
if(max.size()>0 && num<max[0])
{
// push_heap (_First, _Last),要先在容器中加入數(shù)據(jù)，再調(diào)用push_heap ()
max.push_back(num);//先將元素壓入容器
push_heap(max.begin(),max.end(),less<int>());//調(diào)整最大堆
num=max[0];//取出最大堆的最大值
//pop_heap(_First, _Last)，要先調(diào)用pop_heap()再在容器中刪除數(shù)據(jù)
pop_heap(max.begin(),max.end(),less<int>());//刪除最大堆的最大值
max.pop_back(); //在容器中刪除
}
min.push_back(num);//壓入最小堆
push_heap(min.begin(),min.end(),greater<int>());//調(diào)整最小堆
}
else//奇數(shù)時(shí)候，放入最大堆
{
if(min.size()>0 && num>min[0])
{
// push_heap (_First, _Last),要先在容器中加入數(shù)據(jù)，再調(diào)用push_heap ()
min.push_back(num);//先壓入最小堆
push_heap(min.begin(),min.end(),greater<int>());//調(diào)整最小堆
num=min[0];//得到最小堆的最小值（堆頂）
//pop_heap(_First, _Last)，要先調(diào)用pop_heap()再在容器中刪除數(shù)據(jù)
pop_heap(min.begin(),min.end(),greater<int>());//刪除最小堆的最大值
min.pop_back(); //在容器中刪除
}
max.push_back(num);//壓入數(shù)字
push_heap(max.begin(),max.end(),less<int>());//調(diào)整最大堆
}
}
/*獲取中位數(shù)*/
double GetMedian()
{
int si敏感詞.size()+max.size();
if(size<=0) //沒(méi)有元素，拋出異常
return 0;//throw exception("No numbers are available");
if((size&1)==0)//偶數(shù)時(shí)，去平均
return ((double)(max[0]+min[0])/2);
else//奇數(shù)，去最小堆，因?yàn)樽钚《褦?shù)據(jù)保持和最大堆一樣多，或者比最大堆多1個(gè)
return min[0];
}
};
滑動(dòng)窗口的最大值
我的：
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
int le = num.size();
int flag = -1;
int ma = INT_MIN;
vector<int> result;
if(size==0) return result;
for(int i = 0;i<le-size+1;i++){
if(flag<i){
flag = i;
ma = num[i];
for(int j = i+1;j<i+size;j++){
if(num[j]>ma){
flag = j;
ma = num[j];
}
}
}else{
if(num[i+size-1]>num[flag]){
flag = i+size-1;
ma = num[flag];
}
}
result.push_back(ma);
}
return result;
}
//方法2：雙端隊(duì)列
//引用馬客（Mark）的解題思路，馬客沒(méi)加注釋，我用自己的理解加下注釋，希望對(duì)你們有用，
//如有錯(cuò)誤，見(jiàn)諒，我會(huì)及時(shí)修改。
//deque s中存儲(chǔ)的是num的下標(biāo)
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> res;
deque<int> s;
for(unsigned int i=0;i<num.size();++i){
while(s.size() && num[s.back()]<=num[i])//從后面依次彈出隊(duì)列中比當(dāng)前num值小的元素，同時(shí)也能保證隊(duì)列首元素為當(dāng)前窗口最大值下標(biāo)
s.pop_back();
while(s.size() && i-s.front()+1>size)//當(dāng)當(dāng)前窗口移出隊(duì)首元素所在的位置，即隊(duì)首元素坐標(biāo)對(duì)應(yīng)的num不在窗口中，需要彈出
s.pop_front();
s.push_back(i);//把每次滑動(dòng)的num下標(biāo)加入隊(duì)列
if(size&&i+1>=size)//當(dāng)滑動(dòng)窗口首地址i大于等于size時(shí)才開始寫入窗口最大值
res.push_back(num[s.front()]);
}
return res;
}
//方法3：雙端
//時(shí)間復(fù)雜度o（n），空間復(fù)雜度為o（n）
/*思路就是采用雙端隊(duì)列，隊(duì)列中的頭節(jié)點(diǎn)保存的數(shù)據(jù)比后面的要大。
比如當(dāng)前假如的數(shù)據(jù)比隊(duì)尾的數(shù)字大，說(shuō)明當(dāng)前這個(gè)數(shù)字最起碼在從現(xiàn)在起到后面的過(guò)程中可能是最大值
，而之前隊(duì)尾的數(shù)字不可能最大了，所以要?jiǎng)h除隊(duì)尾元素。
此外，還要判斷隊(duì)頭的元素是否超過(guò)size長(zhǎng)度，由于存儲(chǔ)的是下標(biāo)，所以可以計(jì)算得到；
特別說(shuō)明，我們?cè)陔p端隊(duì)列中保存的數(shù)字是傳入的向量的下標(biāo)；
*/
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
vector<int> vec;
if(num.size()<=0 || num.size()<size ||size<=0) return vec;//處理特殊情況
deque<int> dq;
//處理前size個(gè)數(shù)據(jù)，因?yàn)檫@個(gè)時(shí)候不需要輸出最大值；
for(unsigned int i=0;i<size;i++)
{
//假如當(dāng)前的元素比隊(duì)列隊(duì)尾的元素大，說(shuō)明之前加入的這些元素不可能是最大值了。因?yàn)楫?dāng)前的這個(gè)數(shù)字比之前加入隊(duì)列的更晚
while(!dq.empty()&&num[i]>=num[dq.back()])
dq.pop_back();//彈出比當(dāng)前小的元素下標(biāo)
dq.push_back(i);//隊(duì)尾壓入當(dāng)前下標(biāo)
}
//處理size往后的元素，這時(shí)候需要輸出滑動(dòng)窗口的最大值
for(unsigned int i=size;i<num.size();i++)
{
vec.push_back(num[dq.front()]);
while(!dq.empty()&&num[i]>=num[dq.back()])
dq.pop_back();
if(!dq.empty() && dq.front()<=(int)(i-size))//判斷隊(duì)頭的下標(biāo)是否超出size大小，如果超過(guò)，要?jiǎng)h除隊(duì)頭元素
dq.pop_front();//刪除隊(duì)頭元素
dq.push_back(i);//將當(dāng)前下標(biāo)壓入隊(duì)尾，因?yàn)榭赡茉谖磥?lái)是最大值
}
vec.push_back(num[dq.front()]);//最后還要壓入一次
return vec;
}
劍指：方法2，下標(biāo)，每次加入尾部，刪除小于尾部的，頭判斷是不是過(guò)期
矩陣中的路徑
我的：
//方法1：回溯
bool judge(char* matrix, int nrows, int ncols, int rows, int cols,char* str, vector<int>& flag){
if(*str=='\0') return true;
if(nrows<0||nrows>(rows-1)||ncols<0||ncols>(cols-1)||flag[nrows*cols+ncols]==1) return false;
if(matrix[nrows*cols+ncols] == *str){
flag[nrows*cols+ncols]=1;
bool result =
judge(matrix, nrows-1,ncols,rows,cols,str+1,flag)||
judge(matrix, nrows+1,ncols,rows,cols,str+1,flag)||
judge(matrix, nrows,ncols-1,rows,cols,str+1,flag)||
judge(matrix, nrows,ncols+1,rows,cols,str+1,flag);
flag[nrows*cols+ncols]=0;
return result;
}else return false;
}
bool hasPath(char* matrix, int rows, int cols, char* str)
{
if(*str=='\0'||*matrix=='\0') return false;
vector<int> flag(rows*cols, 0);
int count = 0 ;
while(*(matrix+count)!='\0'){
if(*str == *(matrix+count)){
if(judge(matrix, count/cols,count%cols,rows,cols,str,flag))
return true;
}
count++;
}
return false;
}
//方法2：
PS：幾種初始化，和傳入形式，達(dá)到修改原值：
int flag[] = new int[matrix.length]; int [] flag
bool *isOk=new bool[rows*cols](); bool *isOk,
vector<bool> used(strlen(matrix),false); vector<bool>& used
bool *flag=new bool[rows*cols]; bool* flag
bool *flag=new bool[rows*cols];
memset(flag,0,rows*cols);
bool* flag
還是沒(méi)搞明白為什么狀態(tài)要改回來(lái)，不然永久置1了？為什么我測(cè)試還是沒(méi)問(wèn)題。。。。我的測(cè)試有問(wèn)題：
用例:
"ABCEHJIGSFCSLOPQADEEMNOEADIDEJFMVCEIFGGS",5,8,"SGGFIECVAASABCEHJIGQEM"
可以看出有無(wú)恢復(fù)的區(qū)別
劍指：
class Solution {
public:
bool hasPath(char* matrix, int rows, int cols, char* str) {
bool res = 0;
bool *flag=new bool[rows*cols];
memset(flag,0,rows*cols);
for (int i = 0;i<rows;++i) {
for (int j = 0;j<cols;++j) {
//bool *flag = (bool *)calloc(rows*cols, 1);
res = dfs(matrix, rows, cols, i, j, flag, str);//1
if (res == true)
return res;
}
}
delete[] flag;
return res;
}
bool dfs(char* matrix, int rows, int cols, int i, int j, bool* flag, char* str) {
if (*str == '\0')
return true;
if(i<0||i>=rows||j<0||j>=cols)
return false;
if (*(flag+i*cols + j) == 1 || (*(flag+i*cols + j) == 0 && *(matrix + i*cols + j) != *str))
return false;
else {
*(flag+i*cols + j) = 1;
bool res=dfs(matrix, rows, cols, i, j - 1, flag, str + 1)//左
||dfs(matrix, rows, cols, i, j + 1, flag, str+1)//右
||dfs(matrix, rows, cols, i - 1, j, flag, str+1)//上
||dfs(matrix, rows, cols, i + 1, j, flag, str+1);//下
if(res==0)
*(flag+i*cols + j)=0;//這樣從1處開始進(jìn)入的DFS即使沒(méi)找到路徑，但是flag最后全部置為0
return res;
}
}
機(jī)器人的運(yùn)動(dòng)范圍
我的：
//方法1：
int mysum(int x, int y){
int sum = 0;
while(x!=0){
sum=sum+x%10;
x=x/10;
}
while(y!=0){
sum=sum+y%10;
y=y/10;
}
return sum;
}
void judge(int nrows, int ncols, int rows, int cols,int& count, int k, vector<int>& flag){
if(nrows<0||nrows>(rows-1)||ncols<0||ncols>(cols-1)||flag[nrows*cols+ncols]==1||mysum(nrows, ncols)>k) return ;
count++;
flag[nrows*cols+ncols]=1;
judge(nrows,ncols+1,rows,cols,count,k,flag);
judge(nrows,ncols-1,rows,cols,count,k,flag);
judge(nrows+1,ncols,rows,cols,count,k,flag);
judge(nrows-1,ncols,rows,cols,count,k,flag);
}
int movingCount(int threshold, int rows, int cols)
{
if(threshold<0||rows<0||cols<0) return 0;
int count = 0;
vector<int> flag(rows*cols,0);
judge(0, 0, rows, cols,count, threshold, flag);
return count;
}
//方法2：
劍指：
int movingCount(int threshold, int rows, int cols)
{
bool* flag=new bool[rows*cols];
for(int i=0;i<rows*cols;i++)
flag[i]=false;
int count=moving(threshold,rows,cols,0,0,flag);//從（0,0）坐標(biāo)開始訪問(wèn);
delete[] flag;
return count;
}
//計(jì)算最大移動(dòng)位置
int moving(int threshold,int rows,int cols,int i,int j,bool* flag)
{
int count=0;
if(check(threshold,rows,cols,i,j,flag))
{
flag[i*cols+j]=true;
//標(biāo)記訪問(wèn)過(guò)，這個(gè)標(biāo)志flag不需要回溯，因?yàn)橹灰辉L問(wèn)過(guò)即可。
//因?yàn)槿绻茉L問(wèn)，訪問(wèn)過(guò)會(huì)加1.不能訪問(wèn)，也會(huì)標(biāo)記下訪問(wèn)過(guò)。
count=1+moving(threshold,rows,cols,i-1,j,flag)
+moving(threshold,rows,cols,i,j-1,flag)
+moving(threshold,rows,cols,i+1,j,flag)
+moving(threshold,rows,cols,i,j+1,flag);
}
return count;
}
//檢查當(dāng)前位置是否可以訪問(wèn)
bool check(int threshold,int rows,int cols,int i,int j,bool* flag)
{
if(i>=0 && i<rows && j>=0 && j<cols
&& getSum(i)+getSum(j)<=threshold
&& flag[i*cols+j]==false)
return true;
return false;
}
//計(jì)算位置的數(shù)值
int getSum(int number)
{
int sum=0;
while(number>0)
{
sum+=number%10;
number/=10;
}
return sum;
}
