pdu’s gists

pdu / leetcode_container_with_most_water.cpp

Created January 2, 2013 15:27

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. http://leetcode.com/onlinejudge

	#include <algorithm>
	using namespace std;

	class Solution {
	public:
	int maxArea(vector<int> &height) {
	int ret = 0;
	int left = 0, right = height.size() - 1;
	while (left < right) {
	ret = max(ret, (right - left) * min(height[left], height[right]));

pdu / leetcode_convert_sorted_array_to_binary_search_tree.cpp

Created January 3, 2013 15:09

Given an array where elements are sorted in ascending order, convert it to a height balanced BST. http://leetcode.com/onlinejudge

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

pdu / leetcode_convert_sorted_list_to_binary_search_tree.cpp

Created January 3, 2013 23:29

Given a singly linked list where elements are sorted in ascending order, convert it to a height balanced BST. http://leetcode.com/onlinejudge

	/**
	* Definition for singly-linked list.
	* struct ListNode {
	* int val;
	* ListNode *next;
	* ListNode(int x) : val(x), next(NULL) {}
	* };
	*/
	/**
	* Definition for binary tree

pdu / glassdoor_kthnum2.py

Last active December 10, 2015 15:09

find the k-th number of 2 sorted arrays

	#!/usr/bin/python

	def get_less_cnt(buf, pivot):
	left, right = 0, len(buf) - 1
	ret = 0
	while left <= right:
	mid = (left + right) / 2
	if buf[mid] <= pivot:
	ret = max(ret, mid)
	left = mid + 1

pdu / leetcode_count_and_say.cpp

Created January 4, 2013 14:01

The count-and-say sequence is the sequence of integers beginning as follows: 1, 11, 21, 1211, 111221, ... http://leetcode.com/onlinejudge

	class Solution {
	public:
	string countAndSay(int n) {
	string ret = "1";
	while (--n) {
	stringstream ss;
	int cnt = 0;
	for (int i = 0; i < ret.length(); ++i) {
	cnt++;
	if (i == ret.length() - 1 \|\| ret[i] != ret[i + 1]) {

pdu / leetcode_decode_ways.cpp

Created January 4, 2013 14:34

A message containing letters from A-Z is being encoded to numbers using the following mapping: 'A' -> 1 'B' -> 2 ... 'Z' -> 26 Given an encoded message containing digits, determine the total number of ways to decode it. http://leetcode.com/onlinejudge

	class Solution {
	public:
	int numDecodings(string s) {
	if (s.empty())
	return 0;
	int n = s.length();
	int f[3] = {1, 1, 1};
	for (int i = 0; i < n; ++i) {
	f[i % 3] = 0;
	if (s[i] > '0')

pdu / leetcode_distinct_subsequences.cpp

Created January 6, 2013 14:29

Given a string S and a string T, count the number of distinct subsequences of T in S. A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, "ACE" is a subsequence of "ABCDE" while "AEC" is not).

	class Solution {
	public:
	int numDistinct(string S, string T) {
	int n = S.length();
	int m = T.length();
	if (n == 0 \|\| m == 0)
	return 0;
	int *f = new int[n];
	for (int i = 0; i < n; ++i)
	f[i] = new int[m];

pdu / leetcode_divide_two_integers.cpp

Created January 6, 2013 14:46

Divide two integers without using multiplication, division and mod operator. http://leetcode.com/onlinejudge

	class Solution {
	public:
	int divide(int dividend_, int divisor_) {
	long long dividend = dividend_, divisor = divisor_;
	int flag = 1;
	if (dividend < 0) {
	flag *= -1;
	dividend = -dividend;
	}
	if (divisor < 0) {

pdu / leetcode_edit_distance.cpp

Created January 7, 2013 14:04

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.) You have the following 3 operations permitted on a word: a) Insert a character b) Delete a character c) Replace a character http://leetcode.com/onlinejudge

	class Solution {
	public:
	int minDistance(string word1, string word2) {
	int n = word1.size();
	int m = word2.size();
	if (n == 0 \|\| m == 0)
	return max(n, m);
	int *f = new int[n];
	for (int i = 0; i < n; ++i)
	f[i] = new int[m];

pdu / leetcode_first_missing_positive.cpp

Created January 7, 2013 14:18

Given an unsorted integer array, find the first missing positive integer. For example, Given [1,2,0] return 3, and [3,4,-1,1] return 2. Your algorithm should run in O(n) time and uses constant space. http://leetcode.com/onlinejudge

	class Solution {
	public:
	int firstMissingPositive(int A[], int n) {
	for (int i = 0; i < n; ++i)
	while (A[i] >= 1 && A[i] <= n && A[i] != i + 1 && A[i] != A[A[i] - 1])
	swap(A[i], A[A[i] - 1]);
	int ret;
	for (ret = 1; ret <= n; ++ret)
	if (A[ret - 1] != ret)
	break;

Peng Du pdu