面试编程题-整理

admin 2022年1月6日01:37:34安全博客评论12 views3159字阅读10分31秒阅读模式

笔试中遇到的不会做的题目整理

求最大的组合数

求最大的组合数:用不同的数字组合,找到最大的那一个组合

scanner类

求最大的组合数
思路:
自定义符合要求的排序方式,实现符合要求的结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

import java.util.Arrays;
import java.util.Scanner;
import java.util.Vector;

public class StringSort {
public static void main(String[] args) {
//String ss[]={"9","2","20","22"};
Scanner sc=new Scanner(System.in);
Vector<String> v=new Vector<>();
if(sc.hasNextLine()){
String[] inputString=sc.nextLine().split("\\s+");
for(String s: inputString ){
v.add(s);
}
}
sc.close();
MyString mySs[]=new MyString[v.size()];
for (int i = 0; i < v.size(); i++) {
mySs[i]=new MyString(v.get(i));
}
Arrays.sort(mySs);
System.out.print("最大数:");
for (int i = 0; i < mySs.length; i++) {
System.out.print(mySs[i].s);
}
}
}


class MyString implements Comparable<MyString>{
public String s;
public MyString(String s) {
this.s = s;
}

@Override
public int compareTo(MyString o) {
if(o==null||o.s==null) {
return 1;
}
String tmp1 = s+o.s;
String tmp2 = o.s+s;
return -tmp1.compareTo(tmp2);

}
}

类似题求最小的组合数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

import java.util.Arrays;

public class Solution {
public String PrintMinNumber(int[] numbers) {
if (numbers == null || numbers.length == 0)
return "";
int n = numbers.length;
String[] nums = new String[n];
for (int i = 0; i < n; i++)
nums[i] = numbers[i] + "";
Arrays.sort(nums, (s1, s2) -> (s1 + s2).compareTo(s2 + s1));
String ret = "";
for (String str : nums)
ret += str;
return ret;
}
}

已知树的先序和中序,求后序

java实现已知先序遍历和中序遍历,求后序遍历
思路:
先根据先序和中序序列,构建二叉树,然后在中序遍历二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
public class Solution {
public Node initTree(int[] preOrder,int pstart,int pend,int[] inOrder,int instart,int inend){
if(pstart>pend||instart>inend){
return null;
}
int rootData=preOrder[pstart];
Node head=new Node(rootData);
int rootIndex=findIndexInArray(inOrder,rootData,instart,inend);
int offSet=rootIndex-instart-1;
Node left=initTree(preOrder,pstart+1,pstart+offSet+1,inOrder,instart,instart+offSet);
Node right=initTree(preOrder,pstart+offSet+2,pend,inOrder,rootIndex+1,inend);
head.left=left;
head.right=right;
return head;
}
private int findIndexInArray(int[] inOrder,int rootData,int instart,int inend){
for(int i=instart;i<=inend;i++){
if(inOrder[i]==rootData){
return i;
}
}
return -1;

}
public void postOrder(Node root){
if(root!=null){
postOrder(root.left);
System.out.print(root.val+" ");
postOrder(root.right);
}
}


public static void main(String[] args) {
int[] preOrder = {1,2,4,8,9,5,10,3,6,7};
int[] inOrder = {8,4,9,2,10,5,1,6,3,7};
Solution tree=new Solution();
Node root=tree.initTree(preOrder,0,preOrder.length-1,inOrder,0,inOrder.length-1);
tree.postOrder(root);

}

}

动态规划

背包问题

01背包wen
背包问题集合

经典算法总结——背包问题java实现

最后一块石头

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int lastStoneWeightII(int[] stones) {
/* 由于石头拿走还能放回去,因此可以简单地把所有石头看作两堆
* 假设总重量为 sum, 则问题转化为背包问题:如何使两堆石头总重量接近 sum / 2
*/
int len = stones.length;
/* 获取石头总重量 */
int sum = 0;
for (int i : stones) {
sum += i;
}
/* 定义 dp[i] 重量上限为 i 时背包所能装载的最大石头重量 */
int maxCapacity = sum/2;
int[] dp = new int[maxCapacity + 1];
for (int i = 0; i < len; i++) {
int curStone = stones[i];
for (int j = maxCapacity; j >= curStone; j--) {
dp[j] = Math.max(dp[j], dp[j-curStone] + curStone);
}
}
return sum - 2 * dp[maxCapacity];
}
}

https://leetcode-cn.com/problems/last-stone-weight-ii/

力扣 5063 最后一块石头的重量 & II

sigle number

https://blog.csdn.net/crayondeng/article/details/39289387

http://ddrv.cn/a/113829
参考文章

FROM :blog.cfyqy.com | Author:cfyqy

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:37:34
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  面试编程题-整理 http://cn-sec.com/archives/721973.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: