60. n개의 주사위 포인트

61. 포커 순자

62. 동그라미 중 마지막 남은 수

63. 주식의 최대 이윤

64. 제발 1+2+3+...+n

65. 가감 곱하기 나누기 없이 덧셈

66. 곱셈수 그룹 구축

67. 문자열을 정수로 변환하기

68. 나무 중 두 노드의 최저 공공 조상

60. n개의 주사위 포인트

Lintcode

제목 설명

n개의 주사위를 바닥에 놓고 점수와 s의 확률을 구한다.
 

문제풀이의 방향

동적 기획

2차원 그룹 dp를 사용하여 포인트가 나타나는 횟수를 저장합니다. 그 중에서 dp[i][j]는 전 i개의 주사위가 포인트 j를 생성하는 횟수를 나타냅니다.
공간 복잡성: O(N2)

public List<Map.Entry<Integer, Double>> dicesSum(int n) { final int face = 6; final int pointNum = face * n; long[][] dp = new long[n + 1][pointNum + 1]; for (int i = 1; i <= face; i++) dp[1][i] = 1; for (int i = 2; i <= n; i++) for (int j = i; j <= pointNum; j++) /*    i          i */ for (int k = 1; k <= face && k <= j; k++) dp[i][j] += dp[i - 1][j - k]; final double totalNum = Math.pow(6, n); List<Map.Entry<Integer, Double>> ret = new ArrayList<>(); for (int i = n; i <= pointNum; i++) ret.add(new AbstractMap.SimpleEntry<>(i, dp[n][i] / totalNum)); return ret; }

동적 기획 + 회전 그룹

공간 복잡성: O(N)

public List<Map.Entry<Integer, Double>> dicesSum(int n) { final int face = 6; final int pointNum = face * n; long[][] dp = new long[2][pointNum + 1]; for (int i = 1; i <= face; i++) dp[0][i] = 1; int flag = 1; /*      */ for (int i = 2; i <= n; i++, flag = 1 - flag) { for (int j = 0; j <= pointNum; j++) dp[flag][j] = 0; /*        */ for (int j = i; j <= pointNum; j++) for (int k = 1; k <= face && k <= j; k++) dp[flag][j] += dp[1 - flag][j - k]; } final double totalNum = Math.pow(6, n); List<Map.Entry<Integer, Double>> ret = new ArrayList<>(); for (int i = n; i <= pointNum; i++) ret.add(new AbstractMap.SimpleEntry<>(i, dp[1 - flag][i] / totalNum)); return ret; }

61. 포커 순자

NowCoder

제목 설명

다섯 장의 패 중에서 큰 꼬마는 나병이고 표면은 0이다.이 다섯 장의 카드가 순자를 구성할 수 있는지 없는지를 판단하다.
 

문제풀이의 방향

