[LeetCode] Easy Problems

文章目录

1. 1. Binary Tree Level Order Traversal[102]
2. 2. Isomorphic Strings［205］
3. 3. Compare Version Numbers［165］
4. 4. Reverse Integer
5. 5. Remove Nth Node From End of List

Some problems of Leetcode

Binary Tree Level Order Traversal[102]

vector<vector<int>> levelOrder(TreeNode* root) {
    vector<vector<int>> output;
    vector<int> current_level;
    TreeNode* currentNode;
    queue<TreeNode* > t_queue;
    if(root==NULL)
    {
        return output;
    }
    t_queue.push(root);
    t_queue.push(NULL);     //easy to forget
    while(!t_queue.empty())
    {
        currentNode = t_queue.front();
        t_queue.pop();
        if(currentNode == NULL)
        {
            if(!t_queue.empty())        //easy to forget, you have forgot this several times  
            {
                t_queue.push(NULL);
            }
            output.push_back(current_level);
            current_level.clear();
        }
        else
        {
            current_level.push_back(currentNode->val);
            if(currentNode->left!=NULL)
            {
                t_queue.push(currentNode->left);
            }
            if(currentNode->right!=NULL)
            {
                t_queue.push(currentNode->right);
            }
            
        }
        
        
        
    }
    
    
}

Isomorphic Strings［205］

1. Should have two direction check(one word for key, the other for value and vice versa)

   Compare Version Numbers［165］

2. Remember this case, “1” = “1.0”

Reverse Integer

1. If the integer’s last digit is 0, what should the output be? ie, cases such as 10, 100. (handled implicitly by the naive method)
2. the reversed integer might overflow?
   Solution:

• Method1: Use long int for the reversed int
• Method2: check the number before addition and multiplication
  Method1

  int reverse(int x) {
      int flag = 1;
      long result = 0;
      if(x<0)
      {
          flag = -1;
          x = abs(x);
      }
      while(x>0)
      {
          result = result * 10;
          if(result<0)
              return 0;
          result += x % 10;
          if(result<0)
              return 0;
          x = x / 10;
  
      }
      if (result>INT_MAX)
          return 0;
      result = result * flag;
      return (int)result;
      
  }

Method2:

int reverse(int x) {
    int flag = 1;
    int result = 0;
    int d = 0;
    if(x<0)
    {
        flag = -1;
        x = abs(x);
    }
    while(x>0)
    {
        d = x % 10;
        if (result > (INT_MAX-d)/10)
            return 0;
        result = result * 10;
        
        result += d;
        if(result<0)
            return 0;
        x = x / 10;

    }

    result = result * flag;
    return result;
}

Remove Nth Node From End of List

• List Problems if the naive way is so easy. Think about how to make it use less time and memory. Use a different pointer is always a right way to think about.