Leetcode -- 547. Friend Circles(dfs)

547. Friend Circles(dfs)
medium
https://leetcode.com/problems/friend-circles/#/description

There are N students in a class. Some of them are friends, while some are not. Their friendship is transitive in nature. For example, if A is a direct friend of B, and B is a direct friend of C, then A is an indirect friend of C. And we defined a friend circle is a group of students who are direct or indirect friends.

Given a N*N matrix M representing the friend relationship between students in the class. If M[i][j] = 1, then the ith and jth students are directfriends with each other, otherwise not. And you have to output the total number of friend circles among all the students.

Example 1:

Input: 
[[1,1,0],
 [1,1,0],
 [0,0,1]]
Output: 2
Explanation:The 0th and 1st students are direct friends, so they are in a friend circle. 
The 2nd student himself is in a friend circle. So return 2.

Example 2:

Input: 
[[1,1,0],
 [1,1,1],
 [0,1,1]]
Output: 1
Explanation:The 0th and 1st students are direct friends, the 1st and 2nd students are direct friends, 
so the 0th and 2nd students are indirect friends. All of them are in the same friend circle, so return 1.

Note:

1. N is in range [1,200].
2. M[i][i] = 1 for all students.
3. If M[i][j] = 1, then M[j][i] = 1.

思路：- define visited array for each person, mark all ppl in one cycle visited using dfs
           - traverse the he specific row, if get 1, traverse the corresponding row of that column #
             since 2's friend is considered indirect friend of 1
           - once finishing visit a 1 cycle, increment circle res

Complexity: Time O(N^2) -- n cycle  Space O(1)

public class Solution {
    public int findCircleNum(int[][] M) {
        boolean visited[] = new boolean[M.length];
        int cycle = 0;
        for(int i = 0; i < M.length; i ++){
            if(!visited[i]){
                cycle++;
                visited[i] = true;
                dfs(M, visited, i);//dfs to mark all ppl in the cycle visited
            }
        }
        return cycle;
    }
    public void dfs(int[][] M, boolean[] visited, int i){
        for(int j = 0; j < M[0].length; j++){//no return case here!!
            if(!visited[j] && M[i][j] == 1){
                visited[j] = true;
                dfs(M, visited, j);
            }
        }
    }
}

Leetcode -- 322. Coin Change(DP)

322. Coin Change(DP)
Medium
https://leetcode.com/problems/coin-change/#/description

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

思路：-  use dp bottom up, memoization method
          - we know each solution is formed by at least 1 existing coin, so we check if dp[i-coin] exists.
          - keep filling dp[i] with the min
Complexity: Time O(m*n) -  m is amount, n is len of coins,  Space O(m) - dp array

public int coinChange(int[] coins, int amount) {
        int[] dp = new int[amount+1];//0,1,2,..,amount
        for(int i = 1; i <= amount; i++){
            int count = -1;
            //key is min count, all solutions must be generated from existing coin
            for(int coin : coins) {
             if(i >= coin && dp[i-coin]!=-1) {//skip non-existing solution
              int cur = dp[i-coin]+1;
              if(count < 0)
                  count  = cur;
              else if(cur < count)
                  count = cur;
             }
         }
         dp[i] = count;
        }
        return dp[amount];
    }

Leetcode -- 5. Longest Palindromic Substring(Strategy)

5. Longest Palindromic Substring
medium
https://leetcode.com/problems/longest-palindromic-substring/#/description

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example:

Input: "babad"

Output: "bab"

Note: "aba" is also a valid answer.

Example:

Input: "cbbd"

Output: "bb"

思路： - iterate string, keep finding longer palindrome(curLen)
                  check if str[i-curlen-1, i]: curLen+=2
                  else if str[i-curlen, i]: curLen+=1

Complexity: Time O(n^2) for "aaaa..a" Space O(1)

public String longestPalindrome(String s) {
        //if ...*axxa (a), we check if *axxaa isPalindrome
        // else axxa(a)
        //else palindrome disconnect here
        //keep tracking current len to set begin, cuz if < current len, not longest, skip
        if(s.length() < 2)return s;
        String res = "";
        int curLen = 0;//watch index boundary
        for(int i = 1; i < s.length(); i++){
            if(isPalindrome(s, i-curLen-1, i)){
                res = s.substring(i-curLen-1, i+1);//susbstring
                curLen += 2; 
            }else if(isPalindrome(s, i-curLen, i)){
                res = s.substring(i-curLen,i+1);
                curLen += 1;
            }
        }
        return res;
    }
    public boolean isPalindrome(String s, int begin, int end){
        if(begin < 0)return false;
        while(begin < end){
            if(s.charAt(begin) == s.charAt(end)){
                begin++;
                end--;
            }else{
                return false;
            }
        }
        return true;
    }

Leetcode - 328. Odd Even Linked List

 328. Odd Even Linked List

easy

https://leetcode.com/problems/odd-even-linked-list/#/description 

