↓ Skip to main content
111qqz’s blog
  1. Posts/

leetcode 39. Combination Sum (dfs，求所有的组合，和为定值，每个数可以重复用)

·278 words·1 min
ACM DFS Leetcode
Note: This article is available in Chinese only. 本文暂无英文版本。 View original

Given a set of candidate numbers (C) (without duplicates) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.

The same repeated number may be chosen from C unlimited number of times.

Note:

  * All numbers (including target) will be positive integers.
  * The solution set must not contain duplicate combinations.

题意：给n个数，求所有的组合，和为定值，每个数可以重复用)

思路：。。。。一开始用顺着枚举子集的思路。。。发现。。并不好搞。。。？还不如直接dfs…

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月13日 星期四 00时06分12秒
 4File Name :39.cpp
 5************************************************ */
 6class Solution {
 7public:
 8
 9    vector<vector<int> >res;
10    vector<int>tmp;
11    int n;
12    //思路：dfs
13    void dfs( int start,int cur,vector<int> &nums)
14    {
15	if (cur==0)
16	{
17	    res.push_back(tmp);
18	    return ;
19	}
20	else if (cur<0) return;
21	else
22	{
23	    for ( int i = start ; i < n ; i++)
24	    {
25		tmp.push_back(nums[i]);
26		dfs(i,cur-nums[i],nums);
27		tmp.erase(tmp.begin()+tmp.size()-1);
28	    }
29	}
30    }
31
32    vector<vector<int>> combinationSum(vector<int>& nums, int target) {
33	n = nums.size();
34	if (n==0) return res;
35	dfs(0,target,nums);
36	return res;
37    }
38};

Related

leetcode 79. Word Search (dfs)

·374 words·1 min
ACM Leetcode DFS
Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. 思路：dfs即可。记得要回溯一下… 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月07日 星期五 14时32分54秒 4File Name :79.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 int n,m; 11 const int dx4[4]={1,-1,0,0}; 12 const int dy4[4]={0,0,-1,1}; 13 bool vis[1005][1005]; 14 int len; 15 16 bool yes( int x,int y) 17 { 18 if (x>=0&&x<=n-1&&y>=0&&y<=m-1) return true; 19 return false; 20 } 21 22 bool dfs( int x,int y,int cur,vector<vector<char> > & maze,string & st) 23 { 24// printf("x:%d y:%d cur : %d\n",x,y,cur); 25 if (cur>=len) return true; 26 for ( int i = 0 ; i < 4 ; i++) 27 { 28 int nx = x + dx4[i]; 29 int ny = y + dy4[i]; 30 if (!yes(nx,ny)) continue; 31 if (vis[nx][ny]) continue; 32 if (maze[nx][ny]!=st[cur]) continue; 33 vis[nx][ny] = true; 34 bool res = dfs(nx,ny,cur+1,maze,st); 35 if (res) return true; 36 vis[nx][ny] = false ;//好像还要回溯一下啊？ 37 } 38 return false; 39 } 40 41 bool exist(vector<vector<char>>& board, string word) { 42 n = board.size(); 43 if (n==0) return false; 44 m = board[0].size(); 45 if (m==0) return false; 46 len = word.length(); 47 cout<<"len:"<<len<<endl; 48 char beg = word[0]; 49 for ( int i = 0 ; i < n ; i++) 50 for ( int j = 0 ; j < m ; j++) 51 if (board[i][j]==beg) 52 { 53 memset(vis,false,sizeof(vis)); 54 //起点忘记打标记了。。。智力-2.。。 55 vis[i][j] = true; 56 bool ok = dfs(i,j,1,board,word); 57 cout<<"ok:"<<ok<<endl; 58 if (ok) return true; 59 } 60 return false; 61 62 63 } 64 65};

leetcode 40. Combination Sum II (枚举子集，和为定值)

·106 words·1 min
ACM Leetcode 枚举子集
* Total Accepted: **106670** * Total Submissions: **329718** * Difficulty: **Medium** * Contributor: **LeetCode** Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. Each number in C may only be used once in the combination. Note: * All numbers (including target) will be positive integers. * The solution set must not contain duplicate combinations. 题意：若干正数，求所有和为target的组合。

leetcode 495. Teemo Attacking

·251 words·1 min
ACM Leetcode
In LLP world, there is a hero called Teemo and his attacking can make his enemy Ashe be in poisoned condition. Now, given the Teemo’s attacking ascending time series towards Ashe and the poisoning time duration per Teemo’s attacking, you need to output the total time that Ashe is in poisoned condition. You may assume that Teemo attacks at the very beginning of a specific time point, and makes Ashe be in poisoned condition immediately. 题意：若干长度相同的区间，升序给出区间左端点，以及区间长度。问区间被覆盖的长度总和。

leetcode 442. Find All Duplicates in an Array（找出出现两次的元素）

·234 words·1 min
ACM Leetcode
Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? 思路：还是一个映射，如果某个位置要映射的时候已经为负了，就说明之前映射过该位置，那么该位置对应的元素就是出现了两个的元素。

leetcode 48. Rotate Image (旋转方阵(in place))

·575 words·2 mins
ACM Leetcode
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? 题意：给一个n*n的方阵，要求顺时针旋转90度。 思路：(x,y)->(y,n-1-x); 要求in-place的做法的话，其实是若干长度为4的环，保护一个节点，然后顺次做就好了。