1. 配列内の逆順ペア
(学習ビデオの推奨: java コース)
[タイトル]
配列内の 2 つの数値。前の数値が次の数値より大きい場合、2 つの数値は逆順のペアを形成します。配列を入力し、配列 P 内の反転ペアの総数を求めます。そして、P モジュロ 1000000007 の結果を出力します。つまり、出力 P 00000007
質問により、入力配列に同じ数値が存在しないことが確認されます
データ範囲:
对于%50的数据,size<=10^4 对于%75的数据,size<=10^5 对于%100的数据,size<=2*10^5
コード:
/**
*在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
* 输入一个数组，求出这个数组中的逆序对的总数 P。
* 并将 P 对 1000000007 取模的结果输出。 即输出 P%1000000007
*
* 利用归并排序的思想(倒序)
* 当得到left和right两个待归并的数组时，由于二者已经排好顺序
* 当left中的A元素大于right中的B元素，
* 那么right.length-b_index 个逆序对
* */
int count;
public int InversePairs(int [] array) {
return Merge(array,0,array.length-1);
}
public int Merge(int[] a, int start, int end) {
if (start >= end) return count;
int i,j,mid,index;
int[] temp;
mid = (start + end) / 2;
Merge(a,start,mid);
Merge(a,mid+1,end);
i = start;
j = mid + 1;
temp = new int[end-start+1];
index = 0;
while (i<=mid && j<=end) {
if (a[i] > a[j]) {
count = (count +end - j + 1) % 1000000007;
temp[index++] = a[i++];
} else {
temp[index++] = a[j++];
}
}
while (i<=mid) temp[index++] = a[i++];
while (j<=end) temp[index++] = a[j++];
index = start;
for (i=0;i<temp.length; i++) {
a[index++] = temp[i];
}
return count;
}[考え方]
マージソートの過程で、後の配列の数が前の配列の数より小さい場合、必ず逆順のペアを形成することができ、マージされる 2 つの配列が事前に進められているため、逆順のペアの数を計算できます。マージおよびソートが完了しているため、以前のように統計が増減することはありません。
[A,B]の逆順ペア = [A]の逆順ペア [B]の逆順ペア AとBを混ぜた逆順ペア
注: タイトルには、モジュロが必要な特別な要件があります。このモジュロは、結果のモジュロであるだけでなく、プロセスの計算でもモジュロです。
2. 配列内に 1 回のみ出現する数値
[タイトル]
整数配列内の 2 つの数値を除き、他のすべての数値は 2 回出現します。一度しか出現しないこれら 2 つの数字を見つけるプログラムを作成してください。
[コード]
/**
* 一个整型数组里除了两个数字之外，其他的数字都出现了两次。
* 请写程序找出这两个只出现一次的数字。
*
* 位运算中异或的性质：
* 两个相同数字异或 = 0，一个数和 0 异或还是它本身。
* a ⊕ a = 0
* a ⊕ b ⊕ a = b.
* a ⊕ 0 = a
*
* 当只有一个数出现一次时，我们把数组中所有的数，依次异或运算，
* 最后剩下的就是落单的数，因为成对儿出现的都抵消了。
*
* 当出现两个数只出现一次时，依旧是依次异或运算，
* 剩下的结果是两个只出现一次的数的异或结果
* 因为这两个数不同，所以我们通过二进制的异或把二者分开，在依次异或即可分别得到
* */
public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
int i,n,res,count,res1,res2;
n = array.length;
if (n == 0 || array == null) return;
res = 0;// 记录两个不同的数的异或结果
for (i=0; i<n; i++) {
res = res ^ array[i];
}
// 找到异或结果的二进制的的从右向左的第一个1
count = 1;
while ((count & res) == 0) count = count << 1;
// 通过找到的二进制结果来区分两个只出现第一次的数
res1 = 0;
res2 = 0;
for (i=0; i<n; i++) {
if ((count & array[i]) == 0) {
res1 = res1 ^ array[i];
} else {
res2 = res2 ^ array[i];
}
}
num1[0] = res1;
num2[0] = res2;
}[考え方]
まず、ビット演算における XOR の性質: 2 つの同一の数値 XOR = 0、1 つの数値と 0 XOR Orそれ自体です。
1 つの数値のみが 1 回出現する場合、配列内のすべての数値を順番に XOR します。ペアで出現するすべての数値が相殺されるため、最後に残った数値が 1 つの数値になります。
この考え方に従って、2 つの数値 (AB とします) が 1 回出現する配列を見てみましょう。最初に XOR を行う必要があります。残りの数値は、A と B の XOR の結果である必要があります。この結果のバイナリの 1 は、A と B の異なるビットを表します。最初の 1 の桁を 3 桁目とみなして取得し、元の配列を 2 つのグループに分割します。グループ化の基準は、3 桁目が 1 であるかどうかです。このように、同じ数字のすべての桁が同じであるため、同じ数字は確実に同じグループに属しますが、異なる数字は間違いなく同じグループに属しません。次に、元のアイデアに従ってこれら 2 つのグループを順番に XOR します。残りの 2 つの結果は、1 回だけ現れるこれら 2 つの数値になります。
(より関連した面接の質問に関する推奨事項: java 面接の質問と回答 )
3. 合計が S
[トピック] # となる 2 つの数値
##昇順にソートされた配列と数値 S を入力し、その合計が正確に S になるように配列内で 2 つの数値を検索します。合計が S に等しい数値のペアが複数ある場合は、その合計の最小積を出力します。 2つの数字の。 各テスト ケースに対応して 2 つの数値が出力され、小さい方が最初に出力されます。 [コード] /**
* 输入一个递增排序的数组和一个数字 S，
* 在数组中查找两个数，使得他们的和正好是 S，
* 如果有多对数字的和等于 S，输出两个数的乘积最小的。
* */
public ArrayList<Integer> FindNumbersWithSum(int [] array, int sum) {
int mid,i,index,n,j;
ArrayList<Integer> list;
n = array.length;
if (n == 0 || array == null || sum == 0) return new ArrayList<>();
mid = sum >> 1;
if (array[0] > mid) return new ArrayList<>();
// 前两个元素和为sum
list = new ArrayList<>();
if (array[0] == mid) {
if (array[0] + array[1] == sum) {
list.add(array[0]);
list.add(array[1]);
}
return list;
}
// 获得mid在array的索引
index = 0;
for (i=0; i<n; i++) {
if (array[i] >= mid) {
index = i;
break;
}
}
i = 0;
j = index + 1;
while (i<=index) {
while (array[i] + array[j] < sum) {
j++;
}
if (array[i] + array[j] == sum) {
list.add(array[i]);
list.add(array[j]);
break;
} else {
i++;
j = index + 1;
}
}
return list;
} /**
* 输出所有和为S的连续正数序列。
* 序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
*
* 思路：回溯
* 算子，paths，path
* */
TreeSet<Integer> path;
ArrayList<ArrayList<Integer>> paths;
ArrayList<Integer> list;
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
if (sum < 3) return new ArrayList<>();
int n,i,j,mid,count;
paths = new ArrayList<>();
if (sum == 3) {
list = new ArrayList<>();
list.add(1);
list.add(2);
paths.add(list);
return paths;
}
// n代表sum这个数最多由几个数字构成
n = (int)Math.sqrt(sum) + 1;
for (i=n; i>=2; i--) {
count = 0;
mid = sum / i;
count += mid;
path = new TreeSet<>();
path.add(mid);
j = 1;
while (count < sum) {
count += mid+j;
path.add(mid+j);
count += mid-j;
path.add(mid-j);
j++;
}
if (count == sum) {
list = new ArrayList<>();
list.addAll(path);
paths.add(list);
} else {
int last = path.last();
int first = path.first();
if (count-last == sum) {
path.remove(last);
list = new ArrayList<>();
list.addAll(path);
paths.add(list);
}
if (count-first == sum) {
path.remove(first);
list = new ArrayList<>();
list.addAll(path);
paths.add(list);
}
}
}
return paths;
} 連続シーケンスの範囲を左右のポインタが連続して周回する
1、2 つのポインターを定義します。左のポインターは 1 から始まり、右のポインターは 2 から始まります。
ループの開始
2、合計 (1 2 = 3##) #3, 3 が 20 未満と判断した場合、右ポインタ 2 が 3 となり、合計 3 3=6 右ポインタ = 6 になるまでループし、合計が 21 になる。 21 は 20 より大きい、左ポインター、1 は 2 になり、合計から左ポインターの値が減算され、合計は 21-1=20 になります。
5、そうでない場合、合計は入力と同じです。数値を保存します。 [次に、右のポインタを追加して残りの組み合わせを見つけます]
ループの終了
5. ポーカー ストレート カード
LL 今天心情特别好，因为他去买了一副扑克牌，发现里面居然有 2 个大王，2 个小王 (一副牌原本是 54 张 _)… 他随机从中抽出了 5 张牌，想测测自己的手气，看看能不能抽到顺子，如果抽到的话，他决定去买体育彩票，嘿嘿！！“红心 A, 黑桃 3, 小王，大王，方片 5”,“Oh My God!” 不是顺子…LL 不高兴了，他想了想，决定大 \ 小 王可以看成任何数字，并且 A 看作 1,J 为 11,Q 为 12,K 为 13。上面的 5 张牌就可以变成 “1,2,3,4,5”(大小王分别看作 2 和 4),“So Lucky!”。LL 决定去买体育彩票啦。 现在，要求你使用这幅牌模拟上面的过程，然后告诉我们 LL 的运气如何， 如果牌能组成顺子就输出 true，否则就输出 false。为了方便起见，你可以认为大小王是 0。
【代码】
/**
* 判断顺子，大小王为0
*
* 计算0的个数
* 计算非0的差
* */
public boolean isContinuous(int [] numbers) {
if (numbers.length == 0 || numbers == null) return false;
Arrays.sort(numbers);
int n,i,count,minus;
n = numbers.length;
count = 0;
minus = 0;
for (i=0; i<n-1; i++) {
if (numbers[i] == 0) {
count++;
} else {
minus += numbers[i+1] - numbers[i];
}
}
// 除了最后一个其他都是0
if (count == n-1) return true;
// 存在相同的值
if (minus != (numbers[n-1] - numbers[count])) return false;
if (minus == 0) return false;
return (minus - (n-count-1)) > count ? false : true;
}【思考】
可以考虑使用treeset这个结构，本身带有排序功能，并且不会存储相同元素，可以方便判断。
相关推荐：java入门
以上がJava 面接でよくある配列に関する質問のまとめ (4)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。
![[Web フロントエンド] Node.js クイック スタート](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