public boolean isContinuous(int[] nums) {

    if (nums.length < 5) return false; Arrays.sort(nums); //        int cnt = 0; for (int num : nums) if (num == 0) cnt++; //               for (int i = cnt; i < nums.length - 1; i++) { if (nums[i + 1] == nums[i]) return false; cnt -= nums[i + 1] - nums[i] - 1; } return cnt >= 0; }

62. 동그라미의 마지막 남은 수

NowCoder

제목 설명

어린이들을 큰 동그라미로 둘러싸다.그리고 랜덤으로 숫자 m을 지정하여 번호가 0인 어린이가 숫자를 보고하기 시작하도록 한다.매번 m-1을 외치는 그 어린이는 줄을 서서 노래를 부르고 선물 상자에서 임의로 선물을 고를 수 있다. 그리고 다시 권으로 돌아가지 않는다. 그의 다음 어린이부터 계속 0...m-1 번호...이러다가...마지막 어린이가 남을 때까지 공연을 하지 않아도 된다.

문제풀이의 방향

요셉 고리, 동그라미 길이 n의 해는 길이 n-1의 해에 신문의 길이 m로 볼 수 있다.동그라미이기 때문에 마지막에 n을 빼야 합니다.

public int LastRemaining_Solution(int n, int m) {
    if (n == 0) /*         */ return -1; if (n == 1) /*        */ return 0; return (LastRemaining_Solution(n - 1, m) + m) % n; }

63. 주식의 최대 이윤

Leetcode

제목 설명

한 번의 매입과 한 번의 판매가 가능하며, 매입은 반드시 앞에 있어야 한다.최대의 수익을 추구하다.
 

문제풀이의 방향

욕심 전략을 사용하여 i라운드에서 판매 조작을 한다고 가정하면 매입 조작 가격은 i 이전에 가격이 가장 낮아야 한다.

public int maxProfit(int[] prices) {
    if (prices == null || prices.length == 0) return 0; int soFarMin = prices[0]; int maxProfit = 0; for (int i = 1; i < prices.length; i++) { soFarMin = Math.min(soFarMin, prices[i]); maxProfit = Math.max(maxProfit, prices[i] - soFarMin); } return maxProfit; }

64. 1+2+3+...+n

NowCoder

제목 설명

곱셈, for,while,if,else,switch,case 등 키워드와 조건 판단 문장 A를 사용할 수 없습니까?B : C.

문제풀이의 방향

귀환 해법을 사용하는 데 가장 중요한 것은 귀환 조건을 지정하는 것입니다. 그러나 본 문제는if문장을 직접 사용하여 귀환 조건을 지정할 수 없습니다.
조건과 & & 는 단락 원칙을 가지고 있다. 즉, 첫 번째 조건문이 false인 상황에서 두 번째 조건문을 집행하지 않는다.이 특성을 이용하여 귀환의 귀환 조건을 비뚤어진 다음에 &&의 첫 번째 조건문구로 하고 귀환의 주체를 두 번째 조건문구로 바꾸면 귀환의 귀환 조건이true일 경우 귀환의 주체 부분을 집행하지 않고 귀환한다.
본 문제의 귀환 반환 조건은 n<=0이고 비뚤어진 것을 취하면 n>0이다.반복되는 바디 부분은 sum + = Sum 입니다.Solution(n - 1), 조건문으로 변환하면 (sum + = Sum Solution(n - 1) > 0입니다.

public int Sum_Solution(int n) {
    int sum = n;
    boolean b = (n > 0) && ((sum += Sum_Solution(n - 1)) > 0); return sum; }

65. 가감 곱하기 나누기 없이 덧셈을 한다

NowCoder

제목 설명

하나의 함수를 써서 두 정수의 합을 구하고 +, -, *,/네 개의 연산 기호를 사용해서는 안 된다.

문제풀이의 방향

a^b는 진위를 고려하지 않은 상황에서 두 수의 합을 나타낸다. (a&b)<<<1은 진위이다.
귀환이 중지되는 원인은 (a&b)<<<1의 가장 오른쪽에 0이 하나 더 생기면 계속 귀환한다. 가장 오른쪽에 있는 0은 점점 증가하고 마지막에 진위는 0이 되며 귀환이 중지된다.

public int Add(int a, int b) {
    return b == 0 ? a : Add(a ^ b, (a & b) << 1); }

66. 곱셈수 그룹 구축

NowCoder

제목 설명

배열 A[0, 1,..., n-1]를 지정하고 배열 B[0, 1,..., n-1]를 구성하십시오. 여기서 B의 요소 B[i]=A[0]*A[1]*...*A[i-1]*A[i+1]*...*A[n-1].제법을 사용할 수 없도록 요구하다.
 

문제풀이의 방향

public int[] multiply(int[] A) {
    int n = A.length; int[] B = new int[n]; for (int i = 0, product = 1; i < n; product *= A[i], i++) /*        */ B[i] = product; for (int i = n - 1, product = 1; i >= 0; product *= A[i], i--) /*        */ B[i] *= product; return B; }

67. 문자열을 정수로 변환

NowCoder

제목 설명

문자열을 정수로 변환하고, 문자열이 합법적인 수치가 아니면 0을 되돌려줍니다. 문자열로 정수를 변환할 수 없는 라이브러리 함수를 요구합니다.

Iuput:
+2147483647
1a33

Output:
2147483647
0

문제풀이의 방향

public int StrToInt(String str) {
    if (str == null || str.length() == 0) return 0; boolean isNegative = str.charAt(0) == '-'; int ret = 0; for (int i = 0; i < str.length(); i++) { char c = str.charAt(i); if (i == 0 && (c == '+' || c == '-')) /*      */ continue; if (c < '0' || c > '9') /*      */ return 0; ret = ret * 10 + (c - '0'); } return isNegative ? -ret : ret; }

68. 나무 중 두 노드의 최저 공조상

문제풀이의 방향

두 갈래 나무 찾기

Leetcode : 235. Lowest Common Ancestor of a Binary Search Tree
두 갈래 찾기 트리에서 두 노드 p, q의 공공 조상 루트는 루트를 만족시킨다.val >= p.val && root.val <= q.val.
 

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null) return root; if (root.val > p.val && root.val > q.val) return lowestCommonAncestor(root.left, p, q); if (root.val < p.val && root.val < q.val) return lowestCommonAncestor(root.right, p, q); return root; }

노멀 두 갈래 나무

Leetcode : 236. Lowest Common Ancestor of a Binary Tree
좌우 트리에서 p 또는 q가 존재하는지 찾습니다. 만약에 p와 q가 각각 두 개의 트리에 있다면 뿌리 노드가 가장 낮은 공공 조상임을 의미합니다.
 

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
    if (root == null || root == p || root == q) return root; TreeNode left = lowestCommonAncestor(root.left, p, q); TreeNode right = lowestCommonAncestor(root.right, p, q); return left == null ? right : right == null ? left : root; }

전재 대상:https://www.cnblogs.com/daimasanjiaomao/p/11009041.html