\u4f4d\u8fd0\u7b97\uff0c\u5f02\u6216<\/p>\n\n\n\n
136. \u53ea\u51fa\u73b0\u4e00\u6b21\u7684\u6570\u5b57 – \u529b\u6263\uff08LeetCode\uff09<\/a><\/p>\n\n\n\n 169. \u591a\u6570\u5143\u7d20<\/a><\/p>\n\n\n\n 75. \u989c\u8272\u5206\u7c7b<\/a><\/p>\n\n\n\n \u6838\u5fc3\u601d\u60f3\uff1a<\/p>\n\n\n\n \u56e0\u4e3ai\u4ece\u524d\u5f80\u540e\uff0czero\u4e5f\u4ece\u524d\u5f80\u540e\uff0c\u6240\u4ee5zero\u6362\u8fc7\u53bb\u548c\u6362\u8fc7\u6765\u7684\u503c\u77e5\u9053\u3002\u800c <\/p>\n\n\n\n \u4e3e\u4f8b\uff1a<\/p>\n\n\n\n <\/p>\n\n\n\n 287. \u5bfb\u627e\u91cd\u590d\u6570<\/a>\/\/136. \u53ea\u51fa\u73b0\u4e00\u6b21\u7684\u6570\u5b57
public class SingleNumber_136 {
static class Solution {
\/\/\u5f02\u6216\u8fd0\u7b97\u6709\u52a0\u6cd5\u5f8b\u548c\u7ed3\u5408\u5f8b;\u81ea\u8eab\u5f02\u6216\u4e3a0\uff1b\u4e0e0\u5f02\u6216\u4e0d\u53d8
public int singleNumber(int[] nums) {
int result = nums[0];
for (int i = 1; i < nums.length; i++) {
result=result^nums[i];
}
return result;
}
}
public static void main(String[] args) {
Solution solution = new Solution();
int[] nums = {4, 1, 2, 1, 2};
int single = solution.singleNumber(nums);
System.out<\/em>.println(\"\u53ea\u51fa\u73b0\u4e00\u6b21\u7684\u6570\u5b57\u662f: \" + single);
}
}<\/code><\/pre>\n\n\n\n169.\u591a\u6570\u5143\u7d20<\/h1>\n\n\n\n
public static int majorityElement(int[] nums) {\n \/\/\u6709\u5df2\u77e5\u6761\u4ef6\uff1a\u6570\u7ec4\u975e\u7a7a\u3001\u5b58\u5728\u591a\u6570\u5143\u7d20\u3002\u6709\u56e0\u4e3a\u51fa\u73b0\u6b21\u6570 \u5927\u4e8e \u230a n\/2 \u230b \uff0c\u6240\u4ee5\u6709\u4e14\u4ec5\u6709\u4e00\u4e2a\u591a\u6570\u5143\u7d20\u3002\n \/\/\u904d\u5386\u6240\u6709\u5143\u7d20\uff0c\u4e0d\u76f8\u540c\u7684\u62b5\u6d88\uff0c\u5269\u4e0b\u7684\u5c31\u662f\u53ea\u6709\u6240\u6c42\u7684\u201c\u591a\u6570\u5143\u7d20\u201d\u3002\n \/\/\u62b5\u6d88\u64cd\u4f5c\uff1a\u5bf9\u4e8e\u5f53\u524d\u5143\u7d20\u8ba1\u6570count\uff0c\u9047\u5230\u76f8\u540c\u5143\u7d20\uff0c\u8ba1\u6570+1\uff0c\u9047\u5230\u4e0d\u540c\u7684\u5143\u7d20\uff0c\u8ba1\u6570-1\uff1b\u5f53\u8ba1\u6570\u4e3a0\u65f6\uff0c\u5c06\u5f53\u524d\u5143\u7d20\u4f5c\u4e3a\u65b0\u7684\u5019\u9009\u5143\u7d20\u3002\n\n int count = 0;\n int current = 0;\n\n for (int i = 0; i < nums.length; i++) {\n if (count==0){\n current=nums[i];\n }\n if (nums[i]==current){\n count++;\n }else {\n count--;\n }\n }\n\n return current;\n }<\/code><\/pre>\n\n\n\n75.\u989c\u8272\u5206\u7c7b\uff1a<\/h1>\n\n\n\n
\n
zero<\/code>\u6307\u9488\uff1a\u6307\u5411 0 \u533a\u57df\u7684\u4e0b\u4e00\u4e2a\u4f4d\u7f6e\uff08\u5373\u4e0b\u4e00\u4e2a 0 \u5e94\u8be5\u653e\u7f6e\u7684\u4f4d\u7f6e\uff09<\/li>\n\n\n\ntwo<\/code>\u6307\u9488\uff1a\u6307\u5411 2 \u533a\u57df\u7684\u524d\u4e00\u4e2a\u4f4d\u7f6e\uff08\u5373\u4e0b\u4e00\u4e2a 2 \u5e94\u8be5\u653e\u7f6e\u7684\u4f4d\u7f6e\uff09<\/li>\n\n\n\ni<\/code>\u6307\u9488\uff1a\u7528\u4e8e\u904d\u5386\u6570\u7ec4<\/li>\n<\/ul>\n\n\n\n\n
zero<\/code>\u4e3a 0\uff0ctwo<\/code>\u4e3a\u6570\u7ec4\u672b\u5c3e\u7d22\u5f15<\/li>\n\n\n\ni<\/code>\u8d85\u8fc7two<\/code>\u65f6\u7ed3\u675f<\/li>\n\n\n\ntwo<\/code>\u6307\u9488\u4f4d\u7f6e\u5143\u7d20\u4ea4\u6362\uff0ctwo<\/code>\u5de6\u79fb\uff08\u56e0\u4e3a\u4ea4\u6362\u8fc7\u6765\u7684\u5143\u7d20\u53ef\u80fd\u8fd8\u662f 2\uff0c\u9700\u8981\u7ee7\u7eed\u68c0\u67e5<\/li>\n\n\n\nzero<\/code>\u6307\u9488\u4f4d\u7f6e\u5143\u7d20\u4ea4\u6362\uff0czero<\/code>\u53f3\u79fb\uff0ci<\/code>\u53f3\u79fb<\/li>\n\n\n\ni<\/code>\u53f3\u79fb<\/li>\n<\/ol>\n\n\n\ntwo<\/code>\u662f\u4ece\u540e\u5f80\u524d\uff0c\u6362\u8fc7\u6765\u7684\u53ef\u80fd\u8fd8\u662f0\u30012 \u3002\u6240\u4ee5\u9700\u8981while\u5faa\u73af\u68c0\u67e5\u5904\u7406\uff0c\u800c\u5bf9\u96f6\u7684\u5224\u65ad\u5904\u7406\u4e5f\u56e0\u6b64\u8981\u653e\u5728\u5bf92\u5904\u7406\u7684\u540e\u9762\u3002<\/p>\n\n\n\npublic static void sortColors(int[] nums) {
int zero = 0;
int two =nums.length-1;
for (int i = 0; i <= two; i++) {
while (nums[i]==2 && i<=two){
int temp = nums[i];
nums[i] = nums[two];
nums[two] = temp;
two--;
}
if (nums[i]==0){
int temp = nums[i];
nums[i] = nums[zero];
nums[zero] = temp;
zero++;
}
}
}<\/code><\/pre>\n\n\n\n31.\u4e0b\u4e00\u4e2a\u6392\u5e8f\uff1a<\/h1>\n\n\n\n
\u6574\u4f53\u601d\u8def<\/h3>\n\n\n\n
\n
\u627e\u5230\u6700\u5927\u7d22\u5f15 i<\/code>\uff0c\u4f7f\u5f97 nums[i] < nums[i + 1]<\/code>
\u8bf4\u660e\u4ece i+1<\/code> \u5f00\u59cb\u662f\u4e00\u4e2a \u9012\u51cf\u5e8f\u5217<\/strong>\uff08\u5373\u5f53\u524d\u540e\u7f00\u6700\u5927\uff09<\/li>\n\n\n\ni<\/code><\/strong>\uff08\u5373\u5f53\u524d\u4e0d\u662f\u6700\u5927\u6392\u5217\uff09\uff1a\n\n
j<\/code>\uff0c\u4f7f\u5f97 nums[j] > nums[i]<\/code><\/li>\n\n\n\nnums[i]<\/code> \u4e0e nums[j]<\/code><\/li>\n<\/ul>\n<\/li>\n\n\n\ni+1<\/code> \u5230\u672b\u5c3e\uff09
\u628a\u539f\u672c\u9012\u51cf\u7684\u540e\u7f00\u53d8\u4e3a\u6700\u5c0f\u7684\u5347\u5e8f\u6392\u5217\uff0c\u786e\u4fdd\u201c\u521a\u521a\u5927\u4e00\u70b9\u201d<\/li>\n<\/ol>\n\n\n\n
\n\n\n\n\u7279\u6b8a\u60c5\u51b5<\/h3>\n\n\n\n
\n
i<\/code>\uff08\u5373\u5168\u662f\u9012\u51cf\u7684\u6392\u5217\uff0c\u5982 [5,4,3,2,1]<\/code>\uff09\uff0c\u8bf4\u660e\u5df2\u7ecf\u662f\u6700\u5927\u6392\u5217
\u76f4\u63a5 \u53cd\u8f6c\u6574\u4e2a\u6570\u7ec4<\/strong>\uff0c\u53d8\u6210\u6700\u5c0f\u6392\u5217\uff08\u5347\u5e8f\uff09<\/li>\n<\/ul>\n\n\n\n\u6b65\u9aa4<\/th> i<\/th> j<\/th> \u6570\u7ec4\u72b6\u6001<\/th><\/tr><\/thead> \u539f\u59cb\u8f93\u5165<\/td> <\/td> <\/td> [1, 4, 5, 3, 2]<\/code><\/td><\/tr>\u627e\u5230 i<\/td> 1<\/td> <\/td> nums[1]=4<\/code><\/td><\/tr>\u627e\u5230 j<\/td> <\/td> 2<\/td> nums[2]=5<\/code><\/td><\/tr>\u4ea4\u6362 i \u548c j<\/td> <\/td> <\/td> [1, 5, 4, 3, 2]<\/code><\/td><\/tr>\u7ffb\u8f6c\u540e\u7f00<\/td> <\/td> <\/td> [1, 5, 2, 3, 4]<\/code> \u2705<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\npublic static void nextPermutation(int[] nums) {\n \/\/1.\u627e\u5230\u7b2c\u4e00\u4e2a\u5347\u5e8f\u5bf9\uff1ai\uff0ci+1\n int i = nums.length-2;\n while (i>=0 && nums[i]>=nums[i+1]){\n i--;\n }\n\n if (i<0){\n \/\/\u8bf4\u660e\u662f\u6700\u5927\u6392\u5e8f\uff08\u964d\u5e8f\uff09\uff0c\u53cd\u8f6c\u540e\u5373\u4f7f\u6240\u6c42\u7684\u4e0b\u4e00\u4e2a\u6392\u5e8f\uff08\u6700\u5c0f\u7684\uff09\n reverse<\/em>(nums,0,nums.length-1);\n return;\n }\n\n \/\/2.\u4ece\u540e\u5f80\u524d\u627e\u7b2c\u4e00\u4e2a\u5927\u4e8enums[i]\u7684\uff0c\u540c\u65f6\u4e5f\u662f\u6700\u5c0f\u7684\n int j = nums.length-1;\n while (j>i && nums[j]<=nums[i]){\n j--;\n }\n\n \/\/3.\u8c03\u6362i\uff0cj\u3002\n swap<\/em>(nums,i,j);\n\n \/\/4.\u6b64\u65f6nums[i+1]\u5230\u672b\u5c3e\u662f\u964d\u5e8f\uff0c\u53cd\u8f6c\u4e3a\u5347\u5e8f\u4f7f\u5176\u6700\u5c0f\u3002\n reverse<\/em>(nums,i+1,nums.length-1);\n}\n\n\nprivate static void swap(int[] nums, int i, int j) {\n int temp = nums[i];\n nums[i] = nums[j];\n nums[j] = temp;\n}\n\nprivate static void reverse(int[] nums, int left, int right) {\n while (left < right) {\n swap<\/em>(nums, left, right);\n left++;\n right--;\n }\n}<\/code><\/pre>\n\n\n\n287.\u5bfb\u627e\u91cd\u590d\u6570<\/h1>\n\n\n\n
\u6570\u5b66\u8bc1\u660e\uff1a<\/p>\n\n\n\n