Valid Parentheses

 문제 설명

Given a string s containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid.

An input string is valid if:

1. Open brackets must be closed by the same type of brackets.
2. Open brackets must be closed in the correct order.

 제한 사항

• 1 <= s.length <= 104
• s consists of parentheses only '()[]{}'.

 입출력 예

Example 1:

Input: s = "()"
Output: true

Example 2:

Input: s = "()[]{}"
Output: true

Example 3:

Input: s = "(]"
Output: false

 Python 코드

Python code 

class Solution:
  def isValid(self, s: str) -> bool:
      stack = []
      dic = {'(':')',
             '{':'}',
             '[':']'
            }

      for char in s:
          if char in dic.keys():
              stack.append(char)

          elif stack == [] or char != dic[stack.pop()] :
              return False

      return stack ==[]

* 참고 링크 : https://chaerim-kim.github.io/data%20structures%20and%20algorithms/ValidParentheses/

class Solution:
    def isValid(self, s: str) -> bool:
        stack=[]
        brackets={'}':'{',')':'(',']':'['}
        for bracket in s:
            if bracket in brackets.values(): #Opening bracket 
                stack.append(bracket)
            else:# Closing bracket
                if stack and brackets[bracket]==stack[-1] :  
                    stack.pop()
                else: 
                    return False
        
        if stack:
            return False
        return True

* 참고 링크 : https://velog.io/@kgh732/Python-%EC%9C%BC%EB%A1%9C-%ED%91%B8%EB%8A%94-Leetcode20.-Valid-Parentheses

class Solution: 
	def isValid(self, s: str) -> bool: 
    	s_list = list(s)
        
        answer = True 
        
        stack = [] 
        
        for s in s_list: 
        	if s == '[' or s == '(' or s == '{': 
            	stack.append(s) 
            elif len(stack) != 0: 
            	if (s == ']' and stack[-1] == '[') or (s == '}' and stack[-1] == '{') or (s == ')' and stack[-1] == '('): 
                	stack.pop() 
                else: 
                    answer = False 
                    break 
            else: 
            	answer = False 
                break 
                
        if len(stack) != 0: 
        	answer = False 
        return answer

* 참고 링크 : https://somjang.tistory.com/entry/leetCode-20-Valid-Parentheses-Python

C++ 코드

C ++ code

class Solution {
public:
    bool isValid(string s) {
        stack<char> st;
        
        for(int i = 0; i < s.size(); i++) {
            if(s.at(i) == '{' || s.at(i) == '(' || s.at(i) == '[')      st.push(s.at(i));
            else {
                if(st.empty())      return false;
                else {
                    if((s.at(i) == '}' && st.top() != '{') || (s.at(i) == ')' && st.top() != '(') 
                        || (s.at(i) == ']' && st.top() != '['))
                            st.push(s.at(i));
                    else    st.pop();
                }
            }   
        }
        
        return st.empty();
    }
};

* 참고 링크 : https://m.blog.naver.com/tac1994/221839649888

 출처

https://leetcode.com/problems/valid-parentheses/submissions/

Palindrome Linked List

 문제 설명

Given the head of a singly linked list, return true if it is a palindrome.

 제한 사항

• The number of nodes in the list is in the range [1, 105].
• 0 <= Node.val <= 9

 입출력 예

Example 1:

Input: head = [1,2,2,1]
Output: true

Example 2:

Input: head = [1,2]
Output: false

 Python 코드

Python code 

class Solution:
    def isPalindrome(self, head: ListNode) -> bool:
        val_list = []
        curr = head
        while curr:
            val_list.append(curr.val)
            curr = curr.next
        return val_list == val_list[::-1]

* 참고 링크 : https://ceuity.tistory.com/12

https://velog.io/@jayb/LeetCode-234.Palindrome-Linked-List%ED%8C%B0%EB%A6%B0%EB%93%9C%EB%A1%AC-%EC%97%B0%EA%B2%B0-%EB%A6%AC%EC%8A%A4%ED%8A%B8

 C++ 코드

C ++  code

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode *slow = head, *fast = head, *prev, *temp;
        while (fast && fast->next)
            slow = slow->next, fast = fast->next->next;
        prev = slow, slow = slow->next, prev->next = NULL;
        while (slow)
            temp = slow->next, slow->next = prev, prev = slow, slow = temp;
        fast = head, slow = prev;
        while (slow)
            if (fast->val != slow->val) return false;
            else fast = fast->next, slow = slow->next;
        return true;
    }
};

* 참고 링크 : https://dev.to/seanpgallivan/solution-palindrome-linked-list-5721

 출처

https://leetcode.com/problems/palindrome-linked-list/submissions/

