39 组合总和
对于这类寻找所有可行解的题，我们都可以尝试用「搜索回溯」的方法来解决。
思路：dfs 一条条找出所有可能的路径
但是注意题目要求不能有重复的组合，所以我们可以将原数组排序，从小的开始找，这样就可以避免重复。
但避免重复，实际上并不需要排序！！你只要别找以前找过的就可以了呀！！
速度马上加快！
自己的c++代码
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
//sort(candidates.begin(),candidates.end());
dfs(ans,path,candidates,target,0,0);
return ans;
}
void dfs(vector<vector<int>> &ans,vector<int> &path,vector<int>& candidates, int target,int sum,int index){
for(int i=index;i<candidates.size();i++){
if(sum+candidates[i]==target){
path.push_back(candidates[I]);
ans.push_back(path);
path.pop_back();
}
else if(sum+candidates[i]>target){
continue;
}
else{
path.push_back(candidates[I]);
dfs(ans,path,candidates,target,sum+candidates[i],i);
path.pop_back();
}
}
}
};
但sort可以用于剪枝
当发现当前和已经大于target可以直接退出循环，因为后面的数更大，不用再搜了
class Solution {
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<vector<int>> ans;
vector<int> path;
sort(candidates.begin(),candidates.end());
dfs(ans,path,candidates,target,0,0);
return ans;
}
void dfs(vector<vector<int>> &ans,vector<int> &path,vector<int>& candidates, int target,int sum,int index){
for(int i=index;i<candidates.size();i++){
if(sum+candidates[i]==target){
path.push_back(candidates[I]);
ans.push_back(path);
path.pop_back();
}
else if(sum+candidates[i]>target){
break;
}
else{
path.push_back(candidates[I]);
dfs(ans,path,candidates,target,sum+candidates[i],i);
path.pop_back();
}
}
}
};
java版本 还不熟练那些容器，写不出来
class Solution {
public List<List<Integer>> combinationSum(int[] candidates, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();//new ArrayList<>();也可以
List<Integer> path = new ArrayList<Integer>();
Arrays.sort(candidates);
dfs(candidates, target, ans, path, 0, 0);
return ans;
}
public void dfs(int[] candidates, int target, List<List<Integer>> ans, List<Integer> path, int sum,int idx) {
if(sum == target) {
ans.add(new ArrayList<>(path));
//ans.add(new ArrayList(path));这是对的 我不知道为什么
//ans.add(path);这是不对的我不知道为什么好像是因为直接加入的话传入的是地址
return;
}
for(int i = idx;i < candidates.length;i++) {
int rs = candidates[i] + sum;
if(rs <= target) {
path.add(candidates[I]);
dfs(candidates,target,ans,path,rs,i);
path.remove(path.size()-1);
} else {
break;
}
}
}
}
169 多数元素
剑指offer原题
思路1:排序找出第n/2大的元素
class Solution {
public int majorityElement(int[] nums) {
Arrays.sort(nums);
return nums[nums.length/2];
}
}
topk
class Solution {
public int majorityElement(int[] nums) {
int len = (nums.length + 1) >> 1;
PriorityQueue<Integer> pQueue = new PriorityQueue<>(len, Comparator.comparingInt(item -> -item));
for (int num : nums) {
pQueue.offer(num);
if (pQueue.size() > len)
pQueue.poll();
}
return pQueue.poll();
}
}
思路2:利用partition函数找出第n/2大的元素
class Solution {
public int majorityElement(int[] nums) {
if(nums.length==1) return nums[0];
int l=0,r=nums.length-1;
int mid=partition(l,r,nums);
while(mid!=nums.length/2){
if(mid>nums.length/2){
r=mid-1;
}
else{
l=mid+1;
}
mid=partition(l,r,nums);
}
return nums[mid];
}
int partition(int l,int r,int[] nums){
if(l==r) return l;//因为nextint要求参数大于0
Random random=new Random();
int randomIndex = l + 1 + random.nextInt(r-l);
int temp=nums[randomIndex];
nums[randomIndex]=nums[l];
nums[l]=temp;
while(l<r){
while(l<r && nums[r]>temp) r--;
nums[l]=nums[r];
while(l<r && nums[l]<=temp) l++;
nums[r]=nums[l];
}
nums[l]=temp;
return l;
}
}
思路3:摩尔投票法
时间复杂度O(N) 空间复杂度O(1)
class Solution {
public:
int majorityElement(vector<int>& nums) {
//摩尔投票法,先假设第一个数过半数并设cnt=1!；遍历后面的数如果相同则cnt+1，不同则减一，当cnt为0时则更换新的数字为候选数（成立前提：有出现次数大于n/2的数存在）
int res=0,cnt=0;//!
for(int i=0;i<nums.size();i++){
if(cnt==0) {
res=nums[I];
cnt++;
}
else{
res==nums[i]?cnt++:cnt--;
}
}
return res;
}
};
思路4:哈希表计数
O(N) 空间复杂度：O(N)
遍历整个数组，记录每个数值出现的次数(利用HashMap，其中key为数值，value为出现次数)；
接着遍历HashMap中的每个Entry，寻找value值大于 nums.length / 2的key即可。
c++优雅的代码如下
class Solution {
public:
int majorityElement(vector<int>& nums) {
//建立哈希数组找其中出现次数大于n/2的数
unordered_map<int,int> hash;
int res=0;
int len=nums.size();
for(int i=0;i<len;i++){
hash[nums[i]]++;
if(hash[nums[i]]>len/2){
res=nums[I];
break;//优化一下
}
}
return res;
}
};
java
有这么复杂呢？
class Solution {
private Map<Integer, Integer> countNums(int[] nums) {
Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
for (int num : nums) {
if (!counts.containsKey(num)) {
counts.put(num, 1);
} else {
counts.put(num, counts.get(num) + 1);
}
}
return counts;
}
public int majorityElement(int[] nums) {
Map<Integer, Integer> counts = countNums(nums);
Map.Entry<Integer, Integer> majorityEntry = null;
for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {
if (majorityEntry == null || entry.getValue() > majorityEntry.getValue()) {
majorityEntry = entry;
}
}
return majorityEntry.getKey();
}
}
class Solution {
public int majorityElement(int[] nums) {
Map<Integer, Long> map = Arrays.stream(nums).boxed().collect(Collectors.groupingBy(Function.identity(), Collectors.counting()));
long limit = nums.length >> 1;
for (Map.Entry<Integer, Long> entry : map.entrySet())
if (entry.getValue() > limit)
return entry.getKey();
return -1;
}
}
class Solution {
public int majorityElement(int[] nums) {
int limit = nums.length >> 1;
HashMap<Integer, Integer> map = new HashMap<>(limit);
for (int num : nums)
map.merge(num, 1, (o_val, n_val) -> o_val + n_val);
for (Map.Entry<Integer, Integer> entry : map.entrySet())
if (entry.getValue() > limit)
return entry.getKey();
return -1;
}
}
621 任务调度器
思路：
1、将任务按类型分组，正好A-Z用一个int[26]保存任务类型个数
2、对数组进行排序，优先排列个数（count）最大的任务，
如题得到的时间至少为 retCount =（count-1）* (n+1) + 1 ==> A->X->X->A->X->X->A(X为其他任务或者待命)
3、再排序下一个任务，如果下一个任务B个数和最大任务数一致，
则retCount++ ==> A->B->X->A->B->X->A->B
4、如果空位都插满之后还有任务，那就随便在这些间隔里面插入就可以，因为间隔长度肯定会大于n，在这种情况下就是任务的总数是最小所需时间
class Solution {
public int leastInterval(char[] tasks, int n) {
if(n==0) return tasks.length;//
int[] task_cnt=new int[26];//不需要定义字母至出现次数的映射!
for(char c:tasks){
task_cnt[c-'A']++;
}
Arrays.sort(task_cnt);//默认是从小到大排序!!!
int ans=(task_cnt[task_cnt.length-1]-1)*(n+1)+1;
for(int i=task_cnt.length-2;i>=0;i--){
if(task_cnt[i]==task_cnt[25] && (25-i)<=n){
//一定是等于最大的25，而不判断i 是否== i+1
ans++;
}
else break;
}
ans=Math.max(ans,tasks.length);
return ans;
}
}
官方标准同思路代码 很不错！
public int leastInterval(char[] tasks, int n) {
if (tasks.length <= 1 || n < 1) return tasks.length;
//步骤1
int[] counts = new int[26];
for (int i = 0; i < tasks.length; i++) {
counts[tasks[i] - 'A']++;
}
//步骤2
Arrays.sort(counts);
int maxCount = counts[25];
int retCount = (maxCount - 1) * (n + 1) + 1;
int i = 24;
//步骤3
while (i >= 0 && counts[i] == maxCount) {
retCount++;
i--;
}
// 并不需要判断空位是否插满，因为，即使插满了，这样计算出的ret必定小于tasks.length
// 也就是说，这种情况时再用上述公式计算会得到一个不正确且偏小的结果
//步骤4
return Math.max(retCount, tasks.length);
}
