yikaikai/leecode

leecode's Issues

31. Next Permutation

分析
网上看来一个示例，觉得挺好的，也没必要另外找一个了。

6 5 4 8 7 5 1
1
一开始没看对方的后面介绍，就自己在想这个排列的下一个排列是怎样的。

首先肯定从后面开始看，1和5调换了没有用。

7、5和1调换了也没有效果，因此而发现了8、7、5、1是递减的。

如果想要找到下一个排列，找到递增的位置是关键。

因为在这里才可以使其增长得更大。

于是找到了4，显而易见4过了是5而不是8或者7更不是1。

因此就需要找出比4大但在这些大数里面最小的值，并将其两者调换。

那么整个排列就成了：6 5 5 8 7 4 1

然而最后一步将后面的8 7 4 1做一个递增。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
代码
根据上面的思路，在记事本上一气呵成写了如下代码：

class Solution {
public:
void nextPermutation(vector& nums) {
int index = nums.size() - 1;
while(nums[index] <= nums[index-1]) {
--index;
}
if(index == 0) {
sort(nums.begin(), nums.end());
return ;
}

    int second = INT_MAX, secondIndex = INT_MAX;
    for(int i = nums.size() - 1; i >= index - 1; -- i) {
        if(nums[i] > nums[index - 1]) {
            if(nums[i] < second) {
                second = nums[i];
                secondIndex = i;
            }               
        }               
    }       
    int temp = nums[index - 1];
    nums[index - 1] = nums[secondIndex];
    nums[secondIndex] = temp;

    sort(nums.begin()+index, nums.end());       
}

}

22 generate parentheses 生成括号

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"
题意：给定n对括号，生成所有合法的组合情况。
思路：合法的情况是，任意一时刻，左（“(”）括号数要大于等于右（")"）括号数。关键在于题中只给了括号的对数，没有形象的左右括号字符，如何在脑海中转过弯去解题。故，在某次的调用中，
1）left大于right（left和right分别表示剩余左右括号的个数），即，临时变量中右括号的数大于左括号的数，则说明出现了“)(”，这是非法情况，返回即可；
2）left和right都等于0说明，临时变量中左右括号数相等，所以将临时变量中的值存入res中；
3）其余的情况是，先放左括号，然后放右括号，然后递归。注意参数的更新。
class Solution {
public:
vector generateParenthesis(int n)
{
vector res;
generateDFS(n,n,"",res);
return res;
}

/*left、right分别是左右括号剩下的括号数*/
void generateDFS(int left,int right,string temp,vector<string> &res)
{
    if(left>right) return;
    if(left==0&&right==0)  
        res.push_back(temp);
    else
    {
        if(left>0)
            generateDFS(left-1,right,temp+'(',res);
        if(right>0)
            generateDFS(left,right-1,temp+')',res);
    }
}

};
 

82. Remove Duplicates from Sorted List II

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.

Example 1:

Input: 1->2->3->3->4->4->5
Output: 1->2->5
Example 2:

Input: 1->1->1->2->3
Output: 2->3

/**

• Definition for singly-linked list.

• struct ListNode {

• int val;
  

• ListNode *next;
  

• ListNode(int x) : val(x), next(NULL) {}
  

• };
  */
  class Solution {
  public:
  ListNode *deleteDuplicates(ListNode *head) {
  ListNode **runner = &head;

   if(!head || !head->next)return head;
   
   while(*runner)
   {
       if((*runner)->next && (*runner)->next->val == (*runner)->val)
       {
           ListNode *temp = *runner;
           while(temp && (*runner)->val == temp->val)
               temp = temp->next;
           
           *runner = temp;
       }
       else
           runner = &((*runner)->next);
   }
   
   return head;
  

  }
  };

78. Subsets

Given a set of distinct integers, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

Input: nums = [1,2,3]
Output:
[
[3],
[1],
[2],
[1,2,3],
[1,3],
[2,3],
[1,2],
[]
]
class Solution {
public:
vector<vector > subsets(vector &S) {
vector<vector > res(1, vector());
sort(S.begin(), S.end());

for (int i = 0; i < S.size(); i++) {
	int n = res.size();
	for (int j = 0; j < n; j++) {
		res.push_back(res[j]);
		res.back().push_back(S[i]);
	}
}

return res;

}
};

这种方法是一种组合的方式

① 最外层循环逐一从 nums 数组中取出每个元素 num

② 内层循环从原来的结果集中取出每个中间结果集，并向每个中间结果集中添加该 num 元素

③往每个中间结果集中加入 num

④将新的中间结果集加入结果集中

3. Longest Substring Without Repeating Characters

class Solution {
public:
int lengthOfLongestSubstring(string s) {
vector dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
};

46. Permutations

class Solution {
public:
vector<vector> permute(vector& nums) {
vector<vector > ret;

    if (nums.empty())
        return ret;

    sort(nums.begin(), nums.end());
    ret.push_back(nums);
    while (next_permutation(nums.begin(), nums.end()))
        ret.push_back(nums);

    return ret;  
}

};

class Solution {
public:
vector<vector > permute(vector &num) {
vector<vector > result;

    permuteRecursive(num, 0, result);
    return result;
}

// permute num[begin..end]
// invariant: num[0..begin-1] have been fixed/permuted
void permuteRecursive(vector<int> &num, int begin, vector<vector<int> > &result)	{
    if (begin >= num.size()) {
        // one permutation instance
        result.push_back(num);
        return;
    }
    
    for (int i = begin; i < num.size(); i++) {
        swap(num[begin], num[i]);
        permuteRecursive(num, begin + 1, result);
        // reset
        swap(num[begin], num[i]);
    }
}

};

48. Rotate Image

You are given an n x n 2D matrix representing an image.

Rotate the image by 90 degrees (clockwise).

Note:

You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.

Example 1:

Given input matrix =
[
[1,2,3],
[4,5,6],
[7,8,9]
],

rotate the input matrix in-place such that it becomes:
[
[7,4,1],
[8,5,2],
[9,6,3]
]
Example 2:

Given input matrix =
[
[ 5, 1, 9,11],
[ 2, 4, 8,10],
[13, 3, 6, 7],
[15,14,12,16]
],

rotate the input matrix in-place such that it becomes:
[
[15,13, 2, 5],
[14, 3, 4, 1],
[12, 6, 8, 9],
[16, 7,10,11]
]

 void rotate(vector<vector<int>>& matrix) {

int width = matrix[0].size();

    for (int row = 0; row <= (width - 1) / 2; row++) {
        for (int col = row; col < width - 1 - row; col++) {
            int tmp = matrix[row][col];

            matrix[row][col] = matrix[width - 1 - col][row];
            matrix[width - 1 - col][row] = matrix[width - 1 - row][width - 1 - col];
            matrix[width - 1 - row][width - 1 - col] = matrix[col][width - 1 - row];
            matrix[col][width - 1 - row] = tmp;
        }
    }
 }