Single Number

 문제 설명

Given a non-empty array of integers nums, every element appears twice except for one. Find that single one.

You must implement a solution with a linear runtime complexity and use only constant extra space.

 제한 사항

• 1 <= nums.length <= 3 * 104
• -3 * 104 <= nums[i] <= 3 * 104
• Each element in the array appears twice except for one element which appears only once.

 입출력 예

Example 1:

Input: nums = [2,2,1]
Output: 1

Example 2:

Input: nums = [4,1,2,1,2]
Output: 4

Example 3:

Input: nums = [1]
Output: 1

 Python 코드

Python code 

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        answer = 0
        for i in nums:
            answer = answer ^ i
        return answer

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        cnt_dict = Counter(nums) 
        items = cnt_dict.items()
        
        for key, val in items:
            if val == 1:
                answer = key
                break
                
        return answer

* 참고 링크 : https://airsbigdata.tistory.com/89

 C++ 코드

C ++ 100% 0ms code

nt singleNumber(int a[], int n) {
     //xor all numbers, the left over number would be the non repeated one
     // since the equl numbers cancel out each others bits
     int num = 0;
     for (int i = 0; i < n; ++i) {
         num ^= a[i];
     }
     return num;
    }

* 참고 링크 : https://leetcode.com/problems/single-number/discuss/43237/4-lines-of-c%2B%2B-solution

 출처

https://leetcode.com/problems/single-number/

Pascal's Triangle

 문제 설명

Given an integer numRows, return the first numRows of Pascal's triangle.

In Pascal's triangle, each number is the sum of the two numbers directly above it as shown:

 제한 사항

• 1 <= numRows <= 30

 입출력 예

Example 1:

Input : numRows = 5
Output : [[1], [1.1], [1,2,1], [1,3,3,1], [1,4,6,4,1]]

Example 2:

Input : numRows = 1
Output : [[1]]

 Python 코드

Python 8ms code 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def isSameTree(self, p, q):
     
        if not p and not q:
            return True
        if not p or not q:
            return False
        
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

* 참고 링크 : 

 C++ 코드

C ++ 100% 0ms code

- String으로 바꾸지 않고 맨 뒤의 값과 맨 앞의 값을 비교하면서 푼 코드

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) // if the two nodes are empty nodes, return true
            return true;
        else if((p == NULL && q != NULL) || (p != NULL && q == NULL)) // if only one of the nodes from p and q is emtpy, 2 trees are not equal
            return false;
        else 
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
						// First we compare the values in each node from p and q. Then, use a recursive method, call isSameTree function with left nodes of p and q as parameters. Do the same for the right nodes.
    }
};

* 참고 링크 : 

 출처

https://leetcode.com/problems/pascals-triangle/

3Sum

 문제 설명

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

 제한 사항

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

 입출력 예

Example 1:

Input : num = [-1, 0, 1, 2, -1, -4]
Output : [[-1, -1, 2], [-1, 0, 1]]

Example 2:

Input : nums = []
Output : []

Example 3:

Input : nums = [0]
Output : []

 Python 코드

Python 8ms code 

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

class Solution(object):
    def isSameTree(self, p, q):
     
        if not p and not q:
            return True
        if not p or not q:
            return False
        
        return p.val == q.val and self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)

* 참고 링크 : 

 C++ 코드

C ++ 100% 0ms code

- String으로 바꾸지 않고 맨 뒤의 값과 맨 앞의 값을 비교하면서 푼 코드

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL) // if the two nodes are empty nodes, return true
            return true;
        else if((p == NULL && q != NULL) || (p != NULL && q == NULL)) // if only one of the nodes from p and q is emtpy, 2 trees are not equal
            return false;
        else 
            return p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
						// First we compare the values in each node from p and q. Then, use a recursive method, call isSameTree function with left nodes of p and q as parameters. Do the same for the right nodes.
    }
};

* 참고 링크 : 

 출처

https://leetcode.com/problems/3sum/

Add Two Numbers

 문제 설명

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

 제한 사항

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

 입출력 예

Example 1:

Input : l1 = [2, 4, 3], l2 = [5, 6, 4]
Output : [7, 0, 8]
Explanation : 342 + 465 = 807

Example 2:

Input : l1 = [0], l2 = [0]
Output : [0]

Example 3:

Input : l1 = [9, 9, 9, 9, 9, 9, 9], l2 = [9, 9, 9, 9]
Output : [8, 9, 9, 9, 0, 0, 0, 1]

 Python 코드

Python 8ms code 

dd

* 참고 링크 : 

 C++ 코드

C ++ 100% 0ms code

- 

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

* 참고 링크 : 

 출처

https://leetcode.com/problems/add-two-numbers/