LeetCode 31-40

…

31 Next Permutation

Find the next lexicographical permutation of a sequence.

next_permutation() solves this directly. I also saw an excellent binary-search solution in the discussion.

class Solution 
{
public:
    void nextPermutation(vector<int>& nums)
    {
    	int sz = nums.size();
    	if(sz<=1)return;
    	for(int i=sz-2;i>=0;i--)
    	{
    		if(nums[i]<nums[i+1])
    		{
    			break;
    		}
    	}        
    	reverse(begin(nums) + i + 1,end(nums));
    	if(i==-1)return;
    	int pos = upper_bound(begin(nums)+i+1,end(nums),nums[i]);
    	swap(nums[pos],nums[i]);
    }
};

32 Longest Valid Parentheses

Given a parentheses sequence, find its longest valid parentheses substring.

Use a stack to record invalid positions, then find the longest interval.

class Solution
{
public:
	int longestValidParentheses(string s) 
	{
		stack<int>st;
		int res = 0;
		int len = s.length();

		for (int i = 0; i < len; i++)
		{
			if (s[i] == ')')
			{
				if (!st.empty() && s[st.top()] == '(')
				{
					st.pop();
				}
				else
				{
					st.push(i);
				}
			}
			else
			{
				st.push(i);
			}
		}
		if (st.empty())
		{
			res = len;
		}
		else
		{
			int ri = len, le = 0;
			while (!st.empty())
			{
				int k = st.top();
				st.pop();
				res = max(res, ri - k - 1);
				ri = k;
			}
			res = max(res, ri);
		}
		return res;
	}
};

33 Search in Rotated Sorted Array

Find a target value in a rotated sorted array.

Use $O(\log n)$ binary search. I first find the minimum value, then use modular indexing to find the target.

class Solution
{
public:
	int search(vector<int>& nums, int target) 
	{
		int n = nums.size();
		int ri = n - 1;
		int le = 0;
		while (le < ri)
		{
			int mid = (le + ri) >> 1;
			if (nums[mid]>nums[ri])
			{
				le = mid + 1;
			}
			else
			{
				ri = mid;
			}
		}
		int t = le;
		le = 0, ri = n - 1;
		while (le < ri)
		{
			int mid = (le + ri + 1) >> 1;
			int p = (t + mid) % n;
			if (nums[p]>target)
			{
				ri = mid - 1;
			}
			else
			{
				le = mid;
			}
		}
		if (nums[(le + t) % n] == target)return (le + t) % n;
		else return -1;
	}
};

This problem can also search directly for the target with binary search by checking each segment; see the discussion.

public class Solution {
public int search(int[] A, int target) {
    int lo = 0;
    int hi = A.length - 1;
    while (lo < hi) {
        int mid = (lo + hi) / 2;
        if (A[mid] == target) return mid;
        
        if (A[lo] <= A[mid]) {
            if (target >= A[lo] && target < A[mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } else {
            if (target > A[mid] && target <= A[hi]) {
                lo = mid + 1;
            } else {
                hi = mid - 1;
            }
        }
    }
    return A[lo] == target ? lo : -1;
}

37 Sudoku Solver

Solve Sudoku.

Combine this with LeetCode 36 to validate the Sudoku. Check before recursing; keep the check on the left.

bool isValidSudoku(vector< vector < char> >& board,int x,int y)
{
	for (int i = 0; i < 9; i++)
	{
		if (i == x)continue;
		if (board[i][y] == board[x][y])return false;
	}
	for (int i = 0; i < 9; i++)
	{
		if (i == y)continue;
		if (board[x][i] == board[x][y])return false;
	}
	int k = (x / 3)* 3 + y / 3;
	for (int i = 0; i < 9; i++)
	{
		for (int j = 0; j < 9; j++)
		{
			if (i == x&&j == y)continue;
			int k2 = (i / 3) * 3 + j / 3;
			if (k == k2)
			{
				if (board[x][y] == board[i][j])
				{
					return false;
				}
			}
		}
	}
	return true;
}

class Solution 
{
public:
	bool solveSudoku(vector<vector<char>>& board)
	{
		for (int i = 0; i < 9; i++)
		{
			for (int j = 0; j < 9; j++)
			{
				if (board[i][j] == '.')
				{
					for (int k = 1; k <= 9; k++)
					{
						board[i][j] = '0' + k;
						if (isValidSudoku(board,i,j) && solveSudoku(board))
						{
							return true;
						}
						board[i][j] = '.';
					}
					return false;
				}
			}
		}
		return true;
	}
};

39 Combination Sum

Given an array and a target, find all combinations whose values sum to the target. Each number may be used unlimited times.

void dfs(vector<vector<int>>&res, vector<int>& val, vector<int> &cur, int tar, int idx)
{
	if (tar == 0)
	{
		res.push_back(cur);
		return;
	}
	int sz = val.size();
	for (int i = idx; i < sz; i++)
	{
		if (tar < val[i])break;
		cur.push_back(val[i]);
		dfs(res, val, cur, tar - val[i], i);
		cur.pop_back();
	}
}

class Solution 
{
public:
	vector<vector<int>> combinationSum(vector<int>& candidates, int target)
	{
		vector<vector<int>>res;
		vector<int> cur;

		if (candidates.size() == 0)return res;
		sort(candidates.begin(), candidates.end());

		dfs(res, candidates, cur, target, 0);

		return res;
	}
};

40 Combination Sum II

Unlike the previous problem, every array element may be used only once.

Use begin to distinguish duplicates. At each begin position, ignore repeated values because they already duplicate the value at or before begin.

void dfs(vector<vector<int>>&res, vector<int>& val, vector<int> &cur, int tar, int begin)
{
	if (tar == 0)
	{
		res.push_back(cur);
		return;
	}
	int sz = val.size();
	for (int i = begin; i < sz; i++)
	{
		if (tar < val[i])break;
		if(i!=begin&&val[i]==val[i-1])continue;
		
		cur.push_back(val[i]);
		dfs(res, val, cur, tar - val[i], i+1);
		cur.pop_back();
	}
}

class Solution 
{
public:
	vector<vector<int>> combinationSum2(vector<int>& candidates, int target)
	{
		vector<vector<int>>res;
		vector<int> cur;

		if (candidates.size() == 0)return res;
		sort(candidates.begin(), candidates.end());

		dfs(res, candidates, cur, target, 0);

		return res;
	}
};