Given a singly linked list, group all odd nodes together followed by the even nodes. Please note here we are talking about the node number and not the value in the nodes.

You should try to do it in place. The program should run in O(1) space complexity and O(nodes) time complexity.

Example:
Given 1->2->3->4->5->NULL,
return 1->3->5->2->4->NULL.

Note:
The relative order inside both the even and odd groups should remain as it was in the input. 
The first node is considered odd, the second node even and so on ...

思路： - use double pointer, to maintain 2 list: regular & evenlist
           - pointer: even, odd modify current node. evenHead(2 in this case) always point the start of evenlist
           - travel the list to adjust nodes until reach end of evenlist
Complexity: Time O(N) Space O(1)

public class Solution {
    public ListNode oddEvenList(ListNode head) {
        if(head == null)
            return head;
        ListNode odd = head;
        ListNode even = head.next;
        ListNode evenHead = even;
        while(even != null && even.next != null){
            odd.next = even.next;
            odd = odd.next;
            even.next = odd.next;
            even = even.next;
            odd.next = evenHead;
        }
        return head;
    }
}

思路2： - use double pointer, to maintain 2 list:odd& evenlist
              - Traverse the list till end
              - Then connect odd & even list
Complexity: Time O(N) Space O(1)

  Preview (hint: you can copy and paste the preview into Microsoft Word):

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
    def oddEvenList(self, head):
        """
        :type head: ListNode
        :rtype: ListNode
        """
        oddStart = ListNode(0)
        evenStart = ListNode(0)
        oddN = oddStart
        evenN = evenStart
        counter = 1
        while(head != None):
            if(counter % 2 != 0):
                oddN.next = head
                oddN = oddN.next
            else:
                evenN.next = head
                evenN = evenN.next
            head = head.next
            counter += 1
            
        evenN.next = None
        oddN.next = evenStart.next
        
        return oddStart.next

Leetcode -- 227. Basic Calculator II (Stack)

227. Basic Calculator II(Stack)
medium
https://leetcode.com/problems/basic-calculator-ii/

mplement a basic calculator to evaluate a simple expression string.

The expression string contains only non-negative integers, +, -, *, / operators and empty spaces . The integer division should truncate toward zero.

You may assume that the given expression is always valid.

Some examples:

"3+2*2" = 7
" 3/2 " = 1
" 3+5 / 2 " = 5

思路： - use stack to store number after operation. initialize sign as '+'
           - calculating current val = val * 10 + char
           - when meet next sign, perform operation of last sign on current number(+,-*,/)
           - finally sum up number in stack
eg: 2+33*2
            (here) sign = +, val = 33, then sign = *

Complexity: Time O(N) Space O(N)

public int calculate(String s) {
        if(s == null || s.length() == 0) return 0;
        Stack<Integer> st = new Stack();
        char sign = '+';
        int val = 0;
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                val = val*10 + (c -'0');
            }
            if((!Character.isDigit(c) && c != ' ') || i == s.length() - 1){
                if(sign == '+'){
                    st.push(val);
                }
                if(sign == '-'){
                    st.push(-val);
                }
                if(sign == '*'){
                    st.push(st.pop()*val);
                }
                if(sign == '/'){
                    st.push(st.pop()/val);
                }
                sign = c;
                val = 0;
            }
        }
        
        int res = 0;
        for(Integer i: st){
            res += i;
        }
        return res;
    }

Leetcode -- 543. Diameter of Binary Tree(Recur)

543. Diameter of Binary Tree(Recur)
easy
https://leetcode.com/problems/diameter-of-binary-tree/#/description

Given a binary tree, you need to compute the length of the diameter of the tree. The diameter of a binary tree is the length of the longestpath between any two nodes in a tree. This path may or may not pass through the root.

Example:
Given a binary tree 

          1
         / \
        2   3
       / \     
      4   5    

Return 3, which is the length of the path [4,2,1,3] or [5,2,1,3].

Note: The length of path between two nodes is represented by the number of edges between them.

思路1： - traverse every node to get max of leftDepth, then rightDepth, then add those 2
                       - at every node, calculate the max depth by helper

Complexity: Time O(N^2)  Space O(N^2)   

public class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null)
            return 0;
        max = Math.max(max, helper(root.left) + helper(root.right));
        diameterOfBinaryTree(root.left);
        diameterOfBinaryTree(root.right);
        return max;
    }
    public int helper(TreeNode root){
        if(root == null)
            return 0;
        return 1 + Math.max(helper(root.left), helper(root.right));
    }
}

     
思路2： find out the max of leftDepth & rightDepth while at each node, meanwhile update the total max.
Complexity: Time O(N) Space O(N)

public class Solution {
    int max = 0;
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return max;
    }
    public int maxDepth(TreeNode root){
        if(root == null)return 0;
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        max = Math.max(max, left + right);
        return 1 + Math.max(left, right);
    }
}