wszdwp’s gists

wszdwp / Two sum

Created November 12, 2014 16:53

Given an array of integers, find two numbers such that they add up to a specific target number. The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based. You may assume that each input…

	public int[] twoSum(int[] numbers, int target) {

	int[] ans = new int[2];
	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

	for (int i = 0; i < numbers.length; i++) {
	int num = numbers[i];
	if (map.containsKey(num)) {
	ans[0] = map.get(num) + 1;
	ans[1] = i + 1;

wszdwp / 3Sum cloest

Created November 12, 2014 17:13

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. For example, given array S = {-1 2 1 -4}, and target = 1. The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

	public int threeSumClosest(int[] num, int target) {
	http://www.programcreek.com/2013/02/leetcode-3sum-closest-java/
	int min = Integer.MAX_VALUE;
	int result = 0;
	Arrays.sort(num);

	for (int i = 0; i < num.length; i++) {
	int start = i + 1;
	int end = num.length - 1;

wszdwp / Valid Parentheses

Created November 12, 2014 18:26

Given a string containing just the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The brackets must close in the correct order, "()" and "()[]{}" are all valid but "(]" and "([)]" are not.

	public boolean isValid(String s) {
	//http://www.programcreek.com/2012/12/leetcode-valid-parentheses-java/
	if (s == null \|\| s.length() == 0)
	return false;

	Stack<Character> stk = new Stack<Character>();
	HashMap<Character, Character> hMap = new HashMap<Character, Character>();
	hMap.put('(', ')');
	hMap.put('[', ']');
	hMap.put('{', '}');

wszdwp / Anagrams

Created November 12, 2014 20:22

Given an array of strings, return all groups of strings that are anagrams. Note: All inputs will be in lower-case.

	public ArrayList<String> anagrams(String[] strs) {
	//http://blog.csdn.net/linhuanmars/article/details/21664747
	if (strs == null \|\| strs.length == 0)
	return null;

	ArrayList<String> result = new ArrayList<String>();
	HashMap<String, ArrayList<String>> hMap = new HashMap<String, ArrayList<String>>();

	for (String s : strs) {
	char[] cStr = s.toCharArray();

wszdwp / Longest Valid Parentheses

Created November 12, 2014 20:46

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring. For "(()", the longest valid parentheses substring is "()", which has length = 2. Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

	public int longestValidParentheses(String s) {
	//http://rleetcode.blogspot.com/2014/01/longest-valid-parentheses.html
	if (s == null \|\| s.length() < 2)
	return 0;

	int maxLen = 0;
	int last = -1;
	Stack<Integer> stk = new Stack<Integer>();

	for (int i = 0; i < s.length(); i++) {

wszdwp / Letter Combinations of a Phone Number

Created November 16, 2014 00:29

Given a digit string, return all possible letter combinations that the number could represent. A mapping of digit to letters (just like on the telephone buttons) is given below.

	public ArrayList<String> letterCombinations(String digits) {
	final String[] keypads = {"", "", "abc", "def", "ghi", "jkl", "mno",
	"pqrs", "tuv", "wxyz"};
	ArrayList<String> result = new ArrayList<String>();
	result.add("");

	if (digits == null \|\| digits.length() == 0)
	return result;

	for (int i = 0; i < digits.length(); i++) {

wszdwp / Letter Combinations of a Phone Number

Created November 16, 2014 01:14

recursive solu

	public ArrayList<String> letterCombinations(String digits) {
	final String[] keypads = {"", "", "abc", "def", "ghi", "jkl", "mno",
	"pqrs", "tuv", "wxyz"};
	ArrayList<String> result = new ArrayList<String>();
	if (digits.equals(""))
	result.add("");

	if (digits == null \|\| digits.length() == 0)
	return result;

wszdwp / Set Matrix Zeroes

Created November 16, 2014 14:52

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place.

	public void setZeroes(int[][] matrix) {

	if (matrix == null )
	return;

	boolean firstRowZero = false;
	boolean firstColZero = false;

	int rowL = matrix.length;
	int colL = matrix[0].length;

wszdwp / Longest Palindromic Substring

Last active August 29, 2015 14:10

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

	public class Solution {
	public String longestPalindrome(String s) {

	String longest = "";

	for (int i = 0; i < s.length(); i++) {
	String temp = "";

	temp = longestPalindromeHelper(s, i, i);
	if (temp.length() > longest.length())

wszdwp / Palindrome Partitioning

Created November 24, 2014 02:49

Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s. For example, given s = "aab", Return [ ["aa","b"], ["a","a","b"] ]

	//-------------------------solution1-------------------------------------------------------
	//http://blog.csdn.net/linhuanmars/article/details/22777711
	public ArrayList<ArrayList<String>> partition(String s) {
	ArrayList<ArrayList<String>> res = new ArrayList<ArrayList<String>>();
	if(s==null \|\| s.length()==0)
	return res;
	helper(s, getDict(s),0,new ArrayList<String>(), res);
	return res;
	}
	private void helper(String s, boolean[][] dict, int start, ArrayList<String> item, ArrayList<ArrayList<String>> res)

Codingpan wszdwp