华为第一题一直卡在70%,求大佬们指出我的错误

package one;

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();

            int a = n % 9;
            int b = n % 4;
            int c = a % 4;
            if (a != 0 && b != 0 && c != 0 || n < 4) { //肯定没有解
                System.out.println(-1);
                continue;
            }


            int min = (n / 4) + 2;//初始化
            boolean flag = false;
            for (int i = 0; i <= (n / 4); i++) {
                for (int j = 0; j <= (n / 9); j++) {
                    if ((4 * i + 9 * j) == n) {
                        flag = true;
                        if ((i + j) < min) {
                            min = i + j;
                        }
                    }
                }
            }
            if (flag) {
                System.out.println(min);
            } else {
                System.out.println(-1);
            }

        }
    }
}

#华为##笔试题目#

全部评论

推荐最新楼层

little_j

南京理工大学 Java

vector<int> tmp(n+1, 10000); tmp[4] = 1; tmp[9] = 1; for(int i=10; i<n+1; ++i) { tmp[i] = 1 + min(tmp[i-4], tmp[i-9]); } if(tmp[n] > 10000) cout << -1 << endl; else { cout << tmp[n] << endl; }

点赞回复分享

发布于 2019-09-04 21:29

真的好难呀。

杭州电子科技大学 C++

楼主 lc 518 #include <iostream> #include <vector> using namespace std; int main(){ int n; cin >> n; vector<int> dp(n + 1, INT_MAX); vector<int> dingzis{4, 9}; dp[0] = 0, dp[4] = 1, dp[9] = 1; for(auto dingzi : dingzis){ for(int j = dingzi; j <= n; j++) if(dp[j - dingzi] != INT_MAX) dp[j] = min(dp[j], dp[j - dingzi] + 1); } if(dp[n] == INT_MAX) cout << -1 << endl; else cout << dp[n] << endl; }

点赞回复分享

发布于 2019-09-16 00:41

随风吹散

华中科技大学 C++

感觉数学逻辑错了， int func(int n){ if(n<4 || (n>4 && n<7)) return -1; int cnt=n/9; if( n % 9 == 0 ) return cnt; while(cnt!=0){ int lst=n-cnt*9; cout<<lst<<endl; if(lst%4 == 0){ cnt+=lst/4; cout<<cnt<<endl; return cnt; } else cnt--; } if(n%4 == 0){ cnt=n/4; return n/4; } return -1; }

点赞回复分享

发布于 2019-09-04 21:16

Binjer

上海交通大学算法工程师

# Python动态规划解法，比较通用，题目类似找零钱问题 import sys n = int(sys.stdin.readline().strip()) def buy_nails(nails, target): dp = [target + 1] * (target + 1) # 初始化很重要 dp[0] = 0 for i in range(1, len(nails) + 1): for j in range(1, target + 1): if j >= nails[i - 1]: dp[j] = min(dp[j], dp[j - nails[i - 1]] + 1) min_num = dp[-1] if min_num < target + 1: return min_num else: return -1 nails = [4, 9] dp = buy_nails(nails, n) print(dp)

点赞回复分享

发布于 2019-09-05 13:12

隆轰

复旦大学 C++

为什么我题目和你们不一样

点赞回复分享

发布于 2019-09-04 23:02

祭禮之蛇5335

腾讯_CDG_测试开发

直接暴力两个循环不就出来了么

点赞回复分享

发布于 2019-09-04 21:33

c++好难

山东大学 C++

#include<iostream> #include<vector> #include<algorithm> using namespace std; int main() { int n; cin >> n; vector<int> dp(n + 1, 0); dp[4] = 1; dp[9] = 1; for (int i = 4; i <= n; ++i) { if (dp[i] > 0) { if (i + 4 <= n) { if (dp[i + 4] == 0) dp[i + 4] = dp[i] + 1; else dp[i + 4] = min(dp[i + 4], dp[i] + 1); } if (i + 9 <= n) { if (dp[i + 9] == 0) dp[i + 9] = dp[i] + 1; else dp[i + 9] = min(dp[i + 9], dp[i] + 1); } } } if (dp[n] == 0) cout << -1 << endl; else cout << dp[n] << endl; return 0; }

点赞回复分享

发布于 2019-09-04 21:30

little_j

南京理工大学 Java

用动态规划做吧

点赞回复分享

发布于 2019-09-04 21:24

努力找工作的菜鸡

南开大学 C++

不知道这个为什么只有10% #include <iostream> using namespace std; int QuickSort(int n) { if (n<0 || n>200) return -1; int sum = 0; int cur =n%9; sum = n / 9; if (cur == 0) return sum; if (cur % 4 == 0) { sum += (cur / 4); return sum; } else { while (cur < n) { sum -= 1; cur += 9; if (cur % 4 == 0) { sum += (cur / 4); break; } } } return sum==0?-1:sum; } int main() { int n; cin >> n; int res = QuickSort(n); cout << res; }

点赞回复分享

发布于 2019-09-04 21:19

青山依旧叶未红

楼主

中南大学 Java