Combinations (Java)

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,
If n = 4 and k = 2, a solution is:

[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution: a classical DFS problem, pay attention to the format of solve this question which can be apply to many other DFS problems

	/*
	Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.
	For example,
	If n = 4 and k = 2, a solution is:
	[
	[2,4],
	[3,4],
	[2,3],
	[1,2],
	[1,3],
	[1,4],
	]
	Have you been asked this question in an interview?
	*/
	public class Solution {
	public ArrayList<ArrayList<Integer>> combine(int n, int k) {
	if (n<=0||k<=0){
	return null;
	}
	ArrayList<ArrayList<Integer>> result=new ArrayList<ArrayList<Integer>>();
	int st=1;
	int num=0;
	ArrayList<Integer> subResult=new ArrayList<Integer>();
	buildResult(st, num, k, n, subResult, result);
	return result;
	}
	// DFS classical format
	private void buildResult(int start, int currentNum, int k, int n, ArrayList<Integer> subResult, ArrayList<ArrayList<Integer>> result)
	{
	if (currentNum==k){
	ArrayList<Integer> temp=new ArrayList<Integer>(subResult);
	result.add(temp);
	return;
	}
	for (int i=start; i<=n; i++){
	subResult.add(i);
	buildResult(i+1, currentNum+1, k, n, subResult, result);
	subResult.remove(subResult.size()-1);
	}
	}
	}

view raw Combinations.java hosted with ❤ by GitHub

Remove Nth Node From End of List (Java)

Given a linked list, remove the nth node from the end of list and return its head.

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.
Try to do this in one pass.

	/**
	* Definition for singly-linked list.
	* public class ListNode {
	* int val;
	* ListNode next;
	* ListNode(int x) {
	* val = x;
	* next = null;
	* }
	* }
	*/
	public class Solution {
	public ListNode removeNthFromEnd(ListNode head, int n) {
	if (head==null){
	return head;
	}
	ListNode remove=head;
	ListNode last=head;
	ListNode preHead=new ListNode (-1);
	preHead.next=head;
	ListNode pre=preHead;
	while (n>1){
	if (last.next==null){
	return head;
	}
	last=last.next;
	n--;
	}
	while (last.next!=null){
	last=last.next;
	pre=pre.next;
	remove=remove.next;
	}
	pre.next=remove.next;
	return preHead.next;
	}
	}

view raw RemoveNthNodeFromEndOfList .java hosted with ❤ by GitHub