leetcode

DFS和去重

题目链接
本次题目收获如下：
1、从int到string的模板函数to_string()。
2、从string到int的方法stringstream对象。

stringstream stream;
stream<<string_value;
stream>>int_value;

3、在DFS搜索全排列的时候的去重方法：只要设定一个规则，保证在填第i个数的时候重复数字只会被填入一次即可。例如，我们可以选择对原输入字符串input进行排序，保证相同的数字都相邻，然后每次填入的数一定是在这个数所在重复数集合中从左往右第一个未被填过的数字，即如下判断条件：

if (i > 0 && nums[i] == nums[i - 1] && !vis[i - 1]) {
    continue;
}

这个判断保证了对于重复数的集合，一定是从左往右逐个填入的。
假设我们有三个重复数排完序后相邻，那么我们一定保证每次都是从左往右第一个未被填过的数字，即整个数组的状态其实是保证了(未填入，未填入，未填入)到(填入，未填入，未填入)到(填入，填入，填入)的过程，因此可以达到去重的目标。
4、一个字符串去掉一部分，substr函数。

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <sstream>
#include<algorithm>
#include<cmath>
#include<limits.h>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include<vector>
#include<string>
using namespace std;
class Solution {
public:
    void DFS(int step)
    {
        if (step == len)
        {
            stringstream stream;
            stream << now;
            stream >> res;
            if ((res&(-res)) == res)
            {
                flag = 1;
            }
            return;
        }
        for (int i = 0; i < len; i++)
        {
            if (i > 0 && input[i] == input[i - 1] && !vis[i - 1])
                continue;
            if (vis[i] == 0)
            {
                now = now + input[i];
                vis[i] = 1;
                DFS(++step);
                step--;
                vis[i] = 0;
                now = now.substr(0, step);
            }
        }
    }
    int flag = 0;
    int len, temp1, temp2;
    int res;
    int vis[20];
    string now;
    map<char, int>used;
    string input;
    bool reorderedPowerOf2(int n) {
        input = to_string(n);
        len = input.size();
        sort(input.begin(), input.end());
        for (int i = 0; i < len; i++)
        {
            if (input[i] != '0')
            {
                vis[i] = 1;
                now = now + input[i];
                DFS(1);
                vis[i] = 0;
                now = "";
            }
        }
        if (flag)
        {
            return true;
        }
        else
        {
            return false;
        }
    }
};
int main() {
 Solution s;
 cout << s.reorderedPowerOf2(56653) << endl;
 //65536
 return 0;
}

unique用法

要注意unique返回的是一个迭代器。

int size = unique(candyType.begin(),candyType.end())-candyType.begin();

用于有序数组的双指针

题目链接
本次题目收获如下：
1、好的算法不需要程序员自己考虑过多情况（写n多个if），算法本身就可以实现应对多种情况。
2、双指针注意指针的起始位置，可以有效避免访问越界。

//标准设置方法
int left_pointer = 0;
int right_pointer = array.size()-1;//注意要减一，否则后续会访问越界

//我的错误示范
int left_pointer = binary_search(target);//就是使用二分后查找到的0的位置，因为在代码中我将所有大于0和所有小于0的情况都先查找一变，没有结果的才会使用双指针，所以右指针只需要从大于目标和之后的位置开始，左指针只需要从小于0的数字开始，然后我的算法超时了
int right_pointer = binary_search(target)+1;

上述两种代码一对比，谁更简洁一目了然QAQ。
完整代码

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target)
    {
        int left = 0;
        int right = numbers.size()-1;
        vector<int>res;
        while (left < right)
        {
            int sum = numbers[left] + numbers[right];
            if (sum == target)
            {
                res.push_back(left+1);
                res.push_back(right+1);
                return res;
            }
            else if (sum < target)
            {
                left++;
            }
            else
            {
                right--;
            }
        }
        return res;
    }
};

把一个链表变成可以基于下标访问的vector数组

题目链接
基本思路，先把头结点塞入到vector中，然后使用一个while循环，一步一步将头结点的next全部塞入到vector中。

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        vector<ListNode*> A = {head};
        while (A.back()->next != NULL)
            A.push_back(A.back()->next);
        return A[A.size() / 2];
    }

滑动窗口

题目链接
感悟：
1、使用滑动窗口时要注意窗口右端的访问越界问题。
2、当map中的值不是1的时候，在向后滑动窗口的时候不能直接删掉这个键，因为可能会删掉不止一条的记录。只需要将map中对应键的值减一即可。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        map<char, int>mark;
        int len = s.size();
        int windows_end = -1;//consider the same characher is empty
        int res = -1;
        for (int i = 0; i < len; i++)
        {
            if (i != 0)
            {
                mark.erase(s[i - 1]);
            }
            while (windows_end + 1 < len && !mark[s[windows_end+1]])
            {
                mark[s[windows_end + 1]]++;
                windows_end++;
            }
            res = max(res, windows_end - i + 1);
        }
        return res;
    }
};

二叉树的递归

题目链接
感悟：
写递归的时候要注意，一定不能写类似于下列的语句企图将二叉树遍历一遍实现对每个结点左右子树的求和，因为在递归的过程中会多次执行，把只想要执行一遍的代码写在return之后。

a->val = fun(a->left)+fun(a->right)+a->val;

AC代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
  class Solution {
  public:
      int deg = 0;
      int get_sum(TreeNode*& p, int sum = 0)
      {
          if (p != NULL)
          {
              if (p->left == NULL && p->right == NULL)
              {
                  p->val = p->val;
                  return p->val;
              }
              else if (p->left == NULL)
              {
                  return p->val + get_sum(p->right);
              }
              else if (p->right == NULL)
              {
                  return p->val + get_sum(p->left);
              }
              else
              {
                  return p->val + get_sum(p->left) + get_sum(p->right);
              }
          }
          return 0;
      }
      int find_deg(TreeNode* p)
      {
          int score = 0;
          if (p != NULL)
          {
              if (p->left == NULL && p->right == NULL)
              {
                  score = 0;
              }
              else if (p->left == NULL)
              {
                  score = abs(get_sum(p->right));
              }
              else if (p->right == NULL)
              {
                  score = abs(get_sum(p->left));
              }
              else
              {
                  score = abs(get_sum(p->left)-get_sum(p->right));
              }
              deg = deg + score;
              find_deg(p->left);
              find_deg(p->right);
          }
          return deg;
      }
      int findTilt(TreeNode* root) {
          get_sum(root);
          return find_deg(root);
      }
